Thread: Futurama Theorem

  1. #31
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    I give up... Nobody can teach a student who doesn't listen.

  2. #32
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    Also, no student can learn from a master who wont listen to him.
    FYI, I managed to shuffle the minds just fine with a variation of the deck shuffle algorithm. Now I just need an algorithm to follow the theorem, which will most likely be the hardest part. Here's what I have so far if you wanna see what I did:
    Code:
    #include<stdio.h>
    #include<string.h>
    #include<time.h>
    #include<stdlib.h>
    
    
    #define RANDS 9
    
    
    int main (void) {
    int N, i;
    char Body [9] [15];
    
    
            //Input Names
    printf("Give me 9 Names\n");
        for (i = 0; i < 9; i++)
        {
        scanf ("%s", Body[i]);
        }
            //Scramble Array (Minds)
    
    
    int Mind[RANDS];  
        int item = 0;     
        int temp;         
        int idx = 0;      
        srand(time(NULL));
        
        for(idx = 0; idx < RANDS; idx++)
          Mind[idx] = idx + 1;
        
        // shuffle the array
        for (idx = RANDS - 1; idx > 0; idx--)
          { item = rand() % idx;
            temp = Mind[idx];
            Mind[idx] = Mind[item];
            Mind[item] = temp; }
        
        // shuffled array
        printf("\n\n");
        printf ("\t(Body = Mind)\n");
        for (idx = 0; idx < RANDS; idx++){
          printf("%s   %d = %d\n", Body[idx], idx+1, Mind[idx]);}
          
        system ("PAUSE");
        
            //Unscramble, step by step, the array
            
            //Return Names
        system ("PAUSE");
    }

  3. #33
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    There was a Stargate SG-1 episode like this exercise once. It was very well done too.

    So I assume we're left at the coming up with the algorithm part? How about just starting with the implest possible idea you have and see where that gets you.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #34
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    OK, I'm back from running errands, and late to the puzzle party, but please bear with me - some questions, if you don't mind.

    1) What episode of Stargate-SG1 was this on? I completely missed that one! (Season is even fine). I tried to look it up, but there are hundreds of episodes!

    2) I thought there were two heads (one pair) transplanted in the problem. So why the emphasis on the Shuffle algorithm?

    How many heads are on the wrong body?

    3) How many bodies are there, in total that we can use?

    Thanks for the update.

  5. #35
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    Okay, there are 9 bodies, ALL of them with the minds swapped, thus the enfasis in the shuffle. Once shuffled, you may add TWO unshuffled people to solve the equation. I've no idea about the SG episode, sorry.

  6. #36
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    So how are you doing with the shuffle? OK, or need some tips?

  7. #37
    Registered User
    Join Date
    Nov 2011
    Posts
    13
    I already worked out the random shuffle, it's all on the post 32. All I need now is a way to add those 2 un-swapped guys to the array (I've tried strcat, but I'm pretty sure it didn't work), and then find a way to apply a sorting algorithm that won't swap 2 bodies that've already been swapped.

  8. #38
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Perhaps you meant to use strcpy(destination, source), where destination and source, are the names of the char array or pointer to the strings.

    Pardon me, but why a sorting algorithm? I can see you'd need a sequence of swaps, but sorting? Sort what?

    The two new people can be bodies for holding onto brains, right?
    Last edited by Adak; 12-02-2011 at 08:04 PM.

  9. #39
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by iMalc View Post
    There was a Stargate SG-1 episode like this exercise once. It was very well done too.

    So I assume we're left at the coming up with the algorithm part? How about just starting with the implest possible idea you have and see where that gets you.
    Check message 13 ... I kind of set the stage for the puzzle solvers amongst us.

  10. #40
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Ferreres93 View Post
    Okay, there are 9 bodies, ALL of them with the minds swapped, thus the enfasis in the shuffle. Once shuffled, you may add TWO unshuffled people to solve the equation. I've no idea about the SG episode, sorry.
    In SG1 they started with a single swap... but the rule was you can only swap once... that is if a and b are swapped, you can't simply swap them back... The goal is to get all the minds back in the right bodies.

  11. #41
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Adak View Post
    1) What episode of Stargate-SG1 was this on? I completely missed that one! (Season is even fine). I tried to look it up, but there are hundreds of episodes!
    Season 2 episode 17 ... HERE

    It starts with an alien swapping with Daniel... and ends with them doing a bunch of swaps to get everyone back in the right body.

  12. #42
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    The Prisoner of Benda - Wikipedia, the free encyclopedia

    is not

    Quote Originally Posted by Ferreres93
    there are 9 bodies, ALL of them with the minds swapped, thus the enfasis in the shuffle.
    Sorry if I contributed to that mayhem

    Ferreres93, it is you that is going to pass or fail here, and there will be no bodies to switch, so make sure you understand what you are supposed to do and pay attention to the people who are here to help you!

    I love sci-fi but Stargate always looked too gimmicky so I never gave it a chance. Futurama, OTOH, was one of the best series of the past decade

    I'm off to watch "Metal Evolution" pt. 3, lol
    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

  13. #43
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a solution for 3 brains being switched, with two people we can use as "temporary holders". Very likely, it's not the most efficient way to do this.

    persons are number 1, 2, and 3 (4 and 5 for the temps). Brains are denoted by 11, 22, 33, 44 and 55.
    Code:
    Number  People in the Swap    Status
    ==========================================
    1)         1<-->2              1.22, 2.11
    2)         2<-->3              2.33, 3.11
    Now 4 and 5 have joined us, our status is:
    1.22, 2.33, 3.11, 4.44, 5.55
    
    3)         1<-->3              1.11, 3.22
    4)         2<-->5              2.55, 5.33
    5)         3<-->4              3.44, 4.22
    6)         2<-->4              2.22, 4.55
    7)         3<-->5              3.33, 5.44
    8)         4<-->5              4.44, 5.55
    Final status:
    1.11, 2.22, 3.33, 4.44, 5.55

    Of course, that's not for 9 people, and it's not a program, but it shows a pattern that could be used, I believe.

    Brute force, could do this but I believe it's unnecessary in this case.
    Last edited by Adak; 12-02-2011 at 10:58 PM.

  14. #44
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Another example, again 3 brains have been swapped, but this time with a different sequence. Persons 4 and 5, again serve as temporary hosts. Everyone has a brain that is 10x their person number + their person number: 1 is 11, 2 is 22, ...5 is 55.

    Code:
    
    Number  People in the Swap    Status
    ==========================================
    Starting status is:
    1.33, 2.11, 3.22, 4.44, 5.55
    
    Starting swaps to scramble were:
    1) 1 & 2, then 
    2) 1 & 3
    
    3) 1 & 4  1.44, 4.33   2 and 3 are unavailable, take the next person or host?
    4) 3 & 4  3.33, 4.22   3 is ok always take the swap that makes a match, if available
    5) 2 & 5  2.55, 5.11  
    6) 1 & 5  1.11, 5.44   1 is ok
    
    7) 2 & 4  2.22, 4.55   2 is ok
    8) 4 & 5  4.44, 5.55   4 and 5 are ok
    Hmmmm. Where'd I leave that deerstalking cap at?
    Last edited by Adak; 12-02-2011 at 11:46 PM.

  15. #45
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In very limited testing I have a program that works (initially with 3 brains having been swapped). When I get a chance, I'll up the brain number, and see how that goes.

    I used a struct for the brain swappers with their number and their matching brain number, so:

    guys[0].n is the zeroth guy's number, and guys[0].b is his brain number, and they are the same (until the swaps start).

    I used a 2D array "swapped[5][5]", to keep track and increment the "scorecard" of the swaps. Initially, all elements in it were set to zero. So if guys[0] had swapped brains with guys[1], then:

    Code:
    swapped[0][1]++; //and
    swapped[1][0]++;
    If you ever have a two in your scorecard of swaps, then it's an error. Without the scorecard of swaps, I'd have had a very difficult time doing this.

    Last screen:
    Attached Images Attached Images Futurama Theorem-futuramapuzzle-png 

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