Advent of Code 2020 - Day 22

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

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)

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

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…

https://github.com/camilleryr/advent20/blob/main/lib/day_22.ex

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