Three of a kind numbers

Álvaro Begué · 2013-04-12T02:35:09

I added some comments to the code. There are some prerequisites to understanding it:* How integers are represented in binary* Bitwise operations* Constants that start with a `0' in C/C++ are in octal// This struct computes what categories match the dice in the constructor struct Classification { bool is_three_of_a_kind; bool is_four_of_a_kind; bool is_full_house; bool is_small_straight; bool is_large_straight; bool is_yahtzee; bool is_chance; // Pass a pointer to an array of 5 dice, with values in 1..6 Classification(int *dice) { // sum consists of 6 groups of 3 bits, which are counters for the values in the dice int sum = 0; // types marks which values appear at all, one bit per value int types = 0; for (int i=0; i<5; ++i) { sum += 1 << ((dice-1)*3); // Increment the appropriate counter within sum types |= 1 << (dice-1); // Mark the value } int n_types = __builtin_popcount(types); // This only works in gcc. You can find other ways of counting set bits for other compilers. /* // Alternative code to count bits: static int const bitcount_table[64] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6 }; int n_types = bitcount_table[types]; */ // I sorted the checks from easy to hard (somewhat subjectively) // Chance: Every hand qualifies is_chance = true; // Yahtzee: Only one type is_yahtzee = (n_types == 1); // Large straight: Either 1-2-3-4-5 or 2-3-4-5-6, for which types // is 31 or 62 respectively is_large_straight = (types == 31 || types == 62); // Small straight: types must contain four consecutive bits is_small_straight = ((types & (types>>1) & (types>>2) & (types>>3)) != 0); // Full house: Either only two values and none of them appear 4 // times (it can only be a pair and a trio), or is yahtzee is_full_house = ((n_types == 2 && !is_four_of_a_kind) || n_types == 1); // Four of a kind: check if any counter got to 4, by checking the // bit whose value is 4 is_four_of_a_kind = ((sum & 0444444) != 0); // To detect three of a kind, add 1 to each 3-bit counter and see // if any of them trigger the bit whose value is 4 is_three_of_a_kind = (((sum + 0111111) & 0444444) != 0); } }; If you are a beginner and still don't understand it, it's OK. Maybe you can come back to this code after you have gained some experience with the things I listed at the beginning of this post.

For Beginners

Started by chosenkill6 April 01, 2013 04:57 PM

33 comments, last by alvaro 11 years, 1 month ago

alnite

3,454

April 01, 2013 06:09 PM

i dont really understand what a hash is and I would like to keep this game simple. By the way this is for a game of yahtzee not poker

Hashtable.

In java, that'd be in java.util.Hashtable

Paradigm Shifter

5,832

April 01, 2013 08:05 PM

With Yahtzee you might be better having an array of size 6 and store a count of how many dice are rolled of each number. That makes checking the combinations and scoring them really easy.

Can't you still have a full house and 2 pairs in Yahtzee too?

Ten Thousand/Farkle/Dix Mille is a much better dice game though I reckon, especially with the 4 or more 2's = disaster lose all your banked points rule.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

jms bc

448

April 01, 2013 08:11 PM

I think this is the easiest way if you have no need to sort:

int same=0;

for(int i=0;i<4;++i)

for(int j=i+1;j<5;++j)

if(a == a[j])

same++;

same = 1 is a pair

same = 3 is a three of a kind

same = 6 is a quad

same = 10 is 5 of a kind

added:

same = 2 is two pair

same = 4 is a full house

The Four Horsemen of Happiness have left.

NightCreature83

5,061

April 01, 2013 08:15 PM

You could also use histograms as they allow you to check all of the other constraints on placing a roll really quickly. 3 of a kind one histogram bar is at least 3, with 4 it goes to 4, with a large straight all of them are 1, small straight at least four connecting number bars are 1 or more.

Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, theHunter, theHunter: Primal, Mad Max, Watch Dogs: Legion

Paradigm Shifter

5,832

April 01, 2013 08:19 PM

Yeah that's what I was suggesting with the array of 6 entries, use it as a histogram.

I thought a small straight was 1-2-3-4-5 and a large straight was 2-3-4-5-6?

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

nimrodson

276

April 01, 2013 08:20 PM

Just for fun, a (beginner) Haskell implementation:


unique :: (Eq a) => [a] -> [a]
unique []     = []
unique (x:xs) = x : unique (filter (\y -> not (x==y)) xs)

nOcurrences :: (Eq a) => a -> [a] -> Int
nOcurrences elem list = length (filter (==elem) list)

isThreeKind :: (Eq a) => [a] -> Bool
isThreeKind list = elem 3 [nOcurrences i list | i <- (unique list)]

You could parametrize the 3 number in "isThreeKind" function and have a "fourKind", a "fiveKind", or whatever...

Cheers.

spaceship-battle

NightCreature83

5,061

April 01, 2013 08:22 PM

Yeah that's what I was suggesting with the array of 6 entries, use it as a histogram.

I thought a small straight was 1-2-3-4-5 and a large straight was 2-3-4-5-6?

Not according to wikipedia: http://en.wikipedia.org/wiki/Yahtzee

Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, theHunter, theHunter: Primal, Mad Max, Watch Dogs: Legion

Paradigm Shifter

5,832

April 01, 2013 08:28 PM

Looks like I've been playing a weird Yacht/Yahtzee hybrid then ;) I also thought Yacht was the same game as Yahtzee, you learn something new every day ;)

Since I mentioned 10,000 someone should do a physics based simulation of the remarkably similar game "Pass the Pigs" http://en.wikipedia.org/wiki/Pass_the_pigs

EDIT: And I've never heard of the Kissin' Bacon (both snouts touching) rule before. It's not in my ruleset!

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

alvaro

21,604

April 01, 2013 11:02 PM

This should be blazing fast:

struct Classification {
  bool is_three_of_a_kind;
  bool is_four_of_a_kind;
  bool is_full_house;
  bool is_small_straight;
  bool is_large_straight;
  bool is_yahtzee;
  bool is_chance;

  Classification(int *dice) {
    int sum = 0;
    int types = 0;

    for (int i=0; i<5; ++i) {
      sum += 1 << ((dice-1)*3);
      types |= 1 << (dice-1);
    }
    int n_types = __builtin_popcount(types); // This only works in gcc. You can find other ways of counting set bits for other compilers.

    is_three_of_a_kind = (((sum + 0111111) & 0444444) != 0);
    is_four_of_a_kind = ((sum & 0444444) != 0);
    is_full_house = ((n_types == 2) && !is_four_of_a_kind);
    is_small_straight = ((types & (types>>1) & (types>>2) & (types>>3)) != 0);
    is_large_straight = (types == 31 || types == 62);
    is_yahtzee = ((types & (types-1)) == 0);
    is_chance = true;
  }
};

Another alternative is to encode all the bools in a single byte and make a table that maps a 5-digit base-6 number to its classification. That table is smaller than 8KB.

Paradigm Shifter

5,832

April 01, 2013 11:08 PM

*reads Alvaro's post* *checks name of forum*

OK, it's "For Beginners" ;) Probably a tad too advanced for a simple Yahtzee game...

I suggested a sort and count consecutive approach (since it is scalable for more complex problems) until I found out it was Yahtzee where I feel a histogram based approach is going to be simplest to implement and understand.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

Three of a kind numbers

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Three of a kind numbers

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines