Going backwards

I figured I might try the same "loop unrolling" with backwards' as worked so well with digitsIn'. Admittedly I only did it once, but the results didn't go the right way:

COST CENTRE                MODULE  %time %alloc

numWithin                  Main     29.5    7.2
solve                      Main     21.0   35.3
backwards.backwards'       Main     16.6   17.5
backwards.backwards'.(...) Main      9.5   12.6
choices                    Main      5.2    8.9
digitsIn.digitsIn'         Main      5.2    4.9
nDigitYs                   Main      4.6    5.8
tenToThe                   Main      1.8    0.0
floorSqrt.floorSqrt'.y     Main      1.1    1.2
oddDigitsPals              Main      0.9    1.8
noTwos                     Main      0.7    1.3

As you can see by comparison with a previous profile, backwards is now taking up more time and allocation than before.

Guess we'll have to memoize...

backwardsMemo = [backwards' n 0 | n <- [0..]]
    where backwards' n accum
              | n < 10    = accum + n
              | otherwise = let (d, m) = n `divMod` 10
                            in backwards' d (10 * (m + accum))

backwards :: Integer -> Integer

backwards n = backwardsMemo `genericIndex` n

Um, no, we won't, not that way. In theory, at least, we should just be evaluating backwards a bit over 40,000 times, but then there are the calls to backwards'. After about two minutes I killed the process. (Does indexing cause all the intermediate items to be generated?)

We know that the tempting

backwards = read . reverse . show

loses big time in comparison with what we have already as well.

So, let's think about the particular values we're handing backwards:

• For twoTwos, 2 * tenToThe n. Here, backwards will grind down a zero at a time and give us back 2, every time.
• For oneTwo and noTwos,  it will always be a sum of between 1 and 2 (for oneTwo) or 1 and 3 (for noTwos) values of the form tenToThe i.

So... we blew it when we wrote our even and odd number of digit palindrome generators the way we did, and we don't want to generate them the way we are now. We don't want to represent our half-Ys as Integers, but instead as short lists of the powers of ten that you add to make them up. No Integers until we actually churn out the palindromes themselves. Then we can avoid a numeric backwards altogether.