Решение головоломки из университетского квеста с помощью Python
«Треки» — одна из интересных головоломок ежегодного квеста Puzzle Hunt Мельбурнского Университета.
Эта головоломка представляет собой два поля одинакового размера, разделенные на клетки горизонтальными и вертикальными линиями. Таким образом, каждое поле состоит из 6 рядов и 16 столбцов. Помимо этого, оба поля вертикально разделены посередине на две равные части.
В верхнем поле есть клетка, обозначенная как start, и клетка, обозначенная как finish. Каждому столбцу верхнего поля, а также каждой строке в левой и правой его части сопоставлена цифра.
Нижнее поле содержит большое число цифр от 1 до 9, которые довольно хаотично расставлены в некоторых его клетках.
Суть верхнего поля является достаточно очевидной: необходимо построить путь от клетки start до клетки finish, а цифры для столбцов и строк указывают на то, сколько раз требуемый путь должен проходить через данный столбец или данную строку.
Однако значение нижнего поля уже не столь тривиально. С помощью пути из верхнего поля из нижнего поля можно извлечь сообщение, которое также состоит из 6 строк и 16 столбцов, следующим образом. Если через какую-либо клетку нижнего поля, содержащую цифру, проходит путь из верхнего поля, то соответствующее место сообщения должна также занимать эта цифра. В противном случае это место следует оставить пустым. Ниже можно видеть полученное таким образом сообщение.
- | - | - | 5 | 7 | - | - | 7 | 8 | - | - | 8 | 2 | - | - | 2 |
- | - | 5 | - | - | 5 | - | - | - | 5 | - | - | - | 3 | - | - |
- | 5 | - | - | - | - | 5 | - | - | - | 5 | - | - | - | 2 | - |
7 | - | - | - | 6 | - | - | - | 5 | - | - | - | 4 | - | - | - |
- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
Данное сообщение необходимо интерпретировать как гитарные табы и сыграть его на этом музыкальном инструменте.
В результате можно услышать начало знаменитой песни Stairway to Heaven группы Led Zeppelin. Таким образом, ответом на задание является STAIRWAY TO HEAVEN.
Попробуем решить этапы этой головоломки (за исключением игры на гитаре) с помощью Python.
Начнем с поиска пути для верхнего поля. Входными данными для этой задачи являются: число столбцов в левой половине поля; 3 кортежа, которые представляют собой ограничения для столбцов, строк в левой части поля и строк в правой части поля соответственно; кортеж из 2 элементов, обозначающий клетку start, и кортеж из 2 элементов, обозначающий клетку finish.
# number of cols in the left part of the grid
cols_in_left_rows = 8
#constraints for cols of the grid
cols_constr =(3,3,2,1,4,3,2,3,6,3,4,3,5,2,2,3)
#constraints for rows in the left part of the grid
left_rows_constr = (1,1,4,5,6,4)
#constraints for rows in the right part of the grid
right_rows_constr = (5,2,2,7,6,6)
# start cell
start = (0,0)
# finish cell
finish = (15,5)Сразу определим две вспомогательные функции, которые потребуются нам в дальнейшем.
def satisfied(constr):
for value in constr:
if value != 0:
return False
return TrueВ функцию satisfied мы будем передавать кортеж ограничений для столбцов или строк, чтобы определить, являются ли они решенными. Если все значения кортежа равны нулю, то функция вернет True. В противном случае функция вернет False.
def update_constr(constr, index):
updated_value = constr[index] - 1
updated_constr = constr[:index] + (updated_value,) + constr[index+1:]
return updated_constrФункция update_constr будет обновлять ограничения для столбцов или строк после каждого нашего перемещения. Ее входными данными являются кортеж ограничений и индекс элемента в этом кортеже. Функция вернет кортеж, который будет отличаться от первоначального тем, что значение элемента, соответствующего индексу, будет меньше на одну единицу.
Все входные данные мы передаем в функцию search.
def search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr):
# compute number of cols and rows in the grid
num_cols, num_rows = len(cols_constr), len(left_rows_constr)
start_col, start_row = start[0], start[1]
# set active and inactive rows constraints for the start cell
if start_col < cols_in_left_rows:
active_rows_constr = left_rows_constr
inactive_rows_constr = right_rows_constr
else:
active_rows_constr = right_rows_constr
inactive_rows_constr = left_rows_constr
# update constraints for the start cell
updated_cols_constr = update_constr(cols_constr, start_col)
updated_active_rows_constr = update_constr(active_rows_constr, start_row)
path = depth_first_search(start, finish, num_cols, num_rows, cols_in_left_rows,
updated_cols_constr, updated_active_rows_constr, inactive_rows_constr, ())
return pathФункция search сначала определяет, сколько столбцов и рядов содержит поле. Затем, на основании расположения стартовой клетки и количества столбцов в левой части поля, функция определяет, какой набор ограничений для строк будет активным, а какой неактивным, на момент начала поиска. Далее функция обновляет ограничения для столбцов и строк на основании расположения стартовой клетки. После этого функция запускает процедуру поиска в глубину и возвращает ее результат.
def depth_first_search(current_cell, finish, num_cols, num_rows, cols_in_left_rows,
cols_constr, active_rows_constr, inactive_rows_constr, current_path):
current_path += (current_cell,)
# if current cell is a finish cell and constraints satisfied, than path is found;
# it is sufficient to check only constraints for cols, because if they are satisfied, than constraints for rows are also satisfied
if current_cell == finish and satisfied(cols_constr):
return current_path
else:
# find adjacent cells for the current cell with corresponding constraints
adjacent_cells_with_constr = find_adjacent_cells_with_constr(current_cell, finish, num_cols, num_rows, cols_in_left_rows,
cols_constr, active_rows_constr, inactive_rows_constr)
for (adjacent_cell, next_cols_constr, next_active_rows_constr, next_inactive_rows_constr) in adjacent_cells_with_constr:
# we assume, that path is acyclic
if adjacent_cell not in current_path:
path = depth_first_search(adjacent_cell, finish, num_cols, num_rows, cols_in_left_rows,
next_cols_constr, next_active_rows_constr, next_inactive_rows_constr, current_path)
if path != False:
return path
return FalseФункция поиска в глубину сначала добавляет текущую клетку поиска к пройденному пути. Затем она проверяет, совпадает ли текущая клетка с финишной. Если это так, то необходимо проверить, удовлетворены ли ограничения. При прокладывании пути мы не будем рассматривать маршруты, которые нарушают ограничения. Поэтому достаточно будет проверить только ограничения для столбцов. Если они удовлетворены, то задача является решенной, и функция возвращает текущий путь.
Если же текущий путь не является решением, то мы передаем текущую клетку и другие данные в функцию find_adjacent_cells_with_constr. Эта функция для текущей клетки находит смежные с ней клетки, перспективные для дальнейшего поиска, а также ограничения для столбцов и строк, которые получаются при переходе в эти клетки. Мы предполагаем, что искомый путь является ациклическим. Поэтому, прежде чем перейти к поиску пути через одну из смежных клеток, мы проверяем, что не проходили через нее ранее.
Если путь через какую-либо смежную клетку приводит к решению задачи, то функция поиска в глубину вернет соответствующий путь.
В противном случае функция вернет False.
Далее рассмотрим функцию find_adjacent_cells_with_constr.
def find_adjacent_cells_with_constr(cell, finish, num_cols, num_rows, cols_in_left_rows,
cols_constr, active_rows_constr, inactive_rows_constr):
cell_col, cell_row = cell[0], cell[1]
adjacent_cells_with_constr = ()
for direction in ('horizontal','vertical'):
for move in (+1,-1):
active_rows_constr_for_move = active_rows_constr
inactive_rows_constr_for_move = inactive_rows_constr
if direction == 'horizontal':
next_col = cell_col + move
#next col is inside grid
if next_col >= 0 and next_col < num_cols:
next_row = cell_row
else:
continue
# we move from the left part of the grid to the right, or from right to the left;
# so we should swap active and inactive constraints for rows
if (cell_col == cols_in_left_rows - 1 and move == +1) or (cell_col == cols_in_left_rows and move == -1):
active_rows_constr_for_move, inactive_rows_constr_for_move = inactive_rows_constr_for_move, active_rows_constr_for_move
elif direction == 'vertical':
next_row = cell_row + move
# next row is inside grid
if next_row >=0 and next_row < num_rows:
next_col = cell_col
else:
continue
# extract values of constraints for the next col and next row
next_col_value = cols_constr[next_col]
next_row_value = active_rows_constr_for_move[next_row]
# check that constraints
if next_col_value > 0 and next_row_value > 0:
# if value of constraints for the next col will be zero after update,
# and there is some col on the direction, opposite to the finish cell from the next col, with non-zero value of constraints,
# than this path can't led to solution and should be abandoned
if next_col_value == 1:
finish_col = finish[0]
if (next_col <= finish_col and not satisfied(cols_constr[:next_col])
or
(next_col >= finish_col and not satisfied(cols_constr[next_col+1:]))):
continue
# if value of active constraints for the next row will be zero after update,
# and value of inactive constraints for that row is also equal to zero,
# and there is some row on the direction, opposite to the finish cell from the next row, with non-zero value of active or inactive constraints,
# than this path can't led to solution and should be abandoned
if next_row_value == 1 and inactive_rows_constr_for_move[next_row] == 0:
finish_row = finish[1]
if ((next_row <= finish_row and
(not satisfied(active_rows_constr_for_move[:next_row]) or not satisfied(inactive_rows_constr_for_move[:next_row])))
or
(next_row >= finish_row and
(not satisfied(active_rows_constr_for_move[next_row+1:]) or not satisfied(inactive_rows_constr_for_move[next_row+1:])))):
continue
adjacent_cell = (next_col, next_row)
updated_cols_constr = update_constr(cols_constr,next_col)
updated_active_rows_constr_for_move = update_constr(active_rows_constr_for_move, next_row)
adjacent_cells_with_constr += ((adjacent_cell, updated_cols_constr, updated_active_rows_constr_for_move, inactive_rows_constr_for_move),)
return adjacent_cells_with_constrЭта функция рассматривает 2 направления движения (горизонтальное и вертикальное) и 2 варианта перемещения (+1 и -1). Для горизонтального передвижения функция проверят, является ли соответствующий столбец частью поля. Для вертикального передвижения функция проверят, является ли соответствующая строка частью поля. Для горизонтального передвижения функция дополнительно проверят, не перемещаемся ли мы из одной части поля в другую. Если это так, то необходимо поменять местами активные и неактивные ограничения для строк. После этого необходимо проверить, позволяют ли ограничения для смежной клетки переместиться в нее (ограничения для ее строки и столбца должны быть больше нуля).
Интересно, что на этом этапе можно значительно упростить поиск, если сразу отсекать смежные клетки, которые хоть и не нарушают ограничений, но являются бесперспективными.
Рассмотрим сначала столбцы. Допустим, после перемещения в некоторую смежную клетку, значение ограничений для ее столбца станет равным нулю. Обозначим индекс столбца этой смежной клетки как N, а индекс столбца финишной клетки — как F. Если N <= F и существует столбец с индексом K, где K < N, ограничения для которого не являются решенными, то данный путь не может вести к решению задачи. Аналогично, если N >= F и существует столбец с индексом K, где K > N, ограничения для которого не являются решенными, то данный путь не может вести к решению задачи.
Для строк имеем похожую ситуацию. Допустим, после перемещения в некоторую смежную клетку, значение активных ограничений для ее строки станет равным нулю. Помимо этого, предположим, что значение неактивных ограничений для данной строки также равно нулю. Обозначим индекс строки этой смежной клетки как N, а индекс строки финишной клетки — как F. Если N <= F и существует строка с индексом K, где K < N, активные или неактивные ограничения для которой не являются решенными, то данный путь не может вести к решению задачи. Аналогично, если N >= F и существует строка с индексом K, где K > N, активные или неактивные ограничения для которой не являются решенными, то данный путь не может вести к решению задачи.
Мы не будем допускать все эти бесперспективные смежные клетки до дальнейшего поиска.
После этого остается обновить ограничения для столбцов и активные ограничения для строк для каждой перспективной смежной клетки.
Теперь можно запустить поиск следующей командой:
path = search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr)В результате мы получим следующий путь:
((0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (3, 5), (4, 5), (4, 4), (4, 3), (4, 2), (5, 2), (5, 3), (5, 4), (6, 4), (6, 3), (7, 3), (7, 4), (7, 5), (8, 5), (8, 4), (9, 4), (9, 3), (8, 3), (8, 2), (8, 1), (8, 0), (9, 0), (10, 0), (11, 0), (12, 0), (12, 1), (12, 2), (12, 3), (11, 3), (10, 3), (10, 4), (10, 5), (11, 5), (12, 5), (13, 5), (13, 4), (14, 4), (14, 3), (15, 3), (15, 4), (15, 5))Теперь необходимо с помощью этого пути извлечь сообщение из нижнего поля.
Представим нижнее поле как кортеж из кортежей, каждый из которых будет представлять одну строку. Для представления пустых клеток будем использовать None.
bottom_grid = ((None,None,8,6,None,8,None,None,None,None,None,None,None,2,None,9),
(None,1,None,3,None,None,None,1,None,7,None,9,None,None,4,None),
(7,None,4,None,6,None,9,None,5,4,None,3,4,None,1,None),
(2,5,3,3,None,None,5,None,None,None,5,None,None,8,2,None),
(None,None,5,None,None,5,None,None,None,5,None,None,6,3,None,None),
(None,4,None,5,7,None,2,7,8,9,None,8,2,None,None,2))Рассмотрим теперь функцию extract_message.
def extract_message(grid, path):
num_rows = len(grid)
num_cols = len(grid[0])
message = ''
# decremental loop for the number of rows
for row in range(num_rows-1,-1,-1):
for col in range(num_cols):
cell_value = grid[row][col]
if (col,row) in path and isinstance(cell_value, int):
message += str(cell_value)
else:
message += '-'
# add newline character after each row
message += '\n'
return messageСначала эта функция определяет количество строк и столбцов поля. Для извлечения сообщения она по очереди рассматривает строки поля в обратном порядке. Если какая-либо клетка данной строки является частью пути и содержит цифру, то к сообщению добавляется эта цифра. В противном случае, к сообщению добавляется символ '-'. После рассмотрения каждой строки поля функция добавляет к сообщению символ новой строки ('\n').
Теперь остается только добавить к нашей программе команды для нахождения пути, извлечения сообщения и его вывода.
if __name__ == '__main__':
# find path in the upper grid and extract and print corresponding message from the bottom grid of the puzzle
path = search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr)
message = extract_message(bottom_grid, path)
print(message)Код программы целиком можно найти здесь.
