Three of a kind numbers

Recommended Posts

chosenkill6    163

I am creating a method isThreeKind(int[] fiveNumbers) and it should return a boolean if 3 of the 5 are the same. I don't understand how I should go about doing this. I also need to make a similar method but instead do 4 of a kind. If someone could just help me out with understanding the logic that would be great.

Thanks

Share on other sites
SiCrane    11839
One way would be look at the first number and then check the rest of the array for two or more of that number. If there aren't, look at the second number and check the rest of the array, and so on. Another way would be to sort the array first and then see if there or three or more in a row.

Share on other sites
SlamDrag    111

Well, you need to test if 3 of 5 numbers are the same.

What you could do is use a nested for loop to iterate through all the numbers and test which is the same with which then have an integer keep track of how many numbers are the same, then return true if it's greater than three. That's just one possible solution. There are probably others.

Share on other sites
EddieV223    1839

As you loop through the array, you don't have to go back wards, for example test the first one against the ones after it, then test the second one against the ones after it, but you don't have to retest the first one against the second since you already know the first one failed the test.  If you make it to the second to last one, ( only 2 left ) and you haven't found 3 matches yet, you don't have to test the last two since there is only 2 left there can't be 3 matches in 2 objects.

Share on other sites
chosenkill6    163

ok i got it!
I sorted the array and simply checked for the number of consecutive numbers that are the same.

thanks for the help guys

Share on other sites
alnite    3436

Why not just use a Hash?  Something like this (might be missing some corner cases):

int pair_count = 0;
bool three_of_a_kind = false;
bool four_of_a_kind = false;
for (int i=0; i<5; ++i) {
hash[cards[i]]++;
if (hash[cards[i]] == 2) pair_count++;
three_of_a_kind ||= hash[cards[i]] == 3;
four_of_a_kind ||= hash[cards[i]] == 4;
}

// now you can see if it has a two pair, a three of a kind, a four of a kind, or a full house.



Share on other sites
chosenkill6    163

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

here is my code just so you guys could see what I did

Arrays.sort(player1.diceValues);
for(int i = 0; i < 3; i++){
if(player1.diceValues[i] == player1.diceValues[i + 1] && player1.diceValues[i] == player1.diceValues[i + 2]){
player1.score =+ player1.diceValues[i] * 3;
}
}

Edited by nitishk

Share on other sites
alnite    3436

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 [tt]java.util.Hashtable[/tt]

Share on other sites

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.

Share on other sites
jms bc    448

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[i] == 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

same = 2 is two pair

same = 4 is a full house

Edited by jms bc

Share on other sites
NightCreature83    5002
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.

Share on other sites

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?

Share on other sites
nimrodson    276

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.

Edited by nimrodson

Share on other sites
NightCreature83    5002

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

Share on other sites

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!

Share on other sites
alvaro    21246
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[i]-1)*3);
types |= 1 << (dice[i]-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. Edited by Álvaro

Share on other sites

*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.

Share on other sites
alvaro    21246

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

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

Oooops!

I have to agree: A beginner should use an array of counters (a.k.a. histogram) instead of the crazy octal sum I posted. I thought the problem was interesting, I spent some time thinking about it and then I completely forgot what forum this was on. Sorry about that... Edited by Álvaro

Share on other sites

I agree, it is interesting, and worth it if for thinking about AI for more complex games.

If the Earth ever gets invaded by aliens who will destroy the Earth unless we can utilise the power of all of our computers in a rapid fire Yahtzee tournament, we know who they can turn to ;)

Share on other sites
LorenzoGatti    4442
I would simply count the number of occurrences of each value, compiling what other posts rightly call an histogram, without sorting the values; then you can scan the occurrence counts to find values with the appropriate number of occurrences. With few possible values, like in your dice game, the histogram can be represented as a dense array of counts, indexed by values; with many possible values an array would have a lot of wasted slots with a count of 0, if not too many slots to fit into memory. For large sets of allowed values you should therefore implement the same histogram abstract data type (initialize to 0 occurrences for all values; given a value, increment the corresponding occurrence count by 1; produce all value/occurrence count pairs with at least 1 occurrence) using a hash table, a search tree, or another efficient data structure that uses memory proportional to the number of different values in the actual input rather than proportional to the number of possible values.

Share on other sites

I was only suggesting an array of size 6 (number of 1s rolled, number of 2s rolled, etc.).

I wasn't suggesting a 6x6x6x6x6 array with all possible values (size would be 7776 entries).

That's because in Yahtzee you don't have to score the best possible roll (and you can only score a result once). You could do it by storing a bitfield of which combinations are allowed for each roll (so 5 of a kind is also 4 of a kind and a full house, whatever), but then you still have to work out the legal combinations anyway (which is the purpose of the question in the OP)...

Share on other sites
chosenkill6    163

WOW
thanks for so much feedback and help guys

I kind of ended up using a combination of what you guys said. Sorted it and then loop through it but I think my way was a bit inefficient but I do not mind for now. Any feedback on how I did my full house code?

Arrays.sort(player1.diceValues);

if(player1.diceValues[0] == player1.diceValues[1] && player1.diceValues[0] == player1.diceValues[2]){
if(player1.diceValues[3] == player1.diceValues[4]){
player1.score = player1.score + 25;
}
}else if(player1.diceValues[2] == player1.diceValues[3] && player1.diceValues[2] == player1.diceValues[4]){
if(player1.diceValues[0] == player1.diceValues[1]){
player1.score = player1.score + 25;
}
}