Advent of Code 2020 - Day 15

This topic is about Day 15 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:

The join code is:

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… :man_shrugging:


Yep, still have no clue how to make part2 faster than 40sec :exploding_head:

My code

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
    |> String.split(",", trim: true)
    |> iterate(0, %{})

  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))

  def iterate([speak | rest], turn, history) do
    iterate(rest, turn + 1, Map.put(history, speak, turn))

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)}")

  def solve(numbers, x) do
    map = numbers |> Enum.with_index(1) |> Enum.into(%{})
    find_xth(map, 0, map_size(map) + 1, x)

  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)

1 Like

Brute forced :exploding_head:

#!/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,}

|> Stream.unfold(fn {{n, t}, history} ->
  speak = case history[n] do
    nil -> 0
    t2 -> t - t2
  head = {speak, t + 1}
  {head, {head, Map.put(history, n, t)}}
|> Enum.reduce_while(nil, fn
  {n, ^turns}, _ -> {:halt, n}
  {n, _}, _ -> {:cont, n}
|> IO.inspect()
1 Like

One function to rule them all!

(should be self-explanatory)

  defp process(input, limit) do
    base =, ",")), 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
           {Map.update(seen, next, [turn], fn [h | _] -> [turn, h] end), next}
    |> elem(1)
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
        turn: 0,
        start: starting_numbers,
        last_spoken: nil,
        last_spoken_at: %{}
        %{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

          state = Map.put(state, :last_spoken, speak)
          state = update_last_spoken(state, speak)
          {speak, inc_turn(state)}
    |> - 1)

It’s a bit verbose but I prefer it this way, since the subject was an entire by-one-off-index-error trap.

My solution

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]

  def part1(input \\ readinput()) do
    run(input, 2020)

  def part2(input \\ readinput()) do
    run(input, 30000000)

  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)

  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)

  # number does not exist, add it
  def nextsay({-1, -1}, turnsmap, prevspoke, turn) do
    {0, Map.put(turnsmap, prevspoke, {turn, -1})}

  # 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})}

  # 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})}

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!

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

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

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 :slight_smile:

defmodule Aoc2020.Day15 do
  def part1(input) do
    |> setup()
    |> play_until(2020)
    |> elem(0)

  def part2(input) do
    |> setup()
    |> play_until(30_000_000)
    |> elem(0)

  def play_until({_, turn, _} = state, target_turn) when turn == target_turn + 1, do: state

  def play_until(state, target_turn) do
    |> play()
    |> play_until(target_turn)

  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))

  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)}

  def input(path) do!(path)
    |> String.trim()
    |> String.split(",")

input = Aoc2020.Day15.input("input.txt")

|> IO.inspect(label: "part1")

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