rolling dice

[Elijah Cardon]

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

[Malcolm]

Re: rolling dice




"Elijah Cardon" <invalid@invali d.netwrote in message
news:12hteqa2nn nfv34@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
>

Depends on your meory

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.


--

https://www.personal.leeds.ac.uk/~bgy1mm

freeware games to download.

[Michael Mair]

Re: rolling dice

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.

[Frederick Gotham]

Re: rolling dice

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

[Frederick Gotham]

Re: rolling dice

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

[Elijah Cardon]

Re: rolling dice


"Malcolm" <regniztar@btin ternet.comwrote in message
news:RKidna5M9s 8jXoPYRVnyhA@bt .com...

>
>
>
"Elijah Cardon" <invalid@invali d.netwrote in message
news:12hteqa2nn nfv34@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
>>

Depends on your meory
>
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

[Frederick Gotham]

Re: rolling dice

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

[Elijah Cardon]

Re: rolling dice


"Michael Mair" <Michael.Mair@i nvalid.invalidw rote in message
news:4o7ue2Fdfp sbU1@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

[Spiros Bousbouras]

Re: rolling dice

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.

[Eric Sosman]

Re: rolling dice

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
esosman@acm-dot-org.invalid

[Frederick Gotham]

Re: rolling dice

Spiros Bousbouras posted:

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.

Yes, I mean two non-zero positive integers, "k" and "x", which satisfy the
following equation:

(unsigned)pow(2 ,k) % (6 * x) == 0

I played around with my calculator and gave up when I went as far as 2048.
Being a non-mathematician, I'm not great at spotting these things straight
away ;).

--

Frederick Gotham

[Michael Mair]

Re: rolling dice

Elijah Cardon wrote:

"Michael Mair" <Michael.Mair@i nvalid.invalidw rote

>>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

I am still not sure what you want but variable dimension can
be coded straightforward via recursion:

,---
#include <stdio.h>

int countSumOccurre nces(int n, int m, int sum);
void countSumOccurre nces_Rec(int n, int m, int sum, int *pCount);

int main (void)
{
int i;
for (i = 1; i <= 5; ++i)
printf("%d 6 sided dices; occurrence of sum %d: %d times\n",
i, 2*i, countSumOccurre nces(6, i, 2*i));
return 0;
}

int countSumOccurre nces(int n, int m, int sum)
{
int count = 0;
countSumOccurre nces_Rec(n, m, sum, &count);
return count;
}

void countSumOccurre nces_Rec(int n, int m, int sum, int *pCount)
{
#define VALUE_ADJUSTMEN T(v) ((v)+1)
if (m == 1) {
if (sum >= VALUE_ADJUSTMEN T(0) && sum < VALUE_ADJUSTMEN T(n)) {
++*pCount;
}
}
else if (m 1) {
int i;
for (i = 0; i < n && i <= sum; ++i) {
countSumOccurre nces_Rec(n, m - 1,
sum - VALUE_ADJUSTMEN T(i), pCount);
}
}
}
`---

Note that you can always get rid of a recursion via using a stack.
You probably want to get rid of the VALUE_ADJUSTMEN T in this case.


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Spiros Bousbouras]

Re: rolling dice

Elijah Cardon wrote:

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 probability are you looking for ? You still
haven't explained what problem you're trying to
solve.

[Spiros Bousbouras]

Re: rolling dice

Frederick Gotham wrote:

Spiros Bousbouras posted:
>

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.

>
>
Yes, I mean two non-zero positive integers, "k" and "x", which satisfy the
following equation:
>
(unsigned)pow(2 ,k) % (6 * x) == 0

For a large enough k this will be satisfied simply because
pow(2,k) will wrap around to 0. But without wraparound it
will never be true.

[Elijah Cardon]

Re: rolling dice


"Michael Mair" <Michael.Mair@i nvalid.invalidw rote in message
news:4o851uFd5p t3U1@individual .net...

Elijah Cardon wrote:

>"Michael Mair" <Michael.Mair@i nvalid.invalidw rote

>>>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

#include <stdio.h>
>
int countSumOccurre nces(int n, int m, int sum);
void countSumOccurre nces_Rec(int n, int m, int sum, int *pCount);
>
int main (void)
{
int i;
for (i = 1; i <= 5; ++i)
printf("%d 6 sided dices; occurrence of sum %d: %d times\n",
i, 2*i, countSumOccurre nces(6, i, 2*i));
return 0;
}
>
int countSumOccurre nces(int n, int m, int sum)
{
int count = 0;
countSumOccurre nces_Rec(n, m, sum, &count);
return count;
}
>
void countSumOccurre nces_Rec(int n, int m, int sum, int *pCount)
{
#define VALUE_ADJUSTMEN T(v) ((v)+1)
if (m == 1) {
if (sum >= VALUE_ADJUSTMEN T(0) && sum < VALUE_ADJUSTMEN T(n)) {
++*pCount;
}
}
else if (m 1) {
int i;
for (i = 0; i < n && i <= sum; ++i) {
countSumOccurre nces_Rec(n, m - 1,
sum - VALUE_ADJUSTMEN T(i), pCount);
}
}
}
`---
>
Note that you can always get rid of a recursion via using a stack.
You probably want to get rid of the VALUE_ADJUSTMEN T in this case.

This is the line I wanted to take this in, but I gotta get my head around
the notions of recursion and stack depth. To that I end I ask this
question:
long factorial(int n) {
if (n == 1)
return 1;
return n * factorial(n - 1);
}

What is the stack depth as a function of n? If you look at the discussion
in chp 10 of _C Unleashed_, it follows the execution of this source. At the
end, there are n-1 paragraphs that begin:
Back on line ....
, so I think the stack depth is n-1 . If I'm wrong that it's near n, I
don't see how stack depth could be less than (n-1)! . EC