Advent of Code 2020 - Day 15

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

https://github.com/hvnsweeting/adventofcode/blob/master/lib/2020/aoc2020_day15.ex

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…

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

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

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

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

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

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

https://github.com/LostKobrakai/aoc2020/commit/bdcd6307637bce32328f8227a4b560a7dd1b4565

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