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

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!