# A dice game called "Greed"

This game is a variation of the Greed dice game. Imagine we have 5 dice. We roll, them, and jot down the results. Then, based on this chart:

Three 1's => 1000 points
Three 6's =>  600 points
Three 5's =>  500 points
Three 4's =>  400 points
Three 3's =>  300 points
Three 2's =>  200 points
One   1   =>  100 points
One   5   =>   50 point


We calculate the score. This program exactly does that. It has two functions, one is greed() which takes a vector of 5 integers between 1 and 6 and calculates the score, and the other is greed_rand() which first generates the vector randomly, and then calculates the score.

#include <iostream>
#include <vector>
#include <random>
#include <map>

std::random_device seeder;
std::mt19937 engine(seeder());
std::uniform_int_distribution<int> dist(1, 6);

typedef std::vector<int> list_type;

int greed(list_type die_rolls)
{
int ret = 0;
std::map<int, int> cnt;

for (int i = 1; i <= 6; ++i)
{
cnt[i] = 0;
}

for (auto &d : die_rolls)
{
++cnt[d];
}

if (cnt[1] == 3)
{
ret += 1000;
}
if (cnt[1] == 2)
{
ret += 200;
}
if (cnt[1] == 1)
{
ret += 100;
}
if (cnt[1] == 4)
{
ret += 1100;
}
if (cnt[1] == 5)
{
ret += 1200;
}
if (cnt[2] == 3)
{
ret += 200;
}
if (cnt[3] == 3)
{
ret += 300;
}
if (cnt[4] == 3)
{
ret += 400;
}
if (cnt[5] == 1)
{
ret += 50;
}
if (cnt[5] == 2)
{
ret += 100;
}
if (cnt[5] == 3)
{
ret += 500;
}
if (cnt[5] == 4)
{
ret += 550;
}
if (cnt[5] == 5)
{
ret += 600;
}
if (cnt[6] == 3)
{
ret += 600;
}

return ret;

}

int greed_rand()
{
list_type rolls_rand;

for (int i = 1; i <= 5; ++i)
{
rolls_rand.push_back(dist(engine));
}

return greed(rolls_rand);
}

int main() {

list_type rolls = {1, 1, 1, 5, 5};
std::cout << greed(rolls) << std::endl;
std::cout << greed_rand() << std::endl;

return 0;
}


The output of this program is:

1100
150


Note: If you're on Windows, change the random seeder to time(NULL).

• Not enough to warrant an answer but I'm surprised the very good answers we have don't mentioned the function names. Though the game is called greed, wouldn't calculate_score and roll_dice be way more explanatory as function names? Nov 15, 2018 at 8:23
• @sbecker You're right, from now on I'll choose better function and variable names. Nov 15, 2018 at 8:46
• It's a bug or a feature? If the we got five 6, which score you expect? 0 or 600? Actually you get 0 but I think 600 seems more logic. Nov 15, 2018 at 13:27
• I know this game by another name but I cant recall what it is.
– Matt
Nov 15, 2018 at 18:57
• @Matt 10000, Greedy, zilch, Tora? Nov 15, 2018 at 21:40

Style
You're not being charged by the character; there's no need to abbreviate "count", or "ret" (which I would call "score" instead). Also, main has inconsistent brackets with the rest of the program. Other than that, it looks good.

Globals
The globals are only being used by greed_rand, and would be better created within main and passed as parameters to greed_rand.

Counting Logic
Currently you're checking each possible quantity of '1's (and other numbers) separately, and not in order either, which makes it harder to ensure you're not missing a case and will fail if you change the number of total dice. An improvement would be to check for the larger combinations first and just continue scoring as long as possible. For example:

for(; count[1] >= 3; count[1] -= 3)
{
score += 1000;
}
for(; count[1] > 0; --count[1])
{
score += 100;
}


This also matches the score chart more clearly.

Output You're outputting the end result of greed_rand, but not what list generated that result - which means you can't really tell if it was correct. It would probably be better to replace greed_rand with a method that makes a random list, and pass that to greed yourself, so you can also output it:

