Lists of integers are at the core of today’s puzzle. This post is a literate Haskell program; here’s a few imports to skip over.

```
{-# LANGUAGE NamedFieldPuns #-}
import Control.Monad (guard)
import Data.List (find,tails)
```

Part 1 asks to identify the first number that cannot be expressed as the sum of two distinct numbers taken among its 25 predecessors.

There’s not much to fuss about, just doing it is sufficient. I’ll use a list zipper.

`data Zip a = Zip { trail :: ![a], cursor :: !a, list :: [a] }`

The zipper provides a view on an element of a list in context. It can be moved left or right in constant time/space. For this problem I’ll only need going right.

```
advance :: Zip a -> Zip a
Zip t c (c':l)) = Zip (c:t) c' l advance (
```

I can convert from a list by simply expanding the cursor on the list’s first element.

```
fromList :: [a] -> Zip a
:t) = Zip [] h t fromList (h
```

A cursor position is valid if I can find a pair of distinct^{1} numbers among the 25 previous that sum up to it.

```
valid :: Zip Int -> Bool
Zip{trail,cursor} = or $ do
valid :ys) <- tails (take 25 trail)
(x<- ys
y -- guard (x /= y)
pure $ cursor == x + y
```

Part 1 is then solved with a straightforward function composition.

```
part1 :: [Int] -> Int
=
part1 maybe (error "All numbers are valid.") cursor .
not . valid) .
find (drop 25 .
iterate advance .
fromList
```

Instead of a pair, part 2 asks to find a contiguous subsequence that sums to the number found in part 1. The classical response is to construct a list of partial sums, so the sum can be searched for in quadratic time as a difference of two elements.

```
part2 :: [Int] -> Int -> [Int]
=
part2 ns let partials = scanl (+) 0 ns
in \s -> head $ do
:_:bts) <- tails (zip partials [0..])
((a,from)<- bts
(b,to) - a == s)
guard (b pure $ take (to - from) $ drop from ns
```

Here’s `main`

for completeness.

```
= do
main <- map read . lines <$> readFile "day09.in"
ns let special = part1 ns
print special
let contiguous = part2 ns special
print $ minimum contiguous + maximum contiguous
```

This concludes today’s solution. See you soon!

I didn’t notice that distinctness constraint when I first solved it. And I didn’t need it to solve. YMMV.↩︎