12
\$\begingroup\$

This challenge posted by Durron597 intrigued me, and inspired me to answer his question, and also to determine whether a more functional approach was available for poker hand ranking.

The problem description is:

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

I decided to use a cascading most-signigicant-bits type approach to rank hands against each other. In other words, calculate a unique score for each hand. The actual score does not matter, the only reason for the score is to be a relative ranking against another hand. The hand with the larger score wins. The difference between the scores is not important.

In order to accomplish this, I broke a Java long value in to 8 4-bit segments.

7777 6666 5555 4444 3333 2222 1111 0000
   |    |    |    |    |    |    |     --> Lowest ranked card
   |    |    |    |    |    |     -------> Second Lowest card
   |    |    |    |    |     ------------> Third lowest card
   |    |    |    |     -----------------> Second highest card
   |    |    |     ----------------------> Highest ranked card
   |    |     ---------------------------> SMALLSAME - Rank of low pair, if any
   |     --------------------------------> LARGESAME - Rank of largest group, if any
    -------------------------------------> NAMENIBBLE - Hand type value

There are 13 cards, which fit quite nicely in the 16 avaialble values in a nibble.

I ordered the cards as 2 through ace, with the values (in hex) of 2 through E

The hand classifications in the highest nibble are a bit more complicated. The overall classification uses a little trick of bit manipulation too, so I present it in bit (and decimal) format, with a hexadecimal example too:

Type  Dec  Example    Description
====  ===  ========   =======================================================
0000    0  000DA742   High card only  -> King, 10, 7, 4, 2 (no flush)
0001    1  140DA442   One pair        -> King, 10, 4, 4, 2
0010    2  2D4DD442   Two pair        -> King, King 4, 4, 2
0011    3  340DA444   Three of a kind -> King, 10, 4, 4, 4
0100    4  400DCBA9   Straight        -> King, Queen, Jack, 10, 9 (no flush)
1000    8  800DA742   Flush           -> King, 10, 7, 4, 2
1001    9  94DDD444   Full House      -> King, King, 4, 4, 4
1010   10  A40D4444   Four of a kind  -> King, 4, 4, 4, 4
1100   12  C00DCBA9   Straight Flush  -> King, Queen, Jack, 10, 9
1100   12  C00EDCBA   Royal Flush     -> Ace, King, Queen, Jack, 10

Notice how the Straight and the flush bits are 'toggles', and also notice that the Royal Flush is nothing special, just a straight flush starting with an Ace.

Some other notes... no hand with any pairs, triples, or quads, could ever be a straight, or a flush.

Using this system, I can relatively easily shift a card's details around in a way that just slots everything in to position. Any hand with a higher score than another hand will automatically win. Hands with the same score are a tie.

So, the following code is just a way to sort a hand in to a bitwise vector using a few tricks to accomplish the task. As an example, it reads the data from the Project Euler website, or from the specified input file, if given.

I have tried to use Java 8 streams and lambdas where they make sense.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URI;
import java.net.URL;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.IntSummaryStatistics;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;

public class HandSome {
    
    private static final boolean DEBUG = Boolean.getBoolean("DEBUG");

    /*
    7777 6666 5555 4444 3333 2222 1111 0000
       |    |    |    |    |    |    |     --> Lowest ranked card
       |    |    |    |    |    |     -------> Second Lowest card
       |    |    |    |    |     ------------> Third lowest card
       |    |    |    |     -----------------> Second highest card
       |    |    |     ----------------------> Highest ranked card
       |    |     ---------------------------> SMALLSAME - Rank of low pair, if any
       |     --------------------------------> LARGESAME - Rank of largest group, if any
        -------------------------------------> NAMENIBBLE - Hand type value
    */
    
    // Where to shift important information
    // - Hand category in most significant.
    // - rank of most important group (4 of a kind, 3 of a kind,
    //         3 group in full house, highest pair rank)
    // - rank of the lesser group (low pair in full house, or 2 pairs)
    // Remaining lower bits in number represent the individual cards.
    private static final int NAMENIBBLE = 7; // bits 28-31
    private static final int LARGESAME = 6; // bits 24-27
    private static final int SMALLSAME = 5; // bits 20-23