std::vector<int> roll_dice(int count, std::mt19937 &engine)


Use of Templates (Optional)
While not required for this usage, greed would be a good candidate for taking a pair of generic iterators instead of requiring a std::vector:

template<typename Iterator>
int greed(Iterator begin, Iterator end)
{
...
for (auto it = begin; it != end; ++it)
{
++cnt[*it];
}

• Thank you. I don't know what templates are yet, but once I learn about them (in a few hours) I will make use of them. Nov 15, 2018 at 1:05
• Note that your double loops for "counting logic" could probably be replaced by: score += 1000 * (count[1] / 3); score += 100 * (count[1] % 3); Nov 15, 2018 at 17:29
• @scohe001 if the point bonus for 3 is broken up (100 each plus 700 in bonus points), you can just add 700 instead of 1000, which simplifies score += 100 * count[1] to get the individual rolls. The same logic applies to 5s as well. Nov 15, 2018 at 23:08
• regarding the globals: IMHO this is one of the few good circumstances to use statics within the function. Only one initialization on first call, no messy globals, no annoying extra parameters to pass Nov 15, 2018 at 23:16

Nice separation of functionality, well done!

There are some important details that the other review doesn’t address:

int greed(list_type die_rolls)


Here you are taking a std::vector by value. This means it will ve copied. It’s a small array, it probably doesn’t matter here at all, but you should get used to passing larger objects and objects that own stuff (a vector owns a piece of memory in the heap) by reference. Appropriate would be:

int greed(list_type const& die_rolls)


Next, you use a std::map<int, int> cnt to count die rolls. But you only index it using values 1-6. You should use a std::vector here. You’d waste the first element (index 0), but indexing into a vector is much faster than indexing into a map, and it takes less memory to boot. Or, since you know the size at compile time, you could use a std::array<int,7> instead. This is a fixed-sized array that lives entirely on the stack, it doesn’t allocate heap memory.

Next you do

for (int i = 1; i <= 6; ++i)
{
cnt[i] = 0;
}


Since we’re using a std::vector or std::array now, you can use std::fill:

std::fill(cnt.begin(), cnt.end(), 0);


std::array even has a fill member function:

cnt.fill(0);


However, it is even easier to rely on value initialization:

std::array<int,7> cnt{};


This value-initializes each element of cnt to int{}, meaning each element will have a value of 0.

• I didn't know about fill(). Thank you. Nov 15, 2018 at 3:24
• @CrisLuengo disagree. Why using std::fill (...) when you can just default construct? (std::array <int, 7> counts{};) Nov 15, 2018 at 5:29
• @Calak: Good point! Answer updated. Nov 15, 2018 at 6:11

You can easily decouple the scoring-algorithm from the container used to score dice-rolls by using templates. Not that you actually need a container, if you have the right iterators.

Anyway, why aren't you prepared to deal with more dice being thrown?

Also, consider making it data-driven:

template <class InputIt, class Sentinel = InputIt>
auto score(InputIt first, Sentinel last) {
constexpr auto cap = 8;
constexpr unsigned goals[][3] = {
{1, 3, 1000},
{6, 3,  600},
{5, 3,  500},
{4, 3,  400},
{3, 3,  300},
{2, 3,  200},
{1, 1,  100},
{5, 1,   50},
};
unsigned char dice[cap] = {};
for (; first != last; ++first)
++dice[(unsigned)*first % cap];
auto result = 0ULL;
for (auto [which, count, reward] : goals) {
auto& x = dice[which % cap];
result += x / count * reward;
x %= count;
}
return result;
}


Global mutable state is best avoided. Why is the random-generator and related things global?

For some reason, you have extra-newlines surrounding the return of your scoring-function. Maybe you should automate indentation?

main() is your only function where the opening brace doesn't have its own line. While there is Nothing wrong with that, try for consistency.

return 0; is implicit for main().

• What's the need for the cap here - it looks like you're taking an input that could be 16k + face, and provisioning for dice with faces up to 16? Perhaps I've just missed a detail.
– cmh
Nov 15, 2018 at 20:04
• @cmh I'm taking 16 because that's the nearest higher power of two. Nov 15, 2018 at 20:48
• I surely missed something. What's the purpose of x %= count; or even... what are you doing with x after this operation? And, are you sure about your computation in result += x / count * reward;? Compare his result and yours if dice are "1, 1, 1, 1, 2". I don't understand, maybe too tired :) Nov 15, 2018 at 20:50
• @Calak Well, x / count is unsigned integer-arithmetic, so rounded down. * reward is obvious. And x %= count; removes the dice just used. Nov 15, 2018 at 20:56
• @Deduplicator I suppose my confusion is that if I pass the sequence 5, 21, 37 it will (in my opinion) incorrectly give the score 500.
– cmh
Nov 15, 2018 at 20:56
std::random_device seeder;
std::mt19937 engine(seeder());


