Difference between revisions of "Time Weave"

From DoctorWhen
(→‎Attachments)
(→‎Addressing Most Recent Comments)
 
(15 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
= The Pitch =
 
= The Pitch =
−
Dr. When is very excited to be doing his first test of his time machine using a live subject.
+
In an early tests of the prototype Dr When did not supply enough power to the Heisenberg Compensator, the part of the machine responsible for dampending timestream-altering ripple effects.
−
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!! 
+
As a result, when he returned to the present he found a world strangely altered in subtle ways.
  
−
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.
+
He needs your help to recreate the fabric of time, suppressing events that shouldn't happen and enabling connections that should happen.
  
−
Dr When should have studied his chaos theory: as everyone knows, when Chinese butterflies flap their wings, the world changes.
+
A correctly re-ordered timestream should provide a clue on the date of Dr When's next test and the correct amount of power to send to the HC.
−
 
 
−
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 =  
 
= The Puzzle =  
Line 17: Line 13:
 
Players get 10 strips and a board.
 
Players get 10 strips and a board.
  
−
5 strips are 'rows', 5 are 'columns'.  The strips are marked with 'paths'.   
+
5 strips are 'rows', 5 are 'columns'.  The strips are marked with 'paths'.  Places where the strips should cross also contain historical "facts".
  
 
The board is a 5x5 grid, possibly with some extra rows/columns for spacing, and an extra row/column on either side.
 
The board is a 5x5 grid, possibly with some extra rows/columns for spacing, and an extra row/column on either side.
Line 23: Line 19:
 
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.
 
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.
+
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.
 +
 
 +
 
 +
== Expectation ==
 +
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 right", 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 that on a correctly re-assembled grid, if you add the digits of the years of the 'facts' and map to letters using simple A = 1, B = 2, etc., you get the message:
 +
"five gigawatts by mid may"
 +
 
 +
== Addressing Most Recent Comments ==
 +
In the latest playtest, people got the general idea but they did not recognize that some facts were false, so they were left thinking that the only solution was brute force.
 +
 
 +
Solutions:
 +
 
 +
1. Make sure they get directions that talk about altered time stream and setting facts right.
 +
 
 +
2. Added one row of clearly false facts, all grisly deaths taken from Gashlycrumb Tinies.  Hopefully players will realize that these are false, and they conceptually belong together, so they will be well on their way to positioning some strips.  Additionally, the dates on these GT clues map to the corresponding GT letter (e.g. in 2000 someone is devoured by bears, 2+0+0+0 = 2 = B = Basil, devoured by bears), offering an extra clue on how to get final message.
 +
 
 +
= Attachments =
 +
* [[Media:Board.png]]
 +
* [[Media:Rows.PNG]]
 +
* [[Media:Cols.png]]
 +
 
 +
= Code =
 +
<code>
 +
#!python
 +
import random
 +
import sys
 +
import copy
 +
import Image
 +
import ImageDraw
 +
 
 +
"""
 +
Tester for strip puzzle.
 +
"""
 +
 
 +
CELL_SIZE = 160
 +
LINE_WIDTH = 10
 +
HASH_WIDTH = 2
 +
HASH_LENGTH = 20
 +
 
 +
 
 +
TrueFacts = [
 +
    ["2004",
 +
    "Summer Olympics in Athens"],
 +
    ["1800",
 +
    "Millard Fillmore born"],
 +
    ["1993",
 +
    "Ruth Bader Ginsberg",
 +
    "appointed to Supreme",
 +
    "Court"],
 +
    ["2003",
 +
    "Saddam Hussein captured",
 +
    "by American Troops"],
 +
    ["1989",
 +
    "San Francisco Bay area",
 +
    "earthquake measuring 7.1"],
 +
 
 +
    ["2005",
 +
    "Hurricane Katrina wreaks",
 +
    "catastrophic damage on ",
 +
    "the Gulf coast"],
 +
    ["1710",
 +
    "Emperor Higashiyama of",
 +
    "Japan dies"],
 +
    ["2005",
 +
    "Pope John Paul II Dies"],
 +
    ["100",
 +
    "Emperor Trajan and",
 +
    "Sextus Julius Frontinus",
 +
    "become Roman Consuls"],
 +
    ["1985",
 +
    "PLO terrorists hijack",
 +
    "Achille Lauro"],
 +
 
 +
    ["1000",
 +
    "Stephen I becomes King",
 +
    "of Hungary"],
 +
    ["1973",
 +
    "Spiro T. Agnew resigns",
 +
    "as Vice President"],
 +
    ["1883",
 +
    "LIFE magazine is founded"],
 +
    ["1954",
 +
    "Lord of the Flies is",
 +
    "published"],
 +
    ["1998",
 +
    "Former Chilean dictator",
 +
    "Augusto Pinochet",
 +
    "arrested in London"],
 +
 
 +
    ["2000",
 +
    "Vicente Fox Quesada",
 +
    "elected president of",
 +
    "Mexico"],
 +
    ["1978",
 +
    "John Paul I, 65, dies",
 +
    "unexpectedly after 34",
 +
    "days in office"],
 +
    ["1899",
 +
    "Felix Hoffmann patents",
 +
    "aspirin"],
 +
    ["1930",
 +
    "Grant Wood paints ",
 +
    "American Gothic."],
 +
    ["1620",
 +
    "Mysterious rain of",
 +
    "frogs in Weil der",
 +
    "Stadt"],
 +
   
 +
    ["2002",
 +
    "East Timor becomes a",
 +
    "new nation"],
 +
    ["1989",
 +
    "Exxon Valdez oil spill"],
 +
    ["1822",
 +
    "Coffee is no longer"
 +
    "banned in Sweden"],
 +
    ["1000",
 +
    "Olaf I of Norway killed",
 +
    "in battle"],
 +
    ["1977",
 +
    "South African activist",
 +
    "Steve Biko dies in ",
 +
    "police custody"]]
 +
 
 +
FalseFacts = [
 +
    ["2001",
 +
    "Shanghai wins the bid",
 +
    "to host the 2008 Summer",
 +
    "Olympics"],
 +
    ["1955",
 +
    "Alfred Hitchcock",
 +
    "Presents TV program",
 +
    "debuts on ABC-TV"],
 +
    ["500",
 +
    "Emperor Xuanwu becomes",
 +
    "sovereign of the Qing",
 +
    "Dynasty"],
 +
    ["1988",
 +
    "Hurricane Gladys",
 +
    "devastates Jamaica"],
 +
    ["1750",
 +
    "Jose III takes over the",
 +
    "throne of Portugal"],
 +
 
 +
    ["2000",
 +
    "Farrah Fawcett is",
 +
    "devoured by bears"],
 +
    ["1890",
 +
    "Horatio Alger, Jr.",
 +
    "is consumed by a fire"],
 +
    ["1970",
 +
    "Howard Hughes sinks in",
 +
    "a mire"],
 +
    ["1250",
 +
    "Erik Eriksson is done",
 +
    "in by a thug"],
 +
    ["1931",
 +
    "Thomas Edison dies of",
 +
    "ennui"],
 +
 
 +
    ["2007",
 +
    "Luciano Pavarotti dies",
 +
    "in a car accident"],
 +
    ["1969",
 +
    "The Soviet Union",
 +
    "launches Soyuz 2"],
 +
    ["1983",
 +
    "The Greek part of ",
 +
    "Cyprus declares ",
 +
    "independence"],
 +
    ["2005",
 +
    "The Kashmir earthquake",
 +
    "kills about 800 people"],
 +
    ["2002",
 +
    "Venus Williams defeats",
 +
    "Serena Williams in the",
 +
    "French Open"],
 +
 
 +
    ["1984",
 +
    "John Napier Turner",
 +
    "becomes Canada's 27th",
 +
    "Prime Minister"],
 +
    ["1855",
 +
    "The Sigma Chi",
 +
    "Fraternity is founded",
 +
    "at Harvard University"],
 +
    ["200",
 +
    "Empress Sakura sends",
 +
    "a Japanese fleet to",
 +
    "invade Korea"],
 +
    ["1010",
 +
    "Emperor Murasaki writes",
 +
    "The Tale of Genji in",
 +
    "Japanese"],
 +
    ["1831",
 +
    "The Hunchback of Notre",
 +
    "Dame is first published",
 +
    "by Moliere"],
 +
   
 +
    ["1919",
 +
    "The League of Nations",
 +
    "is founded in Berlin"],
 +
    ["2006",
 +
    "The FIFA World Cup",
 +
    "begins in France"],
 +
    ["1985",
 +
    "Rock Hudson dies of",
 +
    "throat cancer"],
 +
    ["1977",
 +
    "American Roy Sullivan",
 +
    "is struck by lightning",
 +
    "for the twelfth time"],
 +
    ["1000",
 +
    "Leif Ericson lands in",
 +
    "North America, calling",
 +
    "it Jotunland"]]
 +
 
 +
 
 +
SOLUTION = "five gigawatts by mid may"
 +
#          0....5....0....5....0....5
 +
 
 +
TURN_TYPES = [
 +
    '+',
 +
    '\\',
 +
    '/',
 +
    ]
 +
 
 +
FWD_TURNS = {
 +
    'E': 'N',
 +
    'S': 'W',
 +
    'W': 'S',
 +
    'N': 'E',
 +
    }
 +
 
 +
BACK_TURNS = {
 +
    'E': 'S',
 +
    'S': 'E',
 +
    'W': 'N',
 +
    'N': 'W',
 +
    }
 +
 
 +
TURNS = """
 +
+ \ \ + +
 +
\ \ + / /
 +
+ + \ / +
 +
\ + / \ \
 +
\ / \ \ +
 +
"""
 +
 
 +
VALUES = """
 +
0 1 1 0 1
 +
1 0 0 0 0
 +
0 1 1 0 1
 +
0 0 0 1 0
 +
1 1 1 0 1
 +
"""
 +
 
 +
def get_pattern_value(x, y):
 +
    pieces = VALUES.split()
 +
    return int(pieces[x + y * 5])
  
−
E.g. Larry Page met Sergei Brin at Stanford.
+
def get_turn_at(x, y, match):
 +
    pieces = TURNS.split()
 +
    val = pieces[x + y * 5]
 +
    if match:
 +
        return val
 +
    else:
 +
        while 1:
 +
            test = random_turn()
 +
            if test != val:
 +
                return test
 +
   
 +
def hash_location(loc):
 +
    return loc[0] * 10 + loc[1] * 100
  
−
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.
+
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, x, y, tp):
 +
        self.value = get_pattern_value(x, y)
 +
        if tp == 'c':
 +
            self.value = (self.value + 1) % 2
 +
        self.turn = get_turn_at(x, y, self.value)
 +
 
 +
