### Great Leap Forward

So, we made the change. Note that we are in fact generating the lists for the combinations!

This gives a definite improvement.

and the worst is

I wish I knew the source of the variation; perhaps other processes running at the time? If we can believe the best result, we're down to 1.27 times the run time of the C++ solution we tested... and we haven't touched the real time sink. Check this out:

So we've cut down total allocation by over 200MB (not to be confused with the memory usage, which takes a final spike of about a quarter megabyte

P.S. Note that I've deviated from the define-before-use ordering that I've stuck to in the past, and the results compiled without complaint. I infer from this that Haskell must be waiting until it's read the whole file to do at least some of the type checking, so I should be able to get away with putting definitions in top-down order.

**{-**

Here's our new approach: rather than generate the upper half separately and

then have to reverse it a digit at a time, we generate both halves at the

same time, when we have information we need to do so.

So, out with backwards and {odd,even}DigitsPal, and twoTwos goes back to its

simple self.

-}

twoTwos :: Int -> [Integer]

twoTwos n

| n == 1 = []

| even n = [twoTwosNoOnes]

| otherwise = [twoTwosNoOnes, twoTwosNoOnes + 10 ^ (n `div` 2)]

where twoTwosNoOnes = 2 * tenToThe (n - 1) + 2

oneTwos :: Int -> [Integer]

oneTwos n

| n == 1 = [2]

| even n = []

| otherwise = [p + 2 * tenToThe halfN

| p <- justOnes n (min 1 (halfN - 1))]

where halfN = n `div` 2

noTwos :: Int -> [Integer]

noTwos n

| n == 1 = [1,3]

| even n = base

| otherwise = concat [[p, p + tenToThe halfN] | p <- base]

where halfN = n `div` 2

base = justOnes n (min 3 (halfN - 1))

choices :: Int -> Int-> [[Int]]

m `choices` n

| n == 0 = [[]]

| m == n = [[m,m-1..1]]

| otherwise = [m : c | c <- (m - 1) `choices` (n - 1)]

++ ((m - 1) `choices` n)

{-

justOnes -- here's where the real action happens. Here we generate palindromes

with a specified number of digits all of whose non-zero digits are 1s. 1 must

thus be the most/least significant digit; in addition, between 0 and a

specified number of 1s are scattered through the rest of each half. If the

number of digits requested is odd, we will leave a 0 in the middle digit,

which the caller may or may not replace with another digit.Here's our new approach: rather than generate the upper half separately and

then have to reverse it a digit at a time, we generate both halves at the

same time, when we have information we need to do so.

So, out with backwards and {odd,even}DigitsPal, and twoTwos goes back to its

simple self.

-}

twoTwos :: Int -> [Integer]

twoTwos n

| n == 1 = []

| even n = [twoTwosNoOnes]

| otherwise = [twoTwosNoOnes, twoTwosNoOnes + 10 ^ (n `div` 2)]

where twoTwosNoOnes = 2 * tenToThe (n - 1) + 2

oneTwos :: Int -> [Integer]

oneTwos n

| n == 1 = [2]

| even n = []

| otherwise = [p + 2 * tenToThe halfN

| p <- justOnes n (min 1 (halfN - 1))]

where halfN = n `div` 2

noTwos :: Int -> [Integer]

noTwos n

| n == 1 = [1,3]

| even n = base

| otherwise = concat [[p, p + tenToThe halfN] | p <- base]

where halfN = n `div` 2

base = justOnes n (min 3 (halfN - 1))

choices :: Int -> Int-> [[Int]]

m `choices` n

| n == 0 = [[]]

| m == n = [[m,m-1..1]]

| otherwise = [m : c | c <- (m - 1) `choices` (n - 1)]

++ ((m - 1) `choices` n)

{-

justOnes -- here's where the real action happens. Here we generate palindromes

with a specified number of digits all of whose non-zero digits are 1s. 1 must

thus be the most/least significant digit; in addition, between 0 and a

specified number of 1s are scattered through the rest of each half. If the

number of digits requested is odd, we will leave a 0 in the middle digit,

which the caller may or may not replace with another digit.

**-}**

justOnes :: Int -> Int -> [Integer]

justOnes n o =

let halfN = n `div` 2

shell = tenToThe (n - 1) + 1

innards = concat [(halfN - 1) `choices` k | k <- [0..o]]

pair i = tenToThe i + tenToThe (n - (i + 1))

in [shell + sum (map pair c) | c <- innards]justOnes :: Int -> Int -> [Integer]

justOnes n o =

let halfN = n `div` 2

shell = tenToThe (n - 1) + 1

innards = concat [(halfN - 1) `choices` k | k <- [0..o]]

pair i = tenToThe i + tenToThe (n - (i + 1))

in [shell + sum (map pair c) | c <- innards]

This gives a definite improvement.

**time**output again varies a fair amount; the best we've seen so far is**real 0m0.509s**

user 0m0.488s

sys 0m0.016suser 0m0.488s

sys 0m0.016s

and the worst is

**real 0m0.581s**

user 0m0.564s

sys 0m0.008suser 0m0.564s

sys 0m0.008s

I wish I knew the source of the variation; perhaps other processes running at the time? If we can believe the best result, we're down to 1.27 times the run time of the C++ solution we tested... and we haven't touched the real time sink. Check this out:

**total alloc = 345,155,656 bytes (excludes profiling overheads)**

**COST CENTRE MODULE %time %alloc**

numWithin Main 44.7 11.3

solve Main 24.7 55.5

digitsIn.digitsIn' Main 6.1 7.8

nDigitYs Main 5.6 7.8

tenToThe Main 5.3 0.0

justOnes Main 3.0 6.4

justOnes.pair Main 2.2 3.1

floorSqrt.floorSqrt'.y Main 2.1 1.9

noTwos Main 1.0 1.0

choices Main 1.0 2.9numWithin Main 44.7 11.3

solve Main 24.7 55.5

digitsIn.digitsIn' Main 6.1 7.8

nDigitYs Main 5.6 7.8

tenToThe Main 5.3 0.0

justOnes Main 3.0 6.4

justOnes.pair Main 2.2 3.1

floorSqrt.floorSqrt'.y Main 2.1 1.9

noTwos Main 1.0 1.0

choices Main 1.0 2.9

So we've cut down total allocation by over 200MB (not to be confused with the memory usage, which takes a final spike of about a quarter megabyte

*above*the previous version). We could take a look at avoiding actually generating the list of chosen exponents for the half-Ys, but we have to face facts.**numWithin**is now eating nearly half the time, and if the above is to be believed,**solve**, of all things, is responsible for*over half*the allocation! (Maybe I don't understand just what the profiling output is trying to tell me.) We're within spitting distance of the C++ version; a move from O(n) to O(log n) for the range check ought to bring us ahead.P.S. Note that I've deviated from the define-before-use ordering that I've stuck to in the past, and the results compiled without complaint. I infer from this that Haskell must be waiting until it's read the whole file to do at least some of the type checking, so I should be able to get away with putting definitions in top-down order.

## Comments