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