Advent of Code 2023 day 09

Day 9 was real old-school, going back to the method of divided differences as used in Babbage's Difference Engine.

Update

Now I've had a chance to think, I've altered a couple of bits of this solution.

1. I don't use the newtype, which allows me to simplify some parts of the code
2. In my quest to avoid explicit recursion, I've used an unfold to expand the sequence.

You can still see the original post below.

Solution

A Sequence is a list of list of numbers.

type Sequence = [[Int]]

That stores all the rows of the expanded sequence, so the sequence of

0   3   6   9  12  15
  3   3   3   3   3
    0   0   0   0

is represented as

[[0,3,6,9,12,15],[3,3,3,3,3]]

(I don't bother storing the last row of zeros.)

Reading the input uses lines and words. That's converted into a Sequence with expand, which unfolds extra rows to the bottom of the sequence as needed.

readInput :: String -> [[Int]]
readInput = fmap (fmap read . words) . lines

expand :: [Int] -> Sequence
expand seq = unfoldr go seq
  where go xs
          | all (== 0) xs = Nothing
          | otherwise = Just (xs, differences xs)

differences :: [Int] -> [Int]
differences xs = zipWith (-) (tail xs) xs

Part 1

I extend a sequence as a foldr, building up a new sequence from the bottom row upwards. The fold keeps track of the rows built so far, and the last number of the highest row. The new row is built by incrementing its own last element by the difference.

extend :: Sequence -> Sequence
extend = fst . foldr extendRow ([], 0)

extendRow :: [Int] -> ([[Int]], Int) -> ([[Int]], Int)
extendRow row (seq, n) = ((row ++ [n']) : seq, n')
  where n' = last row + n

I evaluate a sequence by pulling out the last element of the top row. And that's part 1 done.

part1 :: [Sequence] -> Int
part1 = sum . fmap (evaluate . extend)

evaluate :: Sequence -> Int
evaluate = last . head

Part 2

Extending a sequence backwards is just... extending the reversed sequence.

let rseqs = fmap (expand . reverse) histories
print $ part1 rseqs

Original

Given this was a weekend, I was somewhat wary of this problem, wondering what perils part 2 would hold. That meant I slightly over-engineered the data, by using a newtype to hold the full sequence.

newtype Sequence = Sequence [[Int]] deriving (Show, Eq)

That stores all the rows of the expanded sequence, so the sequence of

0   3   6   9  12  15
  3   3   3   3   3
    0   0   0   0

is represented as

Sequence [[0,3,6,9,12,15],[3,3,3,3,3],[0,0,0,0]]

Reading the input uses lines and words. That's converted into a Sequence with expand, which adds more rows to the bottom of the sequence as needed.

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

main = 
  do  dataFileName <- getDataFileName
      text <- readFile dataFileName
      let histories = readInput text
      let seqs = fmap (expand . Sequence . pure) histories
      print $ part1 seqs

Part 1

I extend a sequence as a foldr, building up a new sequence from the bottom row upwards. The fold keeps track of the rows built so far, and the last number of the highest row. The new row is built by incrementing its own last element by the difference.

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

I evaluate a sequence by pulling out the last element of the top row. And that's part 1 done.

part1 :: [Sequence] -> Int
part1 = sum . fmap (evaluate . extend)

evaluate :: Sequence -> Int
evaluate (Sequence xss) = last $ head xss

Part 2

Extending a sequence backwards is just... extending the reversed sequence.

let rseqs = fmap (expand . Sequence . pure . reverse) histories
print $ part1 rseqs

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.