Advent of Code 2021: Day 3

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.