# Advent of Code 2021: Day 8 & 9

Andrew Fontaine <andrew@afontaine.ca>Another multi-day combo post! I didn’t get to start day 8 until late, and finished it with 10 minutes to spare. Thus, no time to write a post yesterday.

## Day 8

These elves need to maintain their stuff more. It seems the whale problem has left the seven-segment display busted.

Now… I know where this is going, and it’s going to be *awful*. Let’s play
along though, all we have to do is find all the easy digits.

Parsing is a bit of a mess, so I’ll skip that. The end result is pretty simple though:

```
let find_easy list =
List.filter
(fun n ->
let len = String.length n in
len = 2 || len = 4 || len = 3 || len = 7)
list
let p1 =
List.map (fun (_, o) -> find_easy o) input
|> List.flatten |> List.length |> string_of_int
```

All I do is check to see if the length of the pattern matches the length of a 1, 4, 7, or 8, and count the number of times those appear.

⭐ one done!

### Part 2

*Of course* they want us to solve for all the wires.

This code is a mess, so I’m just going to start at the top and work my way in.

```
let group patterns =
List.map
(fun p ->
match String.length p with
| 2 -> (p, [ 1 ])
| 3 -> (p, [ 7 ])
| 4 -> (p, [ 4 ])
| 5 -> (p, [ 2; 3; 5 ])
| 6 -> (p, [ 0; 6; 9 ])
| 7 -> (p, [ 8 ])
| _ -> raise (BadPattern p))
patterns
let initial_guess numbers map char =
let pos =
List.map
(function
| 0 -> [ 'a'; 'b'; 'c'; 'e'; 'f'; 'g' ]
| 1 -> [ 'c'; 'f' ]
| 2 -> [ 'a'; 'c'; 'd'; 'e'; 'g' ]
| 3 -> [ 'a'; 'c'; 'd'; 'f'; 'g' ]
| 4 -> [ 'b'; 'c'; 'd'; 'f' ]
| 5 -> [ 'a'; 'b'; 'd'; 'f'; 'g' ]
| 6 -> [ 'a'; 'b'; 'd'; 'e'; 'f'; 'g' ]
| 7 -> [ 'a'; 'c'; 'f' ]
| 8 -> [ 'a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g' ]
| 9 -> [ 'a'; 'b'; 'c'; 'd'; 'f'; 'g' ]
| i -> raise (BadNumber i))
numbers
|> List.flatten
in
let possibilities = CharSet.of_list pos in
CharMap.update char
(function
| None -> Some possibilities
| Some pos -> Some (CharSet.inter pos possibilities))
map
let rec construct map = function
| [] -> map
| (pattern, numbers) :: rest ->
let chars = Core.String.to_list pattern in
let m = List.fold_left (initial_guess numbers) map chars in
construct m rest
```

First, I need to parse the values into something workable. I want to turn the
patterns into a map of sets. Each character in the patterns maps to a set
containing the possibilities of what that character could actually be, so for
the pattern `ab`

, each character would point to `cf`

, as they could be either
segment making up the 1.

Once that’s done, just solve 🤷

First, I need some code to actually check if the result I found is valid.

```
let valid_patterns =
[
[ 'a'; 'b'; 'c'; 'e'; 'f'; 'g' ];
[ 'c'; 'f' ];
[ 'a'; 'c'; 'd'; 'e'; 'g' ];
[ 'a'; 'c'; 'd'; 'f'; 'g' ];
[ 'b'; 'c'; 'd'; 'f' ];
[ 'a'; 'b'; 'd'; 'f'; 'g' ];
[ 'a'; 'b'; 'd'; 'e'; 'f'; 'g' ];
[ 'a'; 'c'; 'f' ];
[ 'a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g' ];
[ 'a'; 'b'; 'c'; 'd'; 'f'; 'g' ];
]
let is_number pattern result =
let num = List.map (fun x -> CharMap.find x result) pattern in
List.exists (fun n -> List.for_all (fun x -> List.mem x num) n) valid_patterns
let result map =
CharMap.bindings map
|> List.map (fun (k, v) -> (k, List.hd (CharSet.elements v)))
|> List.to_seq |> CharMap.of_seq
let check_patterns patterns map =
let r = result map in
List.for_all (fun p -> is_number p r) patterns
let solved patterns map =
if
CharMap.for_all (fun _ v -> CharSet.cardinal v = 1) map
&& check_patterns patterns map
then Some (result map)
else None
```

Here, each map needs to be pointing to a single character, *and* I check to make
sure each number is possible given the mapping I’ve found.

Next, I need some code that actually comes up with a solution:

```
let rec solver patterns map =
match
CharMap.bindings map |> List.filter (fun (_, v) -> CharSet.cardinal v <> 1)
with
| [] -> solved patterns map
| ms ->
let key, guesses =
List.fold_left
(fun (k1, g1) (k2, g2) ->
if
CharSet.cardinal g1 < CharSet.cardinal g2
&& CharSet.cardinal g1 <> 1
then (k1, g1)
else (k2, g2))
(List.hd ms) (List.tl ms)
in
List.find_map
(fun c ->
let new_map =
CharMap.mapi
(fun k v ->
if k = key then CharSet.singleton c else CharSet.remove c v)
map
in
match solver patterns new_map with None -> None | Some m -> Some m)
(CharSet.elements guesses)
```

Okay, here we go. First, I only want all the “not solved” characters. If I don’t have any “not solved” characters, I have a solution! I check if it is correct.

