Advent of Code 2020 - Day 10

Yes, morge challenging today, so I didn’t come up with a solution for part 2 yet
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)].

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.

https://github.com/LostKobrakai/aoc2020/commit/0617012fccbf1446e867cd40f7022a797254c9ba

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”

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
• write an agent

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

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

https://github.com/camilleryr/advent20/blob/main/lib/day_10.ex

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

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