Problem 189

Problem 189 – Project Euler

まぁ,DPですな.

import Data.List (delete,nub)
import Data.Maybe (mapMaybe)
import Data.Map (fromListWith,toList)
import Control.Arrow ((***))
data Color = R | G | B deriving (Eq,Ord,Show)
normal :: [Color] -> [Color]
normal cs = mapMaybe (flip lookup m) cs
where m = zip (nub cs) $ [R,G,B]
root,branch :: [Color] -> [[Color]]
root = sequence.map (flip delete [R,G,B])
branch cs = sequence.zipWith next (head cs:cs) $ cs ++ [last cs]
where next c1 c2 = delete c1.delete c2 $ [R,G,B]
build :: [([Color], Integer)] -> [([Color], Integer)]
build = gather.tie (map normal.branch).gather.tie (map normal.root)
where tie f = concatMap (uncurry zip.(f***repeat))
gather = toList.fromListWith (+)
p189 :: Int -> Integer
p189 (n+1) = (3*).sum.map snd.(!!n).iterate build $ [([R],1)]
main = print.p189 $ 8

久々に関数型っぽいぞ.

非常にどうでもいいことだが,

root = sequence.map (c -> delete c [R,G,B])

ラムダ抽象化か,

root = sequence.map (flip delete [R,G,B])

flipか.どちらがいいか?

ラムダ抽象化のほうが可読性が高い気がするが,そうするとflipの存在意義が…

追記

id:rst76さんに頂いたコメントから

root = sequence.map (`delete` [R,G,B])

これが良いのではないか,という結論に達した.

More Reading
Newer// Problem 187