Something better than many nested `for` loops?

Viewed 252

I wish to evaluate several different potential rules/scoring systems for a game. The game involves rolling three dice up to three times. In order to consider the results of each eventuality, I'm iterating over all the possible values of each of the nine possible rolls of the dice.

My question is whether the following brute force style coding is the best approach.

// get the result for each possible game
void Evaluate( const ScoringSystem& sys )
{
    for( int d1=0; d1<6; ++d1 )
    {
        for( int d2=0; d2<6; ++d2 )
        {
            for( int d3=0; d3<6; ++d3 )
            {
                for( int d4=0; d4<6; ++d4 )
                {
                    for( int d5=0; d5<6; ++d5 )
                    {
                        for( int d6=0; d6<6; ++d6 )
                        {
                            for( int d7=0; d7<6; ++d7 )
                            {
                                for( int d8=0; d8<6; ++d8 )
                                {
                                    for( int d9=0; d9<6; ++d9 )
                                    {
                                        int rolls[] = { d1, d2, d3, d4, d5, d6, d7, d8, d9 };

                                        // get the result for this particular game
                                        sys.GetGameResult( rolls );
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

The code functions but is ugly and not extensible to a game with more dice. I've got an environment that supports C++17, so I'm open to newer ideas — as long as they don't make the code look too terrible.

(Tangent: 6^9 is over 10 million. I might be better off using pseudo-random numbers and just 'rolling' nine dice a million times. But I still want to know if there's a clever way to work through the permutations.)

8 Answers

If you ever find that you're nesting loops that look pretty much the same you should consider using recursion.

void generateDiceRolls(const ScoringSystem& sys, std::vector<int>& rolls, size_t index)
{
    if (index == rolls.size())
    {
        // Reached the end - all the dice have been rolled
        sys.GetGameResult(rolls);
    }
    else
    {
        // For each value of a die at this index, generate dice rolls for the rest of them
        for (int i = 0; i < 6; i++)
        {
            rolls[index] = i;
            generateDiceRolls(sys, rolls, index + 1);
        }
    }
}
void Evaluate(const ScoringSystem& sys)
{
    std::vector<int> rolls(9);  // Change 9 to however many dice you want to use
    generateDiceRolls(sys, rolls, 0);
}

Some libraries as range-v3 propose cartesian_product to allow simpler:

std::array<int, 6> dice_range{1, 2, 3, 4, 5, 6};
for (auto t : ranges::view::cartesian_product(dice_range, dice_range, dice_range,
                                              dice_range, dice_range, dice_range,
                                              dice_range, dice_range, dice_range))
{
    std::cout << std::get<0>(t)
              << std::get<1>(t)
              << std::get<2>(t)
              /* << .. */
              << std::endl;
    std::apply([](auto... args){ (std::cout << ... << args) << std::endl; }, t); // C++17
}

Without external libraries, you might use a vector that you "increase":

bool increase(std::vector<std::size_t>& it, std::size_t max)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] >= max) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

template <typename F>
void iterate(F f, std::size_t size, std::size_t max = 6)
{
    std::vector<std::size_t> it(size, 0);

    do {
        f(it);
    } while (increase(it, max));
}

int main()
{
    iterate([](const auto& v){ for (auto e : v) std::cout << 1 + e; std::cout << std::endl; }, 4);
}

Demo

You can treat the "game number" as a single number from 0 up to 6*6*6*6*6*6*6*6*6. Think of it in base 6 (so 000000000 up to 555555555) and extract the digits and those are your dice rolls:

for(int game = 0; game < 6*6*6*6*6*6*6*6*6; game++) {
    int d9 = game % 6;
    int d8 = (game / 6) % 6;
    int d7 = (game / (6*6)) % 6;
    // ...
}

This is extensible as long as the total number of games fits in an int. Or you can upgrade to uint64_t (stdint.h). You won't run out of space there because it'll take a universe-lifetime to finish running anyway.

Or, you can use an array to hold the game state, and work out what the "next" game state is. This way the dice rolls don't have to fit in a single number variable:

int d[9] = {0,0,0,0,0,0,0,0,0};
do {
    // ... play the game ...
} while(nextGameState(d));

bool nextGameState(int d[]) {
    // Add 1 to the last die.
    // If it gets to 6, set it back to 0 and add 1 to the previous die instead.
    // If the first one gets to 6 then we're done.
    for(int i = 8; i >= 0; i--) {
        if (d[i] == 5) {
            d[i] = 0;
        } else {
            ++d[i];
            return true;
        }
    }
    return false; // no dice left to increase
}

In all these cases the sequence is the same: 000000000, 000000001, ..., 000000005, 000000010, 000000011, ..., 000000055, 000000100, ..., 555555554, 555555555

You can have one loop over [0, 6^9) and map that to your rolls array

for (int i = 0; i < 10077696; ++i) {
    int temp = i;
    int rolls [9];
    for (int & roll : rolls) {
        roll = temp % 6;
        temp /= 6;
    }
    sys.GetGameResult( rolls );
}

This generalises to any sequence of dice such that the permutations fit into uintmax_t

void iterate_dice(std::vector<int> dice, std::function<void(std::vector<int>)> func) {
    uintmax_t permutations = std::accumulate(dice.begin(), dice.end(), uintmax_t{ 1 }, std::multiplies<uintmax_t>{});

    for (uintmax_t i = 0; i < permutations; ++i) {
        int temp = i;
        std::vector<int> rolls(dice.size());
        for (int j = 0; j < dice.size(); ++j) {
            rolls[j] = temp % dice[j];
            temp /= dice[j];
        }

        func(rolls);
    }
}

That enormous nesting might indeed cause performance issues, and there are cases where a serious improvement can be made, let's have a look at this case:

for( int d1=0; d1<6; ++d1 )
{
    for( int d2=0; d2<6; ++d2 )
    {
        for( int d3=0; d3<6; ++d3 )
        {
            for( int d4=0; d4<6; ++d4 )
            {
              if (condition_1_2(d1, d2) &&
                  condition_1_3(d1, d3) &&
                  condition_1_4(d1, d4))
              {
                 do_something();
              }

This can be replaced by:

for( int d1=0; d1<6; ++d1 )
{
    for( int d2=0; d2<6; ++d2 )
    {
        if (condition_1_2(d1, d2)
        for( int d3=0; d3<6; ++d3 )
        {
            if (condition_1_3(d1, d3))
            for( int d4=0; d4<6; ++d4 )
            {
              if (condition_1_4(d1, d4))
              {
                 do_something();
              }

As you see: the internal d3-loop will only be started if condition_1_2 is met, the internal d4-loop will only be started if condition_1_3 is met, ...

This way of working can be used for solving the well-known queens problem: no need to try to put any queen in the third column if the ones in the first and second column can take each other.

You could also use a custom generator to use in std::generate()

class VariationsGenerator
{
public:
    VariationsGenerator(int setSize, int numberOfChooses): 
        setSize{setSize}, 
        numberOfChooses{numberOfChooses},
        currentVariation(numberOfChooses, 0)
    {}

    int operator()()
    {
        if(currentIndex >= numberOfChooses)
        {
            increment();
            currentIndex = 0;
        }
        return currentVariation[currentIndex++];
    }

private:
    void increment()
    {
        bool shouldContinue = true;
        int index = 0;
        while(shouldContinue)
        {
            currentVariation[index]++;
            index++;
            if(index >= numberOfChooses)
            {
                currentVariation = std::vector<int>(numberOfChooses, 0);
                return;
            }
            if(currentVariation[index - 1] >= setSize)
            {
                currentVariation[index - 1] -= setSize;
            } 
            else
            {
                shouldContinue = false;
            }
        }
    }
 
    const int setSize;
    const int numberOfChooses;
    int currentIndex {0};
    std::vector<int> currentVariation;
};

Usage

VariationsGenerator gen(6, 9);
for(int i = 0; i < 6*6*6*6*6*6*6*6*6; ++i)
{
    int rolls[9];
    std::generate(rolls, rolls+9, std::ref(gen)); //must pass by reference, but std::generate gets a copy
    for(int n: rolls)
        std::cout << n;
    std::cout << '\n';
}

I didn't really test it well, in particular the return to beginning case, but it works for some number of generations.

I like pretty syntax, and dislike recursion.

template<class It, class Sent=It>
struct range {
  It b;
  Sent e;
  It begin() const { return b; }
  Sent end() const { return e; }
};

template<class T>
struct index {
  T t;
  T const& operator*() const { return t; }
  T const* operator->() const { return std::addressof(t); }
  bool operator==(index const&) const = default;
  bool operator<=>(index const&) const = default;
  index& operator++() { ++t; return *this; }
  index operator++(int) { auto self=*this; ++*this; return self; }
};

template<std::size_t N, int max=6>
struct dice:std::array<int, N> {
  static dice last() {
    dice retval;
    for (int& t:retval)
      t = max;
    return retval;
  }
  dice& operator++() {
    bool finished = false;
    for (int& t:*this) {
      ++t;
      if (t!=max)
      {
        finished = true;
        break;
      }
      t = 0;
    }
    if (!finished)
      *this = last();
    return *this;
  }
  dice operator++(int) {
    auto self=*this;
    ++*this;
    return self;
  }
};

template<class T>
range<index<T>> elements_range( T b, T e ) {
  return {{b}, {e}};
}

To test, we just do:

using rolls  = dice<9>;
std::size_t count = 0;
for (auto roll : elements_range( rolls{}, rolls::last() )) {
  ++count;
}
std::cout << count << " total kinds of die rolls\n";

Live example.

As an aside, this isn't just bespoke code. elements_range( vec.begin(), vec.end() ) is surprisingly useful (it is an iteration over the valid iterators into a vector).

The best approach in these kind of problems of finding all the permutations is to use Recursion, ie call a function repeatedly a specific number of times, in this case, we shall call a function to add a number between 1 to 6 to a array 9 times.

Here is the code of the function :

void rec (int A[], int n, const ScoringSystem& sys)
{
    if(n==9) 
    {
        sys.GetGameResult(A);
        return;
    }
    
    for(int i=1;i<=6;i++)
    {
        A[n] = i;
        rec(A,n+1);
    }
}

Trigger the function using:

int A[9];
rec(A, 0, sys);
Related