    private static int lookupRank(char c) {
        switch (c) {
            case '2' : return 0;
            case '3' : return 1;
            case '4' : return 2;
            case '5' : return 3;
            case '6' : return 4;
            case '7' : return 5;
            case '8' : return 6;
            case '9' : return 7;
            case 'T' : return 8;
            case 'J' : return 9;
            case 'Q' : return 10;
            case 'K' : return 11;
            case 'A' : return 12;
        }
        throw new IllegalArgumentException("No such card '" + c + "'.");
    }
    

    private static final int[] REVERSE =
        { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

    // These constants are carefully selected to ensure that
    // - STRAIGHT is > 3-of-a-kind
    // - STRAIGHT and FLUSH are less than 4-of-a-kind and full-house.
    // - STRAIGH + FLUSH (12) is better than others.
    private static final int STRAIGHT = 4;
    private static final int FLUSH = 8;
    // groups representing :
    // HIGH_CARD, 1_PAIR, 2_PAIR, 3_OF_A_KIND, FULL_HOUSE,  4_OF_A_KIND
    private static final int[] GROUPSCORE = { 0, 1, 2, 3, 9, 10 };
    private static final int[] GROUPS = { 
        groupHash(new int[]{ 1, 1, 1, 1, 1 }),
        groupHash(new int[]{ 1, 1, 1, 2 }),
        groupHash(new int[]{ 1, 2, 2 }),
        groupHash(new int[]{ 1, 1, 3 }),
        groupHash(new int[]{ 2, 3 }),
        groupHash(new int[]{ 1, 4 }) };


    private static final int groupHash(int[] group) {
        int ret = 0;
        for (int i = group.length - 1; i >= 0; i--) {
            ret |= group[i] << (3 * i);
        }
        return ret;
    }
    
    private static final boolean isStraight(int[] ranks) {
        // true if there are 5 distinct cards
        // and the highest is 4 larger than the lowest.
        IntSummaryStatistics stats = IntStream.of(REVERSE)
                .filter(i -> ranks[i] != 0).summaryStatistics();
        return stats.getCount() == 5 && stats.getMax() - stats.getMin() == 4;
    }

    private static long shiftCard(long base, int id, int nibble) {
        // Represent cards nicely in the long base.
        // card 0 (the lowest rank), is shifted to 2, and so on, so that
        // the ranks of 0 through 12 become hex 2 through E with 10,
        // Jack, Queen, King, and Ace being represented as A, B, C, D, E
        // Don't offset the values highest nibble, those are not cards. 
        int offset = nibble == NAMENIBBLE ? 0 : 2;
        return base | ((long) (id + offset) << (nibble * 4));
    }

        /**
         * Process an input hand (5 cards) and return a long value that
         * can be used to compare the value of one hand against another
         * @param hand The 5 cards to rank
         * @return the long value representing the hand score.
         */
    public static long scoreHand(List<String> hand) {
        if (hand.size() != 5) {
            throw new IllegalArgumentException("Illegal hand " + hand);
        }

        // sort the cards we are holding in ascending order of rank.
        int[] holding = hand.stream().mapToInt(c -> lookupRank(c.charAt(0)))
                .sorted().toArray();

        int[] countRanks = new int[13];
        IntStream.of(holding).forEach(r -> countRanks[r]++);

        // filter and sort the group counts.
        int countSummary = groupHash(IntStream.of(countRanks).filter(c -> c > 0)
                .sorted().toArray());

        // match the counts against those things that matter
        final int group = IntStream.range(0, GROUPS.length)
                .filter(i -> GROUPS[i] == countSummary)
                .findFirst().getAsInt();

        // record each card as values in the low nibbles of the score.
        long score = IntStream.range(0, 5)
                .mapToLong(i -> shiftCard(0, holding[i], i)).sum();

        // record any group rankings in to the score in the high nibble.
        score = shiftCard(score, GROUPSCORE[group], NAMENIBBLE);

        // for no-cards-the-same, look for a flush.
        if (group == 0 && hand.stream().mapToInt(c -> c.charAt(1)).distinct().count() == 1) {
            score = shiftCard(score, FLUSH, NAMENIBBLE);
        }

        // for no cards the same, look for a straight (could also be a flush)
        if (group == 0 && isStraight(countRanks)) {
            score = shiftCard(score, STRAIGHT, NAMENIBBLE);
        }

        // if there are cards the same, record the groups in descending
        // relevance in the mid-tier nibbles.
        if (group != 0) {
            int[] scounts = IntStream
                    .of(4, 3, 2)
                    .flatMap(
                            c -> IntStream.of(REVERSE).filter(
                                    i -> countRanks[i] == c)).limit(2)
                    .toArray();
            score = shiftCard(score, scounts[0], LARGESAME);
            if (scounts.length > 1) {
                score = shiftCard(score, scounts[1], SMALLSAME);
            }
        }
        
        if (DEBUG) {
            System.out.printf("Hand %s scores as %8X\n", hand, score);
        }

        return score;
    }

    public static long compareHands(String hand) {
        // Convert the String to separate cards
        List<String> cards = Stream.of(hand.split(" ")).collect(
                Collectors.toList());

        long handA = scoreHand(cards.subList(0, 5));
        long handB = scoreHand(cards.subList(5, 10));
        
        return handA - handB;
    }

    public static BufferedReader readSource(String[] args) throws IOException {
        if (args.length > 0) {
            return Files.newBufferedReader(Paths.get(args[0]));
        }
        URL url = URI.create(
                "https://projecteuler.net/project/resources/p054_poker.txt")
                .toURL();
        return new BufferedReader(new InputStreamReader(url.openStream()));
    }

    public static long countPlayer1Wins(Path path) throws IOException {

        try (BufferedReader reader = Files.newBufferedReader(path)) {
            return reader.lines().mapToLong(hands -> compareHands(hands))
                            .filter(diff -> diff > 0).count();
        }
    }
    
    public static void main(String[] args) throws IOException {
        final long[] times = new long[1000]; 
        final long[] results = new long[1000]; 
        final Path source = Paths.get(args.length == 0 ? "p054_poker.txt" : args[0]);
        for (int i = 0; i < times.length; i++) {
            long nano = System.nanoTime();
            results[i] = countPlayer1Wins(source);
            times[i] = System.nanoTime() - nano;
        }
        
        System.out.println(LongStream.of(results).summaryStatistics());
        System.out.println(LongStream.of(times).mapToDouble(t -> t / 1000000.0).summaryStatistics());
        
    }

}

If you want, you can enable the debug output by setting -DDEBUG=true on the java commandline (VM argument, not program argument). When you run with debug you get output like:

Hand [KS, 7H, 2H, TC, 4H] scores as    DA742
Hand [2C, 3S, AS, AH, QS] scores as 1E0EEC32
Hand [8C, 2D, 2H, 2C, 4S] scores as 32084222
Hand [4C, 6S, 7D, 5S, 3S] scores as 40076543
Hand [TH, QC, 5D, TD, 3C] scores as 1A0CAA53
Hand [QS, KD, KC, KS, AS] scores as 3D0EDDDC
Hand [4D, AH, KD, 9H, KS] scores as 1D0EDD94
Hand [5C, 4C, 6H, JC, 7S] scores as    B7654
Hand [KC, 4H, 5C, QS, TC] scores as    DCA54
Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

The implementation; it is really slick. I find the code difficult to review, because you've deliberately set out to present a demonstration of a functional approach. Making the code more elegant may end up disguising the point....

That said, there are improvements available that should not interfere with the implementation

More Abstractions

public static void main(String[] args) throws IOException {
    final long[] times = new long[1000]; 
    final long[] results = new long[1000]; 
    final Path source = Paths.get(args.length == 0 ? "p054_poker.txt" : args[0]);
    for (int i = 0; i < times.length; i++) {
        long nano = System.nanoTime();
        results[i] = countPlayer1Wins(source);
        times[i] = System.nanoTime() - nano;
    }

    System.out.println(LongStream.of(results).summaryStatistics());
    System.out.println(LongStream.of(times).mapToDouble(t -> t / 1000000.0).summaryStatistics());

}

In this method, you have at least three different ideas; your calculator -- the featured element of your demonstration, an instrumentation harness around it, and a data provider. I'd prefer and example that teases those ideas apart.

public static void main(String args[]) throws IOException {
    PokerScoringCalculator calculator = new PokerScoringCalculator();
    InstrumentationHarness testHarness = new InstrumentationHarness(calculator);
    TestDataFactory testDataFactory = new testDataFactory(args);

    testHarness.run(testDataFactory.getSource());
}

public static class InstrumentationHarness {
    private final PokerScoringCalculator target;

