Advent of Code 2023: Day 07

Code for solutions available on GitHub.

Camel Cards

Time to play some poker! Or, well, Camel Cards. In this game, you get a list of hands and the goal is to order these hands based on some criteria.

Each hand consists of 5 cards, labelled as a standard deck of cards: A,K,Q,J,T,9,8,7,6,5,4,3,2. The 10 card is labelled with a T. This makes parsing easier, as every card is represented by a single symbol. I will actually talk a little bit about parsing in this post!

There are no suits, so we don’t need to worry about that. Time for the first type!

#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
enum Card {
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Ten,
    Jack,
    Queen,
    King,
    Ace,
}

Each hand of 5 cards has a type. This type is one of the standard types from regular poker, bar flushes and straights, plus five of a kind:

• Five of a kind
• Four of a kind
• Full house (Three of a kind + one pair)
• Three of a kind
• Two pair
• One pair
• High card (All cards are distinct)

The above list is ordered from strongest to weakest type. I feel like it was very kind of the puzzle authors to leave straights out of the problem. It simplifies the solution quite a bit.

Let’s model these hand types as a new type:

#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
enum HandType {
    HighCard,
    OnePair,
    TwoPair,
    ThreeOfAKind,
    FullHouse,
    FourOfAKind,
    FiveOfAKind,
}

You might notice that I modelled both the HandType and Card enums in ascending order. This is important to decide the order of the hands, whether a hand beats another.

Firstly, a hand beats another if its hand type is stronger than the other’s. For example, ThreeOfAKind beats OnePair. This is why I derived Ord and put the enum in ascending order. Determining which is stronger just becomes a comparison like hand_type1 > hand_type2.

If both hands have the same hand type, the winner is the hand with the highest card first. If both hands’ first cards are equal, then the winner is the one with the highest second card and so on, moving from left to right.

With this in mind, the Hand type can be modelled, and determining which hand of two is stronger, we can manually implement Ord according to the given rules:

#[derive(Debug, PartialEq, Eq)]
struct Hand {
    cards: [Card; 5],
    hand_type: HandType,
}

impl Ord for Hand {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        if self.hand_type != other.hand_type {
            self.hand_type.cmp(&other.hand_type)
        } else {
            self.cards.cmp(&other.cards)
        }
    }
}

