advent of code - day 4

2023-12-04

See the puzzle here.

See my full solution here.

Part 1

Part 1 was really easy. Just parse each line, look for repeat numbers before and after the line, and add up the score.

The only thing that tripped me up was initially I split the line on a space, but there is more white space in some lines than others, so I needed to split like this instead:

const tokens = line.split(/[ ]+/);

Part 2

Part 2 was where it really got interesting.

I'm sure there are a variety of ways to solve part 2, but what felt most natural to me was a dynamic programming solution with recursion and memoization. For those of you that remember hearing about this in college and promptly let it leave your head: this is when you cache/store the results of sub-problems so that you don't have to recompute them later. This is a great technique to use when you have a function that is called multiple times with the same input, and you want to avoid doing the same work over and over.

This is the most important part of the solution:

let memo = {};

 const getTotalCountForCard = (card) => {
 if(card.wins === 0) {
  return 1;
 } else if(memo[card.cardNum] != undefined) {
  return memo[card.cardNum];
 } else {
  let wins = 1;
  for(let i=0; i    wins += getTotalCountForCard(originalCards[card.cardNum+i+1]);
  }
  memo[card.cardNum] = wins;
  return wins;
 }
}

file.on('close', () => {
 let wins = 0;
 for(let i=0; i   wins += getTotalCountForCard(originalCards[i]);
 }
 console.log(wins);
});

(Higher up in the actual solution I calculate the score for each card, and then create an array of each card with its score that I use here.)

Basically, the base case of this recursive function is when a card has no wins. In that case, the card only counts itself.

If the card has wins, we either fetch the total tree of cards from the cache, or we calculate it recursively. Once we have a total for a particular card, we cache it for later so we don't have to recompute it again.