Time Weave

The Pitch

Dr. When is very excited to be doing his first test of his time machine using a live subject. He has selected a particularly attractive female butterfly as a test subject, as Buffy has always been partial to butterflies. And in an effort to avoid any major disruptions in populated areas, should the experiement go awry, he has elected to send the butterfly to a meadow deep in rural China in the 1850's.

And here goes.... the butterfly is gone... and now she is back! Success!!

But, oh dear, we are noticing some serious side effects. The sudden appearance of an attractive female butterfly cause quite a stir among the local Chinese male butterflies, who all began flapping their wings enthusiastically during her brief appearance.

Dr When should have studied his chaos theory: as everyone knows, when Chinese butterflies flap their wings, the world changes.

We need your help to reweave the fabric of time, ordering the threads of destiny so that 5 famous meetings will take happen in the right places. If you complete the task correctly, you should find a sixth couple and their destined meeting place.

The Puzzle

General Idea

(see attached bitmaps for sample pieces) Players get 10 strips and a board.

5 strips are 'rows', 5 are 'columns'. The strips are marked with 'paths'.

The board is a 5x5 grid, possibly with some extra rows/columns for spacing, and an extra row/column on either side.

The top and left of the grid contain cells with the names of famous people (5 top, 5 left). The people can be paired up into famous 'teams' or 'meetings': person X met person Y.

Furthermore, on each row strip, in some particular location on the strip, there is a location Z, giving the meeting place of one of the famous meetings.

E.g. Larry Page met Sergei Brin at Stanford.

The puzzle is to assemble the strips, weaving them over and under each other, so that for each ((X, Y) met at Z), there is a path from X to Y passing through Z.

V1

This was tested 3/17/11.

Additional Tweaks

For each strip, the each location where it would cross another strip was marked with a number. The directions specify that for all intersections, the lower number must be on top.

The board was generated at random by a program that could guarantee unique solutions.

The correct solution contained an encoded message (A=1, B=2, etc): "Enchantment under the sea", which is the name of the dance where George McFly and Lorraine Baines were destined to meet in Back to the Future.

Playtest

Players were told that the lower number should end up on top, that's pretty much it. Players pretty quickly got the gist (connect famous couples), used the internet to quickly and correctly pair up the couples (some were obvious, some needed internet), and quickly assessed that some strips were rows and some were columns.

They understood that the challenge was to figure out the order of the rows and columns (since over/under is deterministic given the numbers).

There were some attempts to come up with a methodology for solving other than brute force. There was a bit of discussion around eliminating choices right at the top/left edges, but even that proved inconclusive since you don't really know if something will be covered up, and if so by what.

It was agreed on that the only real solution was brute force, which is acceptable if you are going to write code but not otherwise.

It was agreed on that the secret message was interesting, and a pleasant 'reward' for the hard work of doing the puzzle, but it would be missed by most people unless there were some specific hint to look for it.

V2

Additional Tweaks

Remove the numbers.

Instead, at each intersection write a very brief "headline".

Half are accurate "Hurricane Katrina Pounds Lousiana Coast".

