Sign in to follow this  
DrunkenLizard

Checking a hand of cards for a win

Recommended Posts

Hi all, I'm trying to think of a simple and elegant way to write an algorithm that checks a hand of cards for a winning combination. The card game is 7-card rummy, and the win conditions are fairly simple: You have 7 cards, and you win by collecting a "set" of 3 and set of 4 cards. The sets are similar to Gin Rummy sets - either 3 or 4 cards of the same suit, or 3 or 4 cards of a straight flush run (that is, same suit and in running order). Does anyone have any suggestions how to go about doing this? I can think of a few different ways but I don't think any of them are very efficient :(

Share this post


Link to post
Share on other sites
This is pretty straightforward. The tricky part is knowing how to do the partitioning to cover all possibilities.


def is_3card_set(cards):
# left as an exercise

def is_4card_set(cards):
# left as an exercise

def test_partitions(left_cards, right_cards):
if len(left_cards) == 3:
return is_3card_set(left_cards) and is_4card_set(right_cards)

for i, card in enumerate(right_cards):
if test_partitions(left_cards + card, right_cards[:i] + right_cards[i:]):
return True

return False

def is_winning_hand(cards):
return test_partitions([], cards)


Share this post


Link to post
Share on other sites
Hi Zahlman, thanks for your reply. I'm not sure if I fully understand your solution however. Is it written in some kind of pseudocode notation?
From what I can gather, you suggest that I test every 3 and 4 card combination in the hand, using a recursive function to iterate over the cards, correct?

Share this post


Link to post
Share on other sites
Quote:
Original post by DrunkenLizard
Hi Zahlman, thanks for your reply. I'm not sure if I fully understand your solution however. Is it written in some kind of pseudocode notation?
Actually, it is written in Python, but it is close enough to pseudo code.
Quote:
From what I can gather, you suggest that I test every 3 and 4 card combination in the hand, using a recursive function to iterate over the cards, correct?
That is correct. However, while this is a very elegant functional programming solution, it may not be the simplest to implement in C++. You might want to look into an approach based on sorting - if you sort the hand by card value, then all cards within a run or set end up adjacent, and runs end up in order.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
From what I can gather, you suggest that I test every 3 and 4 card combination in the hand, using a recursive function to iterate over the cards, correct?
That is correct. (...)


Ok, well that was one way that I initially threw away because I figured it would be a lot slower to go through all possible combinations of cards. On reflection though most combinations would be eliminated pretty quick, so I'm thinking this might be viable.

What I'm looking at the moment is a setup like this (written in Java):

// for every possible 3 card partition (there are 70 (I think))
for (int first = 0; first < hand.size() - 2; ++first)
for (int second = 1; second < hand.size() - 1; ++second)
for (int third = 2; third < hand.size(); ++third)
{
// return is_3_card_set(first, second, third) &&
// is_4_card_set(<other cards>);
}


What I'm having to do to determine <other cards> is create a new copy of the original cards list inside each iteration of the innermost loop, subtract the current 3 card partition from it, and use the remainder as the 4 card partition. What I'd like to be able to do is somehow set up the inner loop to avoid creating a new list each time but I can't get my head around that part. Can anyone think of some primitive type wizardry that could work here?

(Essentially what I'm asking is, given a set of integers C, and given a subset of those integers c, does anyone know a quick way figuring out C-c?).

Share this post


Link to post
Share on other sites
Quote:
Original post by DrunkenLizard
Ok, well that was one way that I initially threw away because I figured it would be a lot slower to go through all possible combinations of cards. On reflection though most combinations would be eliminated pretty quick, so I'm thinking this might be viable.


Well, just how much speed is necessary here, anyway?

Quote:
What I'm having to do to determine <other cards> is create a new copy of the original cards list inside each iteration of the innermost loop, subtract the current 3 card partition from it, and use the remainder as the 4 card partition. What I'd like to be able to do is somehow set up the inner loop to avoid creating a new list each time but I can't get my head around that part. Can anyone think of some primitive type wizardry that could work here?


You could set up an int[] instead of a list; and you could reuse it. I assume that's what you mean by "primitive type wizardry".

Also, instead of putting all the values 0-6 into the container, and then pulling out first/second/third, you could scan through those values and only put in the ones that aren't first/second/third in the first place. :)

Of course, I'd guess you'll get much more of a boost from only considering ordered partitions (notice how I initialize the loop counters). You could also inform the compiler that hand.size() is a constant ;)


int size = hand.size();
int[] others = new int[size - 3];
for (int first = 0; first < size - 2; ++first) {
for (int second = first + 1; second < size - 1; ++second) {
for (int third = second + 1; third < size; ++third) {
int position = 0;
for (int scan = 0; scan < size; ++scan) {
if (scan != first && scan != second && scan != third) {
others[position++] = scan;
}
}
return is_3_card_set(first, second, third) &&
is_4_card_set(others);
}
}
} // And it surely wouldn't kill you to get in the habit of putting in the
// other braces, either...



Share this post


Link to post
Share on other sites
Quote:

Original post by Zahlman
Well, just how much speed is necessary here, anyway?


Point taken - it is written in Java so I wanted to keep it as fast as possible, but ultimately the overhead of manipulating ArrayLists isn't much slower than using the actual arrays themselves. The most concerning part was using
ArrayList.remove(Object)
, which also forces the list to copy all array data one index lower.

Here is what I did anyway, if anyone is interested:


1. sort the cards according to suit then rank
(any valid runs we have will appear somewhere in the hand)

2. search for the largest run contained within the hand

3. take each valid 4 card partition from the run and check the remaining 3 cards for validity

4. take each valid 3 card partition from the run and check the remaining 4 cards for validity

5. if the hand contains any aces, repeat from 1. with ace considered high

6. sort the cards by rank order and check (0,1,2) (3,4,5,6) and (0,1,2,3) (4,5,6) as sets of same rank partitions.

return false


Quote:

// And it surely wouldn't kill you to get in the habit of putting in the
// other braces, either...


Yes, this is a bad habit left over from my old job where for some inexplicable reason the code standard was braces only where necessary. Apologies if it is unreadable!

Share this post


Link to post
Share on other sites
Hey,

you could probably also use some kind of histogram to check the hand.


//check for sets of same suit

//gather data
int suits[4] = { 0 };
for (int i = 0; i < hand.size(); i++) {
if(hand[i].getSuite() == HEARTS)
suits[0]++;
else if(hands[i].getSuite() == SPADES)
suits[1]++;

...
}

//check for sets
if(suits[0] >= 4)
//hand contains 4 cards of hearts
if(suits[1] >= 4)
//hand contains 4 cards of spades
...
...


You can also use histograms of the ranks to check for sequences.

Cheers

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this