Advent of Code 2020 - Day 10

Hi, there :wave:

Today, I felt it was way more challenging! I went through part2 thanks to Agent based memoization (without memoization the execution time was :infinity: , after it was 3ms :sunglasses:)

My code:
Part1 / Part2

4 Likes

Yes, morge challenging today, so I didn’t come up with a solution for part 2 yet :stuck_out_tongue:
Couldn’t decide how I wanna solve it, and then run out of time before work…
Anyway: Heres my part 1 in Erlang:

-module(day10).
-export([run/0]).

run()->
    Input = lists:sort(load_file("day10input.txt")),
    {part1(Input), part2(Input)}.

part1(Input)-> 
    calc([0|Input], 0, 0).

calc([X,Y|T], Ones, Threes) ->
    case Y - X of
        1 -> calc([Y|T], Ones + 1, Threes);
        3 -> calc([Y|T], Ones, Threes + 1);
        _ -> calc([Y|T], Ones, Threes)
    end;
calc(_, Ones, Threes)->
    Ones * (Threes + 1).

part2(_)-> notimplemented.

load_file(Filename)->
    {ok, Binary} = file:read_file(Filename),
    StringContent = unicode:characters_to_list(Binary),
    [ element(1, string:to_integer(Line)) || Line <- string:split(StringContent, "\n", all)].
2 Likes

Thanks for mentioning that. I had part 2 working for the examples, but the full input timed out. Then I rebuild it using :digraph and recursively weighted the edges from the end. This again timed out for the puzzle input but not the examples. Turns out keeping track of the already checked vertexes made the test resolve in 0.1 sec.

2 Likes

I think for part 2 it must be easy to write a solution that never completes. I too have written a function which works for the test input but then never returns for the full input. Time to learn about “Agent based memoization” :smile:

1 Like

Sure it’s easy, the full input leads to a combinatorial explosion.
I let my first un-memoized solution running for more than hour, it never completed.

For memoization, you can do it different ways:

  • carry an accumulator along your calls. Don’t like it very much because its makes the code convoluted and less readable
  • use a library such as memoize but I feel like it’s cheating :wink:
  • write an agent

For memoization you can use the process dictionary: Process.put & Process.get

1 Like

You can actually calculate the answer for part two without the need to run any of the possibilities - if you sort your input and reduce that to a list of the number of consecutive digits in a row ( [1, 2, 3, 6] -> [3, 1] or [1, 3, 4, 5, 8] -> [1, 3, 1]), you can then calculate the number of permutations each ‘block’ will cause and then just find the product of the list

3 Likes

That interesting. I tried something similar by reducing over the list finding certain combinations, where I would know the number of permutations in advance. But i couldn’t really think of a way of handling those combinations while not duplicating/missing other ones “one step futher” into the list.

Phew. This was tough, glad to see I’m not the only one that was struggling!

I realised that the combinations basically form a graph, where each node inherits the number of combinations from its parents. Wrote up my reasoning in my notes.

Here’s my part 2. It completes in 68 microseconds on my machine. I think it’s pretty obtuse without the explanation :crazy_face:. list is the input as a list of integers.

def count_arrangements(list), do: count_arrangements(%{0 => 1}, [0 | Enum.sort(list)])

def count_arrangements(arrs_to, [last]), do: arrs_to[last]

def count_arrangements(arrs_to, [current | rest]) do
  rest
  |> Enum.take(3)
  |> count_reachable(current, arrs_to)
  |> count_arrangements(rest)
end

def count_reachable([], _a, arrs_to), do: arrs_to

def count_reachable([b | rest], a, arrs_to) when b - a <= 3 do
  arrs_to = Map.update(arrs_to, b, arrs_to[a], &(&1 + arrs_to[a]))
  count_reachable(rest, a, arrs_to)
end

def count_reachable([_b | rest], a, arrs_to), do: count_reachable(rest, a, arrs_to)
1 Like

my permutation calculation would have broken if I needed to calculate the permutations for a longer block of consecutive numbers, apparently it needs to be tribonacci numbers…

My solution. Nothing special for p2, just some recursion and Agent for memoization.

defmodule AdventOfCode.Day10 do
  def part1(input) do
    {j1, j3} =
      input
      |> String.split("\n", trim: true)
      |> Enum.map(&String.to_integer/1)
      |> Enum.sort()
      |> count_joltage()

    j1 * j3
  end

  def part2(input) do
    Agent.start_link(&Map.new/0, name: __MODULE__)

    res =
      input
      |> String.split("\n", trim: true)
      |> Enum.map(&String.to_integer/1)
      |> find_combinations(0)

    Agent.stop(__MODULE__)

    res
  end

  def count_joltage(adapters) do
    {_, j1, j3} =
      Enum.reduce(adapters, {0, 0, 1}, fn adapter, {last, j1, j3} ->
        case adapter - last do
          1 -> {adapter, j1 + 1, j3}
          3 -> {adapter, j1, j3 + 1}
          _ -> {adapter, j1, j3}
        end
      end)

    {j1, j3}
  end

  def find_combinations(adapters, adapter) do
    case Agent.get(__MODULE__, &Map.get(&1, adapter)) do
      nil ->
        val = reachable_adapters(adapters, adapter)
        Agent.update(__MODULE__, &Map.put(&1, adapter, val))
        val

      x ->
        x
    end
  end

  def reachable_adapters(adapters, adapter) do
    adapters
    |> Enum.filter(fn a -> a in (adapter + 1)..(adapter + 3) end)
    |> case do
      [] -> 1
      [a] -> find_combinations(adapters, a)
      a -> a |> Enum.map(&find_combinations(adapters, &1)) |> Enum.sum()
    end
  end
