Advent of Code 2023: Day 4 - Scratchcards

Day 4 Scratchcards

Table of Contents

AoC Problem
General Concept
Solution

Today's challenge was a little easier than yesterday's, however, the instructions boggled my brain a bit. The concepts weren't difficult to solve, it was more the way they explained it (more so around the doubling/scoring within part 1).

Being dyslexic there was a lot to read and go through in Part 2, some of which could have been simplified/broken down into smaller chunks (it took a few reads).

General Concept:

Part 1:
So the basic gist of the problem was to parse lines of text into two columns of numbers, winning lottery numbers, and ones I'd picked myself.

Then had to work out how many matching numbers you had. For every matching number, you gained a score based on the provided scoring system.

Part 2:

In Part 2 scoring wasn't a problem, you simply had to count how many scratch cards you had at the end, with the complicated requirement that rather than winning points for each matching number, you won more scratch cards to the sum of winning numbers. The sum was used to count down the next cards and duplicate them

Win 5 cards off card 1 -> The next 5 cards were duplicated, meaning you could win off of them again.

You then would have to include the duplicated cards + their winning numbers and subsequent copied cards in the total and so on... you can see this can be quite hard to get your head around (however explaining it is much harder).

Solution:

as always this can be found on my Github repo, which you can then use for learning and tweaking your solution.

var samplePath = "./sample.txt";
var sample2Path = "./sample2.txt";
var inputPath = "./input.txt";

var lines = File.ReadAllLines(sample2Path);
Part1();
Part2();

void Part1()
{
  Card[] cards = lines.Select(ParseLine).ToArray();
  int accumulativeTotal = cards.Sum(card =>
  {
    int count = card.WinningNumbers.Intersect(card.MyNumbers).Count();
    if (count > 0)
    {
      // double the 3rd numbers onwards
      int points = Enumerable.Range(0, count).Sum(i => i < 2 ? 1 : 2 << (i - 2));
      return points;
    }
    return 0;
  });

  Console.WriteLine($"Part1: {accumulativeTotal.ToString()}");
}

void Part2()
{
  var input = File.ReadAllLines(inputPath);
  // initialize the array - each card has at least one.
  int[] cardCount = Enumerable.Repeat(1, input.Length).ToArray();

  // loop over each card
  for (int cardId = 0; cardId < input.Length; cardId++)
  {
    string? line = input[cardId];
    var card = ParseLine(line);

    // collect number of winning numbers as before.
    var matchCount = card.WinningNumbers.Intersect(card.MyNumbers).Count();

    // for the number of wins, update any cards with extras.
    for (int i = 0; i < matchCount; i++)
    {
      cardCount[cardId + 1 + i] += cardCount[cardId];
    }
  }

  Console.WriteLine(cardCount.Sum());
}


Card ParseLine(string line)
{
  var parts = line.Split(':');
  var numbers = parts[1].Split('|');
  var winningNumbers = ExtractNumbers(numbers[0]);
  var myNumbers = ExtractNumbers(numbers[1]);

  return new Card(winningNumbers, myNumbers);
}

int[] ExtractNumbers(string input)
{
  return input.Split(' ', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries)
       .Select(int.Parse)
       .ToArray();
}
record Card(int[] WinningNumbers, int[] MyNumbers);

Let's break it down a bit shall we:

Part 1:

Firstly its a simple method to use the loaded in text, in string[] format, and then use Linq Select to run ParseLine against each line.

The ParseLine method, simply splits on the relevant characters, removing any whitespace. Storing the values in a Card record, to allow for easy access in the next steps.

Card[] cards = lines.Select(ParseLine).ToArray();

The next part is the meat and 2 veg of the solution.

The Sum method on an array allows us to run a transform function against each element in the array, to return an integer which will be added up at the end.

We can use the Intersect method, which will find all the duplicated values in one array in the other. We can then get this count, and use it to apply the scoring system.

int accumulativeTotal = cards.Sum(card =>
  {
    int count = card.WinningNumbers.Intersect(card.MyNumbers).Count();
    if (count > 0)
    {
      // double the 3rd numbers onwards
      int points = Enumerable.Range(0, count).Sum(i => i < 2 ? 1 : 2 << (i - 2));
      return points;
    }
    return 0;
  });

Scoring system

So we're told that

1st match = 1 point
2nd match = 1 point

and then for every match after that, the score is doubled, meaning that:

3rd match = 2 points
4th match = 4 points
5th match = 8 points and so on.

Enumerable.Range generates a sequence of numbers from 0 to count - 1. E.g from 0 -> lets say 4 matches.

We then use the Sum extension method again, to compute the score for each number (match).

The expression within the Sum method, uses a ternary operator to avoid the 1st two matches being doubled, these are thus allocated 1 point each.

Anything after that is then doubled. This is done using the bitwise left-shift operator. If you know how this works already, you can skip the next part.

Put simply, this operator will shift the binary value of your number to the left, to the power of your provided number. So we can use this to double our number.

Example:
In our code, it shifts the bits of the number 2 to the left by (i - 2) positions.

If i is 2, it shifts by 0 positions (as the result is a negative number), resulting in 2.

If i is 3, it shifts by 1 position, resulting in 4.

If i is 4, it shifts by 2 positions, resulting in 8.

int originalNumber = 7; // Binary: 0111
int shiftedNumber = originalNumber << 2; // Shifting left by 2 positions

Console.WriteLine(Convert.ToString(shiftedNumber, 2)); // Output: 11100

The original binary representation of 7 is 0111.
After applying the left shift operator (<< 2), each bit is shifted two positions to the left.

The result is 11100, which is 28 in decimal.

You don't have to fully understand it, but just know the general gist that it can be used to alter numbers easily. Save it as a snippet, and use it in the future.

Remember the syntax:
{starting number} << number of positions to shift

Part 2:

Part 2 was a little more complex (or at least the problem explanation was). However, the solution was pretty straightforward.

We just had to keep track of how many cards had been won and increment this amount each time we looped over the cards, based on how many cards we'd won from original and copied cards.

Which was all done within this small for loop.

// for the number of wins, update any cards with extras.
    for (int i = 0; i < matchCount; i++)
    {
      cardCount[cardId + 1 + i] += cardCount[cardId];
    }

Then it's just a case of summing up the totals using Sum again.

As alwways give me a follow here for more articles, and jump over to twitter and give me a follow there to have a chat, discuss all things tech and get to know me more.