Thread: Futurama Theorem

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    13

    Exclamation Futurama Theorem

    Recently, on my programming course my teacher has assigned us to write a program in C that compiles the Futurama Theorem, displayed in the chapter Prisoner of Benda. The theorem itsself is a guideline to put someone's mind back in their body after a mind-body swap, in which two bodies which have swapped once, cannot do so again. Neither I nor my partner know how to write this program, it's well beyond our knowledge of programming and I was hoping to come across someone helpful to point us in the right direction. Thank you.

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    You need one more body...

    Code:
    #include <stdio.h>
    
    int main (void)
      {
         int body1, body2, body3;
    
         body 1 = 10;
         body 2 = 20;
    
         printf( "body1 = %d\tbody2 = %d\n",body1,body2);
    
         body3 = body 1;
         body 1 = body 2;
         body 2 = body 3;
         body 3 = 0;
    
         printf( "body1 = %d\tbody2 = %d\n",body1,body2);
         printf( "poor old body three gets %d\n\n", body3);
    
         return 0;
    }
    Actually this is the classic array swap used in lots and lots of C programs.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    Thanks, but this isn't really what I need. I need to be able to input the names, swap them at random, display the changes, and then display, step by step, the changes needed to go back to normal, using at most 2 extra bodies. Thanks anyway.

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    We don't give out finished code here. We will point you in the right direction and help you debug failed code... but we're not going to hand you a complete algorythm in ready to use form.

    I gave you a starting point... the rest is up to you.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What does it mean to compile the Futurama Theorem?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    I know, I didn't ask for a finished code. I just pointed out that that wasn't what we needed. We have an algorithm that generates random numbers, which we plan on using in place of names, but we can't get the numbers to stop repeating themselves. we also have the swapping algorithm, but don't know how to make it random. We still have to find out how to apply the theorem itsself, but I figured we needed to get the input done first, and that's what this is about. This is out random number generator, which we can't get to not return different values. If you have any clues to give at all, you have my thanks in advance.
    insert
    Code:
    #include stdio.h>
    #include stdlib.h>
    #include time.h>
    
    
    #define TOTAL_NUMBERS 10
    #define MAX_VALUE 10.0
    
    
    int main () {
        int i, j;
    
    
        srand(time(NULL));
    
    
        for (i=0 ; i < TOTAL_NUMBERS ; i++) {
            j = 1 + (int)( MAX_VALUE * rand() / ( RAND_MAX + 1.0 ) );
                
            printf ("random_number[%d]= %d\n",i, j);
        }

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Ferreres93
    This is out random number generator, which we can't get to not return different values.
    There are two general approaches when faced with the problem of getting a (pseudo-)random number generator to produce a sequence without duplicates:
    • Populate an array or other list with the numbers, then shuffle.
    • Generate each number and check if it is a duplicate. If so, generate the number again, until it is unique.

    The former is good when the number of numbers is close to the range of possible numbers, otherwise the latter is good.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    What you need is probably the standard "card shuffle" algorythm like laserlight is suggesting...

    Code:
    // card shuffle demonstration
    
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    
    #define RANDS 52
    
    int main (void)
      {
        int Nums[RANDS];  // the array
        int item = 0;     // swaps
        int temp;         
        int idx = 0;      // loops
    
        srand(time(NULL));
    
        for(idx = 0; idx < RANDS; idx++)
          Nums[idx] = idx + 1;
    
    
        // unshuffled array
        for (idx = 0; idx < RANDS; idx++)
          printf("[%d] = %d \t", idx, Nums[idx]);
    
        // shuffle the array
        for (idx = RANDS - 1; idx > 0; idx--)
          { item = rand() % idx;
            temp = Nums[idx];
            Nums[idx] = Nums[item];
            Nums[item] = temp; }
    
        // shuffled array
        printf("\n\n");
        for (idx = 0; idx < RANDS; idx++)
          printf("[%d] = %d \t", idx, Nums[idx]);
    
        printf("\n\nPress Enter to exit...");
        getchar();
        return 0;
      }

  9. #9
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by laserlight View Post
    What does it mean to compile the Futurama Theorem?
    It's actually a logic puzzle, Lase...

    Two people's minds are swapped
    They cannot be swapped back because you can only swap each pair once
    You can use additional bodies as needed
    The problem is to get all the right minds back into the right bodies.

    They did the same thing on Stargate, if you're not a Futurama fan...
    Last edited by CommonTater; 11-30-2011 at 06:13 AM.

  10. #10
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    Okay, I think I pretty much solved it, but I still can't figure out how to stop the changes from repeating a bodyswap. Can anybody help me with that? Any ideas?

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You need to post code and describe your problem in terms of the code.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    Okay, I created this array for the names:
    Code:
    main () {int N;
    char Names [9] [15] = {"Zoidberg", "Fry", "Leela", "Profesor", "Bender", "Amy", "Hermes", "Washbucket", "Emperor Nikolai"};
    scanf ("%d", &N);
    printf ("%c", Names[N]);
    system ("PAUSE");
    }
    I have no idea how to scrable them, nothing I do works, so if you could, I would appreciate some pointers on how to do it. Thanks.

  13. #13
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    @mk27 ... I've been thinking about this one, it presents a very interesting logic problem...
    In "C" terms...

    Code:
    // untested!
    
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    
    void swap(int x, int y, int* array)
      {
          int temp;
         temp = array[x];
         array[x] = array[y];
         array[y] = temp;
      }
    
    // Entry
    int main (void)
      {
         int array[100];
         int i,x,y;
    
         srand(time(NULL));
    
        // initialize
        for (i = 0; i < 100; i++)
           array[i] = i;
    
        // start problem
        x = rand() %100;
        y = rand() %100;
        swap(x,y,array);
    
    
        return 0;
    }
    Now the problem is to sort the array without repeating any combination of x and y to swap values. (Eg. You can only swap array[41] with array [7] once.) The initial swap is already made, so you can't use it again...
    Last edited by CommonTater; 12-02-2011 at 11:57 AM.

  14. #14
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Ferreres93 View Post
    Okay, I created this array for the names:
    Code:
    main () {int N;
    char Names [9] [15] = {"Zoidberg", "Fry", "Leela", "Profesor", "Bender", "Amy", "Hermes", "Washbucket", "Emperor Nikolai"};
    scanf ("%d", &N);
    printf ("%c", Names[N]);
    system ("PAUSE");
    }
    I have no idea how to scrable them, nothing I do works, so if you could, I would appreciate some pointers on how to do it. Thanks.
    If you are following the problem as given in both Futurama (yuk!) and Stargate (well, ok) you need to begin with only 1 swap. From there the problem is to get them back into their right places without swaping the same pair twice...

    There are already problems with your code...
    it's not main() ... it's... int main (void) and it returns an errorlevel when exiting... The minimum skeleton of a C program is...
    Code:
    int main (void)
      {
        // your code here
    
        return 0;
    }
    You've created int N ... this is not wrong, strictly speaking, but capital letters are generally reserved for constants as a matter of form that makes code easier to read.

    The printf() should be printf("%s", Names[n]); ... %c only prints a single character.

    To scramble them you're going to have to use an array of ints, since the index and value give you a means of tracking the original order, which a stings only solution lacks. You would be using the names only to print the values in the various slots... eg: printf("%s is now in %s body\n", Names[array[x]],Names[x]);
    Last edited by CommonTater; 12-02-2011 at 11:44 AM.

  15. #15
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Here's an example of the Fisher-Yates shuffle algorithm:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    void FYshuffle (int *ray, int len) {
            int i, tmp, x;
            for (i=len-1; i>1; i--) {
                    x = rand()%i; 
                    if (x==i) continue;
            // now swap
                    tmp = ray[i];
                    ray[i] = ray[x];
                    ray[x] = tmp;
            }
    }
    
    int main(void) {
         int ray[10] = {0,1,2,3,4,5,6,7,8,9}, i;
    
            srand(time(0));
            FYshuffle(ray,10);
            for (i=0;i<10;i++) printf("%d\n",ray[i]);
    
            return 0;
    }
    But you can't do that with this:
    Code:
    char Names [9] [15];
    However, you can do it with this:
    Code:
    char *Names[9];
    Which can be initialized the same way. You'd then need to modify the shuffle function to work with a char *ray[] (which means changing the first parameter and the type of the tmp variable).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Separating Axis Theorem
    By Astra in forum Game Programming
    Replies: 10
    Last Post: 07-29-2011, 03:27 PM
  2. Separating Axis Theorem
    By Kenki in forum Game Programming
    Replies: 20
    Last Post: 05-22-2005, 11:49 AM
  3. Pythagorans theorem
    By Dummies102 in forum C++ Programming
    Replies: 2
    Last Post: 02-20-2002, 01:46 PM
  4. Galois Theorem
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 01-06-2002, 06:20 PM
  5. David's CProgramming Theorem
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 08-14-2001, 12:29 AM

Tags for this Thread