# Advent of Code 2020: Day 22

I’m asked to play out a game between two players that in part one looks like the classic card game of war, and in part two goes off in a different direction of “recursive combat”. Both parts came together pretty quickly, though part two had a few places where small mistakes made identifying mistakes difficult.

## Challenge

The puzzle can be found here. I’m given two decks and a set of rules very similar to the classic game of war (though this game managed to avoid two players ever having the same card). Each deck takes the top card, and the higher card gets both back onto the bottom of that deck, with the winning card first.

In part two, there’s an extra check. The top cards are checked. This time, if each player has enough cards, they clone that many cards from the top of their deck, and enter those decks into a new game. If either player doesn’t have enough, the higher card wins. There is a check in here for infinite loops as well.

## Solution

### Part 1

My program created both decks,and then loop over them while they both have cards, comparing the top cards, and putting both onto the bottom of the winner:

```
with open(sys.argv[1], 'r') as f:
raw_decks = f.read().strip().split('\n\n')
decks = [list(map(int, deck.split('\n')[1:])) for deck in raw_decks]
while all(decks):
c0, c1 = [d.pop(0) for d in decks]
if c1 > c0:
decks[1] += [c1, c0]
elif c0 > c1:
decks[0] += [c0, c1]
else:
raise
```

When this loop exists, one of the decks will have no cards. I can get the winning deck with `max`

, and then use the score algorithm provided to find the result:

```
winner = max(decks)
part1 = sum([f*c for f,c in zip(range(len(winner), 0, -1), winner)])
print(f'Part 1: {part1}')
```

### Part 2

In part two I’ll make a recursive function to handle the game. It’s important to think about what is being passed here. For example, originally I was tracking rounds by having a list and adding the decks to it. But then as the decks changed, so did the contents in rounds. I could use `deepcopy`

here, but I opted to just create a string from the current state and store that. When I pass the subdecks into the new recursive game, because I’m slicing out of the array, it is actually creating a new copy, so I don’t have to worry about `deepcopy`

there either.

```
def rec_comb(decks):
rounds = set()
while all(decks):
r = '-'.join([str(d) for d in decks])
if r in rounds:
return [decks[0], []]
rounds.add(r)
c0, c1 = [d.pop(0) for d in decks]
if c0 <= len(decks[0]) and c1 <= len(decks[1]):
result = rec_comb([decks[0][:c0], decks[1][:c1]])
winner_is_1 = bool(result[1])
else:
winner_is_1 = c1 > c0
if winner_is_1:
decks[1].extend([c1, c0])
else:
decks[0].extend([c0, c1])
return decks
# Same starting decks
decks = [list(map(int, deck.split('\n')[1:])) for deck in raw_decks]
res = max(rec_comb(decks))
part2 = sum([f*c for f,c in zip(range(len(res), 0, -1), res)])
print(f'Part 2: {part2}')
```

### Final Code

Part one is quick, but part two runs for twenty seconds:

```
$ time python3 day22.py 22-puz
Part 1: 33473
Part 2: 31793
real 0m20.376s
user 0m20.097s
sys 0m0.209s
```

```
#!/usr/bin/env python3
import sys
with open(sys.argv[1], "r") as f:
raw_decks = f.read().strip().split("\n\n")
decks = [list(map(int, deck.split("\n")[1:])) for deck in raw_decks]
while all(decks):
c0, c1 = [d.pop(0) for d in decks]
if c1 > c0:
decks[1] += [c1, c0]
elif c0 > c1:
decks[0] += [c0, c1]
else:
raise
winner = max(decks)
part1 = sum([f * c for f, c in zip(range(len(winner), 0, -1), winner)])
print(f"Part 1: {part1}")
def rec_comb(decks):
rounds = set()
while all(decks):
r = "-".join([str(d) for d in decks])
if r in rounds:
return [decks[0], []]
rounds.add(r)
c0, c1 = [d.pop(0) for d in decks]
if c0 <= len(decks[0]) and c1 <= len(decks[1]):
result = rec_comb([decks[0][:c0], decks[1][:c1]])
winner_is_1 = bool(result[1])
else:
winner_is_1 = c1 > c0
if winner_is_1:
decks[1].extend([c1, c0])
else:
decks[0].extend([c0, c1])
return decks
# Same starting decks
decks = [list(map(int, deck.split("\n")[1:])) for deck in raw_decks]
res = max(rec_comb(decks))
part2 = sum([f * c for f, c in zip(range(len(res), 0, -1), res)])
print(f"Part 2: {part2}")
```