class Board:
 +
    def __init__(self, board_size):
 +
        self.board_size = board_size
 +
        self.rows = []
 +
        self.cols = []
 +
 
 +
    def fill_in_good_board(self):
 +
        for x in xrange(self.board_size):
 +
            col = []
 +
            for y in xrange(self.board_size):
 +
                col.append(Cell(x, y, 'c'))
 +
            self.cols.append(col)
 +
 
 +
        for y in xrange(self.board_size):
 +
            row = []
 +
            for x in xrange(self.board_size):
 +
                row.append(Cell(x, y, 'r'))
 +
            self.rows.append(row)
 +
 
 +
    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:
 +
            return rcell.turn
 +
        return ccell.turn
 +
 
 +
    def get_col_text_lines(self, x, y):
 +
        ccell = self.get_col_cell(x, y)
 +
        if ccell.value:
 +
            return TrueFacts[x + y * 5]
 +
        return FalseFacts[x + y * 5]
 +
       
 +
    def get_row_text_lines(self, x, y):
 +
        rcell = self.get_row_cell(x, y)
 +
        if rcell.value:
 +
            return TrueFacts[x + y * 5]
 +
        return FalseFacts[x + y * 5]
 +
       
 +
       
 +
 
 +
    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 " % 1)
 +
            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 values_are_legit(self):
 +
        for x in xrange(self.board_size):
 +
            for y in xrange(self.board_size):
 +
                rcell = self.get_row_cell(x, y)
 +
                ccell = self.get_col_cell(x, y)
 +
                if rcell.value == ccell.value:
 +
                    return False
 +
        return True
 +
 
 +
 
 +
    def get_matching_solutions(self, solution):
 +
        retval = []
 +
        perms = make_perms(range(self.board_size))
 +
 
 +
        count = 0
 +
        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 not new_board.values_are_legit():
 +
                    continue
 +
 
 +
                new_board.assign_names_based_on_solution(solution)
 +
 
 +
                count += 1
 +
                print "%d legit boards." % count
 +
 
 +
                if new_board.has_same_solution(solution):
 +
                    retval.append(new_board)
 +
        return retval
  
