Exercism Poker attempt (https://exercism.org/tracks/rust/exercises/poker)

poker.rs

#![feature(iter_array_chunks)]

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// Instructions
///
/// Pick the best hand(s) from a list of poker hands.
///
/// See wikipedia for an overview of poker hands.
///
/// Ranking a list of poker hands can be considered a sorting problem.
/// Rust provides the sort method for Vec<T> where T: Ord.
/// Ord types form a total order: exactly one of a < b, a == b, or a > b must be true.
/// Poker hands do not conform to a total order: it is possible for two hands to be non-equal but have equal sort order. 
///     Example: "3S 4S 5D 6H JH", "3H 4H 5C 6C JD".
/// Rust provides the PartialOrd trait to handle the case of sortable things which do not have a total order. 
/// However, it doesn't provide a standard sort method for Vec<T> where T: PartialOrd. The standard idiom to sort a 
/// vector in this case is your_vec.sort_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::{Less|Equal|Greater}));, depending 
/// on your needs.
/// You might consider implementing a type representing a poker hand which implements PartialOrd.
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

pub fn winning_hands<'a>(hands: &[&'a str]) -> Vec<&'a str> {
    let mut prev_hand = Hand(HandRank::Unknown, 0, 0, 0);
    let mut winners = vec![];

    for (i, hand) in hands.iter().enumerate() {
        let curr_hand = Hand::from_slice(hand);

        if curr_hand > prev_hand {
            winners.clear();
            winners.push(hands[i]);
            prev_hand = curr_hand;
        } else if curr_hand == prev_hand {
            winners.push(hands[i]);
        }
    }

    winners
}

// Compare Rank --is a tie?--> tie-breaker 1 --still a tie?--> tie-breaker 2 --still a tie?--> tie-breaker 3
#[derive(Debug, PartialEq, PartialOrd)]
struct Hand(HandRank, u16, u16, u16);

impl Hand {
    // Given a string slice, parse it to bitfields, then generate a scored Hand from the bitfields
    fn from_slice(hand_slice: &str) -> Hand {
        let bfs = hand_slice
            .chars()
            .filter_map(parse_valid_hand_char)
            .array_chunks()
            .fold(Bitfields::init(), |mut bfs, [rank, suit]| {
                // Set highest unset bit in the tally.
                let new_tally_for_rank = bfs.tally_for_rank(rank) << 1 | 1;

                bfs.ranks |= 1 << rank;
                bfs.suits |= 1 << suit;
                bfs.tally |= new_tally_for_rank << (rank * 4);
                bfs.tally_score += 1 << new_tally_for_rank;
                bfs
            });

        Hand::from_bitfields(bfs)
    }

