Thanks for your notes! That ascii illustration made it really click what you were doing and also (sort of) how the tribonacci sequence comes into play.
stevensonmt
ricardo-h
part1 and part2
O(n log n)
defmodule Advent.Day10 do
def start(part \\ :part1, file \\ "/tmp/input.txt"), do:
File.read!(file)
|> String.split()
|> Enum.map(&String.to_integer/1)
|> Enum.sort()
|> execute(part)
defp execute(lst, :part1), do:
lst
|> Enum.reduce({0, %{3 => 1}}, fn o, {last, m} -> {o, Map.update(m, o - last, 1, fn x -> x + 1 end)} end)
|> elem(1)
|> print()
defp execute(lst, :part2) do
(lst ++ [List.last(lst) + 3])
|> Enum.reduce(%{0 => 1}, fn o, acc -> acc |> Map.put(o, 0) |> update(o, -3) |> update(o, -2) |> update(o, -1) end)
|> print(List.last(lst) + 3)
end
def update(acc, v, delta) do
case acc[v + delta] do
nil -> acc
delta_v -> Map.update(acc, v, 1, fn x -> x + delta_v end)
end
end
defp print(m), do: m[1] * m[3] # part1
defp print(m, n), do: m[n] # part2
end
0
ricardo-h
little improvement
dont need to add +1 element in list
...
defp execute(lst, :part2) do
lst
|> Enum.reduce(%{0 => 1}, fn o, acc -> acc |> Map.put(o, 0) |> update(o, -3) |> update(o, -2) |> update(o, -1) end)
|> print(List.last(lst))
end
...
0
bossek
Using map for accumulated values is not necessary because I need at most 3 last added values:
It should be a bit faster… but also a bit uglier.
0
faried
I didn’t figure out how to do part2, so here’s my part1:
defmodule Day10.Adapter do
defstruct jolts: 0, input: nil
def new(jolts) do
%__MODULE__{jolts: jolts, input: (jolts - 3)..(jolts - 1)}
end
end
defmodule Day10 do
alias Day10.Adapter
def readinput(fname \\ "10.input.txt") do
File.read!(fname)
|> String.split("\n", trim: true)
|> Enum.map(&String.to_integer/1)
|> Enum.sort()
|> Enum.map(&Adapter.new/1)
end
def part1(adapters \\ readinput()) do
chain(adapters)
end
# threecount starts with 1 to account for the last adapter <-> your device
def chain(adapters, jolts \\ 0, onecount \\ 0, threecount \\ 1)
def chain([], _jolts, onecount, threecount), do: onecount * threecount
# do: {onecount, threecount, onecount * threecount}
def chain(adapters, jolts, onecount, threecount) do
# since the list is sorted, the adapter we want is always the first one
{adapter, rest} = List.pop_at(adapters, 0)
onecount = if adapter.jolts - jolts == 1, do: onecount + 1, else: onecount
threecount = if adapter.jolts - jolts == 3, do: threecount + 1, else: threecount
chain(rest, adapter.jolts, onecount, threecount)
end
end
0
adamu
faried
jkmrto
hey, sorry for answering quite late.
Here is the whole file, probably I missed something when pasting the code. You just need to do this to execute the task2:
iex -S mix
input = "lib/day10/input.txt"
Aoc2020.Day10.task2(input)
Let me know the results 
0
adamu
Sorry I deleted my benchmark file so I can’t compare them together, but here’s your result.
Name ips average deviation median 99th %
jkmrto 19.12 K 52.29 μs ±22.18% 50 μs 115 μs
Should mention that I edited everyone’s solutions to make sure the file parsing was already done. The input to all the benchmarked solutions was a list of integers.
1
thenrio
Hello all,
Classify?
Part two looks like the problem “Triple Steps” (8.1 of Cracking The Code Interview), for which we have relation : x(n) = x(n-3) + x(n-2) + x(n-1) for i>3 : we can reach 4 from 1, 2, 3, x is the number of combinations.
Bottom up
This problem has as bottom up solution, that need to store only 3 values, O(n) it time and O(1) in space (it’s not in the book).
# Number of combinations to reach step n, with moves of 1, 2, 3 steps.
# Starts from ground (0) and first step is 1.
def solve(n) do
# memo holds {x(1), x(2), x(3)} where x is solve, it's the meat.
memo = {1, 2, 4}
4..n
|> Enum.reduce(memo, fn _i, {n3, n2, n1} ->
{n2, n1, n1 + n2 + n3}
end)
|> elem(2)
end
The difference with the triple steps problem, beside names (step → adapter, number → joltage), is set of valid values as input : x(n) = x(n-3) + x(n-2) + x(n-1) if n in input else x(n) = 0 for i>3
We can adapt above solution:
def combinations(input) do
set = MapSet.new(input)
# memo holds {x(1), x(2), x(3)}
memo =
case 1..3 |> Enum.map(fn i -> if Enum.member?(set, i), do: i, else: 0 end) do
[1, 2, 3] -> {1, 2, 4}
# others are derived
[0, 2, 3] -> {0, 1, 2}
[1, 0, 3] -> {1, 0, 2}
[1, 2, 0] -> {1, 2, 0}
[1, 0, 0] -> {1, 0, 0}
[0, 2, 0] -> {0, 1, 0}
[0, 0, 3] -> {0, 0, 1}
end
max = Enum.max(set)
4..max
|> Enum.reduce(memo, fn n, {xn3, xn2, xn1} ->
if Enum.member?(set, n) do
{xn2, xn1, xn3 + xn2 + xn1}
else
{xn2, xn1, 0}
end
end)
|> elem(2)
end
The meat of change is also in {x(1), x(2), x(3)}.
We have O(n) in time and O(n) in space (the set).
2