 Advent of Code 2020 - Day 1

For part one, I did sth similar, but forgot about a MapSet so just used a map %{100 => 100, 999 => 999, ...}
but the rest was pretty much the same although I’m a little rusty in Elixir so I used Enum.reduce_while instead of Enum.find:

def find_2020(expenses) when is_map(expenses) do
expenses
|> Enum.reduce_while(0, fn {expense, expense}, _acc ->
case Map.fetch!(expenses, 2020 - expense) do
{:ok, value} ->
{:halt, value * expense}

_ ->
{:cont, 0}
end
end)
end

Nice idea for the second part, I basically just fell back to list comprehensions for the 2nd part.

That’s a super cool idea, but I think there is a bug in this code.
The nested flat_maps do not kind of advance the stream by 1 if you know what I mean so they also produce tuples like:

{1721, 1721}

So If you add to the example 1010 on the first line, the result will be 1020100 which is wrong.

|> Stream.filter(fn {x, y} ->
x + y == 2020 and x != y
end)

This passes the example and the real input, but I think that it’s still not 100% correct because there could be duplicate expenses I think.

1010
1010

Then 1020100 would be the correct answer I think.

Here’s my take:

def part_one(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&String.to_integer/1)
|> calc_depth(2)
end

def part_two(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&String.to_integer/1)
|> calc_depth(3)
end

def calc_depth(entries, max_depth),
do: calc_depth_rec(entries, max_depth, 0, [])

defp calc_depth_rec(_, max_depth, depth, terms)
when depth >= max_depth do
sum = Enum.sum(terms)

if sum == 2020 do
Enum.reduce(terms, fn x, acc -> x * acc end)
else
:not_found
end
end

defp calc_depth_rec([], _max_depth, _depth, _terms) do
:not_found
end

defp calc_depth_rec([entry | other_entries], max_depth, depth, terms) do
case calc_depth_rec(other_entries, max_depth, depth + 1, [entry | terms]) do
:not_found ->
calc_depth_rec(other_entries, max_depth, depth, terms)

n ->
n
end
end
end
1 Like

My solution which uses the fact that searching for a + b + c == 2020 is the same as searching for b + c == 2020 - a and the fact that a + b == b + a and a * b == b * a, which mean that [a, …, b] will return the same result as [b, …, a] (in other words, if we didn’t found the solution for earlier elements in list, we never need to look at them anymore):

defmodule Solution do
path
|> File.stream!()
|> Stream.map(&String.to_integer(String.trim(&1)))
|> Enum.to_list()
end

def run([], _, _), do: nil
def run(_, _, sum) when sum < 0, do: nil
def run([a | _], 1, a), do: [a]

def run([a | rest], n, sum) do
case run(rest, n - 1, sum - a) do
nil -> run(rest, n, sum)
nums when is_list(nums) -> [a | nums]
end
end
end

list
|> Solution.run(2, 2020)
|> Enum.reduce(&*/2)

list
|> Solution.run(3, 2020)
|> Enum.reduce(&*/2)

Oh, this is also generic solution for any amount of elements that need to sum to given value.

I have benched against @LostKobrakai code and this is result:

Operating System: macOS
CPU Information: Intel(R) Core(TM) i5-1038NG7 CPU @ 2.00GHz
Number of Available Cores: 8
Available memory: 32 GB
Elixir 1.11.2
Erlang 22.3

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 21 s

Benchmarking first solution...
Benchmarking mine...
Benchmarking optimized...

Name                     ips        average  deviation         median         99th %
mine                  3.92 K      254.84 μs     ±7.99%      251.98 μs      348.98 μs
optimized             3.68 K      271.99 μs    ±10.21%      266.98 μs      397.98 μs
first solution      0.0200 K    49956.44 μs    ±12.46%    48000.98 μs    70571.10 μs

Comparison:
mine                  3.92 K
optimized             3.68 K - 1.07x slower +17.15 μs
first solution      0.0200 K - 196.03x slower +49701.60 μs
3 Likes

That optimized list comprehension is fast but (assuming I’ve benchmarked correctly) I’m getting faster results with Enum.member? (aka in). Here’s my benchmarks using your input file:

Operating System: macOS
CPU Information: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
Number of Available Cores: 16
Available memory: 16 GB
Elixir 1.11.1
Erlang 23.1.1

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s