    // Use the bitfields to calculate the score for the hand
    fn from_bitfields(bfs: Bitfields) -> Hand {
        match bfs.tally_score {
            // High card/Straight/Flush/Straight Flush: Highest card always wins. NOTE: for straights, aces may be low.
            10 => {
                let is_straight = bfs.is_low_straight() | bfs.is_high_straight();
                let is_flush = bfs.suits.count_ones() == 1;
                let kicker = if bfs.is_low_straight() {
                    0b1111
                } else {
                    bfs.ranks
                };

                match (is_straight, is_flush) {
                    (false, false) => Hand(HandRank::HighCard, kicker, 0, 0),
                    (true, false) => Hand(HandRank::Straight, kicker, 0, 0),
                    (false, true) => Hand(HandRank::Flush, kicker, 0, 0),
                    (true, true) => Hand(HandRank::StraightFlush, kicker, 0, 0),
                }
            }
            // One pair: on a tie, highest pair wins. If pairs have same face value, just use highest card,
            // then next highest, then next highest.
            16 => {
                let (hi, midhi, midlo, lo) = bfs.rankpos4();
                let (pair, kicker) = match (
                    bfs.tally_for_rank(hi) == 0b11,
                    bfs.tally_for_rank(midhi) == 0b11,
                    bfs.tally_for_rank(midlo) == 0b11,
                ) {
                    (true, false, false) => (hi, bfs.zero_out_rank(hi)),
                    (false, true, false) => (midhi, bfs.zero_out_rank(midhi)),
                    (false, false, true) => (midhi, bfs.zero_out_rank(midlo)),
                    (false, false, false) => (midlo, bfs.zero_out_rank(lo)),
                    _ => unreachable!(),
                };

                Hand(HandRank::OnePair, pair, kicker, 0)
            }
            // Two pair: on a tie, highest pair wins. If pairs have same face value, next highest pair wins.
            // If those pairs have same value, then the highest face value of the players' remaining card wins.
            22 => {
                let (hi, mid, lo) = bfs.rankpos3();
                let (high_pair, low_pair, kicker) = match (
                    bfs.tally_for_rank(hi) == 0b11,
                    bfs.tally_for_rank(mid) == 0b11,
                ) {
                    (true, true) => (hi, mid, lo),
                    (true, false) => (hi, lo, mid),
                    (false, true) => (mid, lo, hi),
                    _ => unreachable!(),
                };

                Hand(HandRank::TwoPair, high_pair, low_pair, kicker)
            }
            // Three of a kind: on a tie, highest trip wins. If trips have same face value, just use highest card,
            // then next highest. NOTE: cascade is only possible if multiple decks are being used, with single deck
            // will always be highest trip.
            142 => {
                let (hi, lo) = bfs.rankpos2();
                let (trip, kicker) = match bfs.tally_for_rank(hi) == 0b111 {
                    true => (hi, bfs.zero_out_rank(hi)),
                    false => (lo, bfs.zero_out_rank(lo)),
                };

                Hand(HandRank::ThreeOfAKind, trip, kicker, 0)
            }
            // Full house: on a tie, highest trip wins. If trips have same face value, highest pair wins.
            // NOTE: cascade is only possible if multiple decks are being used, with single deck
            // will always be highest trip.
            148 => {
                let (hi, lo) = bfs.rankpos2();
                let (trip, pair) = match bfs.tally_for_rank(hi) == 0b111 {
                    true => (hi, lo),
                    false => (lo, hi),
                };

                Hand(HandRank::FullHouse, trip, pair, 0)
            }
            // Four of a kind: on a tie, highest quad wins. If quads have same face value, highest remaining card wins.
            // NOTE: cascade is only possible if multiple decks are being used, with single deck will always be highest quad.
            32908 => {
                let (hi, lo) = bfs.rankpos2();
                let (quad, kicker) = match bfs.tally_for_rank(hi) == 0b1111 {
                    true => (hi, bfs.zero_out_rank(hi)),
                    false => (lo, bfs.zero_out_rank(lo)),
                };

                Hand(HandRank::FourOfAKind, quad, kicker, 0)
            }
            _ => Hand(HandRank::Unknown, 0, 0, 0),
        }
    }
}

// NOTE: `trailing_zeros` returning a u32 is annoying when dealing with a u16.
fn u16_trailing_zeros(n: u16) -> u16 {
    u16::try_from(n.trailing_zeros()).unwrap()
}

// NOTE: Enum only used to make it a bit more obvious which hand is which (rather than using an int)
#[derive(Debug, Clone, Copy, Eq, Ord, PartialOrd, PartialEq)]
enum HandRank {
    Unknown,
    HighCard,
    OnePair,
    TwoPair,
    ThreeOfAKind,
    Straight,
    Flush,
    FullHouse,
    FourOfAKind,
    StraightFlush,
}

#[derive(Debug)]
struct Bitfields {
    /////////////////////////////////////////////////////////////////////////////////////
    // `tally` is a bitfield containing a tally of each face card in the hand. Knows nothing about suits.
    //                   A    K    Q    J    T    9    8    7    6    5    4    3    2
    // 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
    //
    // So for example, for "3H 9D KS KC 7H"
    //                   A    K    Q    J    T    9    8    7    6    5    4    3    2
    // 0000 0000 0000 0000 0011 0000 0000 0000 0001 0000 0001 0000 0000 0000 0001 0000
    /////////////////////////////////////////////////////////////////////////////////////
    tally: u64,
    /////////////////////////////////////////////////////////////////////////////////////
    // `tally_score` is gradually built up as each card is parsed. Knows nothing about suits.
    // Most of the scoring prior to tie-breaking comes from this, though it can't handle flushes/straights alone
    /////////////////////////////////////////////////////////////////////////////////////
    tally_score: u32,
    /////////////////////////////////////////////////////////////////////////////////////
    // `ranks` shows which ranks are present in the hand. Knows nothing about tally or suits.
    // It means straights can be identified immediately. A 16-bit int has been used to make calculations easier:
    // can coerce *up* just fine, but if I use a larger int started hitting problems where needed
    // to coerce *down*.
    //       A K Q J T 9 8 7 6 5 4 3 2
    // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    //
    // So for example, for "3H 9D KS KC 7H"
    //       A K Q J T 9 8 7 6 5 4 3 2
    // 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0
    /////////////////////////////////////////////////////////////////////////////////////
    ranks: u16,
    /////////////////////////////////////////////////////////////////////////////////////
    // `suits` shows which suits are present in the hand. Knows nothing about tally or ranks.
    // It means flushes can be identified immediately. A 16-bit int has been used to match `ranks`
    //                         S H D C
    // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    /////////////////////////////////////////////////////////////////////////////////////
    suits: u16,
}

