Solution to the puzzle Cat Walk.
Cat Walk is one of the interesting puzzles of the Melbourne University Puzzle Hunt 2012 competition. This task was part of the second act of the game and was preceded by a short narrative that continued the plot. In accordance with it you receive the parcel from your strange companion: a small flash drive is wrapped inside what appears to be a torn page from a children’s puzzle book. You stare long and hard at the puzzle before asking your companion if you had the right answer. He looks back in amazement, quickly plugs the USB drive into his laptop and then happily reports: “This is wonderful! You’ve figured out the password - this is everything that we needed...” As it turned out, the flash drive contained extremely important information, and the solution to the “children's puzzle” was the password to obtain it…
The puzzle itself was below. It was a rectangular maze with colored gates between its parts: gray, red, blue and green. At the bottom of the maze, near the two entrances to it, sat Simon's Cat, who showed with a gesture that he was hungry. The cat's food was at the opposite side of the maze, to which 7 colored exits led.
The first step in solving the puzzle was to determine the number of columns in the maze: there were 26, which corresponds to the number of letters in the English alphabet. Thus, each column could be assigned a letter corresponding to it by number. Then you should pay attention to the colors of the gates inside the maze. You could try to go through the maze using gates of only one color. This was possible to do only for one of the colors - for gray - and only in a single way (if you never move along the path already taken).
A message could be extracted from this passage. To do this, whenever the path ran through a vertical gate, a letter corresponding to the column number for this gate had to be added to the message. The result was REDBLUETHENGREENPATH or RED, BLUE THEN GREEN PATH. Thus, the hint suggested going through the maze one more time, but now alternating the gates of red, blue and green. Again there was only one way to do this.
After successful completion you could receive another message in the same way. To do this, whenever the path ran through a vertical gate, the message had to be supplemented with the corresponding letter. The result was BLACKANDWHITECATFOOT or BLACK AND WHITE CAT FOOT. This strange phrase is a literal translation of the Latin term that refers to the animal species Giant panda (Ailuropoda melanoleuca). Thus, the answer to the task was GIANT PANDA.
Some additional information about the puzzle could be found in the notes for it. There were 3 common guesses given by players: GIANT PANDA (77 times), PANDA (19 times) and BLACK AND WHITE CAT FOOT (11 times). The Background section describes how the task was created.
“This puzzle emerged from a straightforward concept of a maze spelling an answer phrase via either absolute or relative displacements of its solution path. It was later extended to allow for a two-stage process that was intended to be more fun to solve (and which was intentionally made more difficult via lots of long, dead-end branchings in the Red-Blue-Green gateways) but presented no greater difficulty to construct due to the mutual exclusivity of the colouring.
Various second stage answer phrase were floated (i.e. EATS SHOOTS AND LEAVES, SPECIFICALLY PO NOT SHIFU, BEAR APPEARING ON WWF LOGO, etc) in an attempt to differentiate the answer GIANT PANDA from just PANDA [the answer GIANT PANDA was selected in advance for that year's meta-puzzle], though BLACK AND WHITE CAT FOOT was ultimately chosen to coincide with the prevalence of colours in the maze.”
An interesting challenge for this puzzle is to write a program that could automatically find both paths in the maze and extract messages from them. Let's try to write such a program using Python.
Let's start by creating a representation of the maze. The maze is divided into 20 rows and 26 columns by horizontal and vertical lines. To make search in the maze more convenient we will add one cell after each exit. These cells can be considered as an incomplete twenty-first row. Since we will be building the maze row by row, it may be convenient to designate "imaginary" cells that are inside the rectangular grid, but are not part of the maze. Thus, we will add a twenty-first row to the maze, some of the cells of which will be “imaginary”.
# number of columns in the maze
num_cols = 26
# number of rows in the maze with one additional row for searching
num_rows = 21
To represent the maze we will use a dictionary. Its keys will be tuples of two numbers denoting cells, and its values will be dictionaries. Their keys will be strings denoting possible movements for a given cell ('up', 'down', 'right', 'left'). If the movement is carried out through a colored gate, then the value will be a string denoting the color ('blue', 'red', 'green', 'gray'). Otherwise, the value will be None. Thus, the lower-left cell of the maze will be represented in the dictionary as (0,0): {'up': 'blue', 'right': None}.
Next, you need to set the input data that will be used to build the maze.
Let's define the "imaginary" cells, which are all in row 21, using a tuple.
# cells inside rectangular grid that are not part of the maze
imaginary_cells = ((0,20),(1,20),(2,20),(3,20),
(5,20),(6,20),
(8,20),(9,20),(10,20),
(12,20),(13,20),(14,20),(15,20),(16,20),
(18,20),
(20,20),
(22,20),(23,20),
(25,20))
The vast majority of maze cells have horizontal connections with neighboring cells. On the other hand, most cells in the maze do not have vertical connections with neighboring cells, and all vertical connections are colored gates. This can be used to simplify the construction of the maze: it will be enough to specify only the cells that have horizontal borders and the cells that have colored gates.
We will represent cells with horizontal borders using 3 tuples. The first tuple will contain cells on the left edge of the maze. The second tuple will contain cells on the right edge of the maze. The third tuple will contain cells that have a border to the right from the neighboring cell.
# cells on the left edge of the maze
cells_on_the_left_edge = ((0,0),
(0,1),
(0,2),
(0,3),
(0,4),
(0,5),
(0,6),
(0,7),
(0,8),
(0,9),
(0,10),
(0,11),
(0,12),
(0,13),
(0,14),
(0,15),
(0,16),
(0,17),
(0,18),
(0,19),
(4,20),(7,20),(11,20),(17,20),(19,20),(21,20),(24,20))
# cells on the right edge of the maze
cells_on_the_right_edge = ((25,0),
(25,1),
(25,2),
(25,3),
(25,4),
(25,5),
(25,6),
(25,7),
(25,8),
(25,9),
(25,10),
(25,11),
(25,12),
(25,13),
(25,14),
(25,15),
(25,16),
(25,17),
(25,18),
(25,19),
(4,20),(7,20),(11,20),(17,20),(19,20),(21,20),(24,20))
# cells that have a border with another cell on the right side
cells_with_right_border_inside_maze = ((12,0),
(13,2),
(9,3),(18,3),
(14,4),(22,4),
(20,6),
(16,10),
(20,12),
(17,13),
(7,14),
(15,17),
(19,18),
(5,19),(19,19))
To represent cells with coloured gates we will use dictionaries, whose keys will be strings denoting colors ('blue', 'red', 'green', 'gray'), and whose values will be tuples of cells. The first dictionary will contain cells with a coloured gate on the right. The second dictionary will contain cells with a coloured gate on the top.
# cells with coloured gate on the right side
cells_with_right_gate_by_colours = {'blue':((2,1),(21,1),
(4,5),
(21,15)),
'red':((1,2),
(1,6),
(4,8),
(12,9),
(4,11),(15,11),
(15,15),
(7,16)),
'green':((21,9),
(2,10),
(1,12),
(20,14),
(3,15),
(17,16),
(21,17)),
'gray':((9,13),)}
# cells with coloured gate on the upper side
cells_with_upper_gate_by_colours = {'blue':((0,0),(24,0),
(15,1),
(0,2),(23,2),
(8,3),
(14,5),(21,5),
(13,6),
(3,8),(9,8),(22,8),
(2,9),(7,9),(17,9),
(0,11),(19,11),
(18,12),
(5,13),(8,13),
(0,14),(10,14),
(6,15),(19,15),(25,15),
(5,16),(16,16),(19,16),
(11,17),(18,17),(24,17),
(8,18),(25,18),
(4,19),(19,19),(21,19)),
'red':((1,0),(12,0),
(20,1),
(7,2),
(10,4),(23,4),
(1,7),
(18,8),
(11,10),
(8,11),
(14,12),
(2,13),(13,13),(19,13),
(24,14),
(3,15),(20,15),
(20,16),
(4,17),(20,17),
(14,18),(23,18),
(17,19),(24,19)),
'green':((6,0),(19,0),
(1,1),(11,1),(25,1),
(18,2),
(2,3),(25,3),
(14,4),
(0,5),(24,5),
(7,6),(22,6),
(3,7),(14,7),
(1,9),
(8,10),(20,10),
(4,12),
(1,14),(18,14),
(1,15),(4,15),(21,15),
(21,16),(23,16),
(14,17),
(2,18),(20,18),
(11,19)),
'gray':((17,0),(23,0),
(4,1),(24,1),
(3,2),(14,2),(19,2),
(1,3),(15,3),(20,3),(24,3),
(4,4),(11,4),
(1,5),(20,5),(25,5),
(4,6),
(0,7),(19,7),
(7,8),(14,8),(24,8),
(0,9),(4,9),(18,9),
(2,10),(13,10),(24,10),
(1,11),(6,11),(22,11),
(17,12),(23,12),
(4,13),(11,13),(21,13),
(2,14),(4,14),(21,14),
(0,15),(13,15),(18,15),
(15,16),(17,16),(24,16),
(0,17),(21,17),
(4,18),(19,18),(22,18),
(7,19))}
We can now look at the generate_maze function, which uses all of the above inputs to create a representation of the maze.
def generate_maze(num_cols, num_rows, imaginary_cells,
cells_on_the_left_edge, cells_on_the_right_edge,
cells_with_right_border_inside_maze,
cells_with_right_gate_by_colours, cells_with_upper_gate_by_colours):
"""Function for creating representation of the maze for the puzzle Cat Walk
from MUMS Puzzle Hunt 2012 competition."""
cells_with_left_border = cells_on_the_left_edge
cells_with_right_border = cells_on_the_right_edge
for cell in cells_with_right_border_inside_maze:
# extend the tuple of cells with right border
cells_with_right_border += (cell,)
# extend the tuple of cells with left border
cells_with_left_border += ((cell[0]+1,cell[1]),)
cells_with_right_gate = {}
cells_with_left_gate = {}
for colour in cells_with_right_gate_by_colours:
for cell in cells_with_right_gate_by_colours[colour]:
cells_with_right_gate[cell] = colour
cells_with_left_gate[(cell[0]+1,cell[1])] = colour
cells_with_upper_gate = {}
cells_with_lower_gate = {}
for colour in cells_with_upper_gate_by_colours:
for cell in cells_with_upper_gate_by_colours[colour]:
cells_with_upper_gate[cell] = colour
cells_with_lower_gate[(cell[0],cell[1]+1)] = colour
maze = {}
# create a maze, row by row
for row in range(num_rows):
# create one row
for col in range(num_cols):
cell = (col,row)
if cell not in imaginary_cells:
cell_gates = {}
# vertical gates
if cell in cells_with_upper_gate:
cell_gates['up'] = cells_with_upper_gate[cell]
if cell in cells_with_lower_gate:
cell_gates['down'] = cells_with_lower_gate[cell]
# horizontal gates
if cell in cells_with_right_gate:
cell_gates['right'] = cells_with_right_gate[cell]
elif cell not in cells_with_right_border:
cell_gates['right'] = None
if cell in cells_with_left_gate:
cell_gates['left'] = cells_with_left_gate[cell]
elif cell not in cells_with_left_border:
cell_gates['left'] = None
maze[cell] = cell_gates
return maze
First, it creates a tuple of all cells that have a border on the left and a tuple of all cells that have a border on the right. Then it creates 4 dictionaries for cells that have coloured gates. The keys in these dictionaries will be tuples of two numbers denoting cells, and the values will be strings denoting colors ('blue', 'red', 'green', 'gray'). The first dictionary will contain all cells that have a coloured gate on the right, the second - on the left, the third - on the top and the fourth - on the bottom. After that the function iterates over all cells of the maze row by row. If the given cell is not "imaginary", the function creates a transition dictionary for it, where the keys are possible movements ('up', 'down', 'right', 'left'), and the values are colors of gates ('blue', 'red', 'green', 'gray' or None). A cell will have a vertical or horizontal coloured gate, if it is in the corresponding dictionary. A cell will also have a horizontal gate without color, if it is not in the corresponding tuple of cells that have borders. Once the transition dictionary is created, the cell becomes the key, and the dictionary becomes the value in the dictionary that the function will return.
Now we can do the search. To determine the correspondence between a column and a letter we will use the string module.
import string
Let us define a tuple of cells that are entrances to the maze and a tuple of cells that are exits from it.
# starting cells
start_cells = ((12,0),(13,0))
# goal cells
goal_cells = ((4,20),(7,20),(11,20),(17,20),(19,20),(21,20),(24,20))
We need to find 2 paths. The first path will only pass through gray colored gates. In the second path the colored gates will alternate: after red there will be blue, after blue - green, after green - red. Let's create a dictionary for each path, which will contain information about its colored transitions. The keys in these dictionaries will be the colors of the gates through which this path can pass, and the values will be the colors of the gates that follow them.
# colours of gates for the first message
gray_palette = {'gray':'gray'}
# colours of gates for the second message
rbg_palette = {'red':'blue','blue':'green','green':'red'}
Let's move on to the search function.
def search(maze, start_cells, goal_cells, palette, first_colour):
"""Function that perform depth-first search in the maze
from the multiple start cells to the goal cells
according to the colours in palette and first colour."""
for cell in start_cells:
phrase = depth_first_search(maze, (cell,), goal_cells, first_colour, palette, '')
if phrase:
return phrase
return False
The input data for it are: the maze, the maze entrances, the maze exits, the colors of the gates for the given path, and the color of the first colored gate. For each maze entrance the function runs a depth-first search with an empty string for the message. If the search is successful for any entrance, the function will return the corresponding phrase. Otherwise, the function will return False.
def depth_first_search(maze, path, goal_cells, current_colour, palette, current_phrase):
"""Function that performs search in depth-first fashion in the maze from the current_cell to the goal_cells
according to the current_colour of the gate and following colours of the gates in palette."""
current_cell = path[-1]
if current_cell in goal_cells:
return current_phrase
for (cell, letter, colour) in get_near_cells_with_letters_and_colours(maze, current_cell, current_colour, palette):
# required path is acyclic
if cell not in path:
extended_path = path + (cell,)
extended_phrase = current_phrase + letter
phrase = depth_first_search(maze, extended_path, goal_cells, colour, palette, extended_phrase)
if phrase:
return(phrase)
return False
The depth-first search function first determine the current cell of the path. If this cell is one of the exits from the maze, the function will return the current phrase. Otherwise the function passes the maze, the current cell, the color of the next coloured gate and the set of colors to the get_near_cells_with_letters_and_colours function. This function generates possible neighboring cells for the given cell, as well as continuations of the phrase and colors of the next coloured gates corresponding to the movement to these cells. Since the required path is acyclic, before moving to a neighboring cell we check that we have not passed through it before. After the move the function modifies the path and the current phrase and continues the depth-first search with the new data. If any neighboring cell ultimately leads to an exit from the maze, the function will return the phrase corresponding to this path. Otherwise the function will return False.
Let's now look at the get_near_cells_with_letters_and_colours function.
def get_near_cells_with_letters_and_colours(maze, cell, colour, palette):
"""Function that for the current cell and colour will find available near cells
and also letters of the message and next colours,
associated with passage to that cells."""
col = cell[0]
row = cell[1]
for direction in maze[cell]:
gate_colour = maze[cell][direction]
# gate has the same colour
if gate_colour == colour:
# find next colour from the palette
next_colour = palette[colour]
if direction == 'up' or direction == 'down':
letter = string.ascii_uppercase[col]
elif direction == 'left' or direction == 'right':
letter = ''
# gate has no colour
elif gate_colour == None:
# next colour will be the same
next_colour = colour
letter = ''
# gate has a different colour
else:
continue
if direction == 'up':
near_cell = (col, row+1)
elif direction == 'down':
near_cell = (col,row-1)
elif direction == 'left':
near_cell = (col-1,row)
elif direction == 'right':
near_cell = (col+1,row)
yield (near_cell, letter, next_colour)
This function considers all possible movements in the maze for a given cell. If movement to the neighboring cell is carried out through a coloured gate, then its color must match the color from the function input; in this case the color of the next colored gate will be determined in accordance with the palette. If this movement is vertical, then the function will determine the letter corresponding to the column, which will then be added to the message. If the movement through the coloured gate is horizontal, then an empty string will be added to the message. If the gate to the neighboring cell has no color, the color of the next colored gate on the path will remain the same, and an empty string will be added to the message. Next, the function determines the neighboring cell, corresponding to the direction of movement, and then yield this cell along with the continuation of the message and the color of the next colored gate.
Now all that remains is to add commands to our program to build the maze, extract the messages and output them.
if __name__ == '__main__':
# generate the maze in the puzzle
maze = generate_maze(num_cols, num_rows, imaginary_cells,
cells_on_the_left_edge, cells_on_the_right_edge,
cells_with_right_border_inside_maze,
cells_with_right_gate_by_colours, cells_with_upper_gate_by_colours)
# command to exctract the first message in the puzzle
phrase = search(maze,start_cells,goal_cells, gray_palette,'gray')
print(phrase)
# command to extract the second message in the puzzle
phrase = search(maze,start_cells,goal_cells, rbg_palette,'red')
print(phrase)
The result of the program's work is already familiar messages.
REDBLUETHENGREENPATH BLACKANDWHITECATFOOT
The full program code can be found here.
Comments
Post a Comment