−
== V1 ==
+
def draw_cell(cell_type, x, y, im, color="white", lines=None):
−
This was tested 3/17/11.
+
    draw = ImageDraw.Draw(im)
 +
    draw.rectangle((x, y, x + CELL_SIZE, y + CELL_SIZE), color)
  
−
=== Additional Tweaks ===
+
    # Hash marks in corners.
−
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.
+
    draw.rectangle((x, y, x + HASH_LENGTH, y + HASH_WIDTH), "grey")
 +
    draw.rectangle((x, y, x + HASH_WIDTH, y + HASH_LENGTH), "grey")
  
−
The board was generated at random by a program that could guarantee unique solutions.
+
    draw.rectangle((x + CELL_SIZE-HASH_LENGTH, y, x + CELL_SIZE, y + HASH_WIDTH), "grey")
 +
    draw.rectangle((x + CELL_SIZE-HASH_WIDTH, y, x + CELL_SIZE, y + HASH_LENGTH), "grey")
  
−
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.
+
    draw.rectangle((x, y + CELL_SIZE - HASH_WIDTH, x + HASH_LENGTH,
 +
                    y + CELL_SIZE), "grey")
 +
    draw.rectangle((x, y + CELL_SIZE - HASH_LENGTH, x + HASH_WIDTH,
 +
                    y + CELL_SIZE), "grey")
  
−
=== Playtest ===
+
    draw.rectangle((x + CELL_SIZE - HASH_LENGTH, y + CELL_SIZE - HASH_WIDTH,
−
Players were told that the lower number should end up on top, that's pretty much it.
+
                    x + CELL_SIZE, y + CELL_SIZE), "grey")
−
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.
+
    draw.rectangle((x + CELL_SIZE - HASH_WIDTH, y + CELL_SIZE - HASH_LENGTH,
 +
                    x + CELL_SIZE, y + CELL_SIZE), "grey")
  
−
They understood that the challenge was to figure out the order of the rows and columns (since over/under is deterministic given the numbers).
+
    # Und now the marks!
 +
    if (cell_type == '+'):
 +
        draw.rectangle((x + (CELL_SIZE - LINE_WIDTH)/2, y,
 +
                      x + (CELL_SIZE + LINE_WIDTH)/2, y + CELL_SIZE),
 +
                      "grey")
  