Benchmarking day1_enum_member...
Benchmarking day1_list_comp...

Name                       ips        average  deviation         median         99th %
day1_enum_member       25.30 K       39.53 μs    ±23.30%          36 μs          86 μs
day1_list_comp          6.56 K      152.45 μs    ±18.06%         139 μs         277 μs

Comparison:
day1_enum_member       25.30 K
day1_list_comp          6.56 K - 3.86x slower +112.92 μs

And here’s the solution I’m using:

def run_enum_member([a | rest]), do: run_enum_member([a | rest], a, rest)
def run_enum_member([_ | []], _, remaining), do: run_enum_member(remaining)

def run_enum_member([b | rest], a, remaining) do
target = 2020 - a - b

cond do
target <= 0 -> run_enum_member(rest, a, remaining)
target in rest -> {:ok, a * b * target}
true -> run_enum_member(rest, a, remaining)
end
end

Of course a lot of performance depends on where the three numbers show up in the list, no? Great fun seeing everyone’s code.

1 Like

Feels a little hacky, didn’t know how to break out early doing it this way.

defmodule Solutions.Day1 do
alias Solutions.Helpers

def part_1(expenses) do
expenses = Enum.map(expenses, &String.to_integer/1)

sums_to_2020? = fn i, j -> i + j == 2020 end

answers = for i <- expenses, j <- expenses, sums_to_2020?.(i, j), do: {i, j}
i * j
end

def part_2(expenses) do
expenses = Enum.map(expenses, &String.to_integer/1)

sums_to_2020? = fn i, j, k -> i + j + k == 2020 end

for i <- expenses, j <- expenses, k <- expenses, sums_to_2020?.(i, j, k), do: {i, j, k}

i * j * k
end

part_1 = part_1(expenses)
part_2 = part_2(expenses)

IO.inspect(part_1)
IO.inspect(part_2)
end
end
1 Like

Part 1:

Big-O

Sort -> O(n log n)
Find -> O(n)

@lucky_num 2020

def part1(arr), do:
arr |> Enum.sort() |> find()

defp find([first|tail]) do
{lst,[last]} = Enum.split(tail, length(tail) - 1)
find(first, last, lst, tail)
end

defp find(first, last, _lst, _tail) when first + last == @lucky_num, do: first * last
defp find(first, last, lst, _tail) when first + last > @lucky_num, do: find([first | lst])
defp find(_first, _last, _lst, tail), do: find(tail)

end
1 Like

Part2

2 b improved: have a feeling that with one more accumulator can speed up the solution

@lucky_num 2020

def part2(arr), do:
arr |> Enum.sort() |> find()

defp find([first,second|tail]) do
{lst,[last]} = Enum.split(tail, length(tail) - 1)
find(first, second, last, lst, tail)
end

defp find(first, second, last, _lst, _tail) when first + second + last == @lucky_num, do: first * second * last
defp find(first, second, last, lst, _tail) when first + second + last > @lucky_num, do: find([first, second] ++ lst)
defp find(first, second, _last, _lst, tail) do
case find([second | tail]) do
{:error, _reason} -> find([first | tail])
v -> v
end
end

end

Still just getting my feet wet with Elixir. Certainly not optimized but for the presented data set it’s efficient enough on my machine.

def parse_input() do

expenses
|> String.split("\n", trim: true)
|> Enum.map(&String.to_integer(&1))
end

def find_two([h | t], sum) do
case Enum.find(t, fn x -> sum - h == x end) do
nil ->
find_two(t, sum)

y ->
h * y
end
end

def find_two([], _sum) do
nil
end

def find_two(sum) do
parse_input()
|> find_two(sum)
end

def find_three([], _sum) do
nil
end

def find_three([h | t], sum) do
case find_two(t, sum - h) do
nil -> find_three(t, sum)
y -> h * y
end
end

def find_three(sum) do
parse_input()
|> find_three(sum)
end
end

IO.puts(SumMultiply.find_two(2020))
IO.puts(SumMultiply.find_three(2020))

1 Like

Here’s my version with early break out of comprehension.

defmodule Event1 do
def run do
IO.puts("Test part1: #{part1("input/event1/test.txt")}")
IO.puts("Puzzle part1: #{part1("input/event1/puzzle.txt")}")
IO.puts("Test part2: #{part2("input/event1/test.txt")}")
IO.puts("Puzzle part2: #{part2("input/event1/puzzle.txt")}")
end

