#+BEGIN_COMMENT
.. title: Advent of Code 2020 - Day 1
.. slug: advent-of-code-2020-day-1
.. date: 2020-12-06 06:41:03 UTC
.. tags: erlang aoc2020 adventofcode
.. category:
.. link:
.. description: Advent of code 2020 day 1 code and discussion
.. type: text
#+END_COMMENT
* AoC 2020 Day 1
[[https://adventofcode.com/2020/day/1][Day 1]] of the Advent of Code brings us a search problem - find two entries whose sum is 2020 and answer with the product.
** Reading the input file
I like to get the data in from the file and into a workable internal format. For this problem its pretty simple - a list of integers will suffice.
#+begin_src erlang :exports code
read_input(File) ->
{'ok', Lines} = file:read_file(File),
[binary_to_integer(Line, 10) || Line <- binary:split(Lines, <<"\n">>, ['global']), Line =/= <<>>].
#+end_src
Were the test file larger, =file:read_line/1= could be used instead; as-is, let's read the whole file into a binary.
Next, I used =binary:split/3= to break the binary into a list of binaries broken on the end line. Sometimes files have an extra end line so filter any =Line= that is an empty binary.
Since we know each =Line= should contain an integer, use =binary_to_integer(Line, 10)= to explicitly convert from a base-10 encoded integer (vs =<<"1F">>= which would necessitate using 16 instead).
** Processing the list
Now that we have a list of integers, we need to find the two entries whose sum is 2020. Naively, we can take the head of the list and iterate over the tail of the list looking for the winning sum.
#+begin_src erlang
main(_) ->
[H|Input] = read_input("p1.txt"),
{X, Y} = find_2020(Input, H),
io:format("answer: ~p~n", [X*Y]).
find_2020(Input, H) ->
case foldl(Input, H) of
{X, Y} -> {X, Y};
'undefined' -> find_2020(tl(Input), hd(Input))
end.
foldl([], _) -> 'undefined';
foldl([Y|_], X) when X+Y =:= 2020 -> {X, Y};
foldl([_|T], X) -> foldl(T, X).
#+end_src
I decided to manually roll a fold that terminates early when the match is found.
First we pop the head of the list (=[H|Input] = read_input(...)=). Next we fold over the tail of the list (=Input=) looking for an item in the list that sums to 2020 with our =H=. If we exhaust the list (first clause of =foldl/2=) we return the atom =undefined= and recursively call find_2020/2 with the head and tail of the list.
To get an idea of what this looks like in practice, suppose a list of =[1, 2, 3]=; =find_2020/2= would evaluate like:
#+begin_example
[1 | [2, 3]] = read_input(...),
find_2020([2, 3], 1).
find_2020([2, 3], 1) ->
foldl([2, 3], 1).
foldl([2 | [3]], 1) -> foldl([3], 1).
foldl([3 | []], 1) -> foldl([], 1).
foldl([], 1) -> 'undefined'.
find_2020([3], 2).
foldl([3 | []], 2) -> foldl([], 2).
foldl([], 2) -> 'undefined'.
find_2020([], 3).
foldl([], 3) -> 'undefined'.
#+end_example
This effectively searches every combination until the solution is found. Solutions of =O(n^2)= complexity are typically not what one might aspire to use when solving problems, but in this case, with a 200-line input file, we're only looking at 40,000 comparisons (at most).
Run time of the script is =real 0m0.177s= =user 0m0.198s= =sys 0m0.043s=.
** Part 2
Part 2 extends part 1 to find 3 entries that sum to 2020 instead.
Reading the input doesn't change in this one so let's look at the search:
#+begin_src erlang :exports code
main(_) ->
Entries = read_input("p1.txt"),
{X, Y, Z} = find_triple(Entries),
io:format("answer: ~p: ~p~n", [{X, Y, Z}, X * Y * Z]).
find_triple([X | Entries]) ->
case find_double(2020-X, Entries) of
'undefined' -> find_triple(Entries);
{Y, Z} -> {X, Y, Z}
end.
find_double(_Total, []) -> 'undefined';
find_double(Total, _) when Total < 0 -> 'undefined';
find_double(Total, [Y | Entries]) when Y >= Total ->
find_double(Total, Entries);
find_double(Total, [Y | Entries]) ->
case [Z || Z <- Entries, Y+Z =:= Total] of
[] -> find_double(Total, Entries);
[Z] -> {Y, Z}
end.
#+end_src
Similar in concept to part 1, we decompose the problem. Given the head of the list, X, search the tail of the list for two entries that sum to (2020 - X). If none is found, recurse into =find_triple/1= with the tail of the list.
Within =find_double/2= we take the head of the list, Y, and iterate through the tail of the list looking for a Z that will satisfy =Y + Z = 2020 - X=. If none is found, recurse using the tail of the list.
We're pushing into =O(n^3)= territory which still only puts us around 8,000,000 comparisons which is pretty trivial for CPUs. Indeed, run time is indistinguishable from part 1: =real 0m0.175s= =user 0m0.179s= =sys 0m0.067s=.
** Wrap up
Day 1 whet the whistle. Took slightly different approaches to iteration and recursion in each part for fun. Dataset is small enough to not be overly concerned with efficiency of approach, instead focusing on (hopefully) solving the problem in an easy-to-read way.