Beefy Boxes and Bandwidth Generously Provided by pair Networks Joe
Syntactic Confectionery Delight
 
PerlMonks  

Generating all 5-card hands

by thor (Priest)
on May 18, 2005 at 14:42 UTC ( #458233=perlquestion: print w/ replies, xml ) Need Help??
thor has asked for the wisdom of the Perl Monks concerning the following question:

Greetings all,

So, I've been reading a lot about iterators lately and have wanted to try them out, but haven't had the proper problem arise...until now.

At work, we play cribbage over lunch. For a while, there's been a conjecture that any hand that has a 5 in it has at least two points. We've been unable to prove or disprove it (partly because we're lazy, partly because it's an ongoing joke). What I want to do is write a program that brute forces the issue. That is to say that I want to create a program that scores all 5-card hands that have a 5 in them and see what happens.

Unfortunately, my understanding of iterators starts to get really fuzzy after the most trivial of examples. I'd like to learn how to do this, but I don't know where to start. Does anyone have any pointers?

thor

Feel the white light, the light within
Be your own disciple, fan the sparks of will
For all of us waiting, your kingdom will come

Comment on Generating all 5-card hands
Re: Generating all 5-card hands
by Roy Johnson (Monsignor) on May 18, 2005 at 14:54 UTC
    The set of all five-card hands with a 5 is the set of all four-card hands in a deck missing a 5, plus a 5-card. The easy way would be to use glob:
    print "$_\n" while $_=glob '5,{A,2,3,4,6,7,8,9,10,J,Q,K}' .',{A,2,3,4,5,6,7,8,9,10,J,Q,K}'x3;
    but it's not a truly iterative solution (it generates the whole set before beginning iteration). Consider Algorithm::Loops, or Iterating over combinations (found by Super Searching on combinations and iterator).

    Caution: Contents may have been coded under pressure.
Re: Generating all 5-card hands
by merlyn (Sage) on May 18, 2005 at 14:57 UTC
    You might look at Games::Cards for reusable code regarding scoring and representing hands.

    For generating all combinations of 52 cards taken 5 at a time, search here for combinations. I'm sure we've covered this quite a bit. {grin}

    But are you really ready to process all 2598960 iterations? At 100 per second, that's still about a third of a day. Maybe you should use some rules instead.

    -- Randal L. Schwartz, Perl hacker
    Be sure to read my standard disclaimer if this is a reply.

      But are you really ready to process all 2598960 iterations?
      Nope. The number that you mention is 52-choose-5: the number of 5-card hands possible sans restrictions. I consider only those hands that have at least one 5 in them to be interesting. This takes out a significant portion (by my math, it leaves only 886656). I will further reduce the set by using the fact that a cribbage hand is inherently non-ordered and, for my purposes, suit doesn't matter. So, I'll not bother scoring a hand if I've already seen a hand with the same cards in it. I just did it in 30 seconds, generating 1820 distinct hands. :)

      thor

      Feel the white light, the light within
      Be your own disciple, fan the sparks of will
      For all of us waiting, your kingdom will come

      merlyn,
      For generating all combinations of 52 cards taken 5 at a time....But are you really ready to process all 2598960 iterations? At 100 per second, that's still about a third of a day.

      In cribbage, order is important contrary to what thor said earlier. The position of 1 card determines its eligibility for "right-jack" so there really are 12,994,800 hands that need to be considered. Even still, it is possible to both generate and score all those hands in under 15 minutes using pure perl. This would encompass everything thor wanted to do and a lot more.

      Cheers - L~R

        In cribbage, order is important contrary to what thor said earlier.
        While you're correct in that order matters, you and I are not disagreeing. My original problem was to prove that all hands that contained a 5 had at least two points. If knobs is obtained, then a jack was cut. With at least one 5 in the hand, this will yield 2 points for the fifteen, thus satisfying the original problem.

        thor

        The only easy day was yesterday

Re: Generating all 5-card hands
by zentara (Archbishop) on May 18, 2005 at 18:17 UTC
    I don't know if it can be adapted to cribbage, but check out poker-eval

    It has python bindings, but no Perl yet.

    You can do millions of hands in just a few seconds.


    I'm not really a human, but I play one on earth. flash japh
Re: Generating all 5-card hands
by TedPride (Priest) on May 18, 2005 at 18:37 UTC
    use strict; use warnings; @_ = (2..10,'J','Q','K','A'); comb('', 4, 2..4,6..10,'J','Q','K','A',@_,@_,@_); sub comb { my ($str, $depth, @items) = @_; if (!$depth--) { interpret($str); return; } comb("$str $items[$_]", $depth, @items[($_+1)..$#items]) for (0..$ +#items) } sub interpret { my @cards = split / /, "5$_[0]"; # Do whatever with @cards; }
    Actually though, the possible set can't contain any 5's except the original 5, nor can it contain any 10, J, Q, K - since all hands involving those will have at least 2 points. This cuts the number of combinations significantly.
    @_ = (2..4,6..9,'A'); comb('', 4, @_,@_,@_,@_);
    Nor can you have more than one of any card.
    comb('', 4, 2..4,6..9,'A');
    It should be fairly easy to figure out whether there are straights or 15's in the permutations? of this set. Code to follow...
    use strict; use warnings; comb('', 4, 1..4,6..9); sub comb { my ($str, $depth, @items) = @_; if (!$depth--) { interpret($str); return; } comb("$str $items[$_]", $depth, @items[($_+1)..$#items]) for (0..$ +#items) } sub interpret { my @cards = split / /, "5$_[0]"; @cards = sort {$b <=> $a} @cards; my $flag = 1; for (0..3) { $flag = 0 if $cards[$_+1] != ($cards[$_]-1); } return if $flag; for (perm(@cards)) { return if sum(split //) == 15; } print join " ", @cards; } BEGIN { my @c_out; sub perm { @c_out = (); permute('', $_, @_) for (0..$#_); return @c_out; } sub permute { my ($str, $depth, @chars) = @_; if (!$depth--) { push @c_out, $str.$_ for @chars; } else { permute($str.$chars[$_], $depth, @chars[($_+1)..($#chars)] +) for (0..$#chars); } } } sub sum { my $n; $n += $_ for @_; return $n; }
    Very rough code, but upshot is that there are no hands with a 5 that don't have at least 2 points. I could actually have done this whole thing on paper, since there's very few sets of cards that have to be tested for 15's and straights.
Re: Generating all 5-card hands
by 5mi11er (Deacon) on May 18, 2005 at 20:48 UTC
    Forget brute force, using logic to try to create a hand that has no points:

    • All 10, J, Q, K's are eliminated

    • Because 6+9=15 and 7+8=15, we may only take one from each group above 5
       ie. 6 & 8, 7 & 9 or 8 & 9. 6 & 7 gives a three card run.

    • This means we MUST use at least 2 cards less than 5.

    • A, 2, no 3, that would be a 3 card run, 4, 5
       can't have a 6, 6+4=10, or 7, 7+2+A=10, or 8, or 9 for same reasons. Dead end.

    • 2, 3, no 4, 5, 6 ok, no 8 allowed, nor 7. Dead end.

    • A, 3, 5, 8, --> Dead end.

    • A, 4, 5, 7, --> Dead end.

    • 2, 4, 5, 7, no 9, 9+2+4=15. Dead end.

    this elminates all possible hands.

    -Scott

    Update: L~R beat me to what this essentially boils down to up in this node posted just before I'd managed to finish mine.

Re: Generating all 5-card hands
by DrHyde (Prior) on May 19, 2005 at 09:55 UTC
    Hah! Just last night I was thinking about writing a module for scoring cribbage hands, with the intention of analysing the values of various cards. Yes, this would pay no attention to actually *playing* the hand or to pegging tactics.
Re: Generating all 5-card hands
by hv (Parson) on May 19, 2005 at 12:12 UTC

    For a hand with a 5 to avoid scoring 2 points, it must have no pair, and no subset that sums to 15. Since that means we can only have one of each of the pairs (1, 9), (2, 8), (3, 7), (4, 6) that sum to 10, the hands to consider consist of the 16 ways we can choose one from each of those pairs.

    If we have 9 we cannot have 6, so we must have 4, so we cannot have 2, so we must have 8, so we cannot have 7, so we must have 3. But 3+4+8 = 15, so we cannot have 9.

    So we must have 1; if we have 8 we cannot have 7, or 6, so we must have 3 and 4. So we have 3+4+8 = 15 again, which means we cannot have 8.

    So we must have 1 and 2, which means we cannot have 7, so we must have 3. But 1+2+3+5+4 = 15, and 1+3+5+6 = 15. So there is no hand including a five which doesn't include at least 2 points.

    Hugo

      I thought you would be interested to know that I added a link to this discussion at Cribbage Corner, in the section on hand distribution and probabilities. Thank you for taking the trouble to work this out!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://458233]
Approved by polettix
Front-paged by BrowserUk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (6)
As of 2014-04-18 10:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (466 votes), past polls