In today’s puzzle, you get find all the winners on a set of lottery tickets. If you are under the age of 18, don’t worry — minors can receive lottery tickets as gifts.
As always, I encourage you to read the actual problem description yourself — what appears here is a short summary.
Your input consists of lottery cards, one per line. Each card is identified by a number, and has two lists of numbers on it, separated by a vertical bar:
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 set of numbers are the playing numbers on your cards — the second is the list of winning numbers for that card. It’s up to you to find the winners among your numbers on each card. The first winner you find counts for one point — each subsequent winning number doubles the score for that card. Add up all the winning scores for all your cards for the right answer.
Approach
My first observation was that the score for any card was a power of two:
| Number of winners | Score | Power of two |
|---|---|---|
| 1 | 1 | $2^0$ |
| 2 | 2 | $2^1$ |
| 3 | 4 | $2^2$ |
| 4 | 8 | $2^3$ |
| 5 | 16 | $2^4$ |
This makes calculating the score for each card easy — it’s 2 to power of the number of winners minus 1, or $2^{w-1}$. Now all I need is the number of winners for each card…
To figure that out, I used two Vecs for each card — one to hold my play numbers, and one to hold the winning numbers. Once I parsed the numbers for a single card, I loop over my play numbers and count how many are in the winning numbers Vec:
fn count_winners(&self) -> usize{
let mut count = 0;
for num in &self.play{
if self.winning.contains(&num){
count += 1;
}
}
count
}In hindsight, I could have done this with two HashSet<> structures, then used an .intesection() to find which numbers were common to each. Let’s continue assuming I wasn’t that smart at the time (which I wasn’t)…
To make things a bit easier, I created a Card struct (hence the &self reference) and implemented most of the logic to count the winners and calculate the scores there. Unlike Day 3, this actually did make things much easier.
One way it made things easier was my implementation of from_str() to read each line and create a new Card. That made the main part one code a simple loop over each line of input:
fn part1(lines: &Vec<String>) -> usize{
let mut sum = 0;
for line in lines{
let mut card = Card::from_str(line).unwrap();
sum += card.score();
}
sum
}Part 2 – Copies of cards
Of course, this isn’t good enough for part 2. Oh no it is not. This time, the complication is two fold.
First, the score for each card is just the number of matches you have — no doubling is needed. (OK, so this is technically a simplification, but it’s so the rest of part 2 can be complicated.)
The actual complication is that the score for each card isn’t a score anymore — it’s the number of subsequent cards you win and add to your stash.
That requires some explanation.
Assume Card #1 matches 2 numbers. This means you now win two new cards, which are copies of subsequent cards. In this case, you win a copy each of Cards #2 and #3.
Let’s further assume Card #2 also matches two numbers. Since you have two copies of Card #2 (your original, and the copy you just won from Card #1), you now get two copies each of Card #3 and Card #4. This means you now have three copies of Card #3 and two of Card #4 so far.
Your task is now to count how many total cards you get once you process all the cards you have, plus all the cards you won.
Got it? Good.
Now, the naive solution is to process the cards you win as you win them. This can work, but it will be time and memory consuming. Where do you store all those extra cards?
There is a better way, but you need to examine the problem a little differently.
I observed that the matches for each card, whether original or a copy, was the same. This means I only need to calculate the score for each card once, which I did, stuffing all the results in one new Vec:
// Figure out how many winners each card has
for line in lines{
let mut card = Card::from_str(line).unwrap();
card.winners = card.count_winners();
cards.push(card)
}I can use this data to figure out which new cards I’ve won.
I made a second observation from the example above, and that is that you never win more copies of the current card.
Think about it. When I figured out the score to Card #1, I won two new cards — Card #2 and Card #3. I never won another Card #1.
Similarly, for Card #2, I won new copies of Card #3 and Card #4, never Card #2.
At every step, I’m always winning at best the next card.
Why is that important? You’ll see in a minute.
I need to track exactly how many of each card I have — since I started with one each, I initialized another Vec with this info:
// The count for each card
let mut card_count = vec![1;cards.len()];Here’s why winning only the next card matters. I can now loop through cards, and get the number of .winners. Then, starting the next card (in this case current_card+1), I add however of current_card I have to card_count[next_card].
It’s actually easier to understand in code:
// Loop over the entire card list
let mut current_card = 0;
while current_card < cards.len().try_into().unwrap(){
// How many winners on this card?
let current_winners = cards[current_card].winners as usize;
// We add the total count of the current card to all the winners
for next_card in current_card+1..current_card+current_winners+1{
card_count[next_card] += card_count[current_card];
}
current_card += 1;
}I’m using current_card as in index into both the cards and card_count vectors. This lets me do the proper counting of the number of winners.
With what I learned later, I probably could have simplified this with .enumerate() to get both the index and the current card from cards. It’s a failing of mine that I don’t use that more often — in my defense, I learned how to iterate over a loop well before object-oriented programming was taught in school, and so my thinking still drops back to old methods.
Summary
I’m interested on your thoughts on my approach and my code — drop me a note below!
My own thinking led me to possibly more complicated code than I needed, but the algorithm is sound and runs very quickly. I’m leaving the code as is for now as a learning moment, and to give me something to improve upon later.