Futurama Theorem

This is a discussion on Futurama Theorem within the C Programming forums, part of the General Programming Boards category; Recently, on my programming course my teacher has assigned us to write a program in C that compiles the Futurama ...

1. 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. 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. 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. 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. What does it mean to compile the Futurama Theorem?

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

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

10. 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. You need to post code and describe your problem in terms of the code.

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

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

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

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

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]);

15. 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).

Page 1 of 4 1234 Last