DEV Community

Cover image for Scratchcards
Robert Mion
Robert Mion

Posted on

Scratchcards

#adventofcode #javascript #algorithms #programming

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

Ready...set...go!

Create two lists of numbers

I'll do two splits:

  • 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
Enter fullscreen mode Exit fullscreen mode

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) );
Enter fullscreen mode Exit fullscreen mode
Power up and sum

Lastly, I just multiply 1 as many times as the length of the intersected array:

return 1 ** intersection.length
Enter fullscreen mode Exit fullscreen mode
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)
Enter fullscreen mode Exit fullscreen mode
  • 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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Written as card-to-winning-number-counts:

1: 4 2: 2 3: 2 4: 1 5: 0 6: 0
Enter fullscreen mode Exit fullscreen mode

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}
Enter fullscreen mode Exit fullscreen mode 
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
Enter fullscreen mode Exit fullscreen mode

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}
Enter fullscreen mode Exit fullscreen mode

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}
Enter fullscreen mode Exit fullscreen mode

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}
Enter fullscreen mode Exit fullscreen mode

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}
Enter fullscreen mode Exit fullscreen mode

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 }, {})
Enter fullscreen mode Exit fullscreen mode

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++ } } } }
Enter fullscreen mode Exit fullscreen mode

Lastly, I have to extract and sum up all instance values:

Object.values(cards) .map(card => card.instances) .reduce((sum, current) => sum + current)
Enter fullscreen mode Exit fullscreen mode

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)