# Thread: Russian Roulette

1. ## Josephus problem

Hi
I am writing a program of Josephus problem in which each player kills next player and the person which is left is winner.
For Example, for 5 players

1 -- 2 -- 3 -- 4 -- 5

Starting with 1, 1 kills 2

1 -- 3 -- 4 -- 5

3 kills 4

1 -- 3 -- 5

5 kills 1

3 -- 5

3 kills 5

3

So winner is 3.

Here's my Program, I use Circular Doubly Linked List:

Code:
```#include <stdlib.h>

struct node
{
int data;
}*start = NULL, *end = NULL, *new1, *free_me;

void insert_end();
void delete_next();
void display();

void main()
{
int i;
printf(" \n\n\t-- Russian Roulette -- \n\n");

new1 = (struct node*) malloc(6);

start = new1;
end = new1;
start -> addrs_next = start;
start -> addrs_prev = start;
start -> data = 1;

for (i=2; i<11; i++)
insert_end(i);
display();

printf("\tPlayers are ready, Press aky key to start killing ...\n\n");
getch();

while (start != end)
{
delete_next();
new1 = new1 -> addrs_next;
display();
getch();
}

printf("Winner: %d", start->data);
}

void delete_next()
{
end = end -> addrs_prev;
else if (new1 == end)
start = start -> addrs_next;

new1 = new1 -> addrs_next;                                // advance new1
new1 = new1 -> addrs_prev;                            // reset new1
free(free_me);
}

void insert_end(int value)
{
new1 = (struct node*) malloc(4);

end -> addrs_next = new1;
new1 -> addrs_prev = end;

start -> addrs_prev = new1;
new1 -> addrs_next = start;
end = new1;

end -> data = value;
}

void display()
{
int run = 1;
printf("\n\tList:\n\n\t");
if( start == NULL || end == NULL)
return;
for(new1 = start; run; new1 = new1->addrs_next)
{
if (new1->addrs_next == start)
run = 0;
printf("%d  ", new1->data);
}
printf("\n");
}```
But there is something wrong here, the change in new1 not done globally. I mean, if i set new1 = new1 -> addrs_prev in delete_next(), main() does not show this change.

PS: *.c file attached

RR_BKP.c

2. Code:
`    new1 = (struct node*) malloc(6);`
Why 6???
6 is very very very probably not the size of an object of type struct node.
Use the proper size, and try again

Code:
`    new1 = malloc(sizeof *new1);`

3. He wants to use six, so he won't get killed -- of course!

4. Originally Posted by qny
Why 6???
6 is very very very probably not the size of an object of type struct node.
Use the proper size, and try again
Code:
`    new1 = malloc(sizeof *new1);`
Originally Posted by Sumone Unknon
Code:
```struct node
{
int data;
}*start = NULL, *end = NULL, *new1, *free_me;```
Isn't a pointer always of size 2 bytes?

I used sizeof(struct node*) and got 2 bytes. Integer was also 2 bytes.

So 2+2+2 = 6 bytes.

EDIT:
Also, in line 72, it must be malloc(6), changing 4 to 6 solved another problem (which i did not mention) that after everyone was killed, the loop kept on printing 0 indefinitely. Now it does not, but I dont know why. If anyone does, please DO tell me.

5. Originally Posted by Sumone Unknon
I am writing a program of Russian Roulette in which each player kills next player and the person which is left is winner.
This is not Russian Roulette! It's a form of the Josephus problem - Wikipedia, the free encyclopedia

6. Originally Posted by Sumone Unknon
Isn't a pointer always of size 2 bytes?
No. A pointer is the size needed to represent an address on the architecture running the problem. They're most commonly 32 or 64 bits. 16 is less common now but still around.

Originally Posted by Sumone Unknon
I used sizeof(struct node*) and got 2 bytes. Integer was also 2 bytes.

So 2+2+2 = 6 bytes.
You can't assume that either. The compiler can insert padding between structure members, generally for alignment reasons but maybe for others too.

If you use sizeof, as qny suggested, it'll take care of a lot of these problems! Padding will be counted, and pointer size will be hidden and more portable..

7. Do you mean like this?

Code:
`new1 = (structnode*) malloc( ( ( sizeof(struct node*) )*2 ) + 2);`

8. Originally Posted by Sumone Unknon
EDIT:
Also, in line 72, it must be malloc(6), changing 4 to 6 solved another problem (which i did not mention) that after everyone was killed, the loop kept on printing 0 indefinitely. Now it does not, but I dont know why. If anyone does, please DO tell me.
It definitely mustn't malloc(4), as you can be sure that that's not enough memory by your own calculations.

If you malloc 4 bytes for a 6 byte structure, what happens when the program tries to access the 5th and 6th bytes of the structure?
The answer is that it depends on your OS/platform/environment -- often the behaviour is to simply write to those bytes even though they aren't allocated for that structure. Then when the next struct is malloc'd, it could get an overlapping address range with the previous structs.
If you only write to 1 byte of a 20 byte struct, you still must allocate 20 bytes for it. You still have a malloc(4) in your code that you have to fix

I can't see anything in the code that'd explain printing 0, so I think that might have been a memory corruption problem.

9. Originally Posted by Sumone Unknon
Do you mean like this?

Code:
`new1 = (structnode*) malloc( ( ( sizeof(struct node*) )*2 ) + 2);`
Nothing so complicated - you don't need to count the components:

Code:
`new1 = (struct node*) malloc(sizeof(struct node));`

10. Originally Posted by oogabooga
This is not Russian Roulette! It's a form of the Josephus problem - Wikipedia, the free encyclopedia
I changed the title from "Russian Roulette" to "Josephus problem"

Thanks for telling me the real name of the problem

11. Originally Posted by smokeyangel
It definitely mustn't malloc(4), as you can be sure that that's not enough memory by your own calculations.

If you malloc 4 bytes for a 6 byte structure, what happens when the program tries to access the 5th and 6th bytes of the structure?
The answer is that it depends on your OS/platform/environment -- often the behaviour is to simply write to those bytes even though they aren't allocated for that structure. Then when the next struct is malloc'd, it could get an overlapping address range with the previous structs.
If you only write to 1 byte of a 20 byte struct, you still must allocate 20 bytes for it. You still have a malloc(4) in your code that you have to fix

I can't see anything in the code that'd explain printing 0, so I think that might have been a memory corruption problem.
Well yes that makes sense ... but if by memory corruption means that some parts of allocated structures overlap and a garbage value is being printed, why is it always 0? and why is getch() not working?
It just prints "0 0 0 0 0 0 0 0 0 ..." and doesn't even wait for a key to be pressed.

Originally Posted by smokeyangel
Nothing so complicated - you don't need to count the components:

Code:
`new1 = (struct node*) malloc(sizeof(struct node));`
Oh yes, I didn't think of that
I feel stupid :P

Popular pages Recent additions