Advent of Code 2020 - Day 22

This topic is about Day 22 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

Nice with a simpler puzzle after days 19 and 20. In my solution I first tried to use the Erlang’s :queue module, but it turned out that in part 2 a simple list was faster because of the need to keep track of previous states. The running time is 1.5 seconds for both parts on my computer, while the running time for using :queue was almost 3 seconds.

This one was easy, took me awhile to understand the recursion rule for the recursive combat but once I got it, it was pretty straight-forward. I did think about using :queue but felt like trying without first.

defmodule AdventOfCode.Y2020.Day22 do
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 22

  def run_1, do: input!() |> process() |> play() |> score()
  def run_2, do: input!() |> process() |> recursive_combat() |> score()

  def process(input) do
    input
    |> String.split("\n\n")
    |> Enum.flat_map(&String.split(&1, ":"))
    |> decks()
  end

  defp score(cards) do
    cards
    |> Enum.reverse()
    |> Enum.with_index(1)
    |> Enum.map(fn {val, idx} -> val * idx end)
    |> Enum.sum()
  end

  defp decks([_, player_1, _, player_2]), do: {deck(player_1), deck(player_2)}
  defp deck(player), do: Enum.map(String.split(player, "\n", trim: true), &String.to_integer/1)

  defp play({[], player_2}), do: player_2
  defp play({player_1, []}), do: player_1

  defp play({[card_1 | rest_1], [card_2 | rest_2]}) when card_1 > card_2,
    do: play({rest_1 ++ [card_1, card_2], rest_2})

  defp play({[card_1 | rest_1], [card_2 | rest_2]}),
    do: play({rest_1, rest_2 ++ [card_2, card_1]})

  defp recursive_combat(decks), do: decks |> recursive_combat([], []) |> elem(1)
  defp recursive_combat({[], player_2}, _, _), do: {2, player_2}
  defp recursive_combat({player_1, []}, _, _), do: {1, player_1}

  defp recursive_combat({[card_1 | rest_1] = a, [card_2 | rest_2] = b}, h1, h2) do
    if a in h1 || b in h2 do
      {1, a}
    else
      h1 = [a | h1]
      h2 = [b | h2]

      if card_1 <= length(rest_1) && card_2 <= length(rest_2) do
        case recursive_combat({Enum.take(rest_1, card_1), Enum.take(rest_2, card_2)}, [], []) do
          {1, _} -> recursive_combat({rest_1 ++ [card_1, card_2], rest_2}, h1, h2)
          {2, _} -> recursive_combat({rest_1, rest_2 ++ [card_2, card_1]}, h1, h2)
        end
      else
        case card_1 > card_2 do
          true -> recursive_combat({rest_1 ++ [card_1, card_2], rest_2}, h1, h2)
          _ -> recursive_combat({rest_1, rest_2 ++ [card_2, card_1]}, h1, h2)
        end
      end
    end
  end
end

1 Like

The recursion rules tripped me up several times. My part 2 returned the right answer when I ran it with both the infinite example and the worked-out example, and it was only when I traced through the latter that I realized I had to copy a slice of the deck of cards, not the entire rest of the deck.

It does too much work.

defmodule Day22 do
  def readinput() do
    File.read!("22.input.txt")
    |> String.split("\n\n", trim: true)
    |> Enum.map(fn s ->
      String.split(s, "\n", trim: true) |> tl() |> Enum.map(&String.to_integer/1)
    end)
  end

  def part1([player1, player2] \\ readinput()) do
    play1(player1, player2)
  end

  def play1([], cards), do: score(Enum.reverse(cards))
  def play1(cards, []), do: score(Enum.reverse(cards))

  def play1([c1 | cards1], [c2 | cards2]) when c1 > c2, do: play1(cards1 ++ [c1, c2], cards2)
  def play1([c1 | cards1], [c2 | cards2]) when c2 > c1, do: play1(cards1, cards2 ++ [c2, c1])

  def part2([player1, player2] \\ readinput()) do
    play2(player1, player2)
  end

  def play2(cards1, cards2, p1set \\ MapSet.new(), p2set \\ MapSet.new())

  def play2([], cards, _, _), do: {:player2, score(Enum.reverse(cards))}
  def play2(cards, [], _, _), do: {:player1, score(Enum.reverse(cards))}

  def play2([c1 | cards1] = p1cards, [c2 | cards2] = p2cards, p1set, p2set) do
    cond do
      p1cards in p1set or p2cards in p2set ->
        {:player1, true}

      c1 <= length(cards1) and c2 <= length(cards2) ->
        case play2(Enum.take(cards1, c1), Enum.take(cards2, c2)) do
          {:player1, _} ->
            play2(
              cards1 ++ [c1, c2],
              cards2,
              MapSet.put(p1set, p1cards),
              MapSet.put(p2set, p2cards)
            )

          {:player2, _} ->
            play2(
              cards1,
              cards2 ++ [c2, c1],
              MapSet.put(p1set, p1cards),
              MapSet.put(p2set, p2cards)
            )
        end

      c1 > c2 ->
        play2(cards1 ++ [c1, c2], cards2, MapSet.put(p1set, p1cards), MapSet.put(p2set, p2cards))

      true ->
        play2(cards1, cards2 ++ [c2, c1], MapSet.put(p1set, p1cards), MapSet.put(p2set, p2cards))
    end
  end

  def score(cards) do
    Stream.zip(cards, Stream.iterate(1, &(&1 + 1)))
    |> Stream.map(fn {a, b} -> a * b end)
    |> Enum.sum()
  end