While this is fine for small hobby projects or testing, you'll likely want to properly seed std::mt19937. Let's break this down into explicit steps to understand what is going on.

std::random_device rdev;


std::random_device asks the OS for system-provided randomness. It can be, and sometimes is, implemented as a simple PRNG with a fixed seed, meaning you could produce the same sequence on every run. Arguably worse than using time(NULL) as a source for entropy.

auto random_seed{rdev()};


Invoking the random device object returns an unsigned int. This is normally 4 bytes, but it could be 2.

std::seed_seq seeder{random_seed};


A seed sequence is created using that one 2/4-byte value.

std::mt19937 engine(seeder);


You are now attempting to initialize the internal 624 32-bit integer state of the Mersenne Twister with that one value. This leads to issues related to

• predictability - searching for the seed is simple as there are only 2^32 possibilities.
• bias - values like 7 and 13 will never be generated. Two different seeds produce 0, 12 different seeds produce 1226181350.

If you are interested the perils/pitfalls of random bit generation and std::seed_seq, read through the comments here.

 typedef std::vector<int> list_type;


If you are expecting a fixed length container, consider using std::array over std::vector.

    std::map<int, int> cnt;


std::map is overkill for counting a contiguous range of values. std::unordered_map is better. An array-based counting sort would be best.

    for (int i = 1; i <= 6; ++i)
{
cnt[i] = 0;
}

for (auto &d : die_rolls)
{
++cnt[d];
}


std::map and std::unordered_map will default construct a value into the container if the key doesn't exist. You can skip the value initialization for these containers.

    if (cnt[1] == 3) { ret += 1000; }
/* ... */


You can do some strength reduction here by reorganizing the related comparisons and converting some of the branches into integer multiplications. Since you limit the number of dice to five, you can immediately stop checking the remaining triples once the first triple has been found.

    if (cnt[1] >= 3) { score += 1000; cnt[1] -= 3; }
else if (cnt[2] >= 3) { score += 200; }
else if (cnt[3] >= 3) { score += 300; }
else if (cnt[4] >= 3) { score += 400; }
else if (cnt[5] >= 3) { score += 500; cnt[5] -= 3; }
else if (cnt[6] >= 3) { score += 600; }

score += cnt[1] * 100 + cnt[5] * 50;

• Very interesting explanation about randomization! Nov 15, 2018 at 12:00
• You should modify == for >= because if we have more than 3 same values we still have at least 3 values so a combo ;) Nov 15, 2018 at 13:22

## Separation

Good attempt on separation of concerns, but I think you can go further.

• You can wrap the logic to generate a random integer in a function generate_random_int (int min, int max); where the content might looks like the example provided by Bjarne Stroustrup (look at rand_int) and so, no more globals.
• You can wrap the logic about filling a container with random numbers in a function template<class ForwardIt> void fill_random(ForwardIt begin, ForwardIt end) (which internally can rely on std::generate and your generate_random_int).

## Be explicit

Try to be explicit about "how" and "what"

• How: Use self-explanary methods and algorithms.
• What: Uses names that make sense

## Parameters type

