Advent of Code 2023 Day 4
Part 1
Seems pretty straightforward
- Create two lists of numbers
- Use
regex
to extract the numbers - Find their intersections, if any
- Calculate 1 to the power of the number of intersections
Ready...set...go!
Create two lists of numbers
I'll do two split
s:
-
split(':')
to separate the lists of numbers from the game id -
split('|')
to separate each list
Use regex
to extract the numbers
I'll use this simple regular expression:
/\d+/g
to match each number in the separate lists
Find their intersections, if any
Here's what I want to do:
For each item in the list of winning numbers
Check if there's a matching number in the list of numbers had
If it's a match, keep the number
That sounds like a combination of filter()
and includes()
.
Thankfully, it really is that simple care of this Stack Overflow answer:
const intersection = array1.filter(
value => array2.includes(value)
);
Power up and sum
Lastly, I just multiply 1 as many times as the length of the intersected array:
return 1 ** intersection.length
Ooops! I misunderstood that last step!
The instructions say to double the points each time, not multiply 1 some N number of times.
I started with this simple reduce()
:
intersections.reduce(total => total * 2, 1)
- Start at 1
- Double as many times as there are items in the array
Unfortunately, this starts with 1 point before the first item is touched. By the time it touches the second item, the points are already 2!
To rectify this, I halved the accumulated value:
intersections.reduce(total => total * 2, 1/2)
Unfortunately, this attributes 0.5
points to arrays with a single item, instead of 1
.
To account for that, I add a short ternary operation in the return statement of the outer reduce
.
Here's the combined algorithm in JavaScript:
input.reduce((sum, line) => {
const [, list] = line.split(':')
let [winning, had] = list.split('|')
.map(RA => [...RA.matchAll(/\d+/g)].map(el => +el[0]))
const intersection = winning.filter(
value => had.includes(value)
);
const points = intersection.reduce(total => total * 2, 1/2)
return sum + (points < 1 ? 0 : points)
}, 0)
Checking, submitting and hopefully celebrating
- It works on the example input!
- And it works on my puzzle input!
Woohoo!
Part 2
First impression
I get a little anxious when the Part 2 instructions are of equal length as Part 1.
That usually means the rules are about to change enough for the author to merit fully re-explaining the example input.
Ok. Time to read.
That escalated quickly
Day 4 is now Day 3 reversed: Easy Part 1, Hard Part 2.
I read it, then stepped away for a while.
All the while I thought about different ways of solving this.
I feel close to a smart way of solving that just involves counting, and not duplicating game strings.
But I have to walk through this one step at a time to ensure I fully understand how I'd write a program to solve it.
Walk with me
The example cards are:
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 11
Written as card-to-winning-number-counts:
1: 4
2: 2
3: 2
4: 1
5: 0
6: 0
Tracking instances, too:
1: {matches: 4, instances: 1}
2: {matches: 2, instances: 1}
3: {matches: 2, instances: 1}
4: {matches: 1, instances: 1}
5: {matches: 0, instances: 1}
6: {matches: 0, instances: 1}
For each card
For each instance
Increase the instance counter for the next N cards by 1
Where N is the matches counter for the current card
So, starting with Card 1:
- Do 1 time
- Increase the next 4 cards' instance counters by 1
Now the cards are:
1: {matches: 4, instances: 1}
2: {matches: 2, instances: 2}
3: {matches: 2, instances: 2}
4: {matches: 1, instances: 2}
5: {matches: 0, instances: 2}
6: {matches: 0, instances: 1}
Next, for Card 2:
- Do 2 times
- Increase the next 2 cards' instance counters by 1
Now the cards are:
1: {matches: 4, instances: 1}
2: {matches: 2, instances: 2}
3: {matches: 2, instances: 4}
4: {matches: 1, instances: 4}
5: {matches: 0, instances: 2}
6: {matches: 0, instances: 1}
Next, for Card 3:
- Do 4 times
- Increase the next 2 cards' instance counters by 1
Now the cards are:
1: {matches: 4, instances: 1}
2: {matches: 2, instances: 2}
3: {matches: 2, instances: 4}
4: {matches: 1, instances: 8}
5: {matches: 0, instances: 6}
6: {matches: 0, instances: 1}
Next, for Card 4:
- Do 8 times
- Increase the next 1 cards' instance counter by 1
Now the cards are:
1: {matches: 4, instances: 1}
2: {matches: 2, instances: 2}
3: {matches: 2, instances: 4}
4: {matches: 1, instances: 8}
5: {matches: 0, instances: 14}
6: {matches: 0, instances: 1}
Next, for Card 5:
- Do 14 times
- Increase the next 0 cards' instance counters by 1
The cards haven't changed
Next, for Card 6:
- Do 1 time
- Increase the next 0 cards' instance counters by 1
Finally, summing up all instances gets me:
- 30 cards
That's the right answer!
This algorithm works!
And I could optimize it by only funning the instance loop when the matches counter is greater than 0.
I think I'm ready to write this thing.
Writing the algorithm
First, I must make the cards dictionary.
The code is nearly identical to Part 1.
const cards = input.reduce((cards, line) => {
let [id, list] = line.split(':')
id = +id.match(/\d+/)[0]
let [winning, had] = list.split('|')
.map(RA => [...RA.matchAll(/\d+/g)].map(el => +el[0]))
const intersection = winning.filter(
value => had.includes(value)
);
cards[id] = {
matches: intersection.length,
instances: 1
}
return cards
}, {})
Next, I have to iterate through each card and update the instance counters:
for (let card in cards) {
if (cards[card].matches > 0) {
for (let i = 0; i < cards[card].instances; i++) {
for (let m = 1 ; m <= cards[card].matches; m++) {
cards[+card + m].instances++
}
}
}
}
Lastly, I have to extract and sum up all instance values:
Object.values(cards)
.map(card => card.instances)
.reduce((sum, current) => sum + current)
Checking, submitting and celebrating
- It worked on the example input
- And it worked on my puzzle input!
Wow, that turned out to be a lot easier than I first imagined.
I'm glad I stepped away and thought carefully about only the important values that needed tracking.
What a fun Part 2 puzzle!
Bring it on, Day 5!
Top comments (0)