# Advent of Code 2020 - Day 1

Finished Day 1 with Elixir

Here’s my code:

#!/usr/bin/env elixir

defmodule Combination do

@doc "Yields each combination of 2"
def c2(list, _fun) when length(list) < 2, do: :ok

def c2([a|tail], fun) do
Enum.each(tail, fn(b)-> fun.(a, b) end)
c2(tail, fun)
end

@doc "Yields each combination of 3"
def c3(list, _fun) when length(list) < 3, do: :ok

def c3([a|tail], fun) do
c2(tail, fn(b, c)-> fun.(a, b, c) end)
c3(tail, fun)
end
end

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

Combination.c2(nums, fn(a, b)->
if a + b == 2020 do
IO.inspect(a * b, label: "Part 1")
end
end)

Combination.c3(nums, fn(a, b, c)->
if a + b + c == 2020 do
IO.inspect(a * b * c, label: "Part 2")
end
end)
1 Like

Refactored a bit of my code:

#!/usr/bin/env elixir

defmodule Combination do

@type item :: any()

@doc "Yields each combination of n of the given list"
@spec c([item()], pos_integer(), ([item()] -> any())) :: :ok
def c([], _n, _f), do: :ok

def c([a|tail], 1, f) do
f.([a])
c(tail, 1, f)
end

def c([a|tail], n, f) do
c(tail, n - 1, fn(combi)-> f.([a|combi]) end)
c(tail, n, f)
end
end

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

Combination.c(nums, 2, fn([a, b])->
if a + b == 2020 do
IO.inspect(a * b, label: "Part 1")
end
end)

Combination.c(nums, 3, fn([a, b, c])->
if a + b + c == 2020 do
IO.inspect(a * b * c, label: "Part 2")
end
end)

Here’s mine for Day 1. It’s my second implementation, after I realised during part 2 that comprehensions made the whole thing much simpler.

list =
|> String.trim()
|> String.split("\n")
|> Enum.map(&String.to_integer/1)

[{a, b} | _] = for i <- list, j <- list, i + j == 2020, do: {i, j}
IO.puts("Part1: #{a} x #{b} = #{a * b}")

[{a, b, c} | _] = for i <- list, j <- list, k <- list, i + j + k == 2020, do: {i, j, k}
IO.puts("Part2: #{a} x #{b} x #{c} = #{a * b * c}")

I’m putting my solutions on Github.

8 Likes

Part 1 can be optimized by spliting the list in half between greater 1010 and smaller and only searching for a pairs of one number in each. There cannot be two numbers smaller or two numbers greater than 1010 to add up to 2020.

3 Likes

I did the exact same thing

1 Like

So did I!

My first version was more refined : it was preventing the same combinations to be generated and stopped the function at the first match.

But same performance for both solutions

I found improved performance by preventing iterating the list for cases, which are already beyond the allowed sum (unoptimized is 23x slower): https://github.com/LostKobrakai/aoc2020/blob/master/lib/aoc2020/day1.ex#L59-L73

My solution:

def part1(input) do
{a, b} =
input
|> String.trim()
|> String.split("\n")
|> Enum.map(&String.to_integer/1)
|> find_two_entries_that_sum_to_2020()

a * b
end

def part2(input) do
{a, b, c} =
input
|> String.trim()
|> String.split("\n")
|> Enum.map(&String.to_integer/1)
|> find_three_entries_that_sum_to_2020()

a * b * c
end

def find_two_entries_that_sum_to_2020(entries) do
Enum.reduce_while(entries, nil, fn entry, _acc ->
n_to_find = 2020 - entry

case Enum.find(entries, fn x -> x == n_to_find end) do
nil -> {:cont, nil}
x -> {:halt, {entry, x}}
end
end)
end

def find_three_entries_that_sum_to_2020(entries) do
try do
for a <- entries,
b <- entries,
c <- entries,
a + b + c == 2020,
# exit as soon as we find the solution
do: throw({:break, {a, b, c}})
catch
{:break, result} -> result
end
end
end

