Solving a University Quest Puzzle with Python
Cat Walk – one of the interesting puzzles of the game Puzzle Hunt University of Melbourne 2012. This task was part of the second act of the game, and was preceded by a short narrative that continued the plot of the game. According to it, you receive a small package from your strange companion. Upon unwrapping it, you find a flash drive inside, after which your attention switches to the wrapping: it seems to be a page that has been torn out of a book of children's puzzles. You stare long and hard at the puzzle depicted on the page, and it seems that you have managed to solve it. Then you turn to your companion to check your guess. He looks at you in amazement, quickly inserts the flash drive into his laptop, and then happily says: “This is amazing! You figured out the password – that's all we needed …” As it turns out, the flash drive contained extremely important information, and the solution to the “children's” puzzle served as the password to get it …
The puzzle itself was located below. It was a rectangular labyrinth with multi-colored transitions between its parts: gray, red, blue and green. At the bottom of the labyrinth, near two entrances, sat Simon's Cat, who was gesturing that he wanted to eat. The cat's food was at the opposite end of the labyrinth, to which 7 multi-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 its number. Then, it was necessary to pay attention to the colors of the transitions inside the maze. It was possible to try to pass the maze using transitions of only one color. This was possible only for one of the colors – for gray – and only in one way (if you never move along the path you have already taken).
A message could be extracted from this passage. To do this, each time the path led through a vertical passage, one had to add to the message the letter corresponding to the column number for that passage. The result was REDBLUETHENGREENPATH, or RED, BLUE THEN GREEN PATH, or “red, blue, then green path.” Thus, the clue suggested going through the maze one more time, but this time alternating between red, blue, and green passages. Again, this could be done in only one way.
After successfully completing the puzzle, another message could be received in a similar manner. The result was BLACKANDWHITECATFOOT or BLACK AND WHITE CAT FOOT. This strange phrase is a literal translation of the Latin term for the animal species Big Panda (Ailuropoda melanoleuca) or Giant Panda. Thus, answer The mission was GIANT PANDA.
Some additional information about the puzzle could be found in notes to her. The most common answers given by players were: GIANT PANDA (77 times), PANDA (19 times) and BLACK AND WHITE CAT FOOT (11 times). Below is how the task was created.
“This puzzle evolved from the rather simple concept of a maze that spelled out the answer phrase by either absolute or relative permutations of the solution path. This idea was later further developed into a two-stage process that would be more fun to solve (and was deliberately made more challenging by the many long, dead-end branches in the alternation of red, blue, and green passages), but which presented no additional difficulty in construction due to the mutual exclusion of the colors.
The second stage was answered with a variety of different phrases (e.g. EATS SHOOTS AND LEAVES [ест побеги и листья]SPECIFICALLY NOT SHIFU [именно По, а не Шифу]BEAR APPEARING ON WWF LOGO [медведь, изображенный на логотипе WWF] and so on) in an attempt to differentiate the GIANT PANDA response from just PANDA [ответ GIANT PANDA был выбран заранее для составления мета-задания того года]but in the end the choice fell on BLACK AND WHITE CAT FOOT, which matched well with the abundance of flowers in the maze.”
An interesting challenge for this puzzle is to write a program that can independently find both necessary 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 labyrinth. The labyrinth is divided into 20 rows and 26 columns by horizontal and vertical lines. To make searching the labyrinth easier, we'll add one cell after each exit. These cells can be considered an incomplete twenty-first row. Since we'll be building the labyrinth row by row, it may be convenient to designate “imaginary cells” that are inside the rectangular grid but are not part of the labyrinth. So we'll add a twenty-first row to the labyrinth, some of whose cells 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 = 21To represent the maze, we will use a dictionary. Its keys will be 2-tuples representing cells, and its values will be dictionaries. Their keys will be strings representing possible movements for a given cell ('up', 'down', 'right', 'left'). If the movement is via a color transition, the value will be a string representing 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 specify the input data that will be used to build the maze.
Let's define 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 cells in the labyrinth have horizontal connections with neighboring cells. On the other hand, most cells in the labyrinth do not have vertical connections with neighboring cells, and all vertical connections are colored transitions. This can be used to simplify the construction of the labyrinth: it will be enough to specify only the cells that have horizontal boundaries and the cells that have colored transitions.
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 color transitions, 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 color transition on the right. The second dictionary will contain cells with a color transition 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 mazeFirst, 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 color transitions. The keys in these dictionaries will be 2-tuples of 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 color transition 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 cell in question is not “imaginary”, the function creates a transition dictionary for it, where the keys are possible movement options ('up', 'down', 'right', 'left'), and the values are transition colors ('blue', 'red', 'green', 'gray' or None). A cell will have a vertical or horizontal color transition if it is in the corresponding dictionary. A cell will also have a horizontal transition 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 stringLet us define a tuple of cells that are entrances to the labyrinth, 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))In total, we need to lay 2 paths. The first path will only pass through gray colored transitions. In the second path, the colored transitions 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 transitions through which this path can pass, and the values will be the colors of the transitions 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'}The search will start with 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 FalseThe input data for it are: the maze, the maze entrances, the maze exits, the colors of the transitions for a given path, and the color of the first colored transition. For each maze entrance, the function runs a depth-first search with an empty tuple for the path and an empty string for the message. If the search is successful for any of the entrances, the function returns the corresponding phrase. Otherwise, the function returns False.
def depth_first_search(maze, current_cell, goal_cells, path, 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."""
path += (current_cell,)
if current_cell in goal_cells:
return current_phrase
else:
near_cells_with_letters_and_colours = get_near_cells_with_letters_and_colours(maze, current_cell, current_colour, palette)
for (cell, letter, colour) in near_cells_with_letters_and_colours:
# required path is acyclic
if cell not in path:
extended_phrase = current_phrase + letter
phrase = depth_first_search(maze, cell, goal_cells, path, colour, palette, extended_phrase)
if phrase != False:
return(phrase)
return FalseThe depth-first search function first adds the current cell to the path already traversed. If the given cell is one of the exits of the maze, the function returns the current phrase. Otherwise, the function passes the maze, the current cell, the color of the next color transition, and the set of colors to the get_near_cells_with_letters_and_colours function. This function will find all possible neighboring cells for the given cell, as well as continuations of the phrase and colors of the next color transitions 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 current phrase and continues the depth-first search with the new data. If any neighboring cell eventually leads to the exit of the maze, the function returns the phrase corresponding to this path. Otherwise, the function returns False.
Let's look further 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 current 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]
near_cells_with_letters_and_colours = ()
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)
near_cells_with_letters_and_colours += ((near_cell, letter, next_colour),)
return near_cells_with_letters_and_coloursThis function considers all possible variants of movement in the maze for a given cell. If the movement to the neighboring cell is carried out via a colored transition, then its color must match the color from the input data of the function; in this case, the color of the next colored transition 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 via the colored transition is horizontal, then an empty line will be added to the message. In the case where the transition to the neighboring cell has no color, then the color of the next colored transition on the path will remain the same, and an empty line will again be added to the message. Next, the function determines the neighboring cell corresponding to the direction of movement, and then adds this cell along with the continuation of the message and the color of the next colored transition to the final tuple.
Now all that remains is to add commands to our program to build the maze, extract 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
BLACKANDWHITECATFOOTThe full program code can be found Here.
![[Личный опыт] Amazon vs Microsoft: how the interview process is different in large IT companies](https://prog.world/wp-content/uploads/2020/08/1598047320_v1-768x403.png)