def part1(path), do: input_stream(path) |> Enum.into([]) |> find_result()
def part2(path), do: input_stream(path) |> Enum.into([]) |> find_result2()

def input_stream(path), do: path |> File.stream!() |> Stream.map(&parse_input/1)
def parse_input(input), do: input |> Integer.parse() |> elem(0)

def find_result(inputs) do
try do
for(i <- inputs, j <- inputs, i + j == 2020, do: throw(i * j))
catch
x -> x
end
end

def find_result2(inputs) do
try do
for(i <- inputs, j <- inputs, k <- inputs, i + j + k == 2020, do: throw(i * j * k))
catch
x -> x
end
end
end
1 Like

Revisit Day 1

I’ve played a little bit with the Stream module and managed to rewrite my previous solution in a streamable fashion.

The idea came from Ruby’s Array#combination which returns an Enumerator instance if no block is given. If Ruby can do that, why can’t Elixir?

WARNING: EXTREMELY SLOW!!!

Here’s my code:

#!/usr/bin/env elixir

defmodule Combination do

@doc """
Creates a stream that iterates through
all the k-element combinations of the given enumerable.
"""
@spec c(Enumerable.t(), pos_integer) :: Enumerable.t()
def c(enum, 1) do
Stream.map(enum, &[&1])
end

def c(enum, k) when is_integer(k) and k > 1 do
Stream.transform(enum, Stream.drop(enum, 1), fn item, acc ->
next = acc
|> c(k - 1)
|> Stream.map(&[item|&1])
new_acc = Stream.drop(acc, 1)
{next, new_acc}
end)
end
end

nums = "./day1.txt"
|> File.stream!([], :line)
|> Stream.map(&String.trim/1)
|> Stream.map(&String.to_integer/1)

solve = fn(k)->
nums
|> Combination.c(k)
|> Enum.find(&(Enum.sum(&1) == 2020))
|> Enum.reduce(&*/2)
|> IO.puts()
end

solve.(2)
solve.(3)

I feel the time complexity of the stream approach is quite hard for me to assess, while the time complexity of the callback approach is clearly O(combination(n, k)).

Brand new to Elixir, this is my solution to part 1. Happy to hear anything to make it more Elixir-y or performant, or even pointers on to what to read about for concepts to make this better.

