This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.
This exercise consists of a simulation of a card game. We get as input two decks, each a sequence of integers (the values of the cards), for the two players. We read that in two stages, one per player, skipping the headers (that´s the purpose of the line = next(f) lines). We store the decks as deques, as we will be adding and removing items on both ends. We use appendleft to add the cards, so that the topmost one is at the end (so it can be popped).
Part 1
The game is quite straightforward. We play until one of the decks runs out (the condition for the while). In each step, we remove the topmost card from each deck, compare and put both at the end of the winner's deck. By keeping the same deque objects all the time we can check the winner by checking the ID of the deck (winner is deck1).
Since that is the way we check for the winner, we need to return the deck that still has cards, that's the winner. The line return deck1 or deck2 works exactly like that combining Python's truthiness evaluation and short-circuiting or.
Part 2
We now have a recursive version of the game.
The first difference is that we need to keep track of the states at different stages. We will keep them in a set, and represent each state as a tuple of two elements, each a tuple version of each deck. With that we can check at each step the winning condition of repeating a state.
The other difference is that, when we draw the cards, we check their values against the number of cards in the decks, and if either deck has fewer cards than the value of its current playing card we go into the recursive game. Otherwise, we play the usual game as before.
The recursive game is, as it would appear, just a recursive call to the game. We just need to be careful to use a copy of the decks for the recursive game, and check the winner against these copies.
No comments:
Post a Comment