Half are close but not quite accurate: "Last known Passenger Pigeon dies in Cleveland Zoo" (It's actually Cincinnati).

All players get is the flavor text at the top (or some variation thereof).

A very few (3?) of the "wrong" facts are really profoundly wrong (e.g. "Martha Stewart is acquitted of using privileged investment information")

Expectation

'Ha' is the Chinese butterfly joke.

Hopefully an 'ooh' when they see the tiles and paths (I really like playing with tiles/paths just to watch the lines move).

The first "Aha" is that some headlines are wrong (hopefully triggered by the few that are really wrong). This leads to an examination of all the facts, identifying which are right and which are wrong.

The second "Aha" is that since the task is to "put history write", all 'wrong' facts should be covered by a 'right' fact. This would profoundly limit the permutations of rows columns. I would design it so that, within that restriction, all rows but 2 are locked down (2 choices), and all columns but 3 (6 choices).

The first "reward" is you now have the reasonable search space of 12 possibilities to get the paths to work properly.

The second reward is if you get the year of all the correct facts and use the last 2 digits as code (01 = A, 02 = B, etc.) you get the message:

Enchantment under the sea (25 characters)

And if you get the year of all the 'wrong' facts and do the same thing, you get

GeorgeMcFlyLorraineBaines (also 25 characters!)

Which is your final answer: X met Y at Z.

(We would need to make sure that the 'wrong' facts are clearly recognizable facts with one significant detail changed, so that even though they are wrong they can still be accurately dated).

Attachments

• Media:rows.jpg
• Media:columns.jpg
• Media:main_board.jpg

Code

I wanted to do this as an attachment but I can't figure out how and I am tired.

1. !python

import random import sys import copy

""" Tester for strip puzzle. """

TURN_TYPES = [

   '+',
   '\\',
   '/',
   ]

FWD_TURNS = {

   'E': 'N',
   'S': 'W',
   'W': 'S',
   'N': 'E',
   }

BACK_TURNS = {

   'E': 'S',
   'S': 'E',
   'W': 'N',
   'N': 'W',
   }

def hash_location(loc):

   return loc[0] * 10 + loc[1] * 100

def loc_string(loc):

   return "(" + str(loc[0]) + ", " + str(loc[1]) + ")"

def nth_letter(letters, index):

   letter = letters[index]
   if letter == ' ':
       return 0
   return ord(letter) - ord('a') + 1

def random_turn():

   index = random.randrange(0, 3)
   return TURN_TYPES[index]

def make_perms(array):

   if len(array) == 1:
       return [array]
   
   retval = []
   for v in array:
       cp = copy.deepcopy(array)
       cp.remove(v)
       arr = [v]
       perms = make_perms(cp)
       for perm in perms:
           perm.append(v)
           retval.append(perm)

   return retval

class Solution:

   def __init__(self):
       self.walks = []

   def get_min_walk_length(self):
       retval = 5000
       for walk in self.walks:
           if len(walk) < retval:
               retval = len(walk)
       return retval

   def has_similar_walk(self, test_walk):
       for walk in self.walks:
           if (walk[0] == test_walk[0] and
               walk[-1] == test_walk[-1]):
               return True
       return False
           

class Cell:

   def __init__(self):
       self.turn = random_turn()
       self.value = 0

class Board:

   def __init__(self, board_size):
       self.board_size = board_size
       self.rows = []
       self.cols = []

   def assign_names_based_on_solution(self, solution):
       names = ["A", "B", "C", "D", "E", "F"]
       self.names_map = {}
       name_index = 0
       for walk in solution.walks:
           if self.names_map.has_key(walk[0]):
               continue
           self.names_map[walk[0]] = names[name_index] 
           self.names_map[walk[-1]] = names[name_index] 
           name_index += 1 

   def generate_random_content(self, letters):
       for x in xrange(self.board_size):
           col = []
           for y in xrange(self.board_size):
               col.append(Cell())
           self.cols.append(col)
       for y in xrange(self.board_size):
           row = []
           for x in xrange(self.board_size):
               while 1:
                   col_cell = self.get_col_cell(x, y)
                   new_cell = Cell()
                   if new_cell.turn != col_cell.turn:
                       row.append(new_cell)
                       break
           self.rows.append(row)

       for i in xrange(len(letters)):
           x = i % self.board_size
           y = i / self.board_size
           value = 0
           if letters[i] != ' ':
               value = 1 + ord(letters[i]) - ord('a')
           other_value = random.randrange(value+1, 51)

           use_col = random.randrange(0, 2)
           col_cell = self.get_col_cell(x, y)
           row_cell = self.get_row_cell(x, y)
           if use_col:
               col_cell.value = value
               row_cell.value = other_value
           else:
               col_cell.value = other_value
               row_cell.value = value

   def get_col_cell(self, x, y):
       return self.cols[x][y]

   def get_row_cell(self, x, y):
       return self.rows[y][x]
   
   def get_turn(self, x, y):
       rcell = self.get_row_cell(x, y)
       ccell = self.get_col_cell(x, y)
       if rcell.value < ccell.value:
           return rcell.turn
       return ccell.turn

   def get_value(self, x, y):
       rcell = self.get_row_cell(x, y)
       ccell = self.get_col_cell(x, y)
       if rcell.value < ccell.value:
           return rcell.value
       return ccell.value

   def solve(self):
       solution = Solution()
       for i in xrange(self.board_size):
           start = (-1, i)
           direction = 'E'
           solution.walks.append(self.generate_walk([start], direction))
           
           start = (i, -1)
           direction = 'S'
           solution.walks.append(self.generate_walk([start], direction))
       return solution

   def generate_walk(self, current_walk, direction):
       previous_loc = current_walk[-1]
       
       new_location = self.move_in_direction(previous_loc, direction)
       if (new_location[0] == self.board_size or new_location[1] == self.board_size):
           (new_location, direction) = self.do_end_of_row_flip(new_location, direction)

       current_walk.append(new_location)

       if new_location[0] == -1 or new_location[1] == -1:
           return current_walk

       new_direction = self.do_board_turn(new_location, direction)
       return self.generate_walk(current_walk, new_direction)

   def move_in_direction(self, location, direction):
       if direction == 'E':
           return (location[0] + 1, location[1])
       if direction == 'W':
           return (location[0] - 1, location[1])
       if direction == 'S':
           return (location[0], location[1] + 1)
       if direction == 'N':
           return (location[0], location[1] - 1)
       assert(False)

   def do_end_of_row_flip(self, location, direction):
       # Should only happen moving south or east.
       assert(direction == 'S' or direction == 'E')

       new_location = location
       new_direction = None
           
       index = 0
       if direction == 'E':
           index = 1

       val = location[index]

       if (val & 0x1) == 0:
           new_val = val + 1
       else:
           new_val = val -1

       if (new_val == self.board_size):
           if direction == 'E':
               new_direction = 'N'
           else:
               new_direction = 'W'
           return ((self.board_size-1, self.board_size-1), new_direction)

       if index == 0:
           new_location = (new_val, new_location[1] - 1)
       else:
           new_location = (new_location[0] - 1, new_val)

       if direction == 'E':
           new_direction = 'W'
       else:
           new_direction = 'N'
       return (new_location, new_direction)
                   
   def do_board_turn(self, location, direction):
       turn = self.get_turn(location[0], location[1])

       if turn == '+':
           return direction
       if turn == '/':
           return FWD_TURNS[direction]
       return BACK_TURNS[direction] 

   def dump(self, dump_type):
       sys.stdout.write( "\n")
       sys.stdout.write( dump_type + ":\n")
       for y in xrange(self.board_size + 2):
           y = y - 1
           for x in xrange(self.board_size + 2):
               x = x - 1

               if x < 0:
                   if y < 0 or y == self.board_size:
                       sys.stdout.write("    ")
                   else:
                       sys.stdout.write(self.names_map[(x, y)] + "   ")
               elif y < 0:
                   if x == self.board_size:
                       sys.stdout.write("    ")
                   else:
                       sys.stdout.write(self.names_map[(x, y)] + "   ")
               elif x == self.board_size:
                   if (y & 0x1) == 0:
                       sys.stdout.write("\\" + "   ")
                   else:
                       sys.stdout.write("/" + "   ")
               elif y == self.board_size:
                   if (x & 0x1) == 0:
                       sys.stdout.write("\\" + "   ")
                   else:
                       sys.stdout.write("/" + "   ")
               else:
                   if dump_type == "row":
                       sys.stdout.write(self.get_row_cell(x, y).turn)
                       sys.stdout.write("%02d " % self.get_row_cell(x, y).value)
                   elif dump_type == "col":
                       sys.stdout.write(self.get_col_cell(x, y).turn)
                       sys.stdout.write("%02d " % self.get_col_cell(x, y).value)
                   else:
                       sys.stdout.write(self.get_turn(x, y))
                       sys.stdout.write("%02d " % self.get_value(x, y))
           sys.stdout.write("\n")

   def permute_board(self, perm1, perm2):
       new_board = Board(self.board_size)
       for i in perm1:
           new_board.cols.append(self.cols[i])
       for i in perm2:
           new_board.rows.append(self.rows[i])
       return new_board

   def has_same_solution(self, solution):
       for i in xrange(self.board_size):
           start = (-1, i)
           direction = 'E'
           walk = self.generate_walk([start], direction)

           if not solution.has_similar_walk(walk):
               return False
           
           start = (i, -1)
           direction = 'S'

           if not solution.has_similar_walk(walk):
               return False

       return True

   def get_matching_solutions(self, solution):
       retval = []
       perms = make_perms(range(self.board_size))

       for perm1 in perms:
           for perm2 in perms:
               # Don't worry about where perm1 = perm2 = identity.
               if (perm1 == range(self.board_size) and
                   perm2 == range(self.board_size)):
                   continue
               new_board = self.permute_board(perm1, perm2)
               if new_board.has_same_solution(solution):
                   new_board.assign_names_based_on_solution(solution)
                   retval.append(new_board)
       return retval
               

count = 0 while 1:

   # Make a random 5x5 board.
   board = Board(5)
   board.generate_random_content('enchantment under the sea')
   
   solution = board.solve()
   # If the smallest walk from A to B is too short, bail, make a new board.
   if solution.get_min_walk_length() < 8:
       continue

   # Dump this board.
   print "A board with non-trivial solution:"

   board.assign_names_based_on_solution(solution)
   
   board.dump("row")
   board.dump("col")
   board.dump("all")

   # Are there any other permutations of rows that give the same pairs?
   matching_solutions = board.get_matching_solutions(solution)
   if len(matching_solutions) > 0:
       print "  Has " + str(len(matching_solutions)) + " matching solutions."
       print "  An example: "
       matching_solutions[0].dump("row")
       matching_solutions[0].dump("col")
       matching_solutions[0].dump("all")
       count += 1
       if count >= 200:
           print "I quit!"
           break
   else:
       print "Winner!"
       break