Решение головоломки Cat Walk.
Cat Walk — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2012 года. Это задание было частью второго акта игры, и ему предшествовало небольшое повествование, которое продолжало ее сюжет. В соответствии с ним вы получаете от вашего странного компаньона небольшой сверток. Развернув его, вы находите внутри флешку, после чего выше внимание переключается на обертку: она, кажется, представляет собой страницу, которая была вырвана из книги с головоломками для детей. Вы долго и упорно разглядываете головоломку, изображенную на странице, и, похоже, вам удается ее решить. После этого вы обращаетесь к вашему компаньону, чтобы проверить свою догадку. Тот смотрит на вас в изумлении, быстро вставляет флешку в ноутбук, а затем радостно сообщает: «Это потрясающе! Ты разгадал пароль — это же всё, что нам требовалось...» Как оказалось, флешка содержала чрезвычайно важную информацию, а разгадка «детской» головоломки служила паролем для ее получения...
Сама же головоломка располагалась ниже. Она представляла собой лабиринт прямоугольной формы с разноцветными переходами между его частями: серого, красного, синего и зеленого цвета. Внизу лабиринта, около двух входов в него, сидел Кот Саймона, который показывал жестом, что хочет есть. Корм для кота находился на противоположном конце лабиринта, к которому вели 7 разноцветных выходов.
Первым шагом в решении головоломки было определить количество столбцов в лабиринте: их было 26, что соответствует числу букв в английском алфавите. Таким образом, каждому столбцу можно было присвоить соответствующую ему по номеру букву. Затем следовало обратить внимание на цвета переходов внутри лабиринта. Можно было попробовать пройти лабиринт, используя при этом переходы только одного цвета. Это было возможно сделать только для одного из цветов — для серого — и только единственным способом (если никогда не двигаться по уже пройденному пути).
Из данного прохождения можно было извлечь сообщение. Для этого всякий раз, когда путь пролегал через вертикальный переход, следовало добавлять к сообщению букву, соответствующую номеру столбца для данного перехода. Результатом было REDBLUETHENGREENPATH, или RED, BLUE THEN GREEN PATH, или «красный, синий, а затем зеленый путь». Таким образом, подсказка предлагала пройти лабиринт еще один раз, но теперь чередуя переходы красного, синего и зеленого цвета. Это снова можно было сделать единственным способом.
Некоторую дополнительную информацию про головоломку можно было найти в заметках к ней. Самыми частыми ответами, которые давали игроки, были: GIANT PANDA (77 раз), PANDA (19 раз) и BLACK AND WHITE CAT FOOT (11 раз). Ниже говорилось о том, как проходило создание задания.
«Эта головоломка появилась из достаточно простой концепции лабиринта, который произносит по буквам фразу-ответ посредством или абсолютной, или относительной перестановки пути его решения. Позже эта идея получила дальнейшее развитие в виде процесса из двух этапов, который было бы интереснее решать (и который был намеренно сделан более сложным посредством большого количества длинных, заканчивающихся тупиком, ответвлений при чередовании красных, синих и зеленых переходов), но который не представлял дополнительных трудностей при создании из-за взаимного исключения цветов.
В качестве ответа на второй этап предлагалось множество различных фраз (например, EATS SHOOTS AND LEAVES [ест побеги и листья], SPECIFICALLY PO NOT SHIFU [именно По, а не Шифу], BEAR APPEARING ON WWF LOGO [медведь, изображенный на логотипе WWF] и так далее) в попытке дифференцировать ответ GIANT PANDA от просто PANDA [ответ GIANT PANDA был выбран заранее для составления мета-задания того года], однако в итоге выбор пал на BLACK AND WHITE CAT FOOT, который хорошо соответствовал обилию цветов в лабиринте».
Интересной задачей для этой головоломки является написание программы, которая могла бы самостоятельно найти оба необходимых пути в лабиринте и извлечь из них сообщения. Попробуем составить такую программу с помощью Python.
Начнем с создания представления лабиринта. Горизонтальными и вертикальными линиями лабиринт делится на 20 строк и 26 столбцов. Для удобства поиска в лабиринте добавим по одной клетке после каждого выхода из него. Эти клетки можно рассматривать как неполную двадцать первую строку. Так как мы будем строить лабиринт строка за строкой, то может быть удобно обозначить «мнимые» клетки, которые находятся внутри прямоугольной сетки, но при этом не являются частью лабиринта. Таким образом, мы добавим к лабиринту двадцать первую строку, часть клеток которой будет «мнимыми».
# number of columns in the maze
num_cols = 26
# number of rows in the maze with one additional row for searching
num_rows = 21
Для представления лабиринта будем использовать словарь. Его ключами будут кортежи из 2 чисел, обозначающие клетки, а его значениями будут словари. Их ключами будут строки, обозначающие возможные перемещения для данной клетки ('up', 'down', 'right', 'left'). Если перемещение осуществляется через цветной переход, то значением будет строка, обозначающая цвет ('blue', 'red', 'green', 'gray'). В противном случае значением будет None. Таким образом, левая нижняя клетка лабиринта будет представлена в словаре как (0,0): {'up': 'blue', 'right': None}.
Далее необходимо задать входные данные, которые будут использоваться для построения лабиринта.
Зададим «мнимые» клетки, которые все находятся в 21 строке, с помощью кортежа.
# 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))
Подавляющее большинство клеток лабиринта имеет горизонтальное сообщение с соседними клетками. С другой стороны, большинство клеток лабиринта не имеет вертикального сообщения с соседними клетками, а все вертикальные сообщения представляют собой цветные переходы. Это можно использовать для того, чтобы упростить построение лабиринта: достаточно будет задать только клетки, имеющие горизонтальные границы, и клетки, имеющие цветные переходы.
Клетки, имеющие горизонтальные границы, представим с помощью 3 кортежей. Первый кортеж будет содержать клетки на левом краю лабиринта. Второй кортеж будет содержать клетки на правом краю лабиринта. Третий кортеж будут содержать клетки, которые имеют справа границу от соседней клетки.
# 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))
Для представления клеток, имеющих цветные переходы, будем использовать словари, ключами которых будут строки, обозначающие цвета ('blue', 'red', 'green', 'gray'), а значениями — кортежи из клеток. Первый словарь будет содержать клетки, имеющие цветной переход справа. Второй словарь будет содержать клетки, имеющие цветной переход сверху.
# 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))}
Теперь можно рассмотреть функцию generate_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
Сперва она создает кортеж всех клеток, имеющих границу слева, и кортеж всех клеток, имеющих границу справа. Затем она создает 4 словаря для клеток, имеющих цветные переходы. Ключами в этих словарях будут кортежи из 2 чисел, обозначающие клетки, а значениями — строки, обозначающие цвета ('blue', 'red', 'green', 'gray'). Первый словарь будет содержать все клетки, имеющие цветной переход справа, второй — слева, третий — сверху, четвертый — снизу. После этого функция построчно перебирает все клетки лабиринта. Если рассматриваемая клетка не является «мнимой», то функция создает для нее словарь переходов, где ключами являются возможные варианты передвижения ('up', 'down', 'right', 'left'), а значениями — цвета переходов ('blue', 'red', 'green', 'gray' или None). Клетка будет иметь вертикальный или горизонтальный цветной переход, если она находится в соответствующем словаре. Клетка также будет иметь горизонтальный переход без цвета, если ее нет в соответствующем кортеже клеток, имеющих границы. После создания словаря переходов данная клетка становится ключом, а словарь — значением в словаре, который будет возвращать функция.
Теперь можно заняться поиском. Для определения соответствия между столбцом и буквой будем использовать модуль string.
import string
Зададим кортеж клеток, которые являются входами в лабиринт, и кортеж клеток, которые являются выходами из него.
# 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))
Всего нам необходимо проложить 2 пути. Первый путь будет проходить только через цветные переходы серого цвета. Во втором пути цветные переходы будут чередоваться: после красного будет синий, после синего — зеленый, после зеленого — красный. Создадим словарь для каждого пути, который будет содержать информацию о его цветных переходах. Ключами в этих словарях будут цвета переходов, через которые может пролегать данный путь, а значениями — цвета следующих за ними переходов.
# 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'}
Поиск будет начинаться с функции search.
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
Входными данными для нее являются: лабиринт, входы в лабиринт, выходы из лабиринта, цвета переходов для данного пути, а также цвет первого цветного перехода. Для каждого входа в лабиринт функция запускает поиск в глубину c пустой строкой для сообщения. Если для какого-либо входа поиск увенчается успехом, то функция вернет соответствующую ему фразу. В противном случае функция вернет 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
Функция поиска в глубину сначала определяет текущую клетку пути. Если данная клетка представляет собой один из выходов лабиринта, то функция вернет текущую фразу. В противном случае функция передаст лабиринт, текущую клетку, цвет следующего цветного перехода и набор цветов в функцию get_near_cells_with_letters_and_colours. Эта функция для данной клетки генерирует возможные соседние клетки, а также продолжения фразы и цвета следующих цветных переходов, соответствующие перемещению в эти клетки. Так как требуемый путь является ациклическим, то прежде чем переместиться в соседнюю клетку, мы проверяем, что не проходили через нее ранее. После перемещения функция модифицирует путь и текущую фразу и продолжает поиск в глубину уже с новыми данными. Если какая-либо соседняя клетка приведет в итоге к выходу из лабиринта, то функция вернет соответствующую этому пути фразу. В противном случае функция вернет False.
Рассмотрим далее функцию get_near_cells_with_letters_and_colours.
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)
Эта функция рассматривает для данной клетки все возможные варианты передвижения в лабиринте. Если перемещение в соседнюю клетку осуществляется через цветной переход, то его цвет должен совпадать с цветом из входных данных функции; при этом цвет следующего цветного перехода будет определен в соответствии с палитрой. Если данное перемещение является вертикальным, то функция определит букву, соответствующую столбцу, которая затем добавится к сообщению. Если же перемещение через цветной переход является горизонтальным, то к сообщению будет добавлена пустая строка. В том случае, если переход в соседнюю клетку не имеет цвета, то цвет следующего цветного перехода на пути останется тем же, а к сообщению опять же добавится пустая строка. Далее функция определяет соседнюю клетку, соответствующую направлению движения, а затем передает эту клетку вместе с продолжением сообщения и цветом следующего цветного перехода.
Теперь остается только добавить к нашей программе команды для построения лабиринта, извлечения сообщений и их вывода.
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)
Результатом работы программы являются уже знакомые сообщения.
REDBLUETHENGREENPATH BLACKANDWHITECATFOOT
Код программы целиком можно найти здесь.
Comments
Post a Comment