Aetherus

Aetherus

Advent of Code 2020 - Day 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)

Most Liked

adamu

adamu

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.

LostKobrakai

LostKobrakai

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.

mexicat

mexicat

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.

egze

egze

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
hauleth

hauleth

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
  def read_input(path) 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.read_input("input.txt")

list
|> Solution.run(2, 2020)
|> Enum.reduce(&*/2)
|> IO.inspect(label: "task 1")

list
|> Solution.run(3, 2020)
|> Enum.reduce(&*/2)
|> IO.inspect(label: "task 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

Where Next?

Popular in Challenges Top

Aetherus
This topic is about the Advent of Code 2021 - Day 4. Thanks to @bjorng , we now have a new Private Leaderboard. The entry code is: 370...
New
New
bjorng
This topic is about Day 16 of the Advent of Code 2021. We have a private leaderboard (shared with users of Erlang Forums): https://adve...
New
christhekeele
Continuation of Advent of Code 2022​:christmas_tree:, Day 1: Day 2! Leaderboard:
New
maennchen
Ok, that was a rough one today. I haven’t found a way to improve the algorithm further. Part 1 runs in .5 seconds, Part 2 in ~ 5 minutes...
New
jkwchui
Monkeys fitted squarely as GenServers in my head. My initial problem was using cast instead of call; I imagine impolite monkeys slinging...
New
woolfred
It is that time of the year again: Advent of Code 2022 :christmas_tree: Day 1 Leaderboard:
New
New
mattbaker
I’m having so much fun working on the “Protohackers” challenges, I never got into Advent of Code much but this has been amazing. The chal...
New
Aetherus
I spent 3 hours struggling in part 2, until I noticed a very basic mistake :joy: Here’s my code: By the way, the starting position in...
New

Other popular topics Top

srinivasu
How to handle excepions in elixir? Suppose i have A, B, C ,D, E modules. and each module has get() function. A.get() method will call th...
New
Tee
can someone please explain to me how Enum.reduce works with maps
New
joaquinalcerro
Hi there, I am working with Ecto-Postgresql and I need to call all of the records from a specific table but the table has 40,000 record...
New
axelson
This post is a wiki (feel free to hit the edit button near the bottom right of this post to add your own changes!) This post collects co...
239 45766 226
New
lastday4you
I wanted to check elixir version in phoenix because i found that my elixir is 1.5 but when i use Enum.chunk_by it said the function is un...
New
chensan
I have a User schema with a :from_id field set to type :string: defmodule TweetBot.Repo.Migrations.CreateUsers do use Ecto.Migration ...
New
shahryarjb
Hello, I have map which I want to convert it to string like this: the map: %{last_name: "tavakkoli", name: "shahryar"} the string I ne...
New
stefanluptak
Hello everybody, usually, I use a 29" ultra-wide monitor for VSCode which can easily accomodate explorer (files panel) + file with code ...
New
Patoshizzle
After calling mix ecto.create I get this error: 17:00:32.162 [error] GenServer #PID&lt;0.412.0&gt; terminating ** (Postgrex.Error) FATAL...
New
lucidguppy
I have a super simple question about elixir - how would I take a file like this foo bar baz and output a new file that enumerates th...
New

We're in Beta

About us Mission Statement