AoC 2020 Day 1

This is part of a series we did on the Advent of Code 2020 problems. You can see a list of all the problems we wrote about here.
If you are a fan of AoC, and had fun working on these problems, it is likely that you would be a good fit with our team. Our engineering team had a blast with it, as we like to be challenged with hard problems. If you like what you see, we are constantly looking for great talent, please consider joining us!

This story is part of our series on AoC 2020

This exercise, being the first in the series, was designed to warm everyone up. I’m writing about it because it gives a nice introduction to the format, and there is a non-obvious optimisation to speed up the solution.

The problem, like all AoC problems, is divided in two parts. You will only get to see the second problem after solving the first one correctly. I’ll be using OCaml for this particular problem, because it is fun to use new languages, and I’ve been a fan of functional programming for a very long while. After getting set up with the basic toolchain I was ready to go and experiment with finding a solution.

Part 1

There is a nice description on the AoC site which involves a story Elves in accounting. Ultimately, the problem boils down to:

• We have a text file with one number per line
• We are asked to find two numbers that sum to 2020 and return their product

I saved the input into a input.txt file so I wouldn’t have to write boilerplate code to read straight from the URL. I think this is an acceptable shortcut given that the fun lays in finding the algorithm.

Reading the file is then pretty trivial, and we store it in a entries variable of time Int list.

open Core;;
let filename = "input.txt" in
let flines = In_channel.read_lines filename in
let entries = List.map flines ~f:Int.of_string in
() (* print the list however you want)

Once we can confirm that we can read the file correctly, the naive strategy in an imperative paradigm would be to have two nested loops and check the sum of the two numbers. We would want to terminate the loops early when a solution is found. We can translate this to a functional solution by making use of tail recursion, list unpacking, and mapping the result to an Int Option so that we can represent whenever a solution is not found. The full solution looks like this.

open Core;;
let filename = "input.txt" in
let flines = In_channel.read_lines filename in
let entries = List.map flines ~f:Int.of_string in
let target = 2020 in
let rec check target a b =
  match a with
  | [] -> None
  | hd_a :: tl_a ->
      match b with
      | [] -> check tl_a entries
      | hd_b :: tl_b ->
          match hd_a + hd_b with
          | target -> Option.some (hd_a * hd_b)
          | _ -> check target a tl_b
in
let r = match (check target entries entries) with
| Some x -> Int.to_string x
| None -> "not found"
in
print_string r

This is also O(n²), and OCaml has very good tail call optimisation, so we do not need to worry about blowing the stack. However, there is a trick that may not be obvious to make the solution O(n). We can search a hash for membership of (target — a) , which is a O(1) operation if we use the right type of Hash. In OCaml this is called a Hash_set. In the imperative world, this is equivalent to looping only once, which confirms that our solution is now O(n). Notice how we have to do an imperative operation to pre-populate the Hash_set.

open Core;;
let filename = "input.txt" in
let flines = In_channel.read_lines filename in
let entries = List.map flines ~f:Int.of_string in
let seen =
  Hash_set.create ~size:(List.length entries) (module Int)
in
let () =
 List.iter entries ~f:(fun elem -> Hash_set.add seen elem)
in
let rec check a =                                                                                                                                      match a with
  | [] -> None
  | hd_a :: tl_a ->
    if (Hash_set.mem seen (2020 - hd_a)) then
      Some (hd_a * (2020 - hd_a))
    else check tl_a
in
let r = match (check entries) with
  | Some x -> Int.to_string x
  | None -> "not found"                                                                                                                                in
print_string r

Part 2

Once we complete part 1, we are presented with a slightly more complex version of the same problem. Now the number of entries we need to check is three. The solution doesn’t change much, even from the optimised version above. However, we do have to iterate the list twice, which means adding a helper function to do the “outer loop”.

open Core;;
let filename = "input.txt" in
let flines = In_channel.read_lines filename in
let entries = List.map flines ~f:Int.of_string in
let seen = 
  Hash_set.create ~size:(List.length entries) (module Int)
in
let () =
  List.iter entries ~f:(fun elem -> Hash_set.add seen elem)
in
let rec check a b =
  match a with
  | [] -> None
  | hd_a :: tl_a ->
      if (Hash_set.mem seen (2020 - hd_a - b)) then
        Some (hd_a * (2020 - hd_a - b) * b)
else
  check tl_a b
in
let rec check2 a =
  match a with
    | [] -> None
    | hd_a :: tl_a ->
      match check entries hd_a with
        | Some x -> Some x
        | None -> check2 tl_a
      in
let r = match (check2 entries) with
  | Some x -> Int.to_string x
  | None -> "not found"
in
print_string r

I hope you enjoyed reading about this problem. I had fun working on it, and I would encourage you to take a look at the other entries in this series. If you are passionate about software engineering and solving difficult problems, we are constantly hiring for talented engineers.