impl Bitfields {
    fn init() -> Bitfields {
        Bitfields {
            tally: 0,
            tally_score: 0,
            ranks: 0,
            suits: 0,
        }
    }

    // A sequence of 5 contiguous set bits in the ranks represents a straight.
    fn is_high_straight(&self) -> bool {
        let high_mask = 0b11111;
        (self.ranks >> self.ranks.trailing_zeros() & high_mask) == high_mask
    }

    // Aces occupy the highest bit set in ranks. A straight can be A,2,3,4,5, so
    // in that case, looking for 5 contiguous bits won't work.
    fn is_low_straight(&self) -> bool {
        let low_mask = 0b0001000000001111;
        (self.ranks & low_mask) == low_mask
    }

    // If there are two ranks present, get lowest and highest positions
    fn rankpos2(&self) -> (u16, u16) {
        let lorank = u16_trailing_zeros(self.ranks);
        let hirank = u16_trailing_zeros(self.zero_out_rank(lorank));

        (hirank, lorank)
    }

    // If there are three ranks present, get lowest, highest and middle positions
    fn rankpos3(&self) -> (u16, u16, u16) {
        let mut ranks = self.ranks;
        let lorank = u16_trailing_zeros(ranks);
        ranks &= !(1 << lorank);
        let midrank = u16_trailing_zeros(ranks);
        ranks &= !(1 << midrank);
        let hirank = u16_trailing_zeros(ranks);

        (hirank, midrank, lorank)
    }

    // If there are four ranks present, get positions of all four
    fn rankpos4(&self) -> (u16, u16, u16, u16) {
        let mut ranks = self.ranks;
        let lorank = u16_trailing_zeros(ranks);
        ranks &= !(1 << lorank);
        let midlorank = u16_trailing_zeros(ranks);
        ranks &= !(1 << midlorank);
        let midhirank = u16_trailing_zeros(ranks);
        ranks &= !(1 << midhirank);
        let hirank = u16_trailing_zeros(ranks);

        (hirank, midhirank, midlorank, lorank)
    }

    // Isolate the four bits representing a tally for a given card rank
    fn tally_for_rank(&self, rank: u16) -> u64 {
        self.tally >> (rank * 4) & 0b1111
    }

    // Return a new set of ranks with given rank zeroed out
    fn zero_out_rank(&self, rank: u16) -> u16 {
        self.ranks & !(1 << rank)
    }
}

// Parse
fn parse_valid_hand_char(c: char) -> Option<u16> {
    match c {
        '2'..='9' => Some((c as u16) - 50),
        '0' => Some(8),
        'J' => Some(9),
        'Q' => Some(10),
        'K' => Some(11),
        'A' => Some(12),
        // Suits
        'S' => Some(0),
        'H' => Some(1),
        'D' => Some(2),
        'C' => Some(3),
        _ => None,
    }
}
    
#[cfg(test)]
mod tests {
    use std::collections::HashSet;
    use super::winning_hands;

