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]
)
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")
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
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?
That is pretty elegant, kind of wish I’d thought of going backwards. I don’t think the direction is relevant for whether memoization is free or not though. We both just store the accumulated values in a map, and I go forwards. Anyway, the other solutions are faster 
. And @camilleryr’s is faster than @Damirados’ Reddit “optimal” solution, although I don’t pretend to understand it! Very clever.
Name ips average deviation median 99th %
camilleryr 105.88 K 9.44 μs ±75.62% 9 μs 30 μs
reddit 32.58 K 30.69 μs ±34.14% 28 μs 81 μs
adam 25.09 K 39.86 μs ±24.96% 37 μs 91 μs
hallski 19.81 K 50.49 μs ±27.17% 48 μs 126 μs
bossek 19.45 K 51.42 μs ±27.12% 48 μs 121 μs
kwando 16.00 K 62.51 μs ±30.45% 58 μs 158 μs
Comparison:
camilleryr 105.88 K
reddit 32.58 K - 3.25x slower +21.25 μs
adam 25.09 K - 4.22x slower +30.41 μs
hallski 19.81 K - 5.35x slower +41.05 μs
bossek 19.45 K - 5.44x slower +41.98 μs
kwando 16.00 K - 6.62x slower +53.07 μs
It would be interesting to see how the Agent answers do, but I’ve looked at this problem for long enough already!