Problem 145

http://projecteuler.net/index.php?section=problems&id=145
とりあえずナイーブなもの。

import Data.Char

revInt ::Integer -> Integer
revInt = read.reverse.show

reversible n = mod n 10 /= 0 && (all odd.map digitToInt.show.(+n).revInt) n

p145 n = filter reversible [1..n]

main = print.length.p145$10^5

もちろん解けない（計算時間的な意味で）。
悪くはないと思うけど、今回は探索範囲が10^9だから、このままではつらい。
さて、これからどうするか。

[追記]

繰り上がりを考えるとそれが伝播されていく。

rev 0 (0,0) = 1
rev 0 _     = 0

rev 1 (0,0) = 0
rev 1 (1,0) = 0
rev 1 (0,1) = 5
rev 1 (1,1) = 5

rev 2 (0,0) = 30
rev 2 (1,0) = 0
rev 2 (0,1) = 0
rev 2 (1,1) = 25

rev d (0,0) = 30 * (rev (d-2) (0,0))
rev d (1,0) = 20 * (rev (d-2) (0,1))
rev d (0,1) = 25 * (rev (d-2) (1,0))
rev d (1,1) = 25 * (rev (d-2) (1,1))

reversible 1 = 0
reversible d = 20 * (rev (d-2) (0,0) + rev (d-2) (0,1))

main = print.sum.map reversible $ [1..9]

速くなった。探索範囲が10^100でも大丈夫。
DPでもつかえば、もっと速くなるはず。
というか、手計算で求まるはず。