Advent of Code 2020 - Day 1

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

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.

I did the exact same thing

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): aoc2020/lib/aoc2020/day1.ex at master · LostKobrakai/aoc2020 · GitHub

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

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 ?

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

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