−
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.
+
        draw.rectangle((x, y + (CELL_SIZE - LINE_WIDTH)/2,
 +
                      x + (CELL_SIZE - 3 * LINE_WIDTH)/2,
 +
                        y + (CELL_SIZE + LINE_WIDTH)/2),
 +
                      "grey")
 +
                   
 +
        draw.rectangle((x + (CELL_SIZE + 3 * LINE_WIDTH)/2,
 +
                        y + (CELL_SIZE - LINE_WIDTH)/2,
 +
                      x + CELL_SIZE , y + (CELL_SIZE + LINE_WIDTH)/2),
 +
                      "grey")
 +
    elif (cell_type == ' '):
 +
        return
 +
    elif (cell_type == '/'):
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x - CELL_SIZE/2 - i, y - CELL_SIZE/2 - i,
 +
                      x + CELL_SIZE/2 + i, y + CELL_SIZE/2 + i), 0, 90, "grey")
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x - CELL_SIZE/2 + i, y - CELL_SIZE/2 + i,
 +
                      x + CELL_SIZE/2 - i, y + CELL_SIZE/2 - i), 0, 90, "grey")
 +
           
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x + CELL_SIZE - CELL_SIZE/2 - i, y + CELL_SIZE - CELL_SIZE/2 - i,
 +
                      x + CELL_SIZE + CELL_SIZE/2 + i, y + CELL_SIZE + CELL_SIZE/2 + i),
 +
                    180, 270, "grey")
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x + CELL_SIZE - CELL_SIZE/2 + i, y + CELL_SIZE - CELL_SIZE/2 + i,
 +
                      x + CELL_SIZE + CELL_SIZE/2 - i, y + CELL_SIZE + CELL_SIZE/2 - i),
 +
                    180, 270, "grey")
 +
    elif (cell_type == '\\'):
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x - CELL_SIZE/2 - i, y + CELL_SIZE- CELL_SIZE/2 - i,
 +
                      x + CELL_SIZE/2 + i, y + CELL_SIZE + CELL_SIZE/2 + i),
 +
                    270, 360, "grey")
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x - CELL_SIZE/2 + i, y + CELL_SIZE- CELL_SIZE/2 + i,
 +
                      x + CELL_SIZE/2 - i, y + CELL_SIZE + CELL_SIZE/2 - i),
 +
                    270, 360, "grey")
 +
           
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x + CELL_SIZE - CELL_SIZE/2 - i, y - CELL_SIZE/2 - i,
 +
                      x + CELL_SIZE + CELL_SIZE/2 + i, y + CELL_SIZE/2 + i),
 +
                    90, 180, "grey")
 +
        for i in xrange(LINE_WIDTH/2 + 1):
 +
            draw.arc((x + CELL_SIZE - CELL_SIZE/2 + i, y - CELL_SIZE/2 + i,
 +
                      x + CELL_SIZE + CELL_SIZE/2 - i, y + CELL_SIZE/2 - i),
 +
                    90, 180, "grey")
 +
    elif (cell_type == '|'):
 +
        draw.rectangle((x + (CELL_SIZE - LINE_WIDTH)/2, y,
 +
                      x + (CELL_SIZE + LINE_WIDTH)/2 , y + CELL_SIZE),
 +
                      "grey")
 +
    else:
 +
        draw.rectangle((x, y + (CELL_SIZE - LINE_WIDTH)/2,
 +
                      x + CELL_SIZE , y + (CELL_SIZE + LINE_WIDTH)/2),
 +
                      "grey")
  
−
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.
+
    # If text is not None, add it.
 +
    l_count = 0
 +
    if lines is not None:
 +
        for line in lines:
 +
            draw.text((x + 10, y + 10 + l_count * 20), line, "black")
 +
            l_count += 1
  
−
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 ==
+
def create_cols_image_file(board):
 +
    c_count = 0
 +
    image = Image.new("RGB", (5 * (CELL_SIZE + 5), CELL_SIZE * 9), "white")
  
−
=== Additional Tweaks ===
+
    for col in board.cols:
−
Remove the numbers.
+
        x = c_count * (CELL_SIZE + 5)
 +
        r_count = 0
 +
        for cell in col:
 +
            y = r_count * CELL_SIZE * 2
  
−
Instead, at each intersection write a very brief "headline".
+
            text_lines = board.get_col_text_lines(c_count, r_count)
 +
           
 +
            draw_cell(cell.turn, x, y, image, "white", text_lines)
 +
            if r_count != len(col) - 1:
 +
                draw_cell("|", x, y + CELL_SIZE, image, "white")
 +
            r_count += 1
 +
        c_count += 1
  
−
Half are accurate "Hurricane Katrina Pounds Lousiana Coast".
+
    image.show()
 +
    image.save("cols.bmp")
  