Try to pass types that are not cheap to copy, by const& (unless you need "destructive" work on it).

## Map initialization

You don't need to initialize the map with 0's because when you try accessing to a key that doesn't exist, it is default constructed (so with 0's here).

## Choose right types

As stated in other answers since your map's keys is a range of integers, you should use a std::vector or even since you know it size at compile time, std::array that you automatically fill with 0's when you default construct: std::array <int, 7> counts{};. (If you don't want to waste space of the elem at index 0, you have to do some computation later).

## Occurrences counting

When you write:

if (some_var == 3) { do_something(); }             //A
if (some_var == 2) {  do_something_else(); }  //B


If A is true, B can never be true. Instead of re-checking when it's useless, simply use else if :

if (some_var == 3) { do_something(); }
else if (some_var == 3) { do_something_else(); }


But...

... Instead of testing several times for each dice side possible count, you can reduce branchements checking all "combo" first:

if (counts[1] >= 3) {
result += 1000;
counts[1] -= 3; // here we decrement to remove the wombo combo from the count
}
else if (counts[2] >= 3) {
//...
}
// ...
if (counts[1] > 1) {
result += 100 * counts[1];
}
// ...


Or even, automatically compute combo count

// superbonus
if (counts[1] >= 3) {
result += 1000;
counts [1] -= 3;
}
// combo bonus
else  {
for (int index = 2; index < 7; ++index) {
if (counts[index] >= 3) {
result += index * 100;
counts[index] -= 3;
break;
}
}
}
// ...
if (counts[1] > 1) {
result += counts[1] * 100;
}
// ...


Or, maybe more explicit:

// combo bonus
for (int index = 1; index < 7; ++index) {
if (counts[index] >= 3) {
result += index * 100;
counts[index] -= 3;
break;
}
}
if (result == 100) {
result *= 10; // superbonus
}
if (counts[1] > 1) {
result += counts[1] * 100;
}
// ...


Or using the @Snowhawk method, more imperative (and surely more efficient) but less flexible if you want to change your algorithm later.

## User-friendly output

Instead of just printing the output, add some information to the user. It's look nicer if he get as output:

Roll the dice! We got 1, 1, 5, 1, 5, for total of 1100 points

## What's next?

Maybe a good challenge is to try implementing the full game based on complete rules? (this or this)

In addition to a lot of other answers, it's worth noting the bonus logic can be simplified. We don't have to strictly adhere to the written version if we can find a logical equivalent:

1000 pts for 3 ones

100 pts for 1 one (not included in the upper rule)

is equivalent to

100 pts per one

700 pts if 3 or more ones

Which means

if (cnt[1] == 3)
{
ret += 1000;
}
if (cnt[1] == 2)
{
ret += 200;
}
if (cnt[1] == 1)
{
ret += 100;
}
if (cnt[1] == 4)
{
ret += 1100;
}
if (cnt[1] == 5)
{
ret += 1200;
}


can be simplified to

ret += 100 * cnt[1] + 700 * (cnt[1] / 3)  # Note this will not support more than 5 dice


Fives can likewise be simplified and for the other numbers, using integer division we can reduce our summation logic from 56 lines to 6, and it should be clearer what is happening to boot:

# sum score per number count - Note this will not support more than 5 dice
ret += 700 * (cnt[1] / 3) + 100 * cnt[1]
ret += 200 * (cnt[2] / 3)
ret += 300 * (cnt[3] / 3)
ret += 400 * (cnt[4] / 3)
ret += 350 * (cnt[5] / 3) + 50 * cnt[5]
ret += 600 * (cnt[6] / 3)


Alternatively, we can recognize that the bonus we get is 100 * the die roll for every die except 1, and use that logic:

ret += 900 * (cnt[1] / 3);  # Adjustment because 1s give 1000 pts, not 100

# For each value, if 3+ rolled add 100 * value
for (int i = 1; i <= 6; i++){
if (cnt[i] / 3){
ret += 100 * i;
cnt[i] -= 3;
}
}