Best way to check for Sm. and Lg. Straight?

May 17, 2016 at 3:36pm
Given 5 dice, each with a value of 1 - 6. What is the most succinct, expressive and elegant solution you can think of to identify a large straight? I know two things about the dice:

(1) All of their face values
(2) An inventory of how many of each die there are.

Example:

Dice: 1, 5, 3, 4, 4
1
2
3
4
5
6
7
8
Inventory:
0: 0, // there are 0 zeros.
1: 1, // there is 1 one.
2: 0, // there are 0 twos.
3: 1, // ect...
4: 2,
5: 1,
6: 0


Note, I show "0" here because the inventory is basically a vector with 7 integer elements (indices 0 - 6), all initialized to zero. When a die face of the appropriate number is identified the corresponding index of the inventory vector is increased.

1
2
3
4
5
6
7
8
9
10
11
12
13
switch(dieFace)
{
//case 0:
// This exists, but should never be populated as a dice does not have a 0 face
// Make sense?
case 1:
   inventory[1]++;
   break;
case 2:
   inventory[2]++;
   break;
//ect...
}


My attempt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Player::queryLgStraight()
{
	// LgStraight == 2, 3, 4, 5, 6
	// OR
	// LgStraight == 1, 2, 3, 4, 5

	bool lgStraight = true; // Assume we have a largeStraight
	bool leeway = 0; // Declare leeway variable for 1 possible "miss"; read on...
	bool isNotScored = (!sheet.isScored(Scoresheet::Category::LGSTRAIGHT)); // Check that lgStraight isn't scored already

	for (int i = 1; i < inventory.size(); i++) // Cycle through inventory ( 1: 0, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1)
	{
		if (howMany(i) != 1) // Allow one "miss"  (EG: 1: 0, or 6: 0)
		{
			leeway++;
		}
		if (leeway > 1) // But if there are any more misses than 1
			lgStraight = false; // We don't have a lgStraight
	}

	if(lgStraight && isNotScored) // If we have a largeStraight and its not scored. Score 40 pts to LgStraight
		scoreCandidates.push_back(std::make_pair(Scoresheet::Category::LGSTRAIGHT, 40));

}


EDIT: my example doesn't work. If the dice were 1, 2, 6, 3, 5 I'd get 1 leeway and it would read as a lgStraight.
Last edited on May 17, 2016 at 4:07pm
May 17, 2016 at 4:49pm
1
2
3
4
5
6
7
8
9
10
11
12
13
bool large_straight( const std::array< int, 7 >& inventory )
{
    /* // sanity checks
    if( inventory[0] != 0 || std::any_of( std::begin(inventory), std::end(inventory), []( int v ) { return v < 0 ; } ) )
        throw std::invalid_argument( "bad inventory" ) ;
    if( std::accumulate( std::begin(inventory), std::end(inventory), 0 )  != 5 )
        throw std::invalid_argument( "bad number of dice" ) ;
    */

    // large straight if a. no face appears more than once and b. the missing face is either one or six
    return std::count( std::begin(inventory), std::end(inventory), 1 ) == 5 &&
           ( inventory[1] == 0 || inventory[6] == 0 ) ;
}
May 17, 2016 at 5:15pm
Gah!

This is genius. Thank you! This is very much the answer I was looking for.

Can I do small straight similarly?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Player::querySmStraight()
{
	std::vector<int> tempInventory = inventory; // cant afford to mutate the inventory. need for further checks.

	for (int i = 0; i < tempInventory.size(); i++) // reduce all duplicates.
	{
		if (tempInventory.at(i) > 1)
			tempInventory.at(i) = 1;
	}

	if(std::count(std::begin(inventory), std::end(inventory), 1) == 4 &&
		(inventory[1] == 0 && inventory[2] == 0) // 3, 4, 5, 6
		||(inventory[5] == 0 && inventory[6] == 0) // 1, 2, 3, 4
		||(inventory[1] == 0 && inventory[6] == 0)) // 2, 3, 4, 5
	{

		scoreCandidates.push_back(std::make_pair(Scoresheet::Category::SMSTRAIGHT, 30));
	}
}




Last edited on May 17, 2016 at 5:16pm
May 17, 2016 at 5:42pm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool large_straight( const std::vector<int>& inventory )
{
    return inventory == std::vector<int>{0,1,1,1,1,1,0} || // 1, 2, 3, 4, 5
           inventory == std::vector<int>{0,0,1,1,1,1,1} ; // 2, 3, 4, 5, 6
}

bool small_straight( std::vector<int> inventory ) // **** pass by value ****
{
    for( int& v : inventory ) if( v > 1 ) v = 1 ; // reduce all duplicates.

    return // large_straight(inventory) || // uncomment if a large straight is also a small straight
           inventory == std::vector<int>{0,1,1,1,1,0,0} || // 1, 2, 3, 4
           inventory == std::vector<int>{0,0,1,1,1,1,0} || // 2, 3, 4, 5
           inventory == std::vector<int>{0,0,0,1,1,1,1} ; // 3, 4, 5, 6
}
May 17, 2016 at 6:55pm
With bit twiddling:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <array>
#include <cstdlib>

using namespace std;

typedef std::array<unsigned,5> Dice;

// Does bitmap "present" contain a straight of size sz?
bool straight(unsigned present, unsigned sz)
{
    // convert sz to az bits. E.g. 3 -> 111b, 5 -> 11111b
    unsigned val = (1<<sz) - 1;

    while (present >= val) {
        if ((present & val) == val) {
            return true;
        }
        present >>= 1;          // shift down
    }
    return false;
}


