5問目を解いてみた

5問目が流行ってたようなので書いた。本家より超頭が悪い総当たり。40分くらいだけどオフラインどう書くの会場だったら時間内に解ける気がしない。

module Main (main) where

import Control.Monad (forM_)

main :: IO ()
main = forM_ (map showCandidate answers) putStrLn

type Atom = (Char, String)
type Candidate = [Atom]

answers :: [Candidate]
answers = filter ((== 100) . calc) . filter (isplus . head) $ candidates

candidates :: [Candidate]
candidates = makeCandidate "123456789"

makeCandidate :: String -> [Candidate]
makeCandidate = makeCandidate' []

makeCandidate' :: String -> String -> [Candidate]
makeCandidate' [] [] = []
makeCandidate' ns [] = plusminus ns
makeCandidate' ns (x:xs) = ans1 ++ ans2
  where
    ans1 = do
      h <- plusminus (ns ++ [x])
      t <- makeCandidate xs
      return $ h ++ t
    ans2 = makeCandidate' (ns ++ [x]) xs

plusminus :: String -> [Candidate]
plusminus ns = [[('+', ns)], [('-', ns)]]

isplus :: Atom -> Bool
isplus ('+', _) = True
isplus _ = False

calc :: Candidate -> Int
calc = ($ 0) . foldr (\atom f -> hom atom . f) id

hom :: Atom -> Int -> Int
hom ('+', ns) = (+ (read ns))
hom ('-', ns) = (subtract (read ns))

showAtom :: Atom -> String
showAtom (c, ns) = c:ns

showCandidate :: Candidate -> String
showCandidate = tail . concatMap showAtom

リストモナドでdo記法が使えるのは楽。