−
Half are close but not quite accurate: "Last known Passenger Pigeon dies in Cleveland Zoo" (It's actually Cincinnati).
+
def create_rows_image_file(board):
 +
    image = Image.new("RGB", (CELL_SIZE * 9, 5 * (CELL_SIZE + 5)), "white")
  
−
All players get is the flavor text at the top (or some variation thereof).
+
    r_count = 0
 +
    for row in board.rows:
 +
        y = r_count * (CELL_SIZE + 5)
 +
        c_count = 0
 +
        for cell in row:
 +
            x = c_count * CELL_SIZE * 2
  
−
A very few (3?) of the "wrong" facts are really profoundly wrong (e.g. "Martha Stewart is acquitted of using privileged investment information")
+
            text_lines = board.get_row_text_lines(c_count, r_count)
  
−
=== Expectation ===
+
            draw_cell(cell.turn, x, y, image, "white", text_lines)
−
'Ha' is the Chinese butterfly joke.
+
         
 +
            if c_count != len(row) - 1:
 +
                draw_cell("-", x + CELL_SIZE, y, image, "white")
 +
            c_count += 1
 +
        r_count += 1
  
−
Hopefully an 'ooh' when they see the tiles and paths (I really like playing with tiles/paths just to watch the lines move).
+
    image.show()
 +
    image.save("rows.bmp")
  
−
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.
+
def create_board_image_file(board):
 +
    image = Image.new("RGB", (CELL_SIZE * 11,
 +
                              CELL_SIZE * 11), "white")
 +
    for i in xrange(11):
 +
        for j in xrange(11):
 +
            x = i * CELL_SIZE
 +
            y = j * CELL_SIZE
  
−
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).
+
            if i == 0:
 +
                if j == 0:
 +
                    draw_cell("/", x, y, image, "white")
 +
                elif j == 10:
 +
                    draw_cell(" ", x, y, image, "white")
 +
                elif (j & 0x3) == 1:
 +
                    draw_cell("\\", x, y, image, "white")
 +
                elif (j & 0x3) == 3:
 +
                    draw_cell("/", x, y, image, "white")
 +
                else:
 +
                    draw_cell("|", x, y, image, "white")
 +
            elif j == 0:
 +
                if i == 10:
 +
                    draw_cell(" ", x, y, image, "white")
 +
                elif (i & 0x3) == 1:
 +
                    draw_cell("\\", x, y, image, "white")
 +
                elif (i & 0x3) == 3:
 +
                    draw_cell("/", x, y, image, "white")
 +
                else:
 +
                    draw_cell("-", x, y, image, "white")
 +
            elif i == 10 or j == 10:
 +
                draw_cell(" ", x, y, image, "white")                   
 +
            else:
 +
                color = "white"
 +
                draw_cell(" ", x, y, image, color)
 +
    image.show()
 +
    image.save("board.png")
 +
   
 +
                   
 +
count = 0
 +
while 1:
  
−
The first "reward" is you now have the reasonable search space of 12 possibilities to get the paths to work properly.
+
    # Make a random 5x5 board.
 +
    board = Board(5)
 +
    board.fill_in_good_board()
 +
   
 +
    assert(board.values_are_legit())
 +
    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
  
−
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:
+
    # Dump this board.
 +
    print "A board with non-trivial solution:"
  
−
Enchantment under the sea (25 characters)
+
    board.assign_names_based_on_solution(solution)
 +
   
 +
    # 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!"
  
−
And if you get the year of all the 'wrong' facts and do the same thing, you get
 
  
−
GeorgeMcFlyLorraineBaines (also 25 characters!)
+
        board.dump("row")
 +
        board.dump("col")
 +
        board.dump("all")
  
−
Which is your final answer: X met Y at Z.
+
        create_rows_image_file(board)
 +
        create_cols_image_file(board)
 +
        create_board_image_file(board)
  
−
(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).
+
        break
 +
   
 +
       
 +
   
  
−
= Attachments =
+
   
−
* [[Media:rows.jpg]]
+
   
−
* [[Media:columns.jpg]]
+
   
−
* [[Media:main_board.jpg]]
+
   
−
* [[Media:strip_puzzle.py]]
+
   
 +
</code>

Latest revision as of 20:29, 4 April 2011

The Pitch

In an early tests of the prototype Dr When did not supply enough power to the Heisenberg Compensator, the part of the machine responsible for dampending timestream-altering ripple effects.

As a result, when he returned to the present he found a world strangely altered in subtle ways.

He needs your help to recreate the fabric of time, suppressing events that shouldn't happen and enabling connections that should happen.

A correctly re-ordered timestream should provide a clue on the date of Dr When's next test and the correct amount of power to send to the HC.

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'. Places where the strips should cross also contain historical "facts".

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.

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.


Expectation

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 right", 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 that on a correctly re-assembled grid, if you add the digits of the years of the 'facts' and map to letters using simple A = 1, B = 2, etc., you get the message: "five gigawatts by mid may"

Addressing Most Recent Comments

In the latest playtest, people got the general idea but they did not recognize that some facts were false, so they were left thinking that the only solution was brute force.

Solutions:

1. Make sure they get directions that talk about altered time stream and setting facts right.

2. Added one row of clearly false facts, all grisly deaths taken from Gashlycrumb Tinies. Hopefully players will realize that these are false, and they conceptually belong together, so they will be well on their way to positioning some strips. Additionally, the dates on these GT clues map to the corresponding GT letter (e.g. in 2000 someone is devoured by bears, 2+0+0+0 = 2 = B = Basil, devoured by bears), offering an extra clue on how to get final message.