    ...

    public void run(Path source) {
        final int testIterationCount = 1000;

        final long[] times = new long[testIterationCount];
        final long[] results = new long[testIterationCount];

        for (int i = 0; i < times.length; i++) {
            long nano = System.nanoTime();
            results[i] = calculator.countPlayer1Wins(source);
            times[i] = System.nanoTime() - nano;
        }

        ...
    }
}

Further refactoring here might reveal a Clock abstraction, and a Reporter abstraction that is separate from the TestHarness itself....

Another example

public static long compareHands(String hand) {
    // Convert the String to separate cards
    List<String> cards = Stream.of(hand.split(" ")).collect(
            Collectors.toList());

    long handA = scoreHand(cards.subList(0, 5));
    long handB = scoreHand(cards.subList(5, 10));

    return handA - handB;
}

Buried in here, you've got a parser, a comparator, and the scoring encoder. 

// These constants are carefully selected to ensure that
// - STRAIGHT is > 3-of-a-kind
// - STRAIGHT and FLUSH are less than 4-of-a-kind and full-house.
// - STRAIGH + FLUSH (12) is better than others.
// groups representing :
// HIGH_CARD, 1_PAIR, 2_PAIR, 3_OF_A_KIND, FULL_HOUSE,  4_OF_A_KIND

Don't these comments just scream that there's an enumeration waiting to be discovered?

private static final int[] GROUPSCORE = { 0, 1, 2, 3, 9, 10 };
private static final int[] GROUPS = { 
    groupHash(new int[]{ 1, 1, 1, 1, 1 }),
    groupHash(new int[]{ 1, 1, 1, 2 }),
    groupHash(new int[]{ 1, 2, 2 }),
    groupHash(new int[]{ 1, 1, 3 }),
    groupHash(new int[]{ 2, 3 }),
    groupHash(new int[]{ 1, 4 }) };

These arrays do not communicate that score:9 is bound to group[2,3]. It's not even obvious that they should be the same size! There really ought to be a builder here, which takes score pattern pairs as inputs, and gives you the arrays you need at the end. You could be plain

