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.
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
https://github.com/camilleryr/advent20/blob/main/lib/day_15.ex
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).
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).
After struggling with the part 2’s for the past couple days this felt a little weird. Like when the heroes think like they won, but it turns out the villain is going to burst through a wall and take one of them out.
Stay frosty. Day 16 is coming for us! 
defmodule Day15 do
@input [15,5,1,4,7,0]
def part_1 do
@input
|> start(%{}, 1)
|> play(2020)
|> IO.inspect()
end
def part_2 do
@input
|> start(%{}, 1)
|> play(30000000)
|> IO.inspect()
end
def play({_, turn, last}, max) when turn > max, do: last
def play({seen, turn, last}, max) do
number = get_last(seen, last)
seen = update_last_seen(seen, number, turn)
play({seen, turn + 1, number}, max)
end
def start([], seen, turn), do: {seen, turn, 0}
def start([h|t], seen, turn) do
start(t, update_last_seen(seen, h, turn), turn + 1)
end
def get_last(seen, key) do
case Map.get(seen, key) do
{f, s} -> f - s
_ -> 0
end
end
def update_last_seen(seen, key, turn) do
Map.update(seen, key, turn, fn
{f,_} -> {turn,f}
x -> {turn, x}
end)
end
end