I know it’s been a few weeks. I was lucky enough to be in the path of totality for the solar eclipse a few weeks ago. I am a member of the Southern Illinois Concert Band, and we played two Eclipse themed concerts the weekeng before, which took a lot of my time.
Since then, the weather has been up and down, and we’ve been trying to get our yard and gardens in order, as well practice for another concert at the end of the month with another band.
However, the biggest drain on my time has been purely frivolous. One of my students at CodingNomads is working on their capstone, which will be a 2D platformer game written in Python using the Arcade library. To get myself into mentor mode for this, I’ve been playing a lot of games, specifically Icewind Dale and Baldur’s Gate.
Anyway, off to the day 7 challenge, which is an oddly scored version of poker designed to be played on the back of a camel called Camel Cards. The challenge is that there are some crucial differences between Camel Cards and poker…
A Camel Card hand consists of five "standard" playing cards from Ace down to the 2, listed as A, K, Q, J, T, 9, 8, 7, 6, 5, 4, 3, and 2. The deck is the first difference — there are no suits, and from the examples given, there may be more than four of each rank of card. Also, the ace is always high in this system.
Each hand has a type, like three of a kind or full house. Here is where two other differences come in. Scoring the hand follows somewhat normal poker scoring, starting with five of a kind (which is new). Since there are no suits, there are no flushes. Further, there are no straights either. Otherwise, this follows standard poker scoring:
- Five of a kind
- Four of a kind
- Full house (pair of one rank, and three of another)
- Three of a kind
- Two pair (a pair of one rank, and another pair of a different rank)
- One pair
- High card
You have to score the hands and sort them them from strongest to weakest. Of course, it’s possible there may be a tie — for example, two hands may both score as four of a kind. In this case, breaking the tie is the last big difference from poker. Tier are broken by comparing the cards for the tied hands in order, with the highest card winning.
For example, say you have two hands, 3332K and 2AAA9. Both are three of a kind, so you do the tie break. The first card in each hand is 3 and 2, so the first hand scores higher. I know — weird, right?
Your input consists of a list of Camel Card hands, along with a bid for each hand (for example, 3332K 297. Sort the hands from low score to high score, and number them starting with one. Multiply the sorted order by the bid, and add those all up to get your answer.
Approach
To make things easier to manage, I create a struct Hand to manage reading the hand and bid info, maintain a score for the hand, and implement ordering of hands:
#[derive(Debug)]
pub struct Hand{
cards: String,
pub bid: u64,
score: u32
}The ordering is where the tie-breaking code lives. This is because the tie-breaking implementation is only needed if two hands have the same score. In this case, the two hands are self and other:
impl Ord for Hand{
fn cmp(&self, other: &Self) -> Ordering {
let card_order = ['2','3','4','5','6','7','8','9','T','J','Q','K','A'];
if self.score == other.score{
// We need to compare character by character
let self_cards = &self.cards;
let other_cards = &other.cards;
for i in 0..5{
let self_char: char = self_cards.chars().nth(i).unwrap();
let other_char: char = other_cards.chars().nth(i).unwrap();
if self_char != other_char{
return card_order
.iter()
.position(|x| x == &self_char)
.unwrap()
.cmp(&card_order
.iter()
.position(|x| x == &other_char)
.unwrap());
}
}
self.cards.cmp(&other.cards)
} else {
self.score.cmp(&other.score)
}
}
}If the scores are different, I can just compare them and ignore the tie-breaking stuff.
The card_order array comes in when a tie-break needs to happen — it lists all the cards in ascending order of value.
So, what I do is this:
- I start a loop from the first card in the hand to the last, using
ias my loop variable. There are always five card in a hand. - I get the
ith card in each hand using.chars().nth(i)—.chars()gives me achararray, and.nth()gives me the specific card in that array I need. - If these cards are the same, I go to the next card.
- Otherwise, I get the position of that card in
card_orderusingposition(|x| x=card)— this is the Rust way of doing alist.index(card)in Python. - Then, I compare that position to the position of the card in the other hand, and the highest one wins.
Neither hand will be the same (which is helpful), so this will return one or the other as the higher ranking hand.
But how do I score the hand to begin with? I use a technique I first learned during an interview.
History Lesson
Before I first moved to the Seattle area, I interviewed at Microsoft for a support engineer role. I was already working as a support engineer, but this was in Developer Support, which was a step up from the end-user support I was doing.
Anyway, one of the interviewers (who later became a co-worker and good work friend) showed me some C source code, and asked me to figure out what the code did. The function name was missing, so all I had was the code and the signature.
As I recall, the function accepted two strings. It set up an array of 32 integers, then started looping over the characters in the second string. It did a two calculations on each character, using one result as the index into the int array, and performing a bitwise or of the second result on the array element.
Then it looped over the first string, doing the same two calculations, but this time using a bitwise and to compare it’s results to what was in the array. It returned the index when that comparison was true.
I wish I could say I got what it was doing at the time. I didn’t.
Basically, it the code was (at that time) the standard library implementation of the strspn() function, which gives you the length of a substring of one string that is only made up of characters from the second.
The int[32] array is a clever way of setting up 256 bits, each one acting as a bool indicating if an ASCII character is in the second string. The calculations done on each char of the second string find the correct bit to set in the array, using the bitwise or to do so. The array now contains data on which characters are present in the second string. Doing the same calculations on the characters in the first string, but using bitwise and in a comparison, identifies the first character in the first string which isn’t in the second.
It basically takes two nested loops, and unwinds them into two consecutive loops, using as little memory space as possible to store data between them. The array allows what would be an $O(n^2)$ algorithm ti become an $O(n)$ algorithm.
My code does a similar thing — I create an array which tells me exactly how many of each card I have in my hand. Then, I check each card in my hand, updating the array as I go. When the array is built, I check for each type of hand, and assign a score from 1 to 7, with five of a kind getting 7, and high card getting 1. Checking for two pair requires some additional looping, but nothing too bad. I store the score, which is used in the cmp() method above.
Because of all the work done in the Hand struct, my main code is very simple. I reads each line from the input file, creates a new hand which is automatically scored, and stuffs it into a Vec. Then, I .sort() the Vec, which uses the .cmp() method to handle ties. Then I just iterate over the newly sorted Vec and calculate my final answer.
Part 2
Part 2 complicates things in two ways.
First, the J no longer represents the Jack, but is now a Joker. You treat Jokers as wild cards, and this is no exception. So now you score the best hand using the Jokers.
Second, the J is now the lowest scoring card on the table when it comes to a tie-breaker. So the new ordering is A, K, Q, T, 9, 8, 7, 6, 5, 4, 3, 2, and J.
With these changes, you re-rank the hands and compute a new final answer, using the same rules as part 1 otherwise.
Since the final score calculation is the same, my main code does the same thing, but now I have a new Hand method called .calc_score_with_joker() to re-score each hand with this new twist.
First, I try to make life easier — if the hand doesn’t have any jokers, there’s no need to jump through new hoops. I can just use the original .calc_score() method.
If there are Jokers, then I have to do something different.
One thing to realize is that, without straights, this is actually not a hard problem.
Let’s say you have a pair, and one Joker — say 22J47. Under the old scoring, there would be two 2 cards and one J card. Now, if you treat the J as a 2, there are three 2 cards.
Now let’s say you have two Jokers, for 22J4J. That should be four of a kind, adding the two J cards to the two 2 cards to give you four 2 cards.
How about two pair? If you have 224J4, you can get a full house, by either adding the one J to the two 2s, or the two 4s.
In other words, if you add the number of Jokers to one set of other cards in the hand, you’ll have a better hand. But which set of cards do you pick?
In my solution, I pick them all. Well, not all once.
After counting each type of card, I save off the number of Jokers in jokers. I then iterate over card_counts, adding jokers to each, and calculate that hand’s score. I save off the highest score found for that hand, so after 13 iterations, I’ve got the best score. Even though I’ve got the extra loop now, it’s short, efficient, and still runs in a short amount of time.
Easy, peasy, lemon squeezy.
Summary
My code, as always, is here — comments, questions, and PR’s welcome!
One thing I realized too late about part 2 — if there is even a single joker in your hand, you will never score two pair. That’s because the joker can always be added to the single pair to make three of a kind, or a full house if there are already two pair. Same with high card. I didn’t see those at the time, and they represent simplifications I can make to my code now.
I can also tighten up the loop by only adding joker to cards with positive counts — there’s no need to have the Joker represent a card that’s not already in the hand. For example, in the 224J4 hand above, it is meaningless to treat the Joker as a 5 or a K — neither make the hand better.
I also need to update my code so it works without code changes for both Part 1 and Part 2 — right now, the card order is hard-coded in the .cmp() method, which isn’t right.
All that said, part 2 would have been a lot trickier if there were straights involved. Since we were only dealing with sets of cards, it meant I could ignore Jacks altogether.
All that said, this was a fun challenge, and gave me some good ideas for writing my own card games in the future. I used to play cribbage a lot, and writing a good cribbage game sounds like a worthwhile challenge!