Advent of Code 2020 - Day 1

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.