Advent of Code 2023 Day 7
Part 1
A mega-sort() feat. regex
The task: sort all the hands in order from biggest winner to biggest loser.
That's determined by two criteria:
- The type of hand
- The highest card from left-to-right in the case of same hand type
Solving for the second criteria will probably require 'walking' the string.
Solving for the first criteria will either require regex or a dictionary breakdown of the cards and number of occurrences.
I'll start by trying to make regexs for each hand type.
The goal: seven regexs
1. Five of a kind
All five characters must be the same:
/(.)\1{4}/g
-
(.)- Match any character and store as a capture group -
\1{4}- Match that same character exactly four times immediately after
2. Four of a kind
This is trickier because the odd one out could be anywhere:
-XXXX
X-XXX
XX-XX
XXX-X
XXXX-
This seems to work, although it feels overly complicated (like almost every regex, amiright?):
/.*(.).*\1.*\1.*\1.*/g
-
.*Match 0 or more of any character -
(.)Match any character and save as a capture group -
\1Match the capture group
Using regexr.com it at least appears to work as expected.
Solving with a dictionary
I could also count each character in the string and check if any of them is 4.
I'd be looking for this blueprint of an object:
{ X: 4, Y: 1 }
This will feel more reliable than regex for the remaining types.
3. Full house
Three of one character and two of another.
My dictionary blueprint would need to look like this:
{ X: 3, Y: 2 }
And with regex, this may require multiple tests:
- For three of a kind
- For the unmatched characters to be the same
That feels really complicated.
I'll stick with my dictionary.
4. Three of a kind
My dictionary would make this easy to find:
{ X: 3, Y: 1, Z: 1 }
5. Two pair
Again, dictionary for the win:
{ X: 2, Y: 2, Z: 1 }
6. One pair
Again, dictionary for the win:
{ X: 2, Y: 1, Z: 1, W: 1 }
7. High card
Again, dictionary for the win:
{ X: 1, Y: 1, Z: 1, W: 1, V: 1 }
Accounting for Five of a kind
Again, dictionary for the win:
{ X: 5 }
This dictionary feels like a winning approach for determining each hand's type.
Moving on to sorting similar hand types.
Which hand of the same type is stronger?
This is determined by the order of cards:
[A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, 2]
When comparing any two, I'll just compare indices:
J vs 5
3 9
<
!
The stronger card has the lower index.
For equal indexed cards, I need to 'walk' to the next card.
I'm led to believe there are no duplicate hands in my input.
Sorting weakest to strongest
The weakest hand gets rank 1 - resulting in a smaller product of bid and rank compared to stronger hands.
Sorting algorithms work by comparing two values and returning one of three numbers to determine the resulting order:
-
-1moves the first value earlier than the second -
0keeps the original order -
1moves the first value after the second
So, once I determine a hand's type, I want to assign it the appropriate strength.
I'll do that using the numbers 0-7:
Five of a kind: 7
Four of a kind: 6
...
High card: 0
That way, stronger hand types will get moved later in the list, ranking higher.
I think that's right.
I'm sure I'll find out when writing my algorithm whether I have this backwards or not.
I'm ready to start writing the algorithm!
Piecing together a hopefully working algorithm
First, counting how many of each card:
function countingCards(line) {
let [hand, bid] = line.split(' ')
let counts = hand.split('').reduce((dict, card) => {
if (!(card in dict)) dict[card] = 1
else dict[card]++
return dict
}, {})
}
To determine each hand's strength, I first need a legend to look up each hand type that is ordered from weakest to strongest:
const handStrengths = [11111, 2111, 221, 311, 41, 32, 5]
Then, my algorithm must convert the generated dictionary into a number representing the counts of each card:
function getStrengthOf(line) {
let [hand, bid] = line.split(' ')
let counts = hand.split('').reduce((dict, card) => {
if (!(card in dict)) dict[card] = 1
else dict[card]++
return dict
}, {})
const handStrengths = [11111, 2111, 221, 311, 41, 32, 5]
const strength = handStrengths
.indexOf(
parseInt(
Object.values(counts).sort((a, b) => b - a).join('')
)
)
return strength
}
Running it on the example input puts the cards in the right order before accounting for hands of the same type.
So, I think I'm on the right track!
Next, for hands of the same strength, I have to check as many cards necessary until I find different values.
function findWinningCard(a, b) {
let strengths = [2,3,4,5,6,7,8,9,'T','J','Q','K','A']
let hand1 = a.split(' ')[0]
let hand2 = b.split(' ')[0]
let index = 0
while (hand1[index] === hand2[index]) {
index++
}
return strengths.indexOf(hand1[index]) - strengths.indexOf(hand2[index])
}
That returns a number that is less than or greater than 0, thereby sorting both cards appropriately.
Back in my sort(), the logic is pretty simple:
input.sort((a, b) => {
let s1 = getStrengthOf(a)
let s2 = getStrengthOf(b)
if (s1 !== s2) return s1 - s2
else return findWinningCard(a, b)
})
Running it again produces the correctly sorted list for the example input!
Calculating the sum of the rank-bid products should be easy now:
input.sort((a, b) => {
let s1 = getStrengthOf(a)
let s2 = getStrengthOf(b)
if (s1 !== s2) return s1 - s2
else return findWinningCard(a, b)
}).reduce(
(total, line, index) => total += (index + 1) * parseInt(line.split(' ')[1])
}, 0
)
Is it gonna work?
- It generates the correct answer for the example input!
- Darn: my answer is too low for my puzzle input
What might I be doing wrong?
Turns out, it was two silly errors:
- In my legend of ordered card types, I used numbers instead of strings. This confused my algorithm because it was always looking for string values
- In my legend of ordered hand types, I mistakenly had Full House ranked higher than Four of a Kind
After spotting these errors, I re-ran my algorithm on my puzzle input and generated an answer that was higher than my original submission.
Was it right?
YES!!!
Phew. I'm glad I took the time to inspect everything and debug my algorithm.
It's often silly errors like this that are the root cause of a wrong answer.
Part 2
Joker! What an excellent twist!
I have a hypothesis for how to algorithmically deduce the best possible mutated hand:
- Still count up each card type in the hand
- If there any J's...
- Reduce the number of J's to 0...
- And increase the largest count amount by that same number
How does this work?
Let's explore all six hand types
High card with one Joker:
XYZWJ
11111
-1
+1
2111
It becomes one pair
One pair of Jokers:
JJXYZ
2111
-2
+2
311
It becomes three of a kind
One pair with one Joker:
XXYZJ
2111
-1
+1
311
It becomes three of a kind
Two pair with Jokers:
XXJJY
2 21
-2
+2
41
It becomes four of a kind
Full house with Jokers:
XXXJJ
32
-2
+2
5
It becomes five of a kind
Three of a kind Jokers:
JJJXY
311
-3
+3
41
It becomes four of a kind
Four of a kind with one Joker:
XXXXJ
41
-1
+1
5
It becomes five of a kind
Four of a kind Jokers:
JJJJX
41
-4
+4
5
It becomes five of a kind
After working through each of these, I'm feeling really confident that this is a winning strategy.
How am I going to perform this dictionary value arithmetic, though?
Using Jokers to make the best hand type
if ('J' in counts) {
let Js = counts['J']
delete counts['J']
let max = Math.max(...Object.values(counts))
let target = Object.entries(counts).find(item => item[1] == max)[0]
counts[target] += Js
}
An explanation in pseudocode:
If the dictionary mapping alphanumeric characters to counts has a J as a key
Save the count of Js
Remove the J key and its associated value from the dictionary
Determine the new largest count among the remaining values
Determine which alphanumeric character that new largest count is associated with (there may be several, I just need one)
Increment that key's value by the count of Js
Running this algorithm on the example input worked great!
But it generated an error when running on my puzzle input.
Why? Well, I overlooked one important use case.
A hand full of Jokers:
JJJJJ
In this case, after deleting the J key from the dictionary, it would be an empty dictionary.
Thus, my attempt at finding a key with any count amount would fail, and attempting to access the first element of the returned array doesn't work.
My workaround for this is a one-off:
if (counts['J'] == 5) {
counts['A'] = 5
delete counts['J']
} else if ('J' in counts) {
...
}
I picked A arbitrarily. I just need the dictionary to have some key other than J with 5 as a value.
My algorithm no longer generates an error and finishes, producing a number similar to my correct answer for Part 1.
Sadly, it's too low.
What could still be wrong?
Inspecting the sorted hand list for something out-of-order
This took a few minutes.
And when I was done, I didn't notice any hands out of place.
So I was stumped.
I looked back at the rules hoping I missed something.
Indeed, I missed a very important change to the rules.
Jokers are the weakest
I neglected to update my ordered list of card types!
It was still this from Part 1:
['2','3','4','5','6','7','8','9','T','J','Q','K','A']
*
And it should be this for Part 2:
['J','2','3','4','5','6','7','8','9','T','Q','K','A']
*
And with that change, I generated a new number that was higher than my last one.
Copy.
Paste.
Submit.
Correct answer!
Woohoo!
That was another really clever and fun puzzle, with a delightful twist in Part 2.
I'm glad I didn't attempt to solve it with regex as that likely would have been a headache.
Plus, it was clearly about counting cards, not matching patterns in a string.
I hope Day 8 turns out to be...gr8!
Top comments (0)