end

Not very optimized (~1.3s on my laptop) but at least it was quick and easy to write!

defmodule AdventOfCode.Day22 do
  def part1(input) do
    input
    |> parse_input()
    |> play()
    |> elem(1)
    |> calc_score()
  end

  def part2(input) do
    input
    |> parse_input()
    |> play_recursive(MapSet.new())
    |> elem(1)
    |> calc_score()
  end

  def parse_input(input) do
    [p1, p2] = String.split(input, "\n\n", trim: true)

    p1 = p1 |> String.split("\n", trim: true) |> Enum.drop(1) |> Enum.map(&String.to_integer/1)
    p2 = p2 |> String.split("\n", trim: true) |> Enum.drop(1) |> Enum.map(&String.to_integer/1)

    {p1, p2}
  end

  def play({deck1, []}), do: {:p1, deck1}
  def play({[], deck2}), do: {:p2, deck2}

  def play({[card1 | rest1], [card2 | rest2]}) do
    cond do
      card1 > card2 -> play({rest1 ++ [card1, card2], rest2})
      card1 < card2 -> play({rest1, rest2 ++ [card2, card1]})
    end
  end

  def play_recursive({deck1, []}, _), do: {:p1, deck1}
  def play_recursive({[], deck2}, _), do: {:p2, deck2}

  def play_recursive(decks = {[card1 | rest1], [card2 | rest2]}, played) do
    cond do
      decks in played ->
        {:p1, elem(decks, 0)}

      card1 <= length(rest1) and card2 <= length(rest2) ->
        new1 = Enum.take(rest1, card1)
        new2 = Enum.take(rest2, card2)

        case play_recursive({new1, new2}, MapSet.new()) do
          {:p1, _} -> play_recursive({rest1 ++ [card1, card2], rest2}, MapSet.put(played, decks))
          {:p2, _} -> play_recursive({rest1, rest2 ++ [card2, card1]}, MapSet.put(played, decks))
        end

      card1 > card2 ->
        play_recursive({rest1 ++ [card1, card2], rest2}, MapSet.put(played, decks))

      card1 < card2 ->
        play_recursive({rest1, rest2 ++ [card2, card1]}, MapSet.put(played, decks))
    end
  end

  def calc_score(deck) do
    deck
    |> Enum.reverse()
    |> Enum.with_index(1)
    |> Enum.reduce(0, fn {card, i}, acc -> card * i + acc end)
  end
end

Mine ran for 20 minutes and never completed. I totally missed the rule that for recursive combat you have to take only a subset of the remaining cards (long as the drawn card), and not the entire remaining deck cards.

Simple one but has multiple places can be missed:

  • take only n cards in subgame
  • had exactly the same cards in the same order in the same players’ decks (I read as either, and failed miserably)

After reading the text I couldn’t resist, it felt like a too good fit for Erlang/Elixir to pass up.

My code

Nice and clean really liked this one !

I used :queue, but after reading @bjorng experience I may try and refactor to using lists to see if I get a performance boost - my part two is at ~750ms right now, so if I could get it to run twice as fast, that would be fun. I also ran into the issue where missing the rule about the subset of the deck for the recursive game caused an infinite loop, and then when I added that rule it, it was still just slow enough to make me sweat for a second

I would like to spend a little time making it a little easier to track whats happening since the recursive rules are a bit of a mess of nested conditionals right now…

Fastest I could get on my machine was ~150ms, I tried using ETS but that didn’t improve much, anyone got good optimization on this (part 2)?

I got mine down to ~225ms, but I dont see any other obvious ways to optimize from here - I tried to memoize decks between games, but that increased the run time.

1 Like

Oh, man, I thought this one was pretty easy, but then I couldn’t get it to run. Turns out I misread the subgame condition. I thought it was when at least one was equal to the remaining cards in the deck. That makes a pretty big difference. Overall, mine is pretty slow compared, but I think I’m fine for now.

Day 22

That rule got me too. Chanting that == to < made big difference!

1 Like

Hi there :wave:

Can anyone help me with my part2 code which seem to run indefinitely? (more than 60sec)
I read the instructions many times and I can’t figure out the problem.

Tahnks for your help!

Your solution finishes in about 80 seconds on my computer.

The culprit is your key/1 function:

def key(decks) do
    :crypto.hash(:md5, inspect(decks))
end

This key calculation will lead to a more compact key, but the key calculation is very expensive. By using the lists of the decks directly as the key:

def key(decks), do: decks

the runtime is reduced to less than a second on my computer.

1 Like

Oh thank you!
I was really sure I had an infinite loop issue, not an optimization one. Got it now

1 Like

On my computer, using decks as a key gives me the answer within 1.2s.
If I only use one deck as a key, I have the same answer in 100ms.
Don’t know if I’m lucky or not? (given a deck, can the other one be arranged in a different way?)

My code