473,890 Members | 1,372 Online

# rolling dice

Let's say I have m dice having n sides, such that n^m is not going to bust
int as a datatype. With m=4 and n=6, an outcome might be {2, 5, 1, 2}.
What is a good way to represent this in c so that I can check cases by brute
force? EC
Sep 30 '06 #1
101 6448

"Elijah Cardon" <in*****@invali d.netwrote in message
news:12******** *****@corp.supe rnews.com...
Let's say I have m dice having n sides, such that n^m is not going to bust
int as a datatype. With m=4 and n=6, an outcome might be {2, 5, 1, 2}.
What is a good way to represent this in c so that I can check cases by
brute force? EC

typedef struct
{
int m;
int n;
int *roll; /* allocated dice with malloc */
} DICEROLL;

Is the obvious way if you have memory to burn.
However you already know all the possible dice in the roll set. So you can
generate the rolls from an index number by taking modulus and dividing.
--
www.personal.leeds.ac.uk/~bgy1mm
Sep 30 '06 #2
Elijah Cardon wrote:
Let's say I have m dice having n sides, such that n^m is not going to bust
int as a datatype. With m=4 and n=6, an outcome might be {2, 5, 1, 2}.
What is a good way to represent this in c so that I can check cases by brute
force? EC
One way that comes to mind are n-adic numbers; start your results
at 0 (i.e. subtract 1 if necessary), then you get digits of a range
from 0 to n-1. This can be (using ^ to express powers) represented
as
a[m-1]*n^(m-1)+....+a[1]*n^1+a[0]*n^0.
I.e. the above can be represented as
(2-1)*216+(5-1)*36+(1-1)*6+(2-1)*1
In most cases, I'd rather use an array containing the digits -- for
many n, it is easier to debug. If you then really want to be able
to squeeze it into an int, then you can do it as soon as the rest
works.

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Sep 30 '06 #3
Malcolm posted:
typedef struct
{
int m;
int n;
int *roll; /* allocated dice with malloc */
} DICEROLL;

I strongly advocate the use of ALL CAPS for macros and for macros only.

--

Frederick Gotham
Sep 30 '06 #4
Elijah Cardon posted:
Let's say I have m dice having n sides, such that n^m is not going to
bust int as a datatype.

By "bust", do you mean overflow? The highest number reliably stored in an int
is 32767. If "n" is 6, then "m" can be as large as 5.

With m=4 and n=6, an outcome might be {2, 5, 1,
2}. What is a good way to represent this in c so that I can check cases
by brute force? EC

I don't know what you mean by "check cases". The programming language is
invariably spelled with an uppercase C, just so you know.

--

Frederick Gotham
Sep 30 '06 #5

"Malcolm" <re*******@btin ternet.comwrote in message
news:RK******** ************@bt .com...
>
"Elijah Cardon" <in*****@invali d.netwrote in message
news:12******** *****@corp.supe rnews.com...
>Let's say I have m dice having n sides, such that n^m is not going to
bust int as a datatype. With m=4 and n=6, an outcome might be {2, 5, 1,
2}. What is a good way to represent this in c so that I can check cases
by brute force? EC

typedef struct
{
int m;
int n;
int *roll; /* allocated dice with malloc */
} DICEROLL;
For the moment, I want to stay away from mallocs and structs. I think the
above approach would favor object orientation.
Is the obvious way if you have memory to burn.
However you already know all the possible dice in the roll set. So you can
generate the rolls from an index number by taking modulus and dividing.
Rolling the dice is what I'm not going to do. I'm going to enumerate the
outcomes. Memory is plentiful, and stdout will never run out of paper.
#define m 4
#define n 6

I don't see what good the first #define will do me when I need to hard code
the number of '[n]' in the statement

int a[n]a[n]a[n]a[n];

Any comment appreciated. EC
Sep 30 '06 #6
Elijah Cardon posted:
Rolling the dice is what I'm not going to do. I'm going to enumerate
the outcomes.

Bitwise manipulation might be handy for minimising memory consumption. For
instance, if a dice has 6 sides, then we only need 3 bits to log each
individual roll:

