Poker Hand Evaluation - Finding a straight

Question

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, int startIndex, int wildcards) {
     int wildsLeft = wildcards;
     for (int i = startIndex; i >= 0; i--) {
         int count = ranks[i];
         if (count > 0) {
             // do nothing
         }
         else if (wildsLeft > 0) {
             wildsLeft--;
         }
         else {
             return findHighestIndexForStraight(ranks, startIndex - 1, wildcards);
         }
         if (startIndex - i + 1 >= PokerHandResultProducer.HAND_SIZE)
             return startIndex + 1;
     }
     return -1;
 }

   @Override
   public PokerHandResult resultFor(PokerHandAnalyze analyze) {
      int straight = findHighestIndexForStraight(analyze.getRanks(), analyze.getWildcards());
      if (straight != -1)
          return new PokerHandResult(PokerHandType.STRAIGHT, straight, 0, null);
      // We don't need to provide any kickers since we have a straight of 5 cards.

      return null;
   }
}

Here is some code to test the method, also showing what I expect it will return:

private int findHighestIndexForStraight(int[] ranks, int wildcards) {
    int res = PokerStraight.findHighestIndexForStraight(ranks, wildcards);
    return res == -1 ? res : res - 1; // For testing, I want to know the index and not the "rank"
}

@Test
public void straights() {
    assertEquals(7,  findHighestIndexForStraight(new int[]{ 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0 }, 0));
    assertEquals(7,  findHighestIndexForStraight(new int[]{ 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1 }, 0));
    assertEquals(7,  findHighestIndexForStraight(new int[]{ 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 }, 0));
    assertEquals(-1, findHighestIndexForStraight(new int[]{ 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0 }, 1));
    assertEquals(8,  findHighestIndexForStraight(new int[]{ 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0 }, 1));
    assertEquals(6,  findHighestIndexForStraight(new int[]{ 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0 }, 1));
    assertEquals(10, findHighestIndexForStraight(new int[]{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 }, 1));
    assertEquals(4,  findHighestIndexForStraight(new int[]{ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 }, 1));
    assertEquals(8,  findHighestIndexForStraight(new int[]{ 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 }, 1));
    assertEquals(10, findHighestIndexForStraight(new int[]{ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0 }, 1));
    assertEquals(-1, findHighestIndexForStraight(new int[]{ 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1 }, 0));
}

Answer 1

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 <= 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
                // 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;
}

Answer 2

Separation of responsibilities

The findHighestIndexForStraight method is a bit confusing, because there are several elements entangled in it:

• It contains the logic of exploring ranks for a straight (loop from the end to start)
• It contains the logic of checking if a sequence is straight or not
• Somewhere in the middle of it all it references a global constant (HAND_SIZE)

These could be separated in a more readable way:

public static int findHighestIndexForStraight(int[] ranks, int wildcards) {
    for (int endIndex = ranks.length - 1; endIndex >= 0; --endIndex) {
        if (straightExists(ranks, endIndex, HAND_SIZE, wildcards)) {
            return endIndex + 1;
        }
    }
    return -1;
}

public static boolean straightExists(int[] ranks, int endIndex, int targetCount, int wildcards) {
    if (targetCount == 0) {
        return true;
    }
    if (targetCount > endIndex + 1) {
        return false;
    }
    int wildcardsLeft = wildcards;
    if (ranks[endIndex] <= 0) {
        if (wildcards == 0) {
            return false;
        }
        --wildcardsLeft;
    }
    return straightExists(ranks, endIndex - 1, targetCount - 1, wildcardsLeft);
}

In this version the responsibilities are better separated:

• straightExists checks if a straight of given target size exists from a given end-position
• findHighestIndexForStraight contains the logic of searching from the end
• The reference to HAND_SIZE is no longer buried in the middle, it's more visible at a more central place in the code, where its purpose is easier to understand

Empty block with // do nothing comment

Empty blocks are not great. Although the comment // do nothing makes it clear that the empty block is not an accident, it's still not great. The code can be rearranged without the empty block, and then it can speak for itself without necessitating a comment:

if (count <= 0) {
    if (wildsLeft > 0) {
        wildsLeft--;
    } else {
        return findHighestIndexForStraight(ranks, startIndex - 1, wildcards);
    }
}
if (startIndex - i + 1 >= HAND_SIZE) {
    return startIndex + 1;
}

Using the right types

Given this function and its doc string:

/**
  * Scans an array of ints to search for sequence of 1s. [...]
  */
public static int findHighestIndexForStraight(int[] ranks, int wildcards) {

The implementation doesn't really use the integer values in the int[] parameter, it could work just as well with a boolean[]. Having a signature for exactly what's needed would make the code slightly easier to understand.

That said, I haven't looked at the rest of the implementation, and maybe this makes perfect sense and everything's fine. For example it might be too tedious and inefficient to add a filtering step for the ranks parameter, in which case the current version would be still overall more readable. In that case ignore my comment, I leave it up to your judgment.

Answer 3

Call me a necromancer

I realize this answer is a year and a half too late, but this question showed up in the sidebar, so I clicked on it. After I read the question and the answer, I couldn't help myself. So here is my version, which is quite a bit simpler.

The original version

The original code has \$O(n*m)\$ complexity, where \$n\$ is the number of ranks and \$m\$ is the number of cards in a hand. Given that these are 13 and 5 respectively, this isn't too far off from an \$O(n)\$ solution. One thing that could have been changed is to remove the recursive call and simply back up the loop to the proper position, resetting the number of wildcards (or equivalently to use two loops). Either way the code would have the same time complexity, but the recursive might use an extra \$O(n)\$ stack space (or might not if there was a tail recursion optimization).

The revised version

My revised version does pretty much what the original version does in terms of checking ranges of cards from the highest to the lowest. The key difference is that it makes use of the fact that when you reject one set of cards, you can move onto the next set without starting over. For example, if you know you have 4 cards in the 10..Ace range, then you can move to the 9..K range by adding in one card if you have a 9 and subtracting one if you have an Ace. So this version runs in \$O(n)\$ time.

public static final int HAND_SIZE = 5;

/**
 * This function finds a straight by examining a range of HAND_SIZE
 * cards.  It starts with the topmost HAND_SIZE cards and counts how
 * many cards are in that range.  If at any point in time, the number
 * of cards in the range plus the number of wildcards becomes HAND_SIZE,
 * then a straight has been found.  If no straight is found, the range
 * slides down by one rank.  The number of cards in the new range is
 * simply the previous count plus the new lowest card entering the range
 * minus the high card that is leaving the range.
 */
public static int findHighestIndexForStraight(int[] ranks, int wildcards) {
    // Sanity check.
    if (HAND_SIZE > ranks.length)
        return -1;

    int numCardsInRange   = wildcards;
    int lowestCardInRange = ranks.length;

    // Start by counting the cards in the topmost range.
    for (int i=0;i<HAND_SIZE;i++)
        numCardsInRange += ranks[--lowestCardInRange];

    while (true) {
        // Check if we found a straight.
        if (numCardsInRange >= HAND_SIZE)
            return lowestCardInRange + HAND_SIZE;
        // Slide the range down by one rank.  If the lowest card goes
        // below 0, there are no straights.
        if (--lowestCardInRange < 0)
            return -1;
        numCardsInRange += ranks[lowestCardInRange] -
                           ranks[lowestCardInRange+HAND_SIZE];
    }
}