   Checking a hand of cards for a win
  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 :(   
  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 exercisedef is_4card_set(cards):  # left as an exercisedef 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 Falsedef is_winning_hand(cards):  return test_partitions([], cards);  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?   ;Quote:Original post by DrunkenLizardHi 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.   ;Quote:Original post by swiftcoderQuote: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?).   ;Quote:Original post by DrunkenLizardOk, 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...;Quote:Original post by ZahlmanWell, 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 hand3. take each valid 4 card partition from the run and check the remaining 3 cards for validity4. take each valid 3 card partition from the run and check the remaining 4 cards for validity5. if the hand contains any aces, repeat from 1. with ace considered high6. 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 falseQuote:// 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!   ;  Hey,you could probably also use some kind of histogram to check the hand.//check for sets of same suit//gather dataint suits[4] = { 0 };for (int i = 0; i < hand.size(); i++) { if(hand.getSuite() == HEARTS)   suits[0]++; else if(hands.getSuite() == SPADES)   suits[1]++; ...}//check for setsif(suits[0] >= 4)  //hand contains 4 cards of heartsif(suits[1] >= 4)  //hand contains 4 cards of spades......You can also use histograms of the ranks to check for sequences.Cheers