    builder.add(new int[] {2,3}, 9);

Reversing the order of the arguments gives you an opportunity to get cute:

    builder.add(9, 2, 3);

But I don't approve of that approach -- it makes it look like these are all the same thing. It looks a little bit better with the enumeration.

    builder.add(FULL_HOUSE, 2, 3);

I think it's a bit weird that the patterns are described in ascending order. In natural language, the three-of-a-kind comes first; so I would rather see the logic written that way 

    builder.add(FULL_HOUSE, 3, 2);

If you really wanted to make things readable, you might go with a fluent interface here

    builder.forPattern(3,2).scoreAs(FULL_HOUSE);

Readability again:

    switch (c) {
        case '2' : return 0;
        case '3' : return 1;
        case '4' : return 2;
        case '5' : return 3;
        case '6' : return 4;
        case '7' : return 5;
        case '8' : return 6;
        case '9' : return 7;
        case 'T' : return 8;
        case 'J' : return 9;
        case 'Q' : return 10;
        case 'K' : return 11;
        case 'A' : return 12;
    }

Why not

    "23456789TJQKA".indexOf(c)

Although, as before, there's an argument that the more natural representation is "AKQJ...", which gets reversed.

Magic Numbers

In spades.

Choosing two of the easy ones:

    if (hand.size() != 5) {
        throw new IllegalArgumentException("Illegal hand " + hand);
    }
    ...
    long score = IntStream.range(0, 5)
            .mapToLong(i -> shiftCard(0, holding[i], i)).sum();
    ...
    long handA = scoreHand(cards.subList(0, 5));
    long handB = scoreHand(cards.subList(5, 5+5));

Those are all the same "5".

    int[] countRanks = new int[13];

    switch (c) {
        case '2' : return 0;
        case '3' : return 1;
        case '4' : return 2;
        case '5' : return 3;
        case '6' : return 4;
        case '7' : return 5;
        case '8' : return 6;
        case '9' : return 7;
        case 'T' : return 8;
        case 'J' : return 9;
        case 'Q' : return 10;
        case 'K' : return 11;
        case 'A' : return 12;
    }

private static final int[] REVERSE =
    { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

Those are all the same "13".

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.