Determining winning hand in poker

Question

After having reviewed this question, I recalled that I haven't solved Project Euler's problem 54. So I did it, however, I fount out that implementing the exact rules is rather tricky.

So I implemented just the necessary part. It works, problem solved, so let's call my code working. However, there are pairs of cards (not present in the input file), which leads to an exception. I'm not asking for a solution to this, I'd like to get the relevant parts reviewed and then I'll do it myself.

Feel free to ignore slightly deviating coding conventions and lacking javadoc (I hope it's commented enough to be understandable). I'm mostly interested in simplifications as it has got rather long. All classes are nested for simplicity.

Upon request I extracted the classes into separate files. As repeating all the imports would make it considerably longer, I'm presenting the header section just once.

(header)

package maaartin.euler.e0.e05;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import java.util.EnumSet;
import java.util.List;

import lombok.EqualsAndHashCode;
import lombok.Getter;
import lombok.RequiredArgsConstructor;

import com.google.common.base.Joiner;
import com.google.common.base.Predicate;
import com.google.common.base.Splitter;
import com.google.common.collect.EnumMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMultiset;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSortedSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Multiset;

import maaartin.euler.EulerUtils;

EulerUtils is a helper class for reading the input (given E054.class, it reads the file E054.txt, which is my local copy of poker.txt).

Suit

@RequiredArgsConstructor @Getter enum Suit {
    SPADES('S'),
    HEARTS('H'),
    CLUBS('C'),
    DIAMONDS('D'),
    ;

    static Suit forSymbol(char symbol) {
        return checkNotNull(FOR_SYMBOL[symbol], symbol);
    }

    private static final Suit[] FOR_SYMBOL = new Suit[128]; // ASCII sized
    static {
        for (final Suit s : Suit.values()) FOR_SYMBOL[s.symbol] = s;
    }

    private final char symbol;
}

Rank

@RequiredArgsConstructor @Getter enum Rank {
    TWO(2), THREE(3), FOUR(4), FIVE(5), SIX(6), SEVEN(7), EIGHT(8), NINE(9),
    TEN(10, 'T'), JACK(11, 'J'), QUEEN(12, 'Q'), KING(13, 'K'), ACE(14, 'A');

    private Rank(int value) {
        this(value, (char) ('0' + value));
        checkArgument(value < 10);
    }

    static Rank forSymbol(char symbol) {
        return checkNotNull(FOR_SYMBOL[symbol], symbol);
    }

    Card of(Suit suit) {
        return new Card(this, suit);
    }

    private static final Rank[] FOR_SYMBOL = new Rank[128]; // ASCII sized
    static {
        for (final Rank r : Rank.values()) FOR_SYMBOL[r.symbol] = r;
    }

    private final int value;
    private final char symbol;
}

Card

@RequiredArgsConstructor @Getter @EqualsAndHashCode
static class Card implements Comparable<Card> {
    @Override public int compareTo(Card o) {
        int result = rank.compareTo(o.rank);
        if (result==0) result = suit.compareTo(o.suit);
        return result;
    }

    static Card forString(String s) {
        checkArgument(s.length() == 2);
        return new Card(Rank.forSymbol(s.charAt(0)), Suit.forSymbol(s.charAt(1)));
    }

    @Override public String toString() {
        return rank.symbol() + "" + suit.symbol();
    }

    private final Rank rank;
    private final Suit suit;
}

HandValue

@RequiredArgsConstructor enum HandValue implements Predicate<Hand> {
    HIGH_CARD {
        @Override public boolean apply(Hand input) {
            return input.rankHistogram().equals(ImmutableMultiset.of(1, 1, 1, 1, 1));
        }

        @Override List<Card> reorderedCards(Hand hand) {
            // Order the biggest cards last, which is trivial as hand.cards() are already sorted.
            return ImmutableList.copyOf(hand.cards());
        }
    },
    PAIR {
        @Override public boolean apply(Hand input) {
            return input.rankHistogram().equals(ImmutableMultiset.of(1, 1, 1, 2));
        }

        @Override List<Card> reorderedCards(Hand hand) {
            final List<Card> result = Lists.newArrayList();
            final Rank rank = findRepeatedRank(hand.cards());
            // Insert the unpaired cards first in their original order.
            for (final Card c : hand.cards()) {
                if (!c.rank().equals(rank)) result.add(c);
            }
            // Then insert the cards of the pair.
            for (final Card c : hand.cards()) {
                if (c.rank().equals(rank)) result.add(c);
            }
            assert ImmutableSet.copyOf(result).equals(ImmutableSet.copyOf(hand.cards()));
            return result;
        }

        /** Get the first (and only) rank occuring more then once. */
        private Rank findRepeatedRank(Iterable<Card> cards) {
            final EnumSet<Rank> set = EnumSet.noneOf(Rank.class);
            for (final Card c : cards) {
                if (!set.add(c.rank())) return c.rank();
            }
            throw new RuntimeException("Impossible.");
        }
    },
    TWO_PAIRS {
        @Override public boolean apply(Hand input) {
            return input.rankHistogram().equals(ImmutableMultiset.of(1, 2, 2));
        }
    },
    THREE_OF_A_KIND {
        @Override public boolean apply(Hand input) {
            return input.rankHistogram().equals(ImmutableMultiset.of(1, 1, 3));
        }
    },
    STRAIGHT {
        @Override public boolean apply(Hand input) {
            return input.isStraight();
        }
    },
    FLUSH {
        @Override public boolean apply(Hand input) {
            return input.suitHistogram().equals(ImmutableMultiset.of(5));
        }
    },
    FULL_HOUSE {
        @Override public boolean apply(Hand input) {
            return input.rankHistogram().equals(ImmutableMultiset.of(2, 3));
        }
    },
    FOUR_OF_A_KIND {
        @Override public boolean apply(Hand input) {
            return input.rankHistogram().equals(ImmutableMultiset.of(1, 4));
        }
    },
    STRAIGHT_FLUSH {
        @Override public boolean apply(Hand input) {
            return input.isStraight() && input.suitHistogram().equals(ImmutableMultiset.of(5));
        }
    },
    ;

    /**
     * Return the cards reordered so that the ranked cards come last.
     * This way a backward lexicographical comparison of the list can be used to determine which hand is stronger.
     *
     * <p>See also this description copied from <a href="https://projecteuler.net/problem=66">Problem 66</a>:
     *
     * <p>If two players have the same ranked hands then the rank made up of the highest value wins;
     * for example, a pair of eights beats a pair of fives (see example 1 below).
     * But if two ranks tie, for example, both players have a pair of queens,
     * then highest cards in each hand are compared (see example 4 below);
     * if the highest cards tie then the next highest cards are compared, and so on.
     */
    List<Card> reorderedCards(Hand hand) {
        checkArgument(hand.toHandValue().equals(this));
        // Only the methods needed for the problem 54 were implemented.
        throw new RuntimeException("Not implemented: " + this);
    }
}

Hand

@Getter @EqualsAndHashCode(of="cards") static class Hand implements Comparable<Hand> {
    Hand(Iterable<Card> cards) {
        assert Iterables.size(cards) == CARDS_IN_HAND;
        this.cards = ImmutableSortedSet.copyOf(cards);
        checkArgument(this.cards.size() == 5, cards);
        final Multiset<Rank> ranks = EnumMultiset.create(Rank.class);
        final Multiset<Suit> suits = EnumMultiset.create(Suit.class);
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (final Card c : this.cards) {
            final Rank rank = c.rank();
            min = Math.min(min, rank.value());
            max = Math.max(max, rank.value());
            ranks.add(rank);
            suits.add(c.suit());
        }
        rankHistogram = histogram(ranks);
        suitHistogram = histogram(suits);
        isStraight = max - min == CARDS_IN_HAND - 1 && rankHistogram.equals(ImmutableMultiset.of(1, 1, 1, 1, 1));
    }

    /**
     * The inverse method to {@link #toString().}
     *
     * <p>The input must be exactly of the form "vs vs vs vs vs",
     * where {@code v} is a {@code Value.symbol()} and {@code s} is {@code Rank.symbol()},
     * for example {@code "5H 5C 6S 7S KD"}
     */
    static Hand forString(String cards) {
        checkArgument(cards.length() == TO_STRING_LENGTH);
        final List<Card> list = Lists.newArrayList();
        for (final String s : Splitter.on(' ').splitToList(cards)) list.add(Card.forString(s));
        return new Hand(list);
    }

    /**
     * Returns a positive number if {@code this} is stronger than {@code other},
     * a negative number if it's weaker,
     * and 0 if they're equally strong.
     */
    @Override public int compareTo(Hand other) {
        final HandValue myHandValue = toHandValue();
        final HandValue otherHandValue = other.toHandValue();
        int result = myHandValue.compareTo(otherHandValue);
        if (result!=0) return result;

        assert myHandValue == otherHandValue;
        final List<Card> myReorderedCards = myHandValue.reorderedCards(this);
        final List<Card> otherReorderedCards = otherHandValue.reorderedCards(other);
        assert myReorderedCards.size() == otherReorderedCards.size();

        // A backward lexicographical comparison of card ranks.
        for (int i=myReorderedCards.size(); i-->0; ) {
            final Rank myRank = myReorderedCards.get(i).rank();
            final Rank otherRank = otherReorderedCards.get(i).rank();
            result = Integer.compare(myRank.value(), otherRank.value());
            if (result!=0) return result;
        }
        return 0;
    }

    @Override public String toString() {
        return Joiner.on(' ').join(cards);
    }

    private static <E> ImmutableMultiset<Integer> histogram(Multiset<E> multiset) {
        final List<Integer> result = Lists.newArrayList();
        for (final Multiset.Entry<E> e : multiset.entrySet()) result.add(e.getCount());
        return ImmutableMultiset.copyOf(result);
    }

    HandValue toHandValue() {
        for (final HandValue v : HAND_VALUES) {
            if (v.apply(this)) return v;
        }
        throw new RuntimeException("Impossible: " + cards);
    }

    private static final int CARDS_IN_HAND = 5;
    static final int TO_STRING_LENGTH = CARDS_IN_HAND * 3 - 1;

    private static final ImmutableList<HandValue> HAND_VALUES = ImmutableList.copyOf(HandValue.values()).reverse();

    private final ImmutableSortedSet<Card> cards;
    private final ImmutableMultiset<Integer> rankHistogram;
    private final ImmutableMultiset<Integer> suitHistogram;
    private final boolean isStraight;
}

HandPair

@RequiredArgsConstructor @Getter static class HandPair {
    /** Accepts one line of <a href="http://projecteuler.net/project/resources/p054_poker.txt">poker.txt</a>. */
    static HandPair forString(String line) {
        checkArgument(line.length() == 2 * Hand.TO_STRING_LENGTH + 1);
        checkArgument(line.charAt(Hand.TO_STRING_LENGTH) == ' ');
        final Hand hand1 = Hand.forString(line.substring(0, Hand.TO_STRING_LENGTH));
        final Hand hand2 = Hand.forString(line.substring(Hand.TO_STRING_LENGTH + 1));
        return new HandPair(hand1, hand2);
    }

    int compare() {
        return hand1.compareTo(hand2);
    }

    private final Hand hand1;
    private final Hand hand2;
}

E054 (the main class for problem 54)

public class E054 {
    public static void main(String[] args) {
        final List<String> lines = EulerUtils.readLines(E054.class);
        checkArgument(lines.size() == 1000);
        int win = 0;
        for (final String s : lines) {
            final HandPair handPair = HandPair.forString(s);
            final int cmp = handPair.compare();

            if (cmp > 0) {
                ++win;
            } else if (cmp == 0) {
                throw new RuntimeException("No two hands are equally strong in the given input! " + s);
            }
        }
        System.out.println(win);
    }
}

E054Test

The test is very rudimentary and was used to help me to find the bugs, so I could solve the problem. Then I stopped to care.

public class E054Test extends TestCase {
    public void testHandForString() {
        final ImmutableList<Card> cards =
                ImmutableList.of(TEN.of(SPADES), TEN.of(DIAMONDS), NINE.of(SPADES), EIGHT.of(SPADES), EIGHT.of(CLUBS));
        final Hand hand = new Hand(cards);
        assertEquals(hand, Hand.forString("TS TD 9S 8S 8C"));
    }

    public void testHandValue() {
        checkHandValue("2S JD 9H 4C QC", HandValue.HIGH_CARD);
        checkHandValue("2C 2D 2H 3C 3D", HandValue.FULL_HOUSE);
        checkHandValue("2C 3D 4H 5C 6D", HandValue.STRAIGHT);
        checkHandValue("2C 2D 4H 5C 6D", HandValue.PAIR);
        checkHandValue("2C 3C 4C 5C 6C", HandValue.STRAIGHT_FLUSH);
    }

    public void testThreeOfAKind() {
        final Hand h = Hand.forString("2S 2D 2H 4C QC");
        assertFalse(HandValue.TWO_PAIRS.apply(h));
        assertTrue(HandValue.THREE_OF_A_KIND.apply(h));
        assertSame(HandValue.THREE_OF_A_KIND, h.toHandValue());
    }

    public void testTwoPairs() {
        final Hand h = Hand.forString("TS TD 9S 8S 8C");
        assertTrue(HandValue.TWO_PAIRS.apply(h));
        assertFalse(HandValue.THREE_OF_A_KIND.apply(h));
        assertSame(HandValue.TWO_PAIRS, h.toHandValue());
    }

    public void testcompareTo() {
        checkCompareFromLine("5H 5C 6S 7S KD 2C 3S 8S 8D TD", -1);
        checkCompareFromLine("5D 8C 9S JS AC 2C 5C 7D 8S QH", +1);
        checkCompareFromLine("2D 9C AS AH AC 3D 6D 7D TD QD", -1);
        checkCompareFromLine("4D 6S 9H QH QC 3D 6D 7H QD QS", +1);
        // Commented out as neither implemented nor needed for the problem 54 itself.
        // checkCompareFromLine("2H 2D 4C 4D 4S 3C 3D 3S 9S 9D", +1);
    }

    private void checkCompareFromLine(String line, int expected) {
        assertEquals(expected, Integer.signum(HandPair.forString(line).compare()));
    }

    private void checkHandValue(String cards, HandValue expected) {
        assertEquals(expected, toHandValue(cards));
    }

    private HandValue toHandValue(String s) {
        return Hand.forString(s).toHandValue();
    }
}

EVERYTHING

I've just published a compilable project on github. For javac, there's a (oneliner) shell script, for Eclipse, you need to install lombok first (included).

Answer 1

A new encoding that eliminates "ReorderedCards"

I recall from a previous question of yours that you packed a 16x16 puzzle into a single long. So I know you'll appreciate this encoding.

Using a single long, you can encode all of the cards so that you can compare the two hands using the long without any other histograms, "reordered cards", etc. The encoding is:

Bits  0-12    Single cards of rank 2..Ace
Bits 13-25    Pairs        of rank 2..Ace
Bits 26-38    Triples      of rank 2..Ace
Bits 39-51    Quads        of rank 2..Ace

For example, a single 2 would set bit 0.
A pair of 2's would set bit 13 and clear bit 0.
A threesome of 2's would set bit 26 and clear bits 0 and 13.
The hand "AAA88" would have bits 38 (three Aces) and 19 (two eights) set.

This is the basic form of what I called handInfo. This form can be used to do a comparison where you used to use a list of reordered cards. There is a more advanced encoding that I did not code up, but which can replace the whole HandValue class as well. I'll explain that encoding later on.

Creating the handInfo

For each card, if it is the first card of that rank you add a bit into the "single cards". If it isn't the first card of that rank, you shift its bit left by 13. I eliminated the suit and rank histograms and added an isFlush boolean as well:

    // These are masks of 13 cards each.
    public  static final long SINGLE_MASK  = (1L<<13) - (1L<<0);
    public  static final long PAIR_MASK    = (1L<<26) - (1L<<13);
    public  static final long TRIO_MASK    = (1L<<39) - (1L<<26);
    public  static final long QUAD_MASK    = (1L<<52) - (1L<<39);

    // This is a mask for one particular rank (4 bits).
    public  static final long RANK_MASK    = (1L<<0)  | (1L<<13) |
                                             (1L<<26) | (1L<<39);

    // This is used to detect a straight.
    private static final long STRAIGHT_VAL = (1L<<5) - (1L<<0);

    // The descriptor of the hand which can be used for comparisons.
    private final long handInfo;

@Getter @EqualsAndHashCode(of="cards") class Hand implements Comparable<Hand> {
        Hand(Iterable<Card> cards) {
                assert Iterables.size(cards) == CARDS_IN_HAND;
                this.cards = ImmutableSortedSet.copyOf(cards);
                checkArgument(this.cards.size() == 5, cards);
                int  suitBits = 0;
                long info     = 0;

                for (final Card c : this.cards) {
                        final int rank = c.rank().value() - 2;
                        long rankBits  = info & (RANK_MASK << rank);

                        if (rankBits == 0) {
                            // First card of this rank, add it to singles.
                            rankBits = 1L << rank;
                        } else {
                            // Already have card of this rank, shift it to
                            // next count.
                            rankBits |= (rankBits << 13);
                        }
                        info ^= rankBits;
                        suitBits |= (1 << (c.suit().symbol() - 'A'));
                }

                // Determine straight and flush.
                long singleCards = info & SINGLE_MASK;
                singleCards >>>= Long.numberOfTrailingZeros(singleCards);
                isStraight = (singleCards == STRAIGHT_VAL);
                isFlush    = (Integer.bitCount(suitBits) == 1);
                handInfo   = info;
        }

Comparing hands

Comparing hands becomes much simpler:

    /**
     * Returns a positive number if {@code this} is stronger than {@code other},
     * a negative number if it's weaker,
     * and 0 if they're equally strong.
     */
    @Override public int compareTo(Hand other) {
            final HandValue myHandValue = toHandValue();
            final HandValue otherHandValue = other.toHandValue();
            int result = myHandValue.compareTo(otherHandValue);
            if (result!=0) return result;

            assert myHandValue == otherHandValue;

            return Long.compare(handInfo, other.handInfo());
    }

Determining the HandValue

Instead of using a rank histogram, the handInfo can do the same thing by using Long.bitCount().

@RequiredArgsConstructor enum HandValue implements Predicate<Hand> {
        HIGH_CARD {
                @Override public boolean apply(Hand input) {
                        long handInfo = input.handInfo();
                        return Long.bitCount(handInfo & Hand.SINGLE_MASK) == 5;
                }
        },
        PAIR {
                @Override public boolean apply(Hand input) {
                    long handInfo = input.handInfo();
                    return (Long.bitCount(handInfo & Hand.PAIR_MASK) == 1) &&
                           (Long.bitCount(handInfo & Hand.SINGLE_MASK) == 3);
                }
        },
        TWO_PAIRS {
                @Override public boolean apply(Hand input) {
                    long handInfo = input.handInfo();
                    return (Long.bitCount(handInfo & Hand.PAIR_MASK) == 2);
                }
        },
        THREE_OF_A_KIND {
                @Override public boolean apply(Hand input) {
                    long handInfo = input.handInfo();
                    return (Long.bitCount(handInfo & Hand.TRIO_MASK) == 1) &&
                           (Long.bitCount(handInfo & Hand.SINGLE_MASK) == 2);
                }
        },
        STRAIGHT {
                @Override public boolean apply(Hand input) {
                    return input.isStraight();
                }
        },
        FLUSH {
                @Override public boolean apply(Hand input) {
                    return input.isFlush();
                }
        },
        FULL_HOUSE {
                @Override public boolean apply(Hand input) {
                    long handInfo = input.handInfo();
                    return (Long.bitCount(handInfo & Hand.TRIO_MASK) == 1) &&
                           (Long.bitCount(handInfo & Hand.PAIR_MASK) == 1);
                }
        },
        FOUR_OF_A_KIND {
                @Override public boolean apply(Hand input) {
                    long handInfo = input.handInfo();
                    return Long.bitCount(handInfo & Hand.QUAD_MASK) == 1;
                }
        },
        STRAIGHT_FLUSH {
                @Override public boolean apply(Hand input) {
                    return input.isStraight() && input.isFlush();
                }
        },
        ;
    }

The source code for my new Hand.java and HandValue.java replacements can be found here on Github.

A more advanced encoding

By using a few more bits, the whole HandValue class can be removed and encoded into the handInfo. I wasn't sure if you like having the hand value separate from the hand itself, though. Here is how it would look:

Verbose encoding
----------------
Bit 52: High Card
Bit 53: Pair
Bit 54: Two Pair
Bit 55: Three of a Kind
Bit 56: Straight
Bit 57: Flush
Bit 58: Full House
Bit 59: Four of a Kind
Bit 60: Straight Flush

Alternate compact encoding
--------------------------
Bits 52-55: 0 = High Card, 1 = Pair, ..., 8 = Straight Flush

Note: High Card, Pair, Two Pair, and Three of a Kind can be combined
into a single value if only comparisons are required.

With this new encoding, when you create a hand you would immediately classify the type of hand and encode the type into the upper bits. Later, to compare hands, you would just compare the two handInfo longs directly as it now contains the entire information required. If you need to get the hand type for whatever reason, you can read it back out of the handInfo.

The "wheel" straight

This probably isn't within the scope of the problem, but I just wanted to mention that in poker, A-2-3-4-5 is usually considered a valid straight, called a "wheel". It is the valued lower than a 2-3-4-5-6 straight. I didn't address this in my solution, but theoretically, after detecting this type of straight I would clear the cards (or just the Ace) from the handInfo to make sure that it compared properly with other straights. Something like this:

// Ace-2-3-4-5
private static final long WHEEL = 0x100fL;

if ((handInfo & SINGLE_MASK) == WHEEL) {
    isStraight = true;
    // Clear out all cards, or do handInfo ^= 0x1000 to clear just the ace.
    // This keeps the comparison correct with other straights.
    handInfo ^= WHEEL;
}

Final thoughts

It's interesting to see how other people work in their native programming languages. I'm a C programmer at heart, and had I written this program (in Java), I would have made each card an int from 0-51. The suit would naturally be encoded in bits 0-1 and the rank in bits 2-5. I wouldn't have had a Rank, Suit, Card, or RankValue class. A Hand would have been an array of 5 ints and the handInfo long to use for comparisons. So basically, I'd be using very little of what Java has to offer.

I learn a lot of new things when I review code like this. I didn't know you could use MultiSets as Histograms and compare them the way you did. I learned how you could use Enums to represent a pair of values at the same time (symbols + ranks). I look forward to the next review.

Answer 2

final List<Card> list = Lists.newArrayList();

I think this line sums up your code pretty well.

You have a strange and different way of programming. Where I'd write final List<Card> list = new ArrayList<>();, You'd involve some utils class of some sort. It's not wrong, it's just different.

And there's plenty more of those.

Things like putting variables at the bottom of a class, rather than at the top. Or making asserts. Or putting everything into one file because that's easier to work with. Or having some tool that generates various functions at compile time based on annotations... It's not my kind of style, and I'm not used to it.

I read the code in great detail, the only thing I have actual complaints on is how you handled the main class. cmp and win aren't the strongest variable names, and certainly not for code at the highest level of your program.