Advent of Code 2020 - Day 1

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.

read_input(File) ->
    {'ok', Lines} = file:read_file(File),
    [binary_to_integer(Line, 10) || Line <- binary:split(Lines, <<"\n">>, ['global']), Line =/= <<>>].

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).

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.

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).

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₂₀₂₀/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:

[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'.

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

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.

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.

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.