Like Tree3Likes

Futurama Theorem

This is a discussion on Futurama Theorem within the C Programming forums, part of the General Programming Boards category; It's hard to tell from your post whether you took reverse swaps into account... That is if guy 0 swaps ...

  1. #46
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    It's hard to tell from your post whether you took reverse swaps into account...

    That is if guy 0 swaps with guy 1 ... guy 1 cannot swap with guy 0.

    Love to see your code for that (PM if you wish).

  2. #47
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    @Ferreres93: Where are you with this? Do you want to use structs or parallel arrays or ??

  3. #48
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Just thinking out loud, this feels like a problem for a brute force recursive search. You'd be able to try all of the possible swaps, and at each step bail if you run into a case where you're repeating a swap to prune the search space (hopefully this is a heavy pruning). Each step along the way you see if everyone's back in their correct bodies - when you hit that you just return out of the recursive calls printing the moves used along the way.

    Something like
    Code:
    swap(this_source, this_dest, body array, swap scorecard)
    {
      if swap was already tried, return invalid
      swap this_source with this_dest, update records to show that this swap happened
      if everyone is where they should be, return valid (this is the end of the search)
      for each source 0..body array length-1
        for each dest 0..body array length - 1
        {
          if ((source != dest) && (swap(source, dest, ...) == valid))
          {
             print this swap (or push it on a result stack to reverse the order it is printed)
             return valid
          } 
        }
    }
    If this brute force search runs too slowly, you'll have to be smarter about how you explore the search space. Instead of iterating through all combinations of source and dest in order, you'll need a way to weight them as more or less likely to lead to a solution and try those first.

    This reminds me a bit of the 8/15/whatever-puzzle problem, except in this case you can swap any two elements instead of just ones around the spaces. Since that opens up the search space considerably, solutions to that problem may or may not transfer over, but at least it gives you an idea of where to start to look for ideas.

  4. #49
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    To follow up, I coded up my idea and it works. A few tweaks

    Since int swapping source and dest are symmetric, the inner loop can run from source+1..array_len-1. If source is 1, you've already tried all swaps with source = 0 ... no need to redo all of the dest=0 ones also.

    At the end of the swap function, undo the swap, remove the records showing that the swap happened, and return invalid.

    I used a linked list with nodes having source,dest pairs to encode which swaps have already been done in the current sequence. That makes it easy to undo (remove the last node added) and if you traverse this list after finding everyone is where they should be, it will be your list of moves.

Page 4 of 4 FirstFirst 1234
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, 04:27 PM
  2. Separating Axis Theorem
    By Kenki in forum Game Programming
    Replies: 20
    Last Post: 05-22-2005, 12:49 PM
  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, 01:29 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21