defp day1_process(filename) do
|> String.split("\n", trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.filter(&(&1 < 2020))
end

@doc """
Advent of Code day 1 solution

## Examples
"""
def day1 do
input = day1_process("lib/day_one_input.txt")
Enum.map(input, &(2020 - &1))
|> Enum.filter(fn x -> Enum.member?(input, x) end)
|> Enum.reduce(&(&1 * &2))

end
1 Like

You said you are brand new to Elixir, but your code doesn’t look like so. It looks clean and beautiful Pre-eliminating hopeless members is also interesting. It has the potential of optimizing the performance a little.

Your approach is a little bit not so straightforward to me, but I think it’s okay since the time complexity is still O(n * n).

1 Like

Thank you so much! I’m really enjoying Elixir, it’s a really fun language to use so far. I use Pandas quite a bit in my day job, and I love its functional capabilities, so maybe that’s helping me ease into Elixir better 1 Like

The next step maybe to try parallelizing parts of your code? Just for fun The Enum.map part can be easily parallelized. So can the Enum.filter part. The Enum.reduce part is a bit tricky, but you can write your own reduce function that handles only associative operations (scalar multiplication is associative) and parallelize it.

1 Like

Not as elegant as adamu’s solution with comprehensions, but it is about 33% faster, because it avoids checking duplicates. Constructing the map of %{index => number} uses up a lot of memory though: 20 times more according to my benchmark!

Just thought I’d share. Learned a lot from the solutions posted here, thanks!

@spec find_product([pos_integer()]) :: {:ok, pos_integer()} | {:error, String.t()}
def find_product(numbers) do
{_, number_map} = numbers
|> Enum.reduce({0, %{}}, fn(num, {index, acc}) ->
{index + 1, Map.put(acc, index, num)}
end) # %{ 0 => num0, 1 => num1 }

products = for index <- (0..length(numbers) - 3),
index2 <- (index + 1..length(numbers) - 2),
index3 <- (index2 + 1..length(numbers) - 1),
sum_is_2020?(number_map, {index, index2, index3}) do
%{^index => num1, ^index2 => num2, ^index3 => num3} = number_map
num1 * num2 * num3
end

case products do
[product | _tail] -> {:ok, product}
[] -> {:error, "No three numbers were found that add up to 2020"}
end
end

@spec sum_is_2020?(%{pos_integer() => pos_integer()}, {pos_integer(), pos_integer(), pos_integer()}) :: boolean()
defp sum_is_2020?(number_map, {a, b, c}) do
%{^a => num1, ^b => num2, ^c => num3} = number_map
num1 + num2 + num3 == 2020
end

I am just getting started with elixir.
Here is my code for Day 1:

defmodule Day1 do
defp updateExpenseMap([], map) do
map
end

defp updateExpenseMap([head | remainingList], map) do
updateExpenseMap(remainingList, Map.put(map, head, freq + 1))
end

defp takeInput() do
|> String.split("\n", trim: true)
|> Enum.map(fn str ->
{n, _} = Integer.parse(str)
n
end)
end

defp multiplication([], _, _) do
:error
end

defp multiplication([head | remainingList], map, sum) do
if Map.has_key?(map, sum - head) do
else
multiplication(remainingList, map, sum)
end
end

defp multiplicationV2([], _, _) do
:error
end

defp multiplicationV2([head | remainingList], map, sum) do
map = Map.put(map, head, freq - 1)

:error ->
multiplicationV2(remainingList, map, sum)

{:ok, {n1, n2}} ->
end
end

def main(part) do
inputList = takeInput()
map = updateExpenseMap(inputList, %{})
# IO.puts("#{map}")
case part do
1 ->
{n1, n2} = multiplication(inputList, map, 2020)
n1 * n2

2 ->
{n1, n2, n3} = multiplicationV2(inputList, map, 2020)
n1 * n2 * n3
end
end
end

As I have already announced in another thread, I take my time this year and finished day 1 yesterday during the hour when all my kids and my sick wife took a nap, and I actually had some time with the computer…

On my laptop, part 2 requires a full milliseconds since I did shortcutting the result on the first hit. It was ~1.5 before that.

Intuitively, I’d still say the algorithm is O(n³), where n is the length of the input… Though if its less than a second, I usually do not care…

1 Like

Looks like I’m a bit late to the party here Some Erlang allowed? First idea was to take each element and do the calculation to the rest of the list that comes after the element.
Quite easy for part 1:

-module(day1_1).
-export([run/0]).

run()->

StringContent = unicode:characters_to_list(Binary),
[ element(1, string:to_integer(Substr)) || Substr <- string:tokens(StringContent, "\n")].

process_list([H | T])->
case process_sublist(H, T) of
notfound -> process_list(T);
{found, X, Y, Result} -> {X, Y, Result}
end;
process_list([])->
notfound.

process_sublist(Elem, [H | T]) ->
case is_solution(Elem, H) of
true -> {found, Elem, H, H*Elem};
false -> process_sublist(Elem, T)
end;
process_sublist(_, []) ->
notfound.

is_solution(X, Y) ->
X + Y =:= 2020.

but getting more complicated for part 2:

-module(day1_2).
-export([run/0]).

run()->

StringContent = unicode:characters_to_list(Binary),
[ element(1, string:to_integer(Substr)) || Substr <- string:tokens(StringContent, "\n")].

process_list([H | T])->
case process_sublist(H, T) of
notfound -> process_list(T);
X -> X
end;
process_list([])->
notfound.

process_sublist(Elem, [H1 | T]) ->
case process_subsublist(Elem, H1, T) of
notfound -> process_sublist(Elem, T);
X -> X
end;
process_sublist(_, []) ->
notfound.

process_subsublist(Elem1, Elem2, [H | T])->
case is_solution(Elem1, Elem2, H) of
true -> {found, Elem1, Elem2, H, H*Elem1*Elem2};
false -> process_subsublist(Elem1, Elem2, T)
end;
process_subsublist(_,_, []) ->
notfound.

is_solution(X, Y, Z) ->
X + Y + Z =:= 2020.

After finishing that I thought it’s just too much code, and did the brute force one-liner process_list(L)->
[{X, Y, X*Y} || X <- L, Y <- L, X + Y =:= 2020 ].