This topic is about Day 15 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276
The join code is:
39276-eeb74f9a
Not hard one but the logic is convoluted and easy to off-by-one mistake. I used a map number to list of turns to keep track of each turns.
The second part takes 40 seconds and 2GB ram to run. I’m looking for a better way
It was tricky to get the details right for part 1. The same solution solved part 2 in less than half a minute on my computer, so I didn’t try to find a faster solution.
Here is my solution.
I did that at first too, just in case, but after seeing part 2 I confirmed that you don’t need to save the entire history for each number. But removing that didn’t make it any faster… 
2 Likes
That felt pretty weird after the last couple of days to get to part 2 and just have to update the end turn. At least I feel pretty happy about the implementation (not for speed though, looking forward to see if someone posts something clever for a fast solution).
Recursively run iterate until end turn. Took around 30s on Macbook Pro Intel and 15s on a new Macbook Air M1 (running from iex):
defmodule AdventOfCode.Day15 do
@end_turn 30_000_000 - 1
def run(input) do
input
|> String.split(",", trim: true)
|> Enum.map(&String.to_integer/1)
|> iterate(0, %{})
end
def iterate([speak], @end_turn, _history), do: speak
def iterate([speak], turn, history) do
next = turn - Map.get(history, speak, turn)
iterate([next], turn + 1, Map.put(history, speak, turn))
end
def iterate([speak | rest], turn, history) do
iterate(rest, turn + 1, Map.put(history, speak, turn))
end
end
3 Likes
Easiest one in last few days.
Did some research looks like it’s Van Eck’s sequence, and you can’t do it other way than brute forcing it.
defmodule Y2020.Event15 do
@test [0, 3, 6]
@test2 [2, 1, 3]
@puzzle [0, 6, 1, 7, 2, 19, 20]
def run do
IO.puts("Test part1: #{solve(@test, 2020)}")
IO.puts("Test2 part1: #{solve(@test2, 2020)}")
IO.puts("Puzzle part1: #{solve(@puzzle, 2020)}")
IO.puts("Test part2: #{solve(@test, 30_000_000)}")
IO.puts("Puzzle part2: #{solve(@puzzle, 30_000_000)}")
end
def solve(numbers, x) do
map = numbers |> Enum.with_index(1) |> Enum.into(%{})
find_xth(map, 0, map_size(map) + 1, x)
end
def find_xth(_map, last, count, count), do: last
def find_xth(map, last, count, x) do
case Map.get(map, last) do
nil ->
find_xth(Map.put(map, last, count), 0, count + 1, x)
index ->
find_xth(Map.put(map, last, count), count - index, count + 1, x)
end
end
end
1 Like
Brute forced 
#!/usr/bin/env elixir
input = [9,3,1,0,8,4]
turns = 30_000_000
[prev | rest] = input
|> Enum.with_index(1)
|> Enum.reverse()
initial_state = {prev, Map.new(rest)}
initial_state
|> Stream.unfold(fn {{n, t}, history} ->
speak = case history[n] do
nil -> 0
t2 -> t - t2
end
head = {speak, t + 1}
{head, {head, Map.put(history, n, t)}}
end)
|> Enum.reduce_while(nil, fn
{n, ^turns}, _ -> {:halt, n}
{n, _}, _ -> {:cont, n}
end)
|> IO.inspect()
1 Like
One function to rule them all!
(should be self-explanatory)
defp process(input, limit) do
base = Map.new(Enum.with_index(String.split(input, ",")), fn {n, t} -> {String.to_integer(n), [t]} end)
Enum.count(base)..(limit - 1)
|> Enum.reduce(
{base, nil},
fn turn, {seen, last} ->
next = case seen[last] do
[a, b] -> a - b
_ -> 0
end
{Map.update(seen, next, [turn], fn [h | _] -> [turn, h] end), next}
end
)
|> elem(1)
end
1 Like
Who would’ve though I’d be using Stream.unfold in like almost all of those puzzles:
defp stream(starting_numbers, index) do
Stream.unfold(
%{
turn: 0,
start: starting_numbers,
last_spoken: nil,
last_spoken_at: %{}
},
fn
%{start: [speak | rest]} = state ->
state = Map.put(state, :start, rest)
state = Map.put(state, :last_spoken, speak)
state = update_last_spoken(state, speak)
{speak, inc_turn(state)}
state ->
speak =
case Map.fetch(state.last_spoken_at, state.last_spoken) do
{:ok, [a, b | _]} -> a - b
_ -> 0
end
state = Map.put(state, :last_spoken, speak)
state = update_last_spoken(state, speak)
{speak, inc_turn(state)}
end
)
|> Enum.at(index - 1)
end
It’s a bit verbose but I prefer it this way, since the subject was an entire by-one-off-index-error trap.
I’m guessing Elixir with its lists and recursion encourages us to implement this efficiently from the start. I wonder if the assumption was that people would maybe implement part 1 by storing all the turns and indexing them, or something?
Part 2 solved with the same solution for me too, with a slightly uncomfortable wait… I’m wondering if using a mutable data structure would speed it up.
I’m certain it would!
I tried to replace my Elixir map by an erlang array but it made things even worse. I think the solution would be to use a NIF backed mutable data structure.
1 Like
I used a map of two-element tuples to store previous state data.
defmodule Day15 do
def readinput() do
# [0, 3, 6]
[13, 0, 10, 12, 1, 5, 8]
end
def part1(input \\ readinput()) do
run(input, 2020)
end
def part2(input \\ readinput()) do
run(input, 30000000)
end
def run(input, target) do
Enum.with_index(input, 1)
|> Enum.reduce(%{}, fn {number, turn}, turns -> Map.put(turns, number, {turn, -1}) end)
|> loop(List.last(input), length(input), target)
end
def loop(_turnsmap, number, turn, turn), do: number
def loop(turnsmap, prevspoke, turn, endturn) do
{say, newmap} =
Map.get(turnsmap, prevspoke, {-1, -1})
|> nextsay(turnsmap, prevspoke, turn)
loop(newmap, say, turn+1, endturn)
end
# number does not exist, add it
def nextsay({-1, -1}, turnsmap, prevspoke, turn) do
{0, Map.put(turnsmap, prevspoke, {turn, -1})}
end
# number was said once before (possibly starting number?)
def nextsay({turn, -1}, turnsmap, _prevspoke, turn) do
{z1, _} = Map.get(turnsmap, 0, {-1, -1})
{0, Map.put(turnsmap, 0, {turn+1, z1})}
end
# usual case: number was said at least twice
def nextsay({prev1, prev2}, turnsmap, _prevspoke, turn) do
newsay = prev1 - prev2
{s1, _} = Map.get(turnsmap, newsay, {-1, -1})
{newsay, Map.put(turnsmap, newsay, {turn+1, s1})}
end
end
My original brute force solution for part two took about 41 seconds to run (using a map to keep the necessary history). I couldn’t come up with a clever solution, so I did the thing we are not supposed to do and I used the process dictionary for my data structure and got an impressive speed boost using the same algorithm!
MAP :
Name ips average deviation median 99th %
1 2.03 K 0.00049 s ±23.90% 0.00047 s 0.00093 s
2 0.00002 K 41.78 s ±0.00% 41.78 s 41.78 s
PROCESS DICTIONARY :
Name ips average deviation median 99th %
1 6.28 K 0.00016 s ±27.22% 0.00014 s 0.00029 s
2 0.00007 K 14.87 s ±0.00% 14.87 s 14.87 s
3 Likes
I’m guessing the creation of all the tuples is the other half of the problem - so using mutable structures for those would probably make it even faster.
Had to try swapping a map for Process.get/put and saw an improvement from ~15s to ~5s (which seems inline with the improvement you saw as well).
I was hoping it would run sub 10s on the M1!
Todays (16th) problem was just a big off by 1 trap. Nothing fancy to see here 
defmodule Aoc2020.Day15 do
def part1(input) do
input
|> setup()
|> play_until(2020)
|> elem(0)
end
def part2(input) do
input
|> setup()
|> play_until(30_000_000)
|> elem(0)
end
def play_until({_, turn, _} = state, target_turn) when turn == target_turn + 1, do: state
def play_until(state, target_turn) do
state
|> play()
|> play_until(target_turn)
end
def setup(numbers), do: setup(numbers, 1, %{})
defp setup([number | []], turn, map), do: {number, turn + 1, map}
defp setup([number | numbers], turn, map) do
setup(numbers, turn + 1, map |> put_number(number, turn))
end
def play({last_number, turn, seen}) do
case Map.fetch(seen, last_number) do
:error ->
{0, turn + 1, seen |> Map.put(last_number, turn - 1)}
{:ok, previous_turn} ->
new_value = turn - previous_turn - 1
{new_value, turn + 1, seen |> Map.put(last_number, turn - 1)}
end
end
def input(path) do
File.read!(path)
|> String.trim()
|> String.split(",")
|> Enum.map(&String.to_integer/1)
end
end
input = Aoc2020.Day15.input("input.txt")
Aoc2020.Day15.part1(input)
|> IO.inspect(label: "part1")
Aoc2020.Day15.part2(input)
|> IO.inspect(label: "part2")
I actually converted my tuples to function arguments… but I could not see any difference performance (I might have screwed something up though).