end
1 Like

My solution of part 2 is to calculate result backwards, memoization is then “for free”:

data = "data/10" |> File.read!() |> String.split() |> Enum.map(&String.to_integer/1)
data = Enum.sort([0 | data], :desc)

IO.puts(
  Enum.reduce(data, %{(hd(data) + 3) => 1}, fn i, memo ->
    Map.put(memo, i, Enum.sum(Enum.map(1..3, &Map.get(memo, i + &1, 0))))
  end)[0]
)
5 Likes

Today was a bit more tricky, I like when the naive approach just fails :slight_smile:

This is problem you can solve with dynamic programming, but I do not remember how that works so I went for a memoization/cache approach instead. No polish today, first version that worked below.

defmodule Aoc2020.Day10 do
  def part1(numbers) do
    numbers = Enum.sort(numbers, :desc)
    numbers = [hd(numbers) + 3 | numbers]

    diffs =
      numbers
      |> differences()
      |> Enum.frequencies()

    diffs[1] * diffs[3]
  end

  def part2(numbers) do
    numbers = Enum.sort([0 | Enum.to_list(numbers)], :desc)
    computer_joltage = hd(numbers) + 3
    sequence = [computer_joltage | numbers]

    graph = build_graph(sequence)
    rev_seq = Enum.reverse(sequence)

    for number <- rev_seq, reduce: %{} do
      cache -> Map.put(cache, number, count_paths(graph, number, 0, 0, cache))
    end
    |> Map.get(computer_joltage)
  end

  def differences([a]), do: [a]
  def differences([a | [b | _] = rest]), do: [a - b | differences(rest)]

  def build_graph(adapters) do
    for adapter <- adapters, reduce: {%{}, adapters} do
      {allowed, [_ | adapters]} ->
        {Map.put(
           allowed,
           adapter,
           Enum.take_while(adapters, fn joltage -> joltage >= adapter - 3 end)
         ), adapters}
    end
    |> elem(0)
  end

  def count_paths(_, to, to, sum, _), do: sum + 1
  def count_paths(graph, from, to, sum, cache) do
    for node <- graph[from], reduce: sum do
      sum ->
        case Map.fetch(cache, node) do
          {:ok, value} -> sum + value
          :error -> count_paths(graph, node, to, sum, cache)
        end
    end
  end

  def input_stream(path) do
    File.stream!(path)
    |> Stream.map(&parse/1)
  end

  def parse(line) do
    line
    |> String.trim()
    |> String.to_integer()
  end
end

input = Aoc2020.Day10.input_stream("input.txt")

Aoc2020.Day10.part1(input)
|> IO.inspect(label: "part1")

Aoc2020.Day10.part2(input)
|> IO.inspect(label: "part2")
1 Like

yeah, that is a bit cryptic :sweat_smile:

1 Like

Hey, although I don’t normally post my solution, I just read some of them to learn from you, I found my solution to the task2 quite interesting. Similar to wah @adamu said, at the end, all that was needed to take into account was that the number of combination of a value will be the sum of the combinations of the values that point to it:

  def task2(file) do
    voltages = load_voltages(file)

    run(%{0 => 1}, voltages)
    |> Map.get(List.last(voltages))
  end

  def run(comb_registry, [evaluated | others]) do
    comb_registry
    |> check_available_value(evaluated, 1, others)
    |> check_available_value(evaluated, 2, others)
    |> check_available_value(evaluated, 3, others)
    |> run(others)
  end

  def run(comb_registry, []), do: comb_registry

  def check_available_value(comb_registry, current_value, to_add, next_values) do
    comb_current_value = Map.fetch!(comb_registry, current_value)

    cond do
      (current_value + to_add) in next_values ->
        Map.update(
          comb_registry,
          current_value + to_add,
          comb_current_value,
          &(&1 + comb_current_value)
        )

      true ->
        comb_registry
    end
  end

1 Like

Thanks, I stole this idea and implemented it with Erlang :slight_smile:

This is optimal solution (It would be if I wasn’t adding to the end of list). Credit goes to reddit thread. I’ll repo link providing my clunky solution that got me star.

  def part2_optimal(path) do
    input_stream(path)
    |> Enum.sort()
    |> Enum.reduce({[0], [1]}, fn
      element, {interval, accumulators} ->
        relevant_interval = Enum.filter(interval, &(&1 + 3 >= element))
        relevant_accs = Enum.take(accumulators, -length(relevant_interval))

        new_acc =
          (length(relevant_accs) > 1 && Enum.sum(relevant_accs)) || List.last(relevant_accs)

        {relevant_interval ++ [element], relevant_accs ++ [new_acc]}
    end)
    |> elem(1)
    |> List.last()
  end

Struggled a bit with part two today but ended up with a similar solution to @bossek (albite a bit less elegant) and iterating through the reversed list, building up the memoized values along the way.

  def variations([], [{_, v} | _]), do: v

  def variations([head | tail], collector) do
    value =
      collector
      |> Enum.filter(fn {v, _} -> v - head <= 3 end)
      |> Enum.reduce(0, fn {_, branches}, acc -> acc + branches end)

    variations(tail, [{head, value} | collector])
  end

Can you explain how you knew that tribonacci sequence would provide the number of permutations for each block?

I’m trying to compare my answer with yours, but I’m getting an error when running your code against my input.

** (KeyError) key 2 not found in: %{0 => 1}
    :erlang.map_get(2, %{0 => 1})
    (bench 0.1.0) lib/bench.ex:54: Jkmrto.check_available_value/4

Here’s my input.