Need help, loops...

[Fei Liu]

Hi,
I am trying to write a program to count dices. The program takes a
single integer 'n' (number of dice), it then outputs between 'n' and
'6*n', what combinations of the n dice result sums to it. Say, n=4,
sum=5, then it outputs 1 1 1 2 5, 1 1 2 1 5, 1 2 1 1 5, 2 1 1 1 5. I am
stuck with a problem, since my program is supposed to accept arbitrary
number of dice, I can't come up with a way to code the loops. Remember
it needs to iterate through arbitrary number of dices. Here is what I
have (compilies/runs/result is wrong for obvious reasons)

Let me know if you can come up with a smart pattern to solve this:
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>
using namespace std;

int main(void){

unsigned int n, i,k;

while(cin){
cin >> n;
string line;
getline(cin, line);

unsigned int min=n, max=n*6, sum=0;
vector<unsigned int> dice(n);

for(i=min; i <= max; i ++){

for(k=0; k < n; k ++)
for(j=1; j <= 6; j ++)
dice[k] = j;

sum = accumulate(dice.begin(), dice.end(), 0);
if(sum == i) {
copy(dice.begin(), dice.end(),
ostream_iterator<unsigned int>(cout, " "));
cout << i << ' ' << endl;
}
}
}
return 0;
}

 

[Arny]

Sounds like a dynamic programming problem.

Stu

I would solve it by finding all possible combinations, then the unique
combinations, and then create the permutations based on the unique
combinations.

- RaZ

 

[Fei Liu]

I think this is commonly solved using recursion.

V

Good idea, I have a working prototype, it's slow (exponential) but
produces correct answer.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>
using namespace std;

typedef vector<unsigned int>::iterator dice_iterator;
typedef vector<unsigned int>::reverse_iterator dice_reverse_iterator;

void add_and_carry(dice_reverse_iterator iter, int position){

(*iter)++;
if(*iter == 7 && position != 0){
add_and_carry(iter+1, position-1);
*iter = 1;
}
}

int main(void){

unsigned int n, i,k;

while(cin){
cin >> n;
string line;
getline(cin, line);

unsigned int min=n, max=n*6, sum=0;
vector<unsigned int> dice(n);
dice_iterator iter = dice.begin();

for(i = min; i <= max; i++){
for(; iter != dice.end(); iter ++)
*iter = (i-1)/n+1;
iter = dice.begin();
do{

sum = accumulate(dice.begin(), dice.end(), 0);
if(sum == i) {
copy(dice.begin(), dice.end(),
ostream_iterator<unsigned int>(cout, " "));
cout << i << ' ' << endl;
}
add_and_carry(dice.rbegin(), n-1);
} while(*iter != 7);
}
}
return 0;
}

 

[Ben]

Hi,

I am trying to write a program to count dices. The program takes a
single integer 'n' (number of dice), it then outputs between 'n' and
'6*n', what combinations of the n dice result sums to it. Say, n=4, sum=5,
then it outputs 1 1 1 2 5, 1 1 2 1 5, 1 2 1 1 5, 2 1 1 1 5. I am stuck
with a problem, since my program is supposed to accept arbitrary number of
dice, I can't come up with a way to code the loops. Remember it needs to
iterate through arbitrary number of dices. Here is what I have
(compilies/runs/result is wrong for obvious reasons)

Let me know if you can come up with a smart pattern to solve this:

If n is small, you can use a single unsigned integer to store the
combinations. A 64 bit integer can work with n <=18, this will be a lot
faster than using a vector.

If that is the case, the solution is trivial:

int n = 4;
int sum = 8;

int start = sum - n + std:ow(10.0, n)/9;
int end = start/10 + std:ow(10.0, n - 1) * (sum - n + 1);

while (start <= end)
{
std::cout << start << "\n";
start += 9;
}

Of course, this assumes a 10-sided dice . How to adjust the algorithm so
that it outputs 6-sided dice numbers is left for you as an exercise.

Regards,
Ben