### Since I don't have Code Jam time limits...

...I should improve the style.

Lisp is a wonderful language. It's the first (largely) applicative language. Having a simple form that all language constructs follow means you can write seriously powerful tools to manipulate programs without wasting your time on convoluted parsing.

Compare that with the horrors of parsing C++, which strictly speaking is impossible! Thanks to templates, you have to solve the halting problem to successfully parse C++. Even ignoring that, there are ambiguous constructs, with a rule that says which way to decide in the presence of ambiguity. I suspect it all goes back to Stroustrup's eschewing formal language-based tools when writing that first

All that said, Haskell style isn't Lisp style. Any serious Haskell programmer would look at my palindrome program and say I lean far too heavily on

and that's perfectly valid Haskell, but we can do better. How about this?

Here we are using guards, and while, thanks to the current layout, there is still wraparound, the code now honors the golden 80-column punched card that some things, most notably standards for source code layout, still bow down to in the computer world. (UPDATE: I waved a dead chicken at the layout, and it now fits.) Things to note:

Let's take advantage of pattern matching as well as guards:

Yes, I must admit that I chose shorter parameter names. While in the case of this test, I am passing in a number of digits, that is distracting from the function, so here I would say that my initial choice was wrong. It's not just a matter of making lines fit in 80 columns.

I very much repeat myself in the original program when it comes to the formation of a palindrome from its upper half (or in the case of an odd number of digits, the upper half and the middle digit). That needs its own function, or rather functions.

In theory those are all the parameters needed; you can calculate the number of digits in the upper half. Since we have that value, though, I'm inclined to pass it in.

Also speaking of DRY, I should use these functions to generate the palindromes with two 2s rather than making a special case of them. Say what you mean, as clearly as possible.