impl PartialOrd for Hand {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

And that’s all the code needed for comparing hand strengths. Ord requires PartialOrd to be implemented, but nothing stops us from implementing PartialOrd by calling Ord::cmp. So the second impl is just an implementation detail.

With all the types mapped out, let’s take a look at the example input:

32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483

Each line consists of a hand of 5 cards, and a bid. The solution to the problem is given sorting these lines in ascending order by hand strength, multiplying each hand’s list position (rank) by its bid, then summing the results. The rank starts at 1 for the weakest hand, so we’ll have to take that into account.

Let’s add the bid to the Hand struct before continuing:

#[derive(Debug, PartialEq, Eq)]
struct Hand {
    cards: [Card; 5],
+   bid: u64,
    hand_type: HandType,
}

I would like to add a Hand::new(cards: &[Card], bid: u64) constructor method to the Hand struct. But the constructor also needs to set the hand type. So the HandType enum needs a method to convert from a &[Card] to a HandType. For each card in the &[Card], I’d like to go through each possible card and check for a match, keeping track of the counts of all the different types of cards.

This is where the enum-iterator crate comes in handy. It provides a couple functions, but I’m going to make use of the all function – which returns an iterator over all enum value – and the cardinality function, which returns the number of enum values. We can create a Vec filled with zeroes with size given by cardinality, which can be indexed by the enum value by casting it to a usize. Then the all function can be used to iterate over all possible Card values, count how many of each are in the hand of cards, and set the corresponding element in the Vec to the count. This is faster than using a HashMap.

After that, the hand type can be determined by checking the maximum count in the Vec, along with some extra conditions:

impl HandType {
    fn from_cards(cards: &[Card]) -> Self {
        let mut card_counts = vec![0; enum_iterator::cardinality::<Card>()];
        enum_iterator::all::<Card>().for_each(|card| {
            card_counts[card as usize] +=
                cards
                    .iter()
                    .fold(0, |acc, c| if *c == card { acc + 1 } else { acc });
        });

        let two_pair = card_counts.iter().filter(|c| *c == &2).count() == 2;

        match card_counts.iter().max().unwrap() {
            5 => HandType::FiveOfAKind,
            4 => HandType::FourOfAKind,
            3 if card_counts.contains(&2) => HandType::FullHouse,
            3 => HandType::ThreeOfAKind,
            2 if two_pair => HandType::TwoPair,
            2 => HandType::Pair,
            _ => HandType::HighCard,
        }
    }
}

Pretty simple! The constructor is now straightforward:

impl Hand {
    fn new(cards: &[Card], bid: u64) -> Self {
        Self {
            cards: cards.try_into().unwrap(),
            bid,
            hand_type: HandType::from_cards(cards),
        }
    }
}

I will now actually spend some words on parsing. This is simply because I was recently made aware of the nom-supreme crate, which provides extension traits for nom parsers that allow for some combinators to be available as postfix methods. It will become clearer when we look at the parsing of Hand. First, the parsing of a single Card. This is really simple:

impl Card {
    fn parse(input: &str) -> nom::IResult<&str, Self> {
        one_of("23456789TJQKA")
            .map(|c| match c {
                '2' => Card::Two,
                '3' => Card::Three,
                '4' => Card::Four,
                '5' => Card::Five,
                '6' => Card::Six,
                '7' => Card::Seven,
                '8' => Card::Eight,
                '9' => Card::Nine,
                'T' => Card::Ten,
                'J' => Card::Jack,
                'Q' => Card::Queen,
                'K' => Card::King,
                'A' => Card::Ace,
                _ => unreachable!(),
            })
            .parse(input)
    }
}

A straightforward mapping between the single input character and the output card type. one_of, map, and parse are all from the regular nom crate here. But nom-supreme will be used in the parse associatied function for Hand:

impl Hand {
    fn parse(input: impl AsRef<str>) -> Self {
        count(Card::parse, 5)
            .terminated(space1)
            .and(number_parser)
            .map(|(cards, bid)| Self::new(&cards, bid))
            .parse(input.as_ref())
            .unwrap()
            .1
    }
}

I’m unwrapping and getting the Hand out of the nom::IResult as this function will consume the entire input slice anyway. This is not true for Card::parse, which we’re using in this function as a proper parser. But look at those postfix methods! That looks pretty nice. Without nom-supreme, this function would have to look like this:

impl Hand {
    fn parse(input: impl AsRef<str>) -> Self {
        separated_pair(count(Card::parse, 5), space1, number_parser)
            .map(|(cards, bid)| Self::new(&cards, bid))
            .parse(input.as_ref())
            .unwrap()
            .1
    }
}

Which is fine, but I don’t really like the “inside-out-ness” of it. The nom-supreme crate feels more readable, first parsing 5 Cards, terminated by at least 1 space, and then parsing a number. Both of the results are put into a tuple, which we can then map into a Hand by using the constructor. This particular example isn’t that bad, but I’ve written more complicated parsers where the postfix methods would definitely be a whole lot more readable.

You might wonder why input is an impl AsRef<str> rather than a simple &str. I’ll get to that in due time ;)

Are we done? Yes! All of this groundwork is very easily composed into the solution to the first part:

input
    .lines()
    .map(Hand::parse)
    .sorted()
    .enumerate()
    .map(|(i, hand)| hand.bid * (i as u64 + 1))
    .sum()

I’m using Itertools::sorted from the itertools crate to sort the hands in ascending order. That in turn uses the implementation of Ord we made earlier to determine the order of the hands. Then using Iterator::enumerate we can get the index (rank) of the hand. Finally, we multiply the index (plus one) by the hand’s bid and sum up all the results and we’re done!

Part 2

And the twist is that all the Js in the input aren’t jacks, they’re now jokers! And a joker is any card type it needs to be to get as strong of a hand as possible. But it is worth less than a 2 in the case of a hand type tie. So the first step is pretty obvious:

#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
enum Card {
+   Joker,
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Ten,
    Jack,
    Queen,
    King,
    Ace,
}

We need to modify the HandType::from_cards associated function to work differently if there are any jokers in the hand.

impl HandType {
    fn from_cards(cards: &[Card]) -> Self {
        let mut card_counts = vec![0; enum_iterator::cardinality::<Card>()];
        enum_iterator::all::<Card>().for_each(|card| {
            card_counts[card as usize] +=
                cards
                    .iter()
                    .fold(0, |acc, c| if *c == card { acc + 1 } else { acc });
        });

+       if card_counts[Card::Joker as usize] > 0 {
+           return HandType::with_joker(card_counts);
+       }

        let two_pair = card_counts.iter().filter(|c| *c == &2).count() == 2;

        match card_counts.iter().max().unwrap() {
            5 => HandType::FiveOfAKind,
            4 => HandType::FourOfAKind,
            3 if card_counts.contains(&2) => HandType::FullHouse,
            3 => HandType::ThreeOfAKind,
            2 if two_pair => HandType::TwoPair,
            2 => HandType::Pair,
            _ => HandType::HighCard,
        }
    }
}