int
main(int argc, char **argv)
{
    Dice dice;

    // Populate dice with the numbers on command line
    for (int i=1; i<argc; ++i) {
        dice[i-1] = atoi(argv[i]);
    }

    // set Present to a bitmap where bit N set means N appears in dice
    unsigned present = 0;
    for (unsigned die : dice) {
        present |= (1 << die);
    }

    // Report any straights of size 3-6
    for (unsigned sz = 3; sz <6; ++sz) {
        if (straight(present, sz)) {
            cout << "found straight of size " << sz << '\n';
        }
    }

    return 0;
}

May 17, 2016 at 6:56pm
Assuming this is to simulate Yahtzee, @JLBorges' above solution will not work. For a small straight, 4 values in a row out of 5 dice must be >= 1. So, the inventories in the code are invalid because they only represent 4 die values.

The following inventories are a subset of all of the possible small straights.

{0,2,1,1,1,0,0}
{0,1,2,1,1,0,0}
{0,1,1,2,1,0,0}
{0,1,1,1,2,0,0}
etc.
{0,1,0,1,1,1,1}
{0,0,1,1,1,1,1} (also large straight)
{0,1,1,1,1,0,1}
{0,1,1,1,1,1,0} (also large straight)

Last edited on May 17, 2016 at 6:57pm
May 17, 2016 at 7:07pm
Hey all,

I ended up going with this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void Player::queryLgStraight()
{
	if (inventory == std::vector<int> {0, 1, 1, 1, 1, 1, 0} ||
		inventory == std::vector<int> {0, 0, 1, 1, 1, 1, 1})
	{
		scoreCandidates.push_back(std::make_pair(Scoresheet::Category::LGSTRAIGHT, 40));
	}
}

void Player::querySmStraight()
{
	std::vector<int> mockDice;

	for (auto x : hand)
		mockDice.push_back(x->face());

	std::sort(mockDice.begin(), mockDice.end());
	std::unique(mockDice.begin(), mockDice.end());

	if ((mockDice[0] == 1 &&
		mockDice[1] == 2 &&
		mockDice[2] == 3 &&
		mockDice[3] == 4)
		||
		(mockDice[0] == 2 &&
		mockDice[1] == 3 &&
		mockDice[2] == 4 &&
		mockDice[3] == 5)
		||
		(mockDice[0] == 3 &&
		mockDice[1] == 4 &&
		mockDice[2] == 5 &&
		mockDice[3] == 6))
	{
		scoreCandidates.push_back(std::make_pair(Scoresheet::Category::SMSTRAIGHT, 30));
	}
}
May 17, 2016 at 7:09pm
Assuming this is to simulate Yahtzee, @JLBorges' above solution will not work. For a small straight, 4 values in a row out of 5 dice must be >= 1. So, the inventories in the code are invalid because they only represent 4 die values.


If you look at the full function instead of just the lines enumerating the inventories, I think you'll see that is accounted for. Any value greater than one is reduced to one to reduce the number of possibilities one must check.
May 17, 2016 at 7:12pm
You're correct with the Yahtzee guess, btw. Sorry I should have mentioned that. Perhaps it would have made it clearer.

@JLBorges' above solution will not work. For a small straight, 4 values in a row out of 5 dice must be >= 1. So, the inventories in the code are invalid because they only represent 4 die values.


Regarding:

1
2
3
4
5
6
7
8
9
bool small_straight( std::vector<int> inventory ) // **** pass by value ****
{
    for( int& v : inventory ) if( v > 1 ) v = 1 ; // reduce all duplicates.

    return // large_straight(inventory) || // uncomment if a large straight is also a small straight
           inventory == std::vector<int>{0,1,1,1,1,0,0} || // 1, 2, 3, 4
           inventory == std::vector<int>{0,0,1,1,1,1,0} || // 2, 3, 4, 5
           inventory == std::vector<int>{0,0,0,1,1,1,1} ; // 3, 4, 5, 6
}


I found a slight error in the logic when you have dice: 1, 2, 3, 4, 6

I wish there was an easy way to say

inventory == std::vector<int>{0,1,1,1,1,0,0} where any of the zeros could possibly be ones (to account for the fifth die.

Thank you all for your great suggestions!
Last edited on May 17, 2016 at 7:32pm
May 17, 2016 at 7:29pm
@cire

If you look at the full function instead of just the lines enumerating the inventories, I think you'll see that is accounted for. Any value greater than one is reduced to one to reduce the number of possibilities one must check.


You are correct. Sorry @JLBorges. I need to read more carefully.

However, the 1,3,4,5,6 and 1,2,3,4,6 cases are missing from the small permutations.
May 18, 2016 at 2:38am
> I wish there was an easy way to say ... any of the zeros could possibly be ones (to account for the fifth die.

1
2
3
4
5
6
7
8
9
10
11
12
bool has_n_consecutive_ones( std::vector<int> seq, std::size_t n )
{
    for( int& v : seq ) if( v != 0 ) v = 1 ; // reduce all duplicates.

    // any 'n' ones in a row, starting with inventory[1]
    return !seq.empty() && std::search_n( std::begin(seq)+1, std::end(seq), n, 1 ) != std::end(seq) ;
}

bool large_straight( const std::vector<int>& inventory ) { return has_n_consecutive_ones( inventory, 5 ) ; }

bool small_straight( const std::vector<int>& inventory )
{ return has_n_consecutive_ones( inventory, 4 ) /* && !large_straight(inventory) */ ; }
May 18, 2016 at 12:42pm
+1 That's pretty awesome! :)
Topic archived. No new replies allowed.