# Advent of Code 2020 - Day 10

Hi, there

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

My code:
Part1 / Part2

4 Likes

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

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ā

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

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

Agent.stop(__MODULE__)

res
end

{_, j1, j3} =
1 -> {adapter, j1 + 1, j3}
3 -> {adapter, j1, j3 + 1}
end
end)

{j1, j3}
end

nil ->
val

x ->
x
end
end

|> Enum.filter(fn a -> a in (adapter + 1)..(adapter + 3) end)
|> case do
[] -> 1
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

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

{Map.put(
allowed,
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

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

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,
comb_current_value,
&(&1 + comb_current_value)
)

true ->
comb_registry
end
end

``````
1 Like

Thanks, I stole this idea and implemented it with Erlang

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)

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.