Attachments

* Media:Board.png
* Media:Rows.PNG
* Media:Cols.png

Code

  1. !python

import random import sys import copy import Image import ImageDraw

""" Tester for strip puzzle. """

CELL_SIZE = 160 LINE_WIDTH = 10 HASH_WIDTH = 2 HASH_LENGTH = 20


TrueFacts = [ 

   ["2004",
    "Summer Olympics in Athens"],
   ["1800",
    "Millard Fillmore born"],
   ["1993",
    "Ruth Bader Ginsberg",
    "appointed to Supreme",
    "Court"],
   ["2003",
    "Saddam Hussein captured",
    "by American Troops"],
   ["1989",
    "San Francisco Bay area",
    "earthquake measuring 7.1"],

   ["2005",
    "Hurricane Katrina wreaks",
    "catastrophic damage on ",
    "the Gulf coast"],
   ["1710",
    "Emperor Higashiyama of",
    "Japan dies"],
   ["2005",
    "Pope John Paul II Dies"],
   ["100",
    "Emperor Trajan and",
    "Sextus Julius Frontinus",
    "become Roman Consuls"],
   ["1985",
    "PLO terrorists hijack",
    "Achille Lauro"],

   ["1000",
    "Stephen I becomes King",
    "of Hungary"],
   ["1973",
    "Spiro T. Agnew resigns",
    "as Vice President"],
   ["1883",
    "LIFE magazine is founded"],
   ["1954",
    "Lord of the Flies is",
    "published"],
   ["1998",
    "Former Chilean dictator",
    "Augusto Pinochet",
    "arrested in London"],

   ["2000",
    "Vicente Fox Quesada",
    "elected president of",
    "Mexico"],
   ["1978",
    "John Paul I, 65, dies",
    "unexpectedly after 34",
    "days in office"],
   ["1899",
    "Felix Hoffmann patents",
    "aspirin"],
   ["1930",
    "Grant Wood paints ",
    "American Gothic."],
   ["1620",
    "Mysterious rain of",
    "frogs in Weil der",
    "Stadt"],
   
   ["2002",
    "East Timor becomes a",
    "new nation"],
   ["1989",
    "Exxon Valdez oil spill"],
   ["1822",
    "Coffee is no longer"
    "banned in Sweden"],
   ["1000",
    "Olaf I of Norway killed",
    "in battle"],
   ["1977",
    "South African activist",
    "Steve Biko dies in ",
    "police custody"]]

FalseFacts = [ 

   ["2001",
    "Shanghai wins the bid",
    "to host the 2008 Summer",
    "Olympics"],
   ["1955",
    "Alfred Hitchcock",
    "Presents TV program",
    "debuts on ABC-TV"],
   ["500",
    "Emperor Xuanwu becomes",
    "sovereign of the Qing",
    "Dynasty"],
   ["1988",
    "Hurricane Gladys",
    "devastates Jamaica"],
   ["1750",
    "Jose III takes over the",
    "throne of Portugal"],

   ["2000",
    "Farrah Fawcett is",
    "devoured by bears"],
   ["1890",
    "Horatio Alger, Jr.",
    "is consumed by a fire"],
   ["1970",
    "Howard Hughes sinks in",
    "a mire"],
   ["1250",
    "Erik Eriksson is done",
    "in by a thug"],
   ["1931",
    "Thomas Edison dies of",
    "ennui"],

   ["2007",
    "Luciano Pavarotti dies",
    "in a car accident"],
   ["1969",
    "The Soviet Union",
    "launches Soyuz 2"],
   ["1983",
    "The Greek part of ",
    "Cyprus declares ",
    "independence"],
   ["2005",
    "The Kashmir earthquake",
    "kills about 800 people"],
   ["2002",
    "Venus Williams defeats",
    "Serena Williams in the",
    "French Open"],

   ["1984",
    "John Napier Turner",
    "becomes Canada's 27th",
    "Prime Minister"],
   ["1855",
    "The Sigma Chi",
    "Fraternity is founded",
    "at Harvard University"],
   ["200",
    "Empress Sakura sends",
    "a Japanese fleet to",
    "invade Korea"],
   ["1010",
    "Emperor Murasaki writes",
    "The Tale of Genji in",
    "Japanese"],
   ["1831",
    "The Hunchback of Notre",
    "Dame is first published",
    "by Moliere"],
   
   ["1919",
    "The League of Nations",
    "is founded in Berlin"],
   ["2006",
    "The FIFA World Cup",
    "begins in France"],
   ["1985",
    "Rock Hudson dies of",
    "throat cancer"],
   ["1977",
    "American Roy Sullivan",
    "is struck by lightning",
    "for the twelfth time"],
   ["1000",
    "Leif Ericson lands in",
    "North America, calling",
    "it Jotunland"]]


SOLUTION = "five gigawatts by mid may"

  1. 0....5....0....5....0....5

