A Puzzling Array of Scratchcards

Day 4 whisked us away to Island Island, where we encountered an Elf and a pile of scratchcards. Each card contained numbers, and our task was to calculate their total points based on a matching system.

Our Solution

We dove into this challenge by crafting a function in TypeScript that iterated through each card to calculate its point value.

Part One: Calculating Scratchcard Points

export default function partOne(cards: string[]): number {
  const digits = /\d+/g;

  return cards.reduce((totalPoints, card) => {
    const [winningCard, myCard] = card.split(":")[1].split("|");
    const winningNumbers = winningCard.match(digits);
    const myNumbers = myCard.match(digits);

    if (!winningNumbers || !myNumbers) return totalPoints;

    const cardPoints = winningNumbers.reduce((cardPoints, winningNumber) => {
      if (!myNumbers.includes(winningNumber)) return cardPoints;
      return cardPoints ? cardPoints * 2 : 1;
    }, 0);

    return totalPoints + cardPoints;
  }, 0);
}

In our approach, we split the card information into winning numbers and the player’s numbers. Then, we checked for matches, applying the game’s rule that the first match is worth one point, with each subsequent match doubling the card’s value.

Complexity Analysis

The function iterates through each card (O(n)) and then through each set of winning numbers for every card (O(m)). Assuming n is the number of cards and m is the average number of winning numbers per card, the overall complexity is approximately O(n * m).

Part Two: An Expanding Array of Scratchcards

Continuing from our previous scratchcard challenge, we discovered new rules that transformed our approach. Instead of calculating points, we now focused on tracking the number of scratchcards won, with each card potentially unlocking more.

export default function partTwo(cardArray: string[]): number {
  const digits = /\d+/g;

  // Create a map (object) to keep track of the count of each scratch card.
  // Initially, each card count is set to 1.
  const cardCounts: Record<number, number> = {};
  cardArray.forEach((_, index) => (cardCounts[index] = 1));

  // Loop through each card in the array. The reduce method accumulates the total
  // number of cards (including the ones won).
  return cardArray.reduce((totalCards, card, index) => {
    const [winningCard, myCard] = card.split(":")[1].split("|");
    const winningNumbers = winningCard.match(digits);
    const myNumbers = myCard.match(digits);

    if (!winningNumbers || !myNumbers) return totalCards;

    // Count the number of matches (i.e., the same numbers) between the winning card and my card.
    const numOfMatches = winningNumbers.filter(number =>
      myNumbers.includes(number)
    ).length;

    // For each instance of the current card, check if there are additional copies won.
    while (cardCounts[index] > 0) {
      // For each match, increment the count of subsequent cards by 1.
      for (let i = 1; i <= numOfMatches; i++) {
        cardCounts[index + i]++;
      }

      // Decrement the count of the current card, as it's been 'used',
      // and increment the total number of cards processed.
      cardCounts[index]--;
      totalCards++;
    }

    return totalCards;
  }, 0);
}

We introduced a map to keep track of the count of each scratch card and iterated through the card array. For each card, we calculated the number of matches and updated the counts of subsequent cards based on these matches, simulating the “winning” of additional cards.

The Evolution of My Code

As with many challenges in Advent of Code, the journey from initial solution to a refined, efficient version is often as revealing as solving the puzzle itself. In the case of Day 4, Part Two, my original solution, while successful in earning the star, was far from optimal in terms of execution speed.

The Initial Approach

When first tackling the puzzles, my strategy focuses primarily on finding a solution that works, irrespective of its performance. This approach ensures that I grasp the core concepts and logic required to solve the problem. It’s about laying the groundwork and understanding the mechanics of the challenge.

The Art of Refactoring

Once the initial solution is in place, the fascinating process of refinement begins. For this particular scratchcard challenge, my original code took approximately 37 seconds to run - a duration that hinted at significant room for improvement.

Through careful analysis and optimization, I was able to drastically enhance the performance of my code. By optimizing the logic and streamlining the computation process, I reduced the execution time to a mere 77 milliseconds. This dramatic improvement underscores the importance of revisiting and refining one’s code.

My Coding Philosophy

This practice of solving first and refining later has become my cornerstone strategy for Advent of Code. It allows me to separate the problem-solving aspect from optimization, leading to clearer thought processes and more creative solutions initially. The subsequent refactoring phase then becomes an opportunity for learning and growth, allowing me to explore more efficient algorithms and coding practices.

Conclusion

As we continue with more puzzles, remember that the journey from an initial solution to a refined one is a path filled with learning opportunities. It’s a process that not only leads to better code but also to a better understanding of programming itself.

Stay tuned as we navigate more exciting challenges in the Advent of Code!