# Futurama Theorem

Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last
• 11-30-2011
Ferreres93
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.
• 11-30-2011
CommonTater
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.
• 11-30-2011
Ferreres93
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.
• 11-30-2011
CommonTater
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.
• 11-30-2011
laserlight
What does it mean to compile the Futurama Theorem?
• 11-30-2011
Ferreres93
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);     }```
• 11-30-2011
laserlight
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.
• 11-30-2011
CommonTater
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;   }```
• 11-30-2011
CommonTater
Quote:

Originally Posted by laserlight
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...
• 12-02-2011
Ferreres93
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?
• 12-02-2011
MK27
You need to post code and describe your problem in terms of the code.
• 12-02-2011
Ferreres93
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.
• 12-02-2011
CommonTater
@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...
• 12-02-2011
CommonTater
Quote:

Originally Posted by Ferreres93
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]);
• 12-02-2011
MK27
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).
Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last