Part 1
[...]
The Elf leads you over to the pile of colorful cards. There, you discover dozens of scratchcards, all with their opaque covering already scratched off. Picking one up, it looks like each card has two lists of numbers separated by a vertical bar (|): a list of winning numbers and then a list of numbers you have. You organize the information into a table (your puzzle input).
As far as the Elf has been able to figure out, you have to figure out which of the numbers you have appear in the list of winning numbers. The first match makes the card worth one point and each match after the first doubles the point value of that card.
For example:
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
In the above example, card 1 has five winning numbers (41, 48, 83, 86, and 17) and eight numbers you have (83, 86, 6, 31, 17, 9, 48, and 53). Of the numbers you have, four of them (48, 83, 17, and 86) are winning numbers! That means card 1 is worth 8 points (1 for the first match, then doubled three times for each of the three matches after the first).
Card 2 has two winning numbers (32 and 61), so it is worth 2 points.
Card 3 has two winning numbers (1 and 21), so it is worth 2 points.
Card 4 has one winning number (84), so it is worth 1 point.
Card 5 has no winning numbers, so it is worth no points.
Card 6 has no winning numbers, so it is worth no points.
So, in this example, the Elf's pile of scratchcards is worth 13 points.
Take a seat in the large pile of colorful cards. How many points are they worth in total?
Each card clearly has two sets of numbers: the numbers owned and the winning numbers. To keep this information in a normalized way in a database there need to be two tables:
- "Player numbers" with card id (number) and number
- "Winning numbers" with card id (number) and number
When solving this puzzle I assumed that numbers only occur once per card, and as it turns out I would be right. For this reason I have added a composite primary key from card id and number.
CREATE TABLE PlayerNumbers (CardId int, Number int, PRIMARY KEY (CardId, Number));
CREATE TABLE WinningNumbers (CardId int, Number int, PRIMARY KEY (CardId, Number));While I did say that the puzzle would be solved in SQL, inserting the data in a database is a bit cumbersome in SQL and much easier to do in in other languages. I decided to read the input from a text file and insert the numbers with SQL commands in PowerShell. The fact that I can insert the numbers as they are and numbers are automatically casted to an integer in SQL server is very convenient here.
$filePath = "<path to input file>";
$connectionString = "<connection string>";
$connection = new-object System.Data.SqlClient.SQLConnection($connectionString);
$playerNumberQuery = $("INSERT INTO PlayerNumbers (CardId, Number) VALUES (@cardId, @number);");
$cmdPlayerNumbers = new-object System.Data.SqlClient.SqlCommand($playerNumberQuery, $connection);
$cmdPlayerNumbers.CommandTimeout = 0;
$winningNumberQuery = $("INSERT INTO WinningNumbers (CardId, Number) VALUES (@cardId, @number);");
$cmdWinningNumbers = new-object System.Data.SqlClient.SqlCommand($winningNumberQuery, $connection);
$cmdWinningNumbers.CommandTimeout = 0;
$connection.Open();
$input = [System.IO.File]::ReadAllLines($filePath);
$cardId = 1;
foreach ($inputLine in $input)
{
$winningNumbers = $inputLine.substring(10, 30);
$playerNumbers = $inputLine.substring(41, 75);
foreach ($number in ($winningNumbers -split "[\s]+"))
{
if($number -eq "") { continue; }
$cmdWinningNumbers.Parameters.Clear();
$cmdWinningNumbers.Parameters.AddWithValue("@cardId", $cardId);
$cmdWinningNumbers.Parameters.AddWithValue("@number", $number);
$cmdWinningNumbers.ExecuteNonQuery();
}
foreach ($number in ($playerNumbers -split "[\s]+"))
{
if($number -eq "") { continue; }
$cmdPlayerNumbers.Parameters.Clear();
$cmdPlayerNumbers.Parameters.AddWithValue("@cardId", $cardId);
$cmdPlayerNumbers.Parameters.AddWithValue("@number", $number);
$cmdPlayerNumbers.ExecuteNonQuery();
}
++$cardId;
}
$connection.Close();To find the player numbers that occur in the winning numbers we can join both tables together by card id and number. The amount of rows in each group equals the amount of numbers won. We use an inner join as cards without winning numbers are worthless anyway. From the puzzle description we can deduct a formula to calculate the points for each card:
The first match makes the card worth one point and each match after the first doubles the point value of that card.
In other words, the points of a card are powers of two and equal to 2^(amount of winning numbers - 1).
SELECT SUM(CardPoints) FROM
(
SELECT POWER(2, Count(*) - 1) CardPoints
FROM [WinningNumbers] wn
inner join [PlayerNumbers] pn on wn.Number = pn.Number and wn.CardId = pn.CardId
group by wn.CardId
) _;Part 2
Just as you're about to report your findings to the Elf, one of you realizes that the rules have actually been printed on the back of every card this whole time.
There's no such thing as "points". Instead, scratchcards only cause you to win more scratchcards equal to the number of winning numbers you have.
Specifically, you win copies of the scratchcards below the winning card equal to the number of matches. So, if card 10 were to have 5 matching numbers, you would win one copy each of cards 11, 12, 13, 14, and 15.
Copies of scratchcards are scored like normal scratchcards and have the same card number as the card they copied. So, if you win a copy of card 10 and it has 5 matching numbers, it would then win a copy of the same cards that the original card 10 won: cards 11, 12, 13, 14, and 15. This process repeats until none of the copies cause you to win any more cards. (Cards will never make you copy a card past the end of the table.)
This time, the above example goes differently:
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
Card 1 has four matching numbers, so you win one copy each of the next four cards: cards 2, 3, 4, and 5.
Your original card 2 has two matching numbers, so you win one copy each of cards 3 and 4.
Your copy of card 2 also wins one copy each of cards 3 and 4.
Your four instances of card 3 (one original and three copies) have two matching numbers, so you win four copies each of cards 4 and 5.
Your eight instances of card 4 (one original and seven copies) have one matching number, so you win eight copies of card 5.
Your fourteen instances of card 5 (one original and thirteen copies) have no matching numbers and win no more cards.
Your one instance of card 6 (one original) has no matching numbers and wins no more cards.
Once all of the originals and copies have been processed, you end up with 1 instance of card 1, 2 instances of card 2, 4 instances of card 3, 8 instances of card 4, 14 instances of card 5, and 1 instance of card 6. In total, this example pile of scratchcards causes you to ultimately have 30 scratchcards!
Process all of the original and copied scratchcards until no more scratchcards are won. Including the original set of scratchcards, how many total scratchcards do you end up with?
After using functional programming languages for a while, you start to look at problems from a different angle. When reading this sentence I immediately recognized it as a recursive problem, and it reminded me a bit of the "universes" from AOC 2021, day 21 (although this one is much simpler):
you win copies of the scratchcards below the winning card equal to the number of matches
Solving this problem recursively would happen as following:
FinalAmountOfCards(_id) = SUM of FinalAmountOfCards for cards where id < _id and id + WinningNumberCount does not surpass _id
In typical programming languages there can be some serious optimization techniques including memoization that would ultimately lead to complexity O(n). That alone deserves a dedicated article. If you feel so inspired: Fibonacci and Memoization
Although SQL does support different ways of recursion, and it would technically be possible to solve the puzzle this way, it's not so straightforward (I've tried). SQL is inherently a stateful language and we should use its benefits to our advantage.
We will create a temporary table to keep track of the winning number count and amount of cards per id. Because not every card has winning numbers, the inner join will not yield results for all cards and we first have to manually insert id's 1 to 201 (the amount of cards).
DECLARE @Cards table([CardId] int, [Count] int, WinningNumberCount [int]);
--ensure all cards 1..201 exist in the table
INSERT INTO @Cards
SELECT value, 1, 0
FROM GENERATE_SERIES(1, 201);
--SET the WinningNumberCount
with WinningNumberCounts as (
SELECT wn.CardId CardId, Count(1) cnt
FROM [WinningNumbers] wn
INNER JOIN [PlayerNumbers] pn on wn.Number = pn.Number and wn.CardId = pn.CardId
group by wn.CardId
)
UPDATE c
SET c.WinningNumberCount = wnc.cnt
FROM @Cards c INNER JOIN WinningNumberCounts wnc ON c.CardId = wnc.CardId;Now that the starting position is set up we can iterate over every card. During each iteration, every card within the range (id + 1 -> id + WinningCardCount) gets its count increased by the card count of the current id.
DECLARE @cardId int = 1;
WHILE(@cardId < 201)
BEGIN
UPDATE c1
SET c1.[Count] = c1.[Count] + c2.[Count]
FROM @Cards c1
INNER JOIN @Cards c2 ON c1.CardId > c2.CardId AND c1.CardId <= c2.CardId + c2.WinningNumberCount
WHERE c2.CardId = @cardId;
SET @cardId = @cardId + 1;
END
select SUM([Count]) from @Cards;