[We pause here for some testing and checking of run times for the input file with values up to 10

It's hard to say whether it makes a difference; just running the same program repeatedly shows variance in the time output. Here's one towards the low end:

while here's one towards the high end:

IMHO the result is worth the minimal, if it even exists, increase in run time.

Here's the code after the smoke cleared:

UPDATE: Aside from something in a later message, the only things I can think of to do are

Lisp is a wonderful language. It's the first (largely) applicative language. Having a simple form that all language constructs follow means you can write seriously powerful tools to manipulate programs without wasting your time on convoluted parsing.

Compare that with the horrors of parsing C++, which strictly speaking is impossible! Thanks to templates, you have to solve the halting problem to successfully parse C++. Even ignoring that, there are ambiguous constructs, with a rule that says which way to decide in the presence of ambiguity. I suspect it all goes back to Stroustrup's eschewing formal language-based tools when writing that first

*ad hoc*preprocessor for what was then "C with Classes". (BTW, Perl has the same problem. Perhaps there's something about kitchen sink languages.)All that said, Haskell style isn't Lisp style. Any serious Haskell programmer would look at my palindrome program and say I lean far too heavily on

**if ... then ... else**and I don't take advantage of Haskell's pattern matching and guards when defining functions.## Guards!

Take the**backwards**function. At first it was**backwards n = backwards' n 0**

where backwards' n accum = if n < 10 then n + accum

else backwards' (n `div` 10) (10 * (n `mod` 10 + accum))where backwards' n accum = if n < 10 then n + accum

else backwards' (n `div` 10) (10 * (n `mod` 10 + accum))

and that's perfectly valid Haskell, but we can do better. How about this?

**backwards n =**

let backwards' m accum

| m < 10 = accum + m

| otherwise = backwards' (m `div` 10) (10 * (m `mod` 10 + accum))

in backwards' n 0let backwards' m accum

| m < 10 = accum + m

| otherwise = backwards' (m `div` 10) (10 * (m `mod` 10 + accum))

in backwards' n 0

Here we are using guards, and while, thanks to the current layout, there is still wraparound, the code now honors the golden 80-column punched card that some things, most notably standards for source code layout, still bow down to in the computer world. (UPDATE: I waved a dead chicken at the layout, and it now fits.) Things to note:

- there's no
**=**immediately after the list of formal parameters of**backwards'**the way there was in the first version. The**=**are after the guards. - it may just be that I'm not familiar enough with Haskell syntax, but I had to turn things around and use a
**let**rather than a**where**for the definition of the helper function**backwards'**. - speaking of style, did you notice I changed the name of the first parameter of
**backwards'**? I decided I'd better do that, the same way I'd avoid gratuitously redeclaring a variable in an inner block with the same name as one in an outer block.

## Patterns

**if then else**, though. Remember**choose**?**nDigits `choose` nOnes =**

if nOnes == 0 then [0]

else if nDigits == 1 then [1]

else if nDigits == nOnes then [sum [10 ^ n | n <- [0..nDigits - 1]]]

else concat [[0 + 10 * x | x <- (nDigits - 1) `choose` nOnes],

[1 + 10 * x | x <- (nDigits - 1) `choose` (nOnes - 1)]]if nOnes == 0 then [0]

else if nDigits == 1 then [1]

else if nDigits == nOnes then [sum [10 ^ n | n <- [0..nDigits - 1]]]

else concat [[0 + 10 * x | x <- (nDigits - 1) `choose` nOnes],

[1 + 10 * x | x <- (nDigits - 1) `choose` (nOnes - 1)]]

Let's take advantage of pattern matching as well as guards:

**_ `choose` 0 = [0]**

1 `choose` _ = [1]

m `choose` n

| m == n = [sum [10 ^ i | i <- [0..m - 1]]]

| otherwise = concat [[0 + 10 * x | x <- (m - 1) `choose` n],

[1 + 10 * x | x <- (m - 1) `choose` (n - 1)]]1 `choose` _ = [1]

m `choose` n

| m == n = [sum [10 ^ i | i <- [0..m - 1]]]

| otherwise = concat [[0 + 10 * x | x <- (m - 1) `choose` n],

[1 + 10 * x | x <- (m - 1) `choose` (n - 1)]]

**For this, you should know that**

**_**matches anything. An identifier matches anything, too, but you can refer to it on the other side of the**=**. Use**_**when, given the other parameters and/or the previously checked patterns, the value of the function does not depend on the value that**_**matches. The patterns are applied in order, by the way, so here**1 `choose` 0**will match**_ `choose` 0**and not**1 `choose` _**.Yes, I must admit that I chose shorter parameter names. While in the case of this test, I am passing in a number of digits, that is distracting from the function, so here I would say that my initial choice was wrong. It's not just a matter of making lines fit in 80 columns.

## DRY

DRY here is an acronym, and it applies no matter what your programming language. DRY = Don't Repeat Yourself. I said, Don't Repeat Yourself.I very much repeat myself in the original program when it comes to the formation of a palindrome from its upper half (or in the case of an odd number of digits, the upper half and the middle digit). That needs its own function, or rather functions.

In theory those are all the parameters needed; you can calculate the number of digits in the upper half. Since we have that value, though, I'm inclined to pass it in.

Also speaking of DRY, I should use these functions to generate the palindromes with two 2s rather than making a special case of them. Say what you mean, as clearly as possible.

[We pause here for some testing and checking of run times for the input file with values up to 10

^{100}.]It's hard to say whether it makes a difference; just running the same program repeatedly shows variance in the time output. Here's one towards the low end:

**real 0m1.822s**

user 0m1.804s

sys 0m0.012suser 0m1.804s

sys 0m0.012s

while here's one towards the high end:

**real 0m1.905s**

user 0m1.872s

sys 0m0.028suser 0m1.872s

sys 0m0.028s

IMHO the result is worth the minimal, if it even exists, increase in run time.

Here's the code after the smoke cleared:

**import Prelude**

import Data.List

backwards :: Integer -> Integer

backwards n =

let backwards' n accum

| n < 10 = accum + n

| otherwise = backwards' (n `div` 10) (10 * (n `mod` 10 + accum))

in backwards' n 0

evenDigitsPal :: Integer -> Integer -> Integer

evenDigitsPal topHalf nDigits = topHalf * 10 ^ nDigits + backwards topHalf

oddDigitsPal :: Integer -> Integer -> Integer -> Integer

oddDigitsPal topHalf nDigits middle = (topHalf * 10 + middle) * 10 ^ nDigits + backwards topHalf

choose :: Integer -> Integer-> [Integer]

_ `choose` 0 = [0]

1 `choose` _ = [1]

m `choose` n

| m == n = [sum [10 ^ i | i <- [0..m - 1]]]

| otherwise = concat [[0 + 10 * x | x <- (m - 1) `choose` n],

[1 + 10 * x | x <- (m - 1) `choose` (n - 1)]]

chooseRange :: Integer -> [Integer] -> [Integer]

m `chooseRange` ns = concat [m `choose` n | n <- ns, n <= m]

twoTwos :: Integer -> [Integer]

twoTwos n

| even n = [evenDigitsPal msd (n `div` 2)]

| otherwise = [oddDigitsPal msd (n `div` 2) d | d <- [0,1]]

where msd = 2 * 10 ^ (n `div` 2 - 1)

oneTwo :: Integer -> [Integer]

oneTwo n

| even n = []

| otherwise = let halfN = n `div` 2

msd = 10 ^ (halfN - 1)

in [oddDigitsPal (msd + x) halfN 2 |

x <- (halfN - 1) `import Data.List

backwards :: Integer -> Integer

backwards n =

let backwards' n accum

| n < 10 = accum + n

| otherwise = backwards' (n `div` 10) (10 * (n `mod` 10 + accum))

in backwards' n 0

evenDigitsPal :: Integer -> Integer -> Integer

evenDigitsPal topHalf nDigits = topHalf * 10 ^ nDigits + backwards topHalf

oddDigitsPal :: Integer -> Integer -> Integer -> Integer

oddDigitsPal topHalf nDigits middle = (topHalf * 10 + middle) * 10 ^ nDigits + backwards topHalf

choose :: Integer -> Integer-> [Integer]

_ `choose` 0 = [0]

1 `choose` _ = [1]

m `choose` n

| m == n = [sum [10 ^ i | i <- [0..m - 1]]]

| otherwise = concat [[0 + 10 * x | x <- (m - 1) `choose` n],

[1 + 10 * x | x <- (m - 1) `choose` (n - 1)]]

chooseRange :: Integer -> [Integer] -> [Integer]

m `chooseRange` ns = concat [m `choose` n | n <- ns, n <= m]

twoTwos :: Integer -> [Integer]

twoTwos n

| even n = [evenDigitsPal msd (n `div` 2)]

| otherwise = [oddDigitsPal msd (n `div` 2) d | d <- [0,1]]

where msd = 2 * 10 ^ (n `div` 2 - 1)

oneTwo :: Integer -> [Integer]

oneTwo n

| even n = []

| otherwise = let halfN = n `div` 2

msd = 10 ^ (halfN - 1)

in [oddDigitsPal (msd + x) halfN 2 |

x <- (halfN - 1) `

noTwos :: Integer -> [Integer]

noTwos n

| even n = [evenDigitsPal (msd + x) halfN | x <- choices]

| otherwise = concat [[oddDigitsPal (msd + x) halfN 0,

oddDigitsPal (msd + x) halfN 1] | x <- choices]

where halfN = n `div` 2

msd = 10 ^ (halfN - 1)

choices = (halfN - 1) `chooseRange` [0..3]

possibles :: Integer -> [Integer]

possibles 1 = [0..3]

possibles 2 = [11, 22]

possibles n = sort (concat [noTwos n, oneTwo n, twoTwos n])

ys = concat [possibles nDigits | nDigits <- [1..]]

xs = [y * y | y <- ys]

palSquares :: Integer -> Integer -> [Integer]

palSquares m n = takeWhile (<= n) (dropWhile (< m) xs)

-- jagd's main, which I believe is set up to read stdin

solve i num = do

[a, b] <- getLine >>= return . map read . words

putStrLn $ "Case #" ++ show i ++ ": " ++ (show $ length (palSquares a b))

if i < num

then solve (i+1) num

else return ()

main = do

num <- getLine >>= return.read

solve 1 num**chooseRange`**[0..1]]noTwos :: Integer -> [Integer]

noTwos n

| even n = [evenDigitsPal (msd + x) halfN | x <- choices]

| otherwise = concat [[oddDigitsPal (msd + x) halfN 0,

oddDigitsPal (msd + x) halfN 1] | x <- choices]

where halfN = n `div` 2

msd = 10 ^ (halfN - 1)

choices = (halfN - 1) `chooseRange` [0..3]

possibles :: Integer -> [Integer]

possibles 1 = [0..3]

possibles 2 = [11, 22]

possibles n = sort (concat [noTwos n, oneTwo n, twoTwos n])

ys = concat [possibles nDigits | nDigits <- [1..]]

xs = [y * y | y <- ys]

palSquares :: Integer -> Integer -> [Integer]

palSquares m n = takeWhile (<= n) (dropWhile (< m) xs)

-- jagd's main, which I believe is set up to read stdin

solve i num = do

[a, b] <- getLine >>= return . map read . words

putStrLn $ "Case #" ++ show i ++ ": " ++ (show $ length (palSquares a b))

if i < num

then solve (i+1) num

else return ()

main = do

num <- getLine >>= return.read

solve 1 num

UPDATE: Aside from something in a later message, the only things I can think of to do are

- adding concise comments that suffice to describe what the code does and how to the extent that the code itself is unclear
- changing some function names.
**possibles**sort of made sense when we were range checking and/or palindrome checking right there, but the range checking is moved out and given the math, they're not possible, they're certain. Also,**choose**isn't quite right. We're not counting combinations, as the phrase "m choose n" is meant in standard math nomenclature--we're generating them. I'm not sure what to use in their place, though.

## Comments