Velocity Reviews > C++ > Need help, loops...

# Need help, loops...

Fei Liu
Guest
Posts: n/a

 04-22-2010
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
Guest
Posts: n/a

 04-22-2010

On 22.04.2010 17:13, Stuart Golodetz wrote:
> Fei Liu wrote:
>> 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:

>
> 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
Guest
Posts: n/a

 04-22-2010
Victor Bazarov wrote:
> Fei Liu wrote:
>> 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)

>
> I think this is commonly solved using recursion.
>
> V

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

#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){
*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;
}
} while(*iter != 7);
}
}
return 0;
}

Ben
Guest
Posts: n/a

 04-23-2010
> 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