Robert Mion

Posted on

# Scratchcards

## Advent of Code 2023 Day 4

### Part 1

#### Seems pretty straightforward

1. Create two lists of numbers
2. Use `regex` to extract the numbers
3. Find their intersections, if any
4. Calculate 1 to the power of the number of intersections

##### 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(':')
.map(RA => [...RA.matchAll(/\d+/g)].map(el => +el[0]))
const intersection = winning.filter(
);
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.

#### 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

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]
.map(RA => [...RA.matchAll(/\d+/g)].map(el => +el[0]))
const intersection = winning.filter(
);
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!