TURN_TYPES = [ 

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

FWD_TURNS = { 

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

BACK_TURNS = { 

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

TURNS = """ + \ \ + + \ \ + / / + + \ / + \ + / \ \ \ / \ \ + """

VALUES = """ 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 0 1 """

def get_pattern_value(x, y): 

   pieces = VALUES.split()
   return int(pieces[x + y * 5])

def get_turn_at(x, y, match): 

   pieces = TURNS.split()
   val = pieces[x + y * 5]
   if match:
       return val
   else:
       while 1:
           test = random_turn()
           if test != val:
               return test

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, x, y, tp):
       self.value = get_pattern_value(x, y)
       if tp == 'c':
           self.value = (self.value + 1) % 2
       self.turn = get_turn_at(x, y, self.value)

class Board: 

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

   def fill_in_good_board(self):
       for x in xrange(self.board_size):
           col = []
           for y in xrange(self.board_size):
               col.append(Cell(x, y, 'c'))
           self.cols.append(col)

       for y in xrange(self.board_size):
           row = []
           for x in xrange(self.board_size):
               row.append(Cell(x, y, 'r'))
           self.rows.append(row)

   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:
           return rcell.turn
       return ccell.turn

   def get_col_text_lines(self, x, y):
       ccell = self.get_col_cell(x, y)
       if ccell.value:
           return TrueFacts[x + y * 5]
       return FalseFacts[x + y * 5]
       
   def get_row_text_lines(self, x, y):
       rcell = self.get_row_cell(x, y)
       if rcell.value:
           return TrueFacts[x + y * 5]
       return FalseFacts[x + y * 5]
       
       

   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 " % 1)
           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 values_are_legit(self):
       for x in xrange(self.board_size):
           for y in xrange(self.board_size):
               rcell = self.get_row_cell(x, y)
               ccell = self.get_col_cell(x, y)
               if rcell.value == ccell.value:
                   return False
       return True



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

       count = 0
       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 not new_board.values_are_legit():
                   continue

               new_board.assign_names_based_on_solution(solution)

               count += 1
               print "%d legit boards." % count

               if new_board.has_same_solution(solution):
                   retval.append(new_board)
       return retval

def draw_cell(cell_type, x, y, im, color="white", lines=None): 

   draw = ImageDraw.Draw(im)
   draw.rectangle((x, y, x + CELL_SIZE, y + CELL_SIZE), color)

   # Hash marks in corners.
   draw.rectangle((x, y, x + HASH_LENGTH, y + HASH_WIDTH), "grey")
   draw.rectangle((x, y, x + HASH_WIDTH, y + HASH_LENGTH), "grey")

   draw.rectangle((x + CELL_SIZE-HASH_LENGTH, y, x + CELL_SIZE, y + HASH_WIDTH), "grey")
   draw.rectangle((x + CELL_SIZE-HASH_WIDTH, y, x + CELL_SIZE, y + HASH_LENGTH), "grey")

   draw.rectangle((x, y + CELL_SIZE - HASH_WIDTH, x + HASH_LENGTH,
                   y + CELL_SIZE), "grey")
   draw.rectangle((x, y + CELL_SIZE - HASH_LENGTH, x + HASH_WIDTH,
                   y + CELL_SIZE), "grey")

   draw.rectangle((x + CELL_SIZE - HASH_LENGTH, y + CELL_SIZE - HASH_WIDTH,
                   x + CELL_SIZE, y + CELL_SIZE), "grey")
   draw.rectangle((x + CELL_SIZE - HASH_WIDTH, y + CELL_SIZE - HASH_LENGTH,
                   x + CELL_SIZE, y + CELL_SIZE), "grey")

   # Und now the marks!
   if (cell_type == '+'):
       draw.rectangle((x + (CELL_SIZE - LINE_WIDTH)/2, y,
                      x + (CELL_SIZE + LINE_WIDTH)/2, y + CELL_SIZE),
                      "grey")

       draw.rectangle((x, y + (CELL_SIZE - LINE_WIDTH)/2, 
                      x + (CELL_SIZE - 3 * LINE_WIDTH)/2,
                       y + (CELL_SIZE + LINE_WIDTH)/2),
                      "grey")
                   
       draw.rectangle((x + (CELL_SIZE + 3 * LINE_WIDTH)/2,
                       y + (CELL_SIZE - LINE_WIDTH)/2,
                      x + CELL_SIZE , y + (CELL_SIZE + LINE_WIDTH)/2),
                      "grey")
   elif (cell_type == ' '):
       return
   elif (cell_type == '/'):
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x - CELL_SIZE/2 - i, y - CELL_SIZE/2 - i,
                     x + CELL_SIZE/2 + i, y + CELL_SIZE/2 + i), 0, 90, "grey")
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x - CELL_SIZE/2 + i, y - CELL_SIZE/2 + i,
                     x + CELL_SIZE/2 - i, y + CELL_SIZE/2 - i), 0, 90, "grey")
           
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x + CELL_SIZE - CELL_SIZE/2 - i, y + CELL_SIZE - CELL_SIZE/2 - i,
                     x + CELL_SIZE + CELL_SIZE/2 + i, y + CELL_SIZE + CELL_SIZE/2 + i),
                    180, 270, "grey")
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x + CELL_SIZE - CELL_SIZE/2 + i, y + CELL_SIZE - CELL_SIZE/2 + i,
                     x + CELL_SIZE + CELL_SIZE/2 - i, y + CELL_SIZE + CELL_SIZE/2 - i),
                    180, 270, "grey")
   elif (cell_type == '\\'):
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x - CELL_SIZE/2 - i, y + CELL_SIZE- CELL_SIZE/2 - i,
                     x + CELL_SIZE/2 + i, y + CELL_SIZE + CELL_SIZE/2 + i),
                    270, 360, "grey")
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x - CELL_SIZE/2 + i, y + CELL_SIZE- CELL_SIZE/2 + i,
                     x + CELL_SIZE/2 - i, y + CELL_SIZE + CELL_SIZE/2 - i),
                    270, 360, "grey")
           
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x + CELL_SIZE - CELL_SIZE/2 - i, y - CELL_SIZE/2 - i,
                     x + CELL_SIZE + CELL_SIZE/2 + i, y + CELL_SIZE/2 + i),
                    90, 180, "grey")
       for i in xrange(LINE_WIDTH/2 + 1):
           draw.arc((x + CELL_SIZE - CELL_SIZE/2 + i, y - CELL_SIZE/2 + i,
                     x + CELL_SIZE + CELL_SIZE/2 - i, y + CELL_SIZE/2 - i),
                    90, 180, "grey")
   elif (cell_type == '|'):
       draw.rectangle((x + (CELL_SIZE - LINE_WIDTH)/2, y,
                      x + (CELL_SIZE + LINE_WIDTH)/2 , y + CELL_SIZE),
                      "grey")
   else:
       draw.rectangle((x, y + (CELL_SIZE - LINE_WIDTH)/2,
                      x + CELL_SIZE , y + (CELL_SIZE + LINE_WIDTH)/2),
                      "grey")

   # If text is not None, add it.
   l_count = 0
   if lines is not None:
       for line in lines:
           draw.text((x + 10, y + 10 + l_count * 20), line, "black")
           l_count += 1


