+-- Writeup at https://work.njae.me.uk/2023/12/09/advent-of-code-2023-day-09/
+
+import AoC
+import Data.List
+
+newtype Sequence = Sequence [[Int]] deriving (Show, Eq)
+
+main :: IO ()
+main =
+ do dataFileName <- getDataFileName
+ text <- readFile dataFileName
+ let histories = readInput text
+ -- print histories
+ let seqs = fmap (expand . Sequence . pure) histories
+ -- print seqs
+ -- let seqs' = fmap extend seqs
+ -- print seqs'
+ print $ part1 seqs
+ let rseqs = fmap (expand . Sequence . pure . reverse) histories
+ print $ part1 rseqs
+
+part1 :: [Sequence] -> Int
+part1 = sum . fmap (evaluate . extend)
+
+
+readInput :: String -> [[Int]]
+readInput = fmap (fmap read . words) . lines
+
+expand :: Sequence -> Sequence
+expand (Sequence xss)
+ | all (== 0) $ last xss = Sequence xss
+ | otherwise = expand $ Sequence $ xss ++ [differences $ last xss]
+
+differences :: [Int] -> [Int]
+differences xs = zipWith (-) (tail xs) xs
+
+extend :: Sequence -> Sequence
+extend (Sequence xss) = Sequence $ fst $ foldr extendRow ([], 0) xss
+
+extendRow :: [Int] -> ([[Int]], Int) -> ([[Int]], Int)
+extendRow row (seq, n) = ((row ++ [n']) : seq, n')
+ where n' = last row + n
+
+evaluate :: Sequence -> Int
+evaluate (Sequence xss) = last $ head xss