Advent of Code 2020 - Day 1

[bodgix]

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.

[bodgix]

@egze

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

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.

I fixed this by adding:

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

So if the input had

1010
1010
…
…

Then 1020100 would be the correct answer I think.

[rhamorim]

Here’s my take:

defmodule AdventOfCode.Events.Event2020.Day01 do
  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

[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

[gianthamster]

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.

[agundy]

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} = List.first(answers)
    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

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

    {i, j, k} = List.first(answers)
    i * j * k
  end

  def answer do
    expenses = Helpers.load_list_file("priv/day_1_input.txt")
    part_1 = part_1(expenses)
    part_2 = part_2(expenses)

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

full code: https://gitlab.com/agundy/advent_of_code/-/blob/master/2020/solutions/lib/solutions/day_1.ex

[ricardo-h]

Part 1:

Big-O

Sort → O(n log n)
Find → O(n)

defmodule Advent.Day1 do

  @lucky_num 2020

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

  defp find(lst) when length(lst) < 2, do: {:error, "not found"}
  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

[ricardo-h]

Part2

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

defmodule Advent.Day1b do

  @lucky_num 2020

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

  defp find(lst) when length(lst) < 3, do: {:error, "not found"}
  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

[stevensonmt]

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
    {:ok, expenses} = File.read("lib/input.txt")

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

[Damirados]

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

[Aetherus]

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

[achillesdev]

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
    File.read!(Path.absname(filename)) 
    |> String.split("\n", trim: true) 
    |> Enum.map(&String.to_integer/1) 
    |> Enum.filter(&(&1 < 2020))
  end

  @doc """
  Advent of Code day 1 solution

  ## Examples
      iex> AdventOfCode2020.day1()
  """
  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

[Aetherus]

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

[achillesdev]

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

[Aetherus]

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.

[mochromatic]

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

[akagrawal]

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
    freq = Map.get(map, head, 0)
    updateExpenseMap(remainingList, Map.put(map, head, freq + 1))
  end

  defp takeInput() do
    File.read!("Day1.txt")
    |> 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
      {:ok, {head, sum - head}}
    else
      multiplication(remainingList, map, sum)
    end
  end

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

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

    case multiplication([head | remainingList], map, sum - head) do
      :error ->
        map = Map.put(map, head, freq)
        multiplicationV2(remainingList, map, sum)

      {:ok, {n1, n2}} ->
        {n1, n2, head}
    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

[NobbZ]

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…

NobbZ/aoc_ex/-/blob/master/lib/y2020/d01.ex

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…

[Rainer]

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()->
    process_list(load_file("day1input.txt")).

load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    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()->
    process_list(load_file("day1input.txt")).

load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    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 ].