Thread: Russian Roulette

  1. #1
    Registered User
    Join Date
    Aug 2012
    Posts
    6

    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;
        struct node *addrs_next, *addrs_prev;    
    }*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()
    {
        if(new1 == end->addrs_prev)
            end = end -> addrs_prev;
        else if (new1 == end)
            start = start -> addrs_next;
    
    
        free_me = new1 -> addrs_next;                            // addrs bkp for free()
        new1 -> addrs_next = new1 -> addrs_next -> addrs_next;    // change addrs_next
        new1 = new1 -> addrs_next;                                // advance new1
        new1 ->addrs_prev = new1 ->addrs_prev ->addrs_prev;     // change addrs_prev
        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
    Last edited by Sumone Unknon; 10-13-2012 at 03:37 PM.

  2. #2
    Registered User
    Join Date
    Sep 2012
    Posts
    357
    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. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    He wants to use six, so he won't get killed -- of course!

  4. #4
    Registered User
    Join Date
    Aug 2012
    Posts
    6
    Quote Originally Posted by qny View Post
    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);
    Quote Originally Posted by Sumone Unknon View Post
    Code:
    struct node
    {
        int data;
        struct node *addrs_next, *addrs_prev;    
    }*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.
    Last edited by Sumone Unknon; 10-13-2012 at 03:11 PM.

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Sumone Unknon View Post
    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
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    583
    Quote Originally Posted by Sumone Unknon View Post
    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.

    Quote Originally Posted by Sumone Unknon View Post
    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. #7
    Registered User
    Join Date
    Aug 2012
    Posts
    6
    Do you mean like this?

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

  8. #8
    Registered User
    Join Date
    Mar 2010
    Posts
    583
    Quote Originally Posted by Sumone Unknon View Post
    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. #9
    Registered User
    Join Date
    Mar 2010
    Posts
    583
    Quote Originally Posted by Sumone Unknon View Post
    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. #10
    Registered User
    Join Date
    Aug 2012
    Posts
    6
    Quote Originally Posted by oogabooga View Post
    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
    Last edited by Sumone Unknon; 10-13-2012 at 03:52 PM.

  11. #11
    Registered User
    Join Date
    Aug 2012
    Posts
    6

    Smile

    Quote Originally Posted by smokeyangel View Post
    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.

    Quote Originally Posted by smokeyangel View Post
    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 subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 05-22-2009, 07:03 AM
  2. Russian Peasent
    By Lucid15 in forum C Programming
    Replies: 34
    Last Post: 09-30-2008, 12:07 PM
  3. Russian student attacks Estonia
    By Perspective in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 01-25-2008, 10:35 AM
  4. Roulette!
    By DanC in forum C++ Programming
    Replies: 11
    Last Post: 03-09-2006, 01:57 PM
  5. Russian stuffffffffff
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 04-22-2004, 01:21 PM