If I’m not done yet… I find the “most solved” character. The one with the least number of options.

Once I pick one, for each of its possible solutions, I construct a state assuming I am correct.

I take that possible solution and pass it back into my solver function. This continues until the first conditional is met and I check if I am right. If not, I construct a state with the next possible solution. Eventually, I am right.

The rest of the code is taking the solution, decoding the output, and finding the final answer:

```
let decode_code result code =
let pattern = List.map (fun x -> CharMap.find x result) code in
let numbers = List.mapi (fun i n -> (i, n)) valid_patterns in
List.find_map
(fun (i, n) ->
if
List.length pattern = List.length n
&& List.for_all (fun x -> List.mem x n) pattern
then Some i
else None)
numbers
let decode codes result =
codes |> List.map Core.String.to_list |> List.map (decode_code result)
let compute patterns codes =
let map = patterns |> group |> construct CharMap.empty in
let p = List.map Core.String.to_list patterns in
match solver p map with
| None -> [ None ]
| Some result -> decode codes result
let p2 =
List.fold_left
(fun s (patterns, codes) ->
let r = compute patterns codes in
let n =
List.map
(function
| None -> raise (BadPattern "BLAH")
| Some i -> char_of_int (i + zero))
r
|> Core.String.of_char_list
in
int_of_string n + s)
0 input
|> string_of_int
```

That’s day eight ✔️

## Day 9

Today was slightly easier, thankfully. This isn’t being written 10 minutes to midnight.

It turns out those case are lava tubes. *yay*.

The first problem is to find the lowest points of the caves, to avoid the smoke easier. I must find all the points where each adjacent point is higher.

Once parsing the output is out of the way, the solution is simple:

```
type coords = int * int
module Coords = struct
type t = coords
let compare (x1, y1) (x2, y2) =
if x1 < x2 then -1
else if x1 > x2 then 1
else if y1 < y2 then -1
else if y1 > y2 then 1
else 0
end
module TupleMap = Map.Make (Coords)
let parse =
let width = List.hd input |> List.length in
let height = List.length input in
let with_index =
List.mapi (fun i r -> (i, List.mapi (fun j c -> (j, c)) r)) input
in
( width,
height,
List.fold_left
(fun m (i, r) ->
List.fold_left (fun n (j, c) -> TupleMap.add (i, j) c n) m r)
TupleMap.empty with_index )
let low_points (width, height, map) =
TupleMap.filter
(fun (i, j) c ->
let n = if i = 0 then 9 else TupleMap.find (i - 1, j) map in
let s = if i = height - 1 then 9 else TupleMap.find (i + 1, j) map in
let w = if j = 0 then 9 else TupleMap.find (i, j - 1) map in
let e = if j = width - 1 then 9 else TupleMap.find (i, j + 1) map in
c < n && c < s && c < e && c < w)
map
let p1 =
let results = low_points parse in
TupleMap.fold (fun _ c sum -> c + 1 + sum) results 0 |> string_of_int
```

I take the integers and put them into a map where the coordinate of the point points to the height of the point. Then, I filter through all the points, checking for bounds, and ensuring all adjacent points are higher. Once the lower points are found, I calculate the “total risk value”.

⭐ one done!

### Part 2

Oh, so the low points make up basins. I think it’s pretty amazing how they
manage to create the input required for these problems. A basin is a group of
points bordered by the boundary or the highest point (a `9`

).

Good thing I have code that already finds the lowest points! I’m going to need a set to better keep track of what is in the basin, but the rest didn’t take too much to work out:

```
module TupleSet = Set.Make (Coords)
let rec find_basin width height m (i, j) acc =
if TupleMap.find (i, j) m = 9 then acc
else if TupleSet.mem (i, j) acc then acc
else
let new_acc = TupleSet.add (i, j) acc in
let n =
if i <> 0 then find_basin width height m (i - 1, j) new_acc else new_acc
in
let s =
if i + 1 < height then find_basin width height m (i + 1, j) n else n
in
let w = if j <> 0 then find_basin width height m (i, j - 1) s else s in
let e =
if j + 1 < width then find_basin width height m (i, j + 1) w else w
in
TupleSet.union n (TupleSet.union s (TupleSet.union w e))
let basins =
let w, h, m = parse in
let finder = find_basin w h m in
let low = low_points (w, h, m) in
TupleMap.mapi (fun (i, j) _ -> finder (i, j) TupleSet.empty) low
let p2 =
let results = basins in
TupleMap.fold (fun _ v m -> TupleSet.cardinal v :: m) results []
|> List.sort (fun x y -> y - x)
|> List.filteri (fun i _ -> i < 3)
|> List.fold_left (fun x y -> x * y) 1
|> string_of_int
```

For each of the lowest points, I recursively map out the area surrounding the point, adding it to the set containing all the points of the basin. If I hit a boundary or a ‘9’, I stop.

Once all the basins are found, the solution is a matter of finding the 3 biggest, and finding the product of them.

I think problems like this one are a lot of fun. It’s a great use of recursion, and a set makes it easy to keep track of where I’ve visited.

Solvers like in day 8 are fun, too, but it makes such a mess of code. I am sure it could be cleaner somehow, but 10 minutes to midnight is not the time for cleanup 😅

#### Want to discuss this post?

Reach out via email to ~afontaine/blog-discuss@lists.sr.ht, and be sure to follow the mailing list etiquette.

Other posts