def create_cols_image_file(board): 

   c_count = 0
   image = Image.new("RGB", (5 * (CELL_SIZE + 5), CELL_SIZE * 9), "white")

   for col in board.cols:
       x = c_count * (CELL_SIZE + 5)
       r_count = 0
       for cell in col:
           y = r_count * CELL_SIZE * 2

           text_lines = board.get_col_text_lines(c_count, r_count)
           
           draw_cell(cell.turn, x, y, image, "white", text_lines)
           if r_count != len(col) - 1:
               draw_cell("|", x, y + CELL_SIZE, image, "white")
           r_count += 1
       c_count += 1

   image.show()
   image.save("cols.bmp")

def create_rows_image_file(board): 

   image = Image.new("RGB", (CELL_SIZE * 9, 5 * (CELL_SIZE + 5)), "white")

   r_count = 0
   for row in board.rows:
       y = r_count * (CELL_SIZE + 5)
       c_count = 0
       for cell in row:
           x = c_count * CELL_SIZE * 2

           text_lines = board.get_row_text_lines(c_count, r_count)

           draw_cell(cell.turn, x, y, image, "white", text_lines)
          
           if c_count != len(row) - 1:
               draw_cell("-", x + CELL_SIZE, y, image, "white")
           c_count += 1
       r_count += 1

   image.show()
   image.save("rows.bmp")

def create_board_image_file(board): 

   image = Image.new("RGB", (CELL_SIZE * 11,
                             CELL_SIZE * 11), "white")
   for i in xrange(11):
       for j in xrange(11):
           x = i * CELL_SIZE
           y = j * CELL_SIZE

           if i == 0:
               if j == 0:
                   draw_cell("/", x, y, image, "white")
               elif j == 10:
                   draw_cell(" ", x, y, image, "white")
               elif (j & 0x3) == 1:
                   draw_cell("\\", x, y, image, "white")
               elif (j & 0x3) == 3:
                   draw_cell("/", x, y, image, "white")
               else:
                   draw_cell("|", x, y, image, "white")
           elif j == 0:
               if i == 10:
                   draw_cell(" ", x, y, image, "white")
               elif (i & 0x3) == 1:
                   draw_cell("\\", x, y, image, "white")
               elif (i & 0x3) == 3:
                   draw_cell("/", x, y, image, "white")
               else:
                   draw_cell("-", x, y, image, "white")
           elif i == 10 or j == 10:
               draw_cell(" ", x, y, image, "white")                    
           else:
               color = "white"
               draw_cell(" ", x, y, image, color)
   image.show()
   image.save("board.png")

count = 0 while 1: 

   # Make a random 5x5 board.
   board = Board(5)
   board.fill_in_good_board()
   
   assert(board.values_are_legit())
   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)
   
   # 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!"



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

       create_rows_image_file(board)
       create_cols_image_file(board)
       create_board_image_file(board)

       break




Retrieved from "http://doctorwhen.com/kiwi/index.php?title=Time_Weave&oldid=2215"