Problem32

30分プログラム、その305。Project Euler - Problem32。

7254は面白い性質を持っている. 39 × 186 = 7254と書け, 掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

いい方法が思いつかなかったので、力づくで解いてみた。

• [1..9]を適当に並べ替えたリストLを作る。例えば、[3,9,1,8,6,7,2,5,4]
• 適当な数字、a,bを選ぶ。ただしa < b。例えば、2と5。
• Lをaとbの位置で分解する。lhs=39, rhs=186, res=7254
• lhs*rhs=resかどうかを確認する

こうして、全てのresを求めたあと重複を削除してみた。遅いけど、まあ間違ってはいない。

使い方

$ time ./problem32
45228
./problem32  66.45s user 2.07s system 80% cpu 1:25.26 total

ソースコード

import Data.List
import Control.Monad.List

combination :: [Int] -> [[Int]]
combination [x] = [[x]]
combination xs = do x <- xs
                    rest <- combination $ delete x xs
                    return (x:rest)

makeInt xs = foldl (\x y->10*x+y) 0 xs

satisfy xs = do a <- [1..size-2]
                b <- [a+1..size-1]
                let (ys,res)  = splitAt b xs
                let (lhs,rhs) = splitAt a ys
                guard $ makeInt lhs * makeInt rhs == makeInt res
                return $ makeInt res
    where size = length xs

solve = do xs <- combination [1..9]
           x <- satisfy xs
           return x

main = print $ sum $ nub solve

参考

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