C++

Forum

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

Aaron Vienneau (211)
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
JLBorges (13770)
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 ) ;
}
Aaron Vienneau (211)
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
JLBorges (13770)
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
}
dhayden (5798)
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;
}

doug4 (1538)
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
Aaron Vienneau (211)
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));
	}
}
cire (8284)
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.
Aaron Vienneau (211)
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
doug4 (1538)
@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.
JLBorges (13770)
> 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) */ ; }
Aaron Vienneau (211)
+1 That's pretty awesome! :)
Topic archived. No new replies allowed.