After finishing part 1 I realized that my approach would not work with part 2, so they’re quite different
I tried to make both parts efficient, so they stop calculation as soon as they find a correct result.

3 Likes

You probably shouldn’t be including the file reading/parsing in the calculations - I bet that’s throwing everything off.

Is there no other way to short circuit comprehensions than try and throw ?

1 Like

Seems like it, but that made it even more different

Comparison:
optimized            16.87 K
first solution       0.163 K - 103.53x slower +6.08 ms
Details

Benchee.run(%{
"first solution" => fn ->
try do
for x <- list, y <- list, z <- list, x + y + z == 2020 do
throw(x * y * z)
end

:error
catch
num -> {:ok, num}
end
end,
"optimized" => fn ->
try do
for x <- list,
rest = 2020 - x,
y <- list,
y < rest,
rest = 2020 - x - y,
z <- list,
z <= rest,
x + y + z == 2020,
do: throw(x * y * z)

:error
catch
num -> {:ok, num}
end
end
})

Operating System: macOS
CPU Information: AMD Ryzen 5 3600X 6-Core Processor
Number of Available Cores: 12
Available memory: 16 GB
Elixir 1.11.1
Erlang 23.0

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 first solution...
Benchmarking optimized...

Name                     ips        average  deviation         median         99th %
optimized            16.87 K      0.0593 ms     ±6.07%      0.0590 ms      0.0730 ms
first solution       0.163 K        6.14 ms     ±2.99%        6.10 ms        6.91 ms

Comparison:
optimized            16.87 K
first solution       0.163 K - 103.53x slower +6.08 ms

Ugly, but it worked. I didn’t consider @mexicat’s throw/catch idea – that makes it a lot cleaner.

defmodule Day01 do
File.stream!("1.input.txt")
|> Enum.map(fn numstr -> numstr |> String.trim() |> String.to_integer() end)
end

find2020_2(numbers, tl(numbers))
end

find2020_3(numbers, tl(numbers), tl(tl(numbers)))
end

defp find2020_2(numbers, []) when tl(numbers) == [], do: :barf

defp find2020_2(numbers, []), do: find2020_2(tl(numbers), tl(tl(numbers)))

defp find2020_2([n1 | _nums1] = numbers, [n2 | nums2]) do
if n1 + n2 == 2020, do: n1 * n2, else: find2020_2(numbers, nums2)
end

defp find2020_3(numbers, [], []) when length(numbers) < 3, do: :barf

defp find2020_3(numbers, [], []),
do: find2020_3(tl(numbers), tl(tl(numbers)), tl(tl(tl(numbers))))

defp find2020_3(numbers1, numbers2, []) when tl(numbers2) == [], do: find2020_3(numbers1, [], [])

defp find2020_3(numbers1, numbers2, []), do: find2020_3(numbers1, tl(numbers2), tl(tl(numbers2)))

defp find2020_3([n1 | _nums1] = numbers1, [n2 | _num2] = numbers2, [n3 | nums3]) do
if n1 + n2 + n3 == 2020, do: n1 * n2 * n3, else: find2020_3(numbers1, numbers2, nums3)
end
end

I later tried these libraries:

{:combination, "~> 0.0.3"},
{:math_combinations, "~> 0.2.0"},
{:comb, git: "https://github.com/tallakt/comb.git", tag: "master"}

They were all very slow.

1 Like

What happens if you let it run the full comprehension, without throwing, then just take the first result? Just wondering if try has significant overhead compared to the benefits of short-circuiting

I timed it. The for comprehension for part 2 is noticeably slower on my 2018 15" MBP (i7 processor). That’s why I stuck with my ugly hack.

1 Like

The short circuit (at least for the given dataset) is considerably faster:

Comparison:
optimized                        16803.28
optimized, no short circuit        473.86 - 35.46x slower +2.05 ms
first solution                     163.47 - 102.79x slower +6.06 ms
no short circuit                     8.52 - 1971.12x slower +117.25 ms

Afaik throw/catch on the beam is meant exactly for such cases, so there should not be to much overhead in it.

