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
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
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:
After reading the text I couldn’t resist, it felt like a too good fit for Erlang/Elixir to pass up.
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.
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.
That rule got me too. Chanting that ==
to <
made big difference!
Hi there
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.
Oh thank you!
I was really sure I had an infinite loop issue, not an optimization one. Got it now
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?)