Scratchcards
Tags: adventofcode, javascript, algorithms, programming
Published: 2023-12-06 00:08:33

## [Advent of Code 2023 Day 4](https://adventofcode.com/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 `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](https://stackoverflow.com/a/1885569):
```js
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:
```js
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:
```js
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.

```js
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:
```js
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:
```js
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!