module Problem122 where

import Control.Arrow
import Data.Array

data Node = Node { value :: Int, depth :: Int, parent :: Maybe Node }

instance Show Node where
    show node = "(" ++ show (value node) ++ ")"

getChildren :: Array Int Int -> Node -> [Node]
getChildren mVals node = map (\val -> Node val newDepth (Just node)) newValues
  where
    newDepth = depth node + 1
    ancestors (Node val _ Nothing ) = [val]
    ancestors (Node val _ (Just p)) = val : ancestors p
    newValues = filter (\v -> mVals ! v > newDepth) $ filter (<= 200) $ map
        (+ value node)
        (ancestors node)

main :: IO ()
main = print . sum . snd . head . dropWhile (elem 999 . snd) $ iterate
    (\(nodes, mVals) ->
        let children = concatMap (getChildren mVals) nodes
        in (children, storeMinDepths mVals children)
    )
    ([root], initMVal)
  where
    root     = Node 1 0 Nothing
    initMVal = array (1, 200) $ (1, 0) : zip [2 .. 200] (repeat 999)
    storeMinDepths mVals children = accum min mVals (map (value &&& depth) children)
