module Euler.Util.TrianglePath
(
Triangle
, Row
, parseTriangle
, reduceTriangle
) where
import Euler.Prelude
import qualified Data.List.NonEmpty as NE
import qualified Data.Text as T
import Euler.Util.List (neTails)
import Prelude (read)
import qualified Data.List as List
type Row a = NonEmpty a
type Triangle a = NonEmpty (Row a)
parseTriangle :: Integral a => Text -> Triangle a
parseTriangle =
NE.fromList . List.reverse . mapMaybe parseRow . T.lines
where
parseRow = nonEmpty . fmap (readI . T.unpack) . T.words
readI t = fromIntegral (read t :: Int)
reduceTriangle :: Integral a => Triangle a -> a
reduceTriangle (row :| []) =
List.maximum row
reduceTriangle (row :| [x :| []]) =
x + List.maximum (NE.take 2 row)
reduceTriangle (row1 :| row2 : otherRows) =
reduceTriangle (newFirstRow :| otherRows)
where
newFirstRow = do
(row, x) <- NE.zip (neTails row1) row2
return $ reduceTriangle $ row :| [x :| []]