Advent of Code 2020 - Day 1

Learning Questions & Discussions Coding Challenges
,
1

Finished Day 1 with Elixir :tada:

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
2

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

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 =
  File.read!("input")
  |> 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
4

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.

Edit: I’ve added some benchmarks.

4 Likes
5

I did the exact same thing :smiley:

1 Like
6

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

7

I found improved performance by preventing iterating the list for cases, which are already beyond the allowed sum (unoptimized is 23x slower): aoc2020/lib/aoc2020/day1.ex at master · LostKobrakai/aoc2020 · GitHub

8

My solution:

defmodule AdventOfCode.Day01 do
  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 :slight_smile:
I tried to make both parts efficient, so they stop calculation as soon as they find a correct result.

3 Likes
9

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

10

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

1 Like
11

Seems like it, but that made it even more different :smiley:

Comparison: 
optimized            16.87 K
first solution       0.163 K - 103.53x slower +6.08 ms
Details 
list = Aoc2020.Day1.load_report()

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
12

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

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

  def part1(numbers \\ readinput()) do
    find2020_2(numbers, tl(numbers))
  end

  def part2(numbers \\ readinput()) do
    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
13

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

14

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
15

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
16

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
17

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
18

I do this:

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

  end

  def read_file(path) do
    case File.read(path) do
      {: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

19

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
20

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

1 Like