patternjavaMinor

Poker Hand Evaluation - Finding a straight

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

pokerhandevaluationstraightfinding

Problem

Weekend Challenge #2 - Poker Hand Evaluation

Finding a straight with wildcards

Because of a size limit on Code Review I have to split my weekly challenge result in two, and here is a part where I think there is some room for speed optimization. I started writing this method in another approach, but after several hours it still didn't work as expected so I threw it away and started writing this method which directly worked as I wanted it to.

The method should take an int array as input, loops through the array to find the highest possible straight (at least five consecutive values of > 0). If encountering a 0 and it has a wildcard to use, it should use the wildcard to "fill in the gap". For example, the array 1 0 1 1 1 with one wildcard is a straight, while the array 1 0 0 1 1 with a wildcard is not a straight.

There is no limit to how many wildcards can be used, but if there are five or more wildcards then the wildcards themselves should return the highest possible straight.

I'm not quite sure what the time complexity is in this method I have written, but I think worst case is between \$O(n)\$ and \$O(n^2)\$, I think it is about \$O(n^2 / 2)\$ or something. If anyone knows, please let me know.

Is it possible to write this method with worst case not higher than \$O(n)\$?

```
/**
* Checks for a normal STRAIGHT. Returns null if no straight was found
*/
public class PokerStraight implements PokerHandResultProducer {

/**
* Scans an array of ints to search for sequence of 1s. Can fill in gaps by using wildcards
* @param ranks An array of the ranks provided by {@link PokerHandAnalyze}
* @param wildcards Number of usable wildcards to fill gaps for the straight
* @return The highest rank (index + 1) for which the straight started
*/
public static int findHighestIndexForStraight(int[] ranks, int wildcards) {
return findHighestIndexForStraight(ranks, ranks.length - 1, wildcards);
}

private static int findHighestIndexForStraight(int[] ranks,

Solution

In this case bit-wise manipulation is your friend .... (as it often is...)....

I believe the following solution makes the combination/permutation expense a 1-off setup problem, and using the Integer.bitCount(...) makes it almost trivial ...

The code I hacked up appears to have a time-complexity of O(n) related to the size of the rank, and a small penalty for the number of wild-cards.... but, in essence, the method runs O(1) since those things will never change much....

but the code looks like:

private static final int[][] WILDCARDS = buildWildCards();

private static int[][] buildWildCards() {
    // up to 5 wild cards
    // that is up to 0x1f or 32 values (counting 0).
    int[] pos = new int[6];
    int[][] ret = new int[6][];
    ret[0] = new int[1];  // one value with no bits set. 0x00
    ret[1] = new int[5];  // 5 with 1 bits set 0b10000, 0b01000, 0b00100, 0b00010, 0b00001
    ret[2] = new int[10]; // 10 with 2 bits set ....
    ret[3] = new int[10]; // 10 with 3 bits set ....
    ret[4] = new int[5];  // 5 with 4 bits set 0b01111, 0b10111, 0b11011, 0b11101, 0b11110
    ret[5] = new int[1];  // one value with all bits set. 0x1f
    for (int i = 0; i = WILDCARDS.length) {
        throw new IllegalArgumentException("WildCard count is not valid. Input " + 
                wildcards + " should be between 0 and " + (WILDCARDS.length - 1));
    }

    int hand = 0;
    for (int r : ranks) {
        hand = 5) {
        // OK, so 'hand' is a bit-pattern with the most 'valuable' cards on the right.
        // if the right-5 bits are all set then there's a straight.
        for (int wcpattern : wildcardoptions) {
            // Look at our combinations of wild-card options.
            if (((hand | wcpattern) & 0x1f) == 0x1f) {
                // return the position if a wild-card match makes 5-in-a-row.
                // what we do is 'OR' all of the wild-card patterns (for the number of
                // wildcards we have), with the 5-right bits, and if any of the results
                // have all the 5-right bits set, then there's a match.
                return position;
            }
        }
        // OK, so none of the wild-cards matched this 5 bits... so we shift the hand
        // right once, and try all the patterns again.
        // shift the hand ....
        hand >>>= 1;
    }
    // could not match a consecutive set of straights.
    return -1;
}

Code Snippets

private static final int[][] WILDCARDS = buildWildCards();

private static int[][] buildWildCards() {
    // up to 5 wild cards
    // that is up to 0x1f or 32 values (counting 0).
    int[] pos = new int[6];
    int[][] ret = new int[6][];
    ret[0] = new int[1];  // one value with no bits set. 0x00
    ret[1] = new int[5];  // 5 with 1 bits set 0b10000, 0b01000, 0b00100, 0b00010, 0b00001
    ret[2] = new int[10]; // 10 with 2 bits set ....
    ret[3] = new int[10]; // 10 with 3 bits set ....
    ret[4] = new int[5];  // 5 with 4 bits set 0b01111, 0b10111, 0b11011, 0b11101, 0b11110
    ret[5] = new int[1];  // one value with all bits set. 0x1f
    for (int i = 0; i <= 0x1f; i++) {
        // cout the bits that are set in this number.
        final int bc = Integer.bitCount(i);
        // load this number in to the slot matching the set bit count.
        ret[bc][pos[bc]++] = i;
    }
    return ret;
}



/**
 * Scans an array of ints to search for sequence of 1s. Can fill in gaps by using wildcards
 * @param ranks An array of the ranks provided by {@link PokerHandAnalyze}
 * @param wildcards Number of usable wildcards to fill gaps for the straight
 * @return The highest rank (index + 1) for which the straight started
 */
public static int findHighestIndexForStraight(int[] ranks, int wildcards) {
    if (wildcards < 0 || wildcards >= WILDCARDS.length) {
        throw new IllegalArgumentException("WildCard count is not valid. Input " + 
                wildcards + " should be between 0 and " + (WILDCARDS.length - 1));
    }

    int hand = 0;
    for (int r : ranks) {
        hand <<= 1;
        hand |= r != 0 ? 1 : 0;
    }
    // OK, the `hand` is set up so that the bits represent the hand.
    // for example, an input array of [0,1,0,0,1,1,1,1,0,0,1] will become:
    //    0b01001111001 or 0x0279

    // We now shift off the hand to see if we can make a match;
    // position is a backward-count of the number of shifts we have to do.
    // it starts off at the ranks's length -1, and counts back down.
    // when it is less than 5 (or actually 4 because the condition is checked
    //    before the decrement)
    // there cannot possibly be a 5-card match, so there is thus no match. 
    int position = ranks.length;

    // choose the set of wild-card options that match the input value.
    int[] wildcardoptions = WILDCARDS[wildcards];

    while (position-- >= 5) {
        // OK, so 'hand' is a bit-pattern with the most 'valuable' cards on the right.
        // if the right-5 bits are all set then there's a straight.
        for (int wcpattern : wildcardoptions) {
            // Look at our combinations of wild-card options.
            if (((hand | wcpattern) & 0x1f) == 0x1f) {
                // return the position if a wild-card match makes 5-in-a-row.
                // what we do is 'OR' all of the wild-card patterns (for the number of
                // wildcards we have), with the 5-right bits, and if any of the results

Context

StackExchange Code Review Q#36915, answer score: 6

Revisions (0)

No revisions yet.