Advent of Code 2021: Day 3Andrew Fontaine <email@example.com>
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.
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, 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
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
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
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 ~firstname.lastname@example.org, and be sure to follow the mailing list etiquette.Other posts