    fn hs_from<'a>(input: &[&'a str]) -> HashSet<&'a str> {
        let mut hs = HashSet::new();
        for item in input.iter() {
            hs.insert(*item);
        }
        hs
    }

    /// Test that the expected output is produced from the given input
    /// using the `winning_hands` function.
    ///
    /// Note that the output can be in any order. Here, we use a HashSet to
    /// abstract away the order of outputs.
    fn test(input: &[&str], expected: &[&str]) {
        assert_eq!(hs_from(&winning_hands(input)), hs_from(expected))
    }

    #[test]
    fn test_single_hand_always_wins() {
        test(&["4S 5S 7H 8D JC"], &["4S 5S 7H 8D JC"])
    }

    #[test]
    fn test_duplicate_hands_always_tie() {
        let input = &["3S 4S 5D 6H JH", "3S 4S 5D 6H JH", "3S 4S 5D 6H JH"];
        assert_eq!(&winning_hands(input), input)
    }

    #[test]
    fn test_highest_card_of_all_hands_wins() {
        test(
            &["4D 5S 6S 8D 3C", "2S 4C 7S 9H 10H", "3S 4S 5D 6H JH"],
            &["3S 4S 5D 6H JH"],
        )
    }

    #[test]
    fn test_a_tie_has_multiple_winners() {
        test(
            &[
                "4D 5S 6S 8D 3C",
                "2S 4C 7S 9H 10H",
                "3S 4S 5D 6H JH",
                "3H 4H 5C 6C JD",
            ],
            &["3S 4S 5D 6H JH", "3H 4H 5C 6C JD"],
        )
    }

    #[test]
    fn test_high_card_can_be_low_card_in_an_otherwise_tie() {
        // multiple hands with the same high cards, tie compares next highest ranked,
        // down to last card
        test(&["3S 5H 6S 8D 7H", "2S 5D 6D 8C 7S"], &["3S 5H 6S 8D 7H"])
    }

    #[test]
    fn test_one_pair_beats_high_card() {
        test(&["4S 5H 6C 8D KH", "2S 4H 6S 4D JH"], &["2S 4H 6S 4D JH"])
    }

    #[test]
    fn test_highest_pair_wins() {
        test(&["4S 2H 6S 2D JH", "2S 4H 6C 4D JD"], &["2S 4H 6C 4D JD"])
    }

    #[test]
    fn test_two_pairs_beats_one_pair() {
        test(&["2S 8H 6S 8D JH", "4S 5H 4C 8C 5C"], &["4S 5H 4C 8C 5C"])
    }

    #[test]
    fn test_two_pair_ranks() {
        // both hands have two pairs, highest ranked pair wins
        test(&["2S 8H 2D 8D 3H", "4S 5H 4C 8S 5D"], &["2S 8H 2D 8D 3H"])
    }

    #[test]
    fn test_two_pairs_second_pair_cascade() {
        // both hands have two pairs, with the same highest ranked pair,
        // tie goes to low pair
        test(&["2S QS 2C QD JH", "JD QH JS 8D QC"], &["JD QH JS 8D QC"])
    }

    #[test]
    fn test_two_pairs_last_card_cascade() {
        // both hands have two identically ranked pairs,
        // tie goes to remaining card (kicker)
        test(&["JD QH JS 8D QC", "JS QS JC 2D QD"], &["JD QH JS 8D QC"])
    }

    #[test]
    fn test_three_of_a_kind_beats_two_pair() {
        test(&["2S 8H 2H 8D JH", "4S 5H 4C 8S 4H"], &["4S 5H 4C 8S 4H"])
    }

    #[test]
    fn test_three_of_a_kind_ranks() {
        //both hands have three of a kind, tie goes to highest ranked triplet
        test(&["2S 2H 2C 8D JH", "4S AH AS 8C AD"], &["4S AH AS 8C AD"])
    }

    #[test]
    fn test_low_three_of_a_kind_beats_high_two_pair() {
        test(&["2H 2D 2C 8H 5H", "AS AC KS KC 6S"], &["2H 2D 2C 8H 5H"])
    }

    #[test]
    fn test_three_of_a_kind_cascade_ranks() {
        // with multiple decks, two players can have same three of a kind,
        // ties go to highest remaining cards
        test(&["4S AH AS 7C AD", "4S AH AS 8C AD"], &["4S AH AS 8C AD"])
    }

    #[test]
    fn test_straight_beats_three_of_a_kind() {
        test(&["4S 5H 4C 8D 4H", "3S 4D 2S 6D 5C"], &["3S 4D 2S 6D 5C"])
    }

    #[test]
    fn test_aces_can_end_a_straight_high() {
        // aces can end a straight (10 J Q K A)
        test(&["4S 5H 4C 8D 4H", "10D JH QS KD AC"], &["10D JH QS KD AC"])
    }

    #[test]
    fn test_aces_can_start_a_straight_low() {
        // aces can start a straight (A 2 3 4 5)
        test(&["4S 5H 4C 8D 4H", "4D AH 3S 2D 5C"], &["4D AH 3S 2D 5C"])
    }

    #[test]
    fn test_no_ace_in_middle_of_straight() {
        // aces cannot be in the middle of a straight (Q K A 2 3)
        test(&["2C 3D 7H 5H 2S", "QS KH AC 2D 3S"], &["2C 3D 7H 5H 2S"])
    }

    #[test]
    fn test_straight_ranks() {
        // both hands with a straight, tie goes to highest ranked card
        test(&["4S 6C 7S 8D 5H", "5S 7H 8S 9D 6H"], &["5S 7H 8S 9D 6H"])
    }

    #[test]
    fn test_straight_scoring() {
        // even though an ace is usually high, a 5-high straight is the lowest-scoring straight
        test(&["2H 3C 4D 5D 6H", "4S AH 3S 2D 5H"], &["2H 3C 4D 5D 6H"])
    }

    #[test]
    fn test_flush_beats_a_straight() {
        test(&["4C 6H 7D 8D 5H", "2S 4S 5S 6S 7S"], &["2S 4S 5S 6S 7S"])
    }

    #[test]
    fn test_flush_cascade() {
        // both hands have a flush, tie goes to high card, down to the last one if necessary
        test(&["4H 7H 8H 9H 6H", "2S 4S 5S 6S 7S"], &["4H 7H 8H 9H 6H"])
    }

    #[test]
    fn test_full_house_beats_a_flush() {
        test(&["3H 6H 7H 8H 5H", "4S 5C 4C 5D 4H"], &["4S 5C 4C 5D 4H"])
    }

    #[test]
    fn test_full_house_ranks() {
        // both hands have a full house, tie goes to highest-ranked triplet
        test(&["4H 4S 4D 9S 9D", "5H 5S 5D 8S 8D"], &["5H 5S 5D 8S 8D"])
    }

    #[test]
    fn test_full_house_cascade() {
        // with multiple decks, both hands have a full house with the same triplet, tie goes to the pair
        test(&["5H 5S 5D 9S 9D", "5H 5S 5D 8S 8D"], &["5H 5S 5D 9S 9D"])
    }

    #[test]
    fn test_four_of_a_kind_beats_full_house() {
        test(&["4S 5H 4D 5D 4H", "3S 3H 2S 3D 3C"], &["3S 3H 2S 3D 3C"])
    }

    #[test]
    fn test_four_of_a_kind_ranks() {
        // both hands have four of a kind, tie goes to high quad
        test(&["2S 2H 2C 8D 2D", "4S 5H 5S 5D 5C"], &["4S 5H 5S 5D 5C"])
    }

    #[test]
    fn test_four_of_a_kind_cascade() {
        // with multiple decks, both hands with identical four of a kind, tie determined by kicker
        test(&["3S 3H 2S 3D 3C", "3S 3H 4S 3D 3C"], &["3S 3H 4S 3D 3C"])
    }

    #[test]
    fn test_straight_flush_beats_four_of_a_kind() {
        test(&["4S 5H 5S 5D 5C", "7S 8S 9S 6S 10S"], &["7S 8S 9S 6S 10S"])
    }

    #[test]
    fn test_aces_can_end_a_straight_flush_high() {
        // aces can end a straight flush (10 J Q K A)
        test(&["KC AH AS AD AC", "10C JC QC KC AC"], &["10C JC QC KC AC"])
    }

    #[test]
    fn test_aces_can_start_a_straight_flush_low() {
        // aces can start a straight flush (A 2 3 4 5)
        test(&["KS AH AS AD AC", "4H AH 3H 2H 5H"], &["4H AH 3H 2H 5H"])
    }

    #[test]
    fn test_no_ace_in_middle_of_straight_flush() {
        // aces cannot be in the middle of a straight flush (Q K A 2 3)
        test(&["2C AC QC 10C KC", "QH KH AH 2H 3H"], &["2C AC QC 10C KC"])
    }

    #[test]
    fn test_straight_flush_ranks() {
        // both hands have a straight flush, tie goes to highest-ranked card
        test(&["4H 6H 7H 8H 5H", "5S 7S 8S 9S 6S"], &["5S 7S 8S 9S 6S"])
    }

    #[test]
    fn test_straight_flush_scoring() {
        // even though an ace is usually high, a 5-high straight flush is the lowest-scoring straight flush
        test(&["2H 3H 4H 5H 6H", "4D AD 3D 2D 5D"], &["2H 3H 4H 5H 6H"])
    }

}