000 == Rolled 1 on the dice.
001 == Rolled 2 on the dice.
010 == Rolled 3 on the dice.
011 == Rolled 4 on the dice.
100 == Rolled 5 on the dice.
101 == Rolled 6 on the dice.

For even more conservative use of memory, we can find a multiple of 6 which
is also a integral power of 2 (unfortunately though, any such number is
quite large).

This problem would be far better solved with an OO language, but if you
want to use C, then so be it. Maybe something like:

#include <stddef.h>
#include <limits.h>
#include <assert.h>
#include <stdlib.h>

typedef struct EnumInfo {
unsigned bits_per_outcom e;
size_t quant_bytes;
char unsigned *p;
} EnumInfo;

unsigned BitsNeeded(unsi gned combinations)
{
/* I'm pretty sure there's a far
better way of implementing this
function.
*/

int const assert_dummy = (assert(!!combi nations),0);

unsigned bits = 1;

--combinations;

while(combinati ons >>= 1) ++bits;

return bits;
}

EnumInfo EnumerateResult s(unsigned const throws,unsigned const sides)
{
EnumInfo info;

info.bits_per_o utcome = BitsNeeded(side s);

info.quant_byte s = info.bits_per_o utcome * (throws/CHAR_BIT +1);
/* A few bytes wasted */
/* We might want a few checks to make sure
the size_t hasn't overflowed. */

info.p = malloc(info.qua nt_bytes);

/* Write the results to memory */

return info;
}

It will be a little tricky if CHAR_BIT isn't evenly divisible by
"bits_per_outco me" (which will happen quite a lot for 6-sided die on a
system with 8-Bit bytes). The complexity could be greatly reduced however
if you used an OO language which allowed you to implement a BitHandle which
could encapsulate the nitty-gritty of the bit manipulation away from your
other code -- but still, it's achievable in C.

--

Frederick Gotham
Sep 30 '06 #7

"Michael Mair" <Mi**********@i nvalid.invalidw rote in message
news:4o******** ****@individual .net...
Elijah Cardon wrote:
>Let's say I have m dice having n sides, such that n^m is not going to
bust int as a datatype. With m=4 and n=6, an outcome might be {2, 5, 1,
2}. What is a good way to represent this in c so that I can check cases
by brute force? EC

One way that comes to mind are n-adic numbers; start your results
at 0 (i.e. subtract 1 if necessary), then you get digits of a range
from 0 to n-1. This can be (using ^ to express powers) represented
as
a[m-1]*n^(m-1)+....+a[1]*n^1+a[0]*n^0.
I.e. the above can be represented as
(2-1)*216+(5-1)*36+(1-1)*6+(2-1)*1
In most cases, I'd rather use an array containing the digits -- for
many n, it is easier to debug. If you then really want to be able
to squeeze it into an int, then you can do it as soon as the rest
works.

#include "stdio.h"
#define n 6

int main(int argc, char* argv[])
{
int i1, i2, a[n][n];

for (i1 = 0; i1 < n; i1 ++)
{
for (i2 = 0; i2 < n; i2 ++)
{
/*what here */
}
}
printf("Hello World!\n");
return 0;
}
I was thinking that arrays were the way to go, but as I start to write the
control loops, it's the dummies themselves that I want. And I would
re-write the loops to go from 1 to n, as opposed to the matrix-friendly 0 to
n-1 . Where I have the comment, I could test for whether the dummies add to
seven and keep a counter of those that do, and those that don't. I would
then have the probability I'm looking for.

What I don't see is how I would take this approach and have a program that
isn't totally hard-coded for every dimension. EC
Sep 30 '06 #8
Frederick Gotham wrote:
For even more conservative use of memory, we can find a multiple of 6 which
is also a integral power of 2 (unfortunately though, any such number is
quite large).
If by power of 2 you mean a number of the form
2^k then no such number can be a multiple of 6.

Sep 30 '06 #9
Frederick Gotham wrote:
[...]
For even more conservative use of memory, we can find a multiple of 6 which
is also a integral power of 2 (unfortunately though, any such number is
quite large).
I can think of only one such integer, but it isn't very
large at all ...

--
Eric Sosman
es*****@acm-dot-org.invalid
Sep 30 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.