So a new associated function called with_joker can be implemented to determine the best possible hand given the joker count and the remaining cards. It’s probably worth going through the possibilities first, from most jokers to least.

• 5 jokers will be a five of a kind.
• 4 jokers + any card will also be five of a kind, as the jokers match that card.
• 3 jokers + a pair is also five of a kind.
• 3 jokers + no pair is four of a kind.
• 2 jokers + three of a kind is five of a kind.
• 2 jokers + a pair is four of a kind.
• 2 jokers + no pairs is three of a kind.
• 1 joker + four of a kind is five of a kind.
• 1 joker + three of a kind is four of a kind.
• 1 joker + two pair is a full house.
• 1 joker + a pair is three of a kind.
• 1 joker + no pairs is a pair.

No other hand types are possible. Two pair will never be generated, as for a two pair + joker hand, such as 22J33, the joker can match either of the pairs to make a full house, which is stronger than a two pair. And for a one pair + joker hand, such as 22J34, the joker will match the 2, making three of a kind, which is stronger than a two pair.

Now we can use the fact that the Card enum is ordered to split off the joker count from card_count, get the hand type of the remaining cards, and just translate the list of possibilities above into a pretty straightforward match:

impl HandType {
    fn with_joker(card_counts: Vec<u8>) -> Self {
        let num_jokers = card_counts[Card::Joker as usize];
        let card_counts = &card_counts[Card::Two as usize..];

        let hand_without_jokers = card_counts
            .iter()
            .enumerate()
            .flat_map(|(i, c)| {
                let card = Card::try_from_primitive(i as u8 + 1).unwrap();
                vec![card; *c as usize]
            })
            .collect_vec();
        let hand_type = HandType::from_cards(&hand_without_jokers);

        match (num_jokers, hand_type) {
            (5, _) | (4, _) => HandType::FiveOfAKind,
            (3, HandType::Pair) => HandType::FiveOfAKind,
            (3, HandType::HighCard) => HandType::FourOfAKind,
            (2, HandType::ThreeOfAKind) => HandType::FiveOfAKind,
            (2, HandType::Pair) => HandType::FourOfAKind,
            (2, HandType::HighCard) => HandType::ThreeOfAKind,
            (1, HandType::FourOfAKind) => HandType::FiveOfAKind,
            (1, HandType::ThreeOfAKind) => HandType::FourOfAKind,
            (1, HandType::TwoPair) => HandType::FullHouse,
            (1, HandType::Pair) => HandType::ThreeOfAKind,
            (1, HandType::HighCard) => HandType::Pair,
            _ => unreachable!(),
        }
}

I’m making use of the num-enum crate for casting the u8 into the Card enum, and the fact that the card_counts list is sorted by card value.

Now we just need to figure out how to make the parsing know that a J is a joker, not a jack. Preferably without having to pass a bool or something like that. Well, why not just make all Js into js in the input and parse those as jokers in Card::parse?

impl Card {
    fn parse(input: &str) -> nom::IResult<&str, Self> {
-       one_of("23456789TJQKA")
+       one_of("j23456789TJQKA")
            .map(|c| match c {
+               'j' => Card::Joker,
                '2' => Card::Two,
                <snip>

And putting it all together:

input
    .lines()
+   .map(|line| line.replace('J', "j"))
    .map(Hand::parse)
    .sorted()
    .enumerate()
    .map(|(i, hand)| hand.bid * (i as u64 + 1))
    .sum()

With this groundwork, adding a single line to the solution from part 1 solves part 2!

Remember how input is an impl AsRef<str> in Hand::parse? The only reason I did that was to enable the change to be a single line. str::replace returns a String, and so if the input was a &str, the solution would have to look like this instead:

input
    .lines()
    .map(|line| line.replace('J', "j"))
    .map(|line| Hand::parse(&line))
    .sorted()
    .enumerate()
    .map(|(i, hand)| hand.bid * (i as u64 + 1))
    .sum()

And I just found that to be too ugly for my tastes. I much prefer to just use function names directly in map. And both &str and String implement AsRef<str>, so it all works out!