# Advent of Code 2021: Day 3

Andrew Fontaine <andrew@afontaine.ca>

Okay, the submarine is moving, we can see where we’re going. Now to make sure systems are ✔.

Today’s struggle in learning was motivation. Fridays are tricky that way, sometimes it’s a mad rush to get everything done in time for Saturday, others it’s just a slog to the weekend. Today was the latter.

I found the first problem’s trickiest bit to be how to parse the list properly. Only after eating dinner and not being distracted by hunger did the solution become obvious.

## Parsing blues

First, I make a bit type:

``````(* bits are one or zero *)
type bit = One | Zero

(* parse a character into a bit *)
let bit_of_char c =
match c with '1' -> One | '0' -> Zero | c -> raise (BadBit c)

(* turn a bit into a string for combining later *)
let string_of_bit b =
match b with
| One -> "1"
| Zero -> "0"

(* take a list of bits and turn that into a number *)
let int_of_bit r =
List.fold_left (fun b x -> b ^ (string_of_bit x)) "0b" r
|> int_of_string
``````

Next, I map the list of codes from the rows to the columns:

``````let input =  Core.In_channel.read_lines "./priv/2021/D03"
|> List.map (fun row -> List.map bit_of_char (Core.String.to_list row))

let p1_input =
match input with
| [] -> raise (BadBit 'l')
| hd :: t -> List.fold_left (fun result row ->
List.map2 (fun r bit ->  bit :: r) result row) (List.map (fun x -> [x]) hd) t
``````

Ocaml has the lovely `map2` function to map 2 lists together. I inject the first row, split into lists of single bits, to start the rows off. Then, I fold over the rest of the rows, adding each character to the list in the correct column. The end result:

``````[1, 2, 3]         [1, 4, 7]
[4, 5, 6] becomes [2, 5, 8]
[7, 8, 9]         [3, 6, 9]``````

The rest of the problem is simple. Mark the most common bit in each column, and multiply the resulting final numbers together:

``````let counts row =
List.fold_left
(fun (one, zero) b ->
match b with One -> (one + 1, zero) | Zero -> (one, zero + 1))
(0, 0) row

let greatest_bit (one, zero) = if one >= zero then One else Zero

let p1_sol input =
let g, e =
List.fold_left
(fun (g, e) row ->
let c = counts row in
match greatest_bit c with
| One -> (g ^ "1", e ^ "0")
| Zero -> (g ^ "0", e ^ "1"))
("0b", "0b") input
in
(int_of_string g, int_of_string e)

let p1 =
let g, e = p1_sol p1_input in
let sol = g * e in
Int.to_string sol``````

⭐ one done!

## Problem 2

Problem 2, while similar, certainly starts to raise the difficultly. I fear for the weekend challenges now!

In essence, I am seeking for a specific row. That row needs to match a set of rules, where, for one, we chase the most common bit, and the other, the least common. It took me a few re-reads before I understood the problem at hand. This one is fun, in that there’s a good amount of re-usable code between both seeking:

``````let consider f input =
let firsts = List.map (fun r -> match r with
| ([], _) -> raise (BadBit 'l')
| (h :: _, _) -> h) input in
let bit = greatest_bit (counts firsts) in
List.filter (fun r -> match r with
| ([], _) -> raise (BadBit 'l')
| (h :: _, _) -> f bit h) input
|> List.map (fun (r, i) -> match r with
| [] -> raise (BadBit 'c')
| _ :: t -> (t, i))

let oxygen bit h = bit = h

let co2 bit h = bit <> h

let rec find crit input =
match input with
| [] -> -1
| [(_, x)] -> x
| list -> let results = consider crit list in find crit results

let compute input crit =
let i = List.mapi (fun x r -> (r, x)) input in
find crit i
|> List.nth input
|> int_of_bit

let p2_sol input =
let co2_result = compute input co2 in
let oxygen_result = compute input oxygen in
string_of_int (co2_result * oxygen_result)

let p2 = p2_sol input``````

`find` is the main entry point into the interesting stuff. It recursively seeks the index of the row that matches the specific criteria. `consider` takes the criteria, puts together the first column of numbers, and determines which rows make the cut. It also lops off the considered column, so the recursive `find` call eventually goes through all the columns. The criteria are encoded as `oxygen` (the most common bit) and `co2` (the least common bit). Once the right index is found, its full row is retrieved and parsed into a number to find the final solution.

This one I found the parsing to be the most painful part. Once I was over that hurdle, it was smooth sailing. Eventually I hit a few bumps. There’s an extra rule in part 2 where `One` wins tie breakers for the most common bit that I missed, and it took some puzzling to realize I wasn’t lopping off the column in the beginning. Once those two issues were caught, the ⭐ was mine.

Now if you’ll excuse me, Day 4 just unlocked, and I better see how much of a crunch my weekend will be.

#### 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