Problem36

30分プログラム、その309。Problem36 - Project Euler。

585 = 10010010012 (2進) は10進でも2進でも回文数である.
100万未満で10進でも2進でも回文数になるような数の総和を求めよ.
(注: 先頭に0を含めて回文にすることは許されない.)

0が条件を満すかどうか、しばらくの間悩んでた。でも総和だから、含めても含めなくても答えは同じなんだよね。恥かしい・・・。
あと、Haskellは強すぎるだろ。

使い方

*Main> main
872187

ソースコード

import Numeric
import Control.Monad.List
kaibunDigit :: Int -> [Int]
kaibunDigit 1 = [1..9]
kaibunDigit 2 = [11*n | n <- [1..9]]
kaibunDigit n = do x <- 0:kaibunDigit (n-2)
                   y     <- [1..9]
                   return (base*y+x*10+y)
    where base = 10^(n-1)

binary :: Int -> String
binary x = showIntAtBase 2 (\x -> if x == 0 then '0' else '1') x ""
isKaibunBin :: Int -> Bool
isKaibunBin x = bin == reverse bin
    where bin = binary x

main = print $ sum $ do n <- [1..6]
                        x <- kaibunDigit n
                        guard $ isKaibunBin x
                        return x

参考

• 過去の30分プログラム
• Problem 36 - PukiWiki