2 Likes

Did it with streams:

defmodule Aoc.Y2020.D1 do
use Aoc.Boilerplate,
transform: fn raw -> raw |> String.split() |> Enum.map(&String.to_integer(&1)) end

def part1(input \\ processed()) do
[{x, y}] =
Stream.flat_map(input, fn i ->
Stream.flat_map(input, fn j ->
[{i, j}]
end)
end)
|> Stream.filter(fn {x, y} ->
x + y == 2020
end)
|> Enum.take(1)

x * y
end

def part2(input \\ processed()) do
[{x, y, z}] =
Stream.flat_map(input, fn i ->
Stream.flat_map(input, fn j ->
Stream.flat_map(input, fn k ->
[{i, j, k}]
end)
end)
end)
|> Stream.filter(fn {x, y, k} ->
x + y + k == 2020
end)
|> Enum.take(1)

x * y * z
end
end
3 Likes

I’ve been doing a lot of staring at SQL EXPLAIN this week, so I wrote a solution in raw SQL:

select * from (values (1765), (1742), (1756), etc etc) as t1 (v),
(values (1765), (1742), (1756), etc etc) as t2 (v)
where t1.v + t2.v = 2020;
1 Like

I do this:

defmodule FindEntries do
def find(numbers) do
numbers
|> String.trim()
|> String.split("\n")
|>  Enum.map(&String.to_integer/1)
#|> IO.inspect(label: "Enum.map(&String.to_integer/1 \n")
|> match_2020()

end

{:ok, body} ->
body
{:error, reason} ->
reason
end
end

def match_2020(list) do
[{a, b} | _list] =
for i <- list, j <- list,
i + j == 2020,
do: {i, j}

IO.puts "The sum of two numbers of the list which is equal to 2020 is: \{ #{a}, #{b} \}."
IO.puts "The multiplication: (#{a} x #{b}) = #{a * b}"

[{a, b, c} | _] =
for i <- list, j <- list, k <- list,
i + j + k == 2020,
do: {i, j, k}

IO.puts "The sum of three numbers of the list which is equal to 2020 is: [#{a}, #{b}, #{c}]."
IO.puts "The multiplication: (#{a} x #{b} x #{c}) = #{a * b * c}"
end
end

FindEntries.find "./puzzle_input.txt"

\$ elixir find_entries.ex
#=> The sum of two numbers of the list which is equal to 2020 is: { 16, 2004 }.
#=> The multiplication: (16 x 2004) = 32064
#=> The sum of three numbers of the list which is equal to 2020 is: [248, 820, 952].
#=> The multiplication: (248 x 820 x 952) = 193598720

Whoa I never thought of solving those with SQL.
Here is my attempt

-- dont know how to `copy` into a cte or temp table
create table table1 (
input   integer
);
create table table2 (
input   integer
);

create table table3 (
input   integer
);

copy table1 from '/input.txt';
copy table2 from '/input.txt';
copy table3 from '/input.txt';

-- part 1
select
table1.input * lag(table1.input) over()
from
table1, table2
where
table1.input + table2.input = 2020;

-- part 2, had to multiply the result by hand, could not figure out how to multiply  it on the clause
select
distinct table1.input
from
table1, table2, table3
where
table1.input + table2.input + table3.input = 2020;
1 Like

I converted the list of numbers into a MapSet and used the following code to find the pair of numbers.

@spec find_sum(MapSet.t(), number) :: nil | {number, number}
def find_sum(numbers, sum) do
numbers
|> Enum.find(&MapSet.member?(numbers, sum - &1))
|> case do
nil -> nil
number -> {number, sum - number}
end
end

I could reuse that function to find the 3 numbers in part2 as well like this:

sum = 2020

a =
numbers
|> Enum.find(&find_sum(numbers, sum - &1))

{b, c} = find_sum(numbers, sum - a)

IO.inspect(a: a, b: b, c: c, sum: a + b + c, product: a * b * c

Input was small enough so this pretty much run instantly on my machine

1 Like