If you missed any previous days or are looking for another year, click here for all my content about that: Advent of Code, if you want to know why you should participate and try to code the solution for yourself, click here: Advent Of Code 2022 – 7 Reasons why you should participate. If you’re here to see the solution of this year’s Day 4, continue reading 😉
GitHub Repository
https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2023
I will upload all of my solutions there in the form of Python notebooks (.ipynb files), but you can copy paste the code into normal .py files, too. I am uploading the examples from the task as ‘example.txt’ files to test my solution. You will have to use your own ‘input.txt’ with your supplied input since everyone gets their own and everyone needs to provide a different solution based on their input.
Day 4 Puzzle
In this blog post I’ll describe the puzzle and solution steps, but if you want to jump ahead to said solution, you can do so here: https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2023/blob/main/Day01_Python/AdventOfCode_Day04_Python.ipynb
Here is the challenge, if you want to read the full puzzle: https://adventofcode.com/2023/day/4
In summary, on day 4 our newly fixed gondola brings us to another island and we ask about water sources. The elfves seem obsessed with games, because the ones on this island has little cards now. We need to help him with scratch cards that have number on them determining if you are winning something.
The puzzle input describes the cards:
Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11The first part before ‘|’ are the winning numbers and the second part are the numbers that we have drawn.
Here’s how I parse this input, just lots of splitting strings and converting to integers:
class CardGame:
def __init__(self, card_str: str):
card_part, numbers_part = card_str.split(':')
self.card_id = int(card_part.split(' ')[-1])
winning_part, drawn_part = numbers_part.split('|')
self.winning_numbers = [int(x) for x in winning_part.split(' ') if len(x) > 0]
self.drawn_numbers = [int(x) for x in drawn_part.split(' ') if len(x) > 0]Part 1
Now we have to compute the number of points we win for each card. The task tells us: “The first match makes the card worth one point and each match after the first doubles the point value of that card.” And “match” refers to each drawn number that is listed as a winning number.
So we simply count the matches by checking if they are in the winning list, then the points are simply:
2^{matches - 1} \\
2^{1 - 1} = 2^0 = 1 \\
2^{2 - 1} = 2^1 = 2 \\
2^{3 - 1} = 2^2 = 4The points double for each match and start at 1 point for one match, so the above formula works. Unless we have 0 matches because then the score is 0. So we add the compute_scores method to the CardGame class:
class CardGame:
def __init__(self, card_str: str):
# see above
def compute_score(self) -> int:
nr_of_wins = 0
for number in self.drawn_numbers:
if number in self.winning_numbers:
nr_of_wins += 1
if nr_of_wins == 0:
return 0
return 2**(nr_of_wins-1)The final solving method is then fairly straightforward combining these methods:
def solve_part1(input_file: str) -> int:
with open(input_file, "r") as f:
lines = f.readlines()
cards = [line.strip() for line in lines]
cards = [CardGame(card) for card in cards]
scores = [card.compute_score() for card in cards]
return sum(scores)Part 2
Alright, nooow all the winning cards “spawn” new cards. Only the cards that don’t have any winning numbers don’t spawn new cards. This is a problem that reminded me (and many redditors of the Lanternfish problem of 2021-Day 6. Basically it’s an exploding population of … cards. (It makes more sense when it’s animals procreating I guess). When each card spawns 3 new ones, and they in turn spawn 3 new ones and so on and so forth… You can see how you should definitely not model each card as an object – you will run out of memory in your computer.
Soooo what do we do instead? Well, first I adjust the CardGame object and use it to compute for each card type which new cards it spawns:
class CopyCardGame:
def __init__(self, card_str: str):
card_part, numbers_part = card_str.split(':')
self.card_id = int(card_part.split(' ')[-1])
winning_part, drawn_part = numbers_part.split('|')
self.winning_numbers = [int(x) for x in winning_part.split(' ') if len(x) > 0]
self.drawn_numbers = [int(x) for x in drawn_part.split(' ') if len(x) > 0]
self.won_cards = self.compute_won_cards()
def compute_won_cards(self) -> List[int]:
nr_of_wins = 0
for number in self.drawn_numbers:
if number in self.winning_numbers:
nr_of_wins += 1
return [self.card_id + wins for wins in range(1, nr_of_wins+1)]
def __repr__(self) -> str:
return f'CardGame(card_id={self.card_id}, won_cards={self.won_cards})'Count the number of matches again as in Part 1. But then we save the IDs of the spawned cards (For Card 2 with 3 matches, it will spawn one card of each IDs 3, 4 and 5 (that’s what I compute with the list comprehension of [self.card_id + wins for wins in range(1, nr_of_wins+1)]).
Important: We only create this object once for every of the starting cards. This will serve us as a finite look-up table.
The next important bit is that we keep track of the number of cards of each ID/type with a dict:
def solve_part2(input_file: str) -> int:
with open(input_file, "r") as f:
lines = f.readlines()
cards = [line.strip() for line in lines]
cards = [CopyCardGame(card) for card in cards]
card_counts = {card.card_id: 1 for card in cards}We will now create a queue to work through the cards and their spawns and only update this card_counts dict:
card_queue = deque([card.card_id for card in cards])
while card_queue:
card_id = card_queue.popleft()
won_cards = cards[card_id-1].won_cards
for won_card in won_cards:
card_counts[won_card] += 1
card_queue.extend(won_cards)
return sum(card_counts.values())A deque (from collections import deque) is simply a list that is more efficient for accessing the first and last elements. I’m not sure I need it here, but I used it last year and simply gotten used to using this instead of lists for this queue-activity.
- Initialize the queue with the initial cards from the input text
- Take out the first card with
popleft() - See which cards it spawns
- Append those to the queue
The queue will end at some point by design because some of the tasks have no winners. At the end simply add all the values (i.e. counts) from the dictionary.
Conclusion
If you know the trick that you should simply count the fish… ehm I mean cards… at each stage instead of modeling each on its own, this is actually quite a pleasant puzzle. If you don’t … well then it’s probably not as easy.
Overall, I think it’s a good reminder to consider which are the important parts of the data and how we can represent data in different structures depending on the use-case.