Решение головоломки Треки.

Треки — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2008 года. Это задание было частью пятого акта игры, и ему предшествовало небольшое повествование, которое продолжало ее сюжет. В соответствии с ним ночь в стране выдалась неспокойная; и вместо того, чтобы спать, вы провели ее в ужасе наблюдая по телевизору за уличными беспорядками. С наступлением дня ситуация несколько улучшилась, и вы решаете выйти из дома, чтобы подышать свежим воздухом. На улице вы замечаете детей, беззаботно играющих в классики на дороге. Когда вы подходите к ним поближе в надежде на то, что часть их безмятежности передастся и вам, то ваше внимание переключается на очертания классиков, небрежно нарисованных мелом на дороге. Они совершенно не соответствуют ни одним классикам, в которые вам когда-либо доводилось играть...

Ниже можно было видеть эти «классики». 

Они представляли собой два поля одинакового размера, разделенные на клетки горизонтальными и вертикальными линиями. Таким образом, каждое поле состояло из 6 рядов и 16 столбцов. Помимо этого, оба поля были вертикально разделены посередине на две равные части.

В верхнем поле была клетка, обозначенная как start, и клетка, обозначенная как finish. Каждому столбцу верхнего поля, а также каждой строке в левой и правой его части была сопоставлена цифра.

Нижнее поле содержало большое число цифр от 1 до 9, которые довольно хаотично были расставлены в некоторых его клетках.

Автором этой головоломки был Стивен Мюрхед, который в то время отвечал за публичное освящение деятельности Сообщества Математики и Статистики Мельбурнского Университета (MUMS). Интересно отметить, что Стивен Мюрхед является также автором длинной интересной статьи, посвященной основателю WikiLeaks, и вероятному создателю загадки Cicada 3301, Джулиану Ассанжу и его участию в жизни сообщества во время учебы в Мельбурнском Университете, которая вышла в журнале Paradox, издаваемом сообществом, в 2010 году.

Суть верхнего поля была достаточно очевидной: участникам игры предлагалось построить путь от клетки start до клетки finish, а цифры для столбцов и строк указывали на то, сколько раз требуемый путь должен проходить через данный столбец или данную строку. Эта задача является довольно интересной и несложной: путь можно постепенно построить по частям, исходя из логических соображений.

Однако значение нижнего поля было уже не столь тривиальным. 

На следующий день после выхода головоломки появилась первая подсказка к ней: 

«Трек (существительное): 1) путь, маршрут или курс; или 2) одно музыкальное произведение как часть более крупной коллекции».

А еще через день появилась вторая подсказка: 

«Попробуйте наложить треки друг на друга».

Следовательно, путь из верхнего поля следовало наложить на нижнее поле. После этого можно было извлечь сообщение из нижнего поля следующим образом: если через какую-либо клетку нижнего поля, содержащую цифру, проходил путь из верхнего поля, то соответствующее место сообщения должна была также занимать эта цифра. В противном случае соответствующее место следовало оставить пустым. Ниже можно видеть полученное таким образом сообщение.

-	-	-	5	7	-	-	7	8	-	-	8	2	-	-	2
-	-	5	-	-	5	-	-	-	5	-	-	-	3	-	-
-	5	-	-	-	-	5	-	-	-	5	-	-	-	2	-
7	-	-	-	6	-	-	-	5	-	-	-	4	-	-	-
-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

Теперь, очевидно, требовалось каким-то образом связать его с некоторым музыкальным произведением. Для этого следовало интерпретировать сообщение как гитарные табы и сыграть его на этом музыкальном инструменте. 

В результате можно было услышать начало знаменитой песни Stairway to Heaven группы Led Zeppelin, выпущенной в альбоме Led Zeppelin IV в 1971 году.

Таким образом, ответом на задание было STAIRWAY TO HEAVEN.

Интересной задачей для этой головоломки является написание программы, которая могла бы самостоятельно найти путь для верхнего поля, а затем, с его помощью, извлечь сообщение из нижнего поля. Попробуем составить такую программу на языке Python.

Начнем с поиска пути для верхнего поля. Входными данными для этой задачи будут: число столбцов в левой части поля; 3 списка чисел, которые представляют собой ограничения для столбцов, строк в левой части поля и строк в правой части поля соответственно; кортеж из 2 чисел, обозначающий клетку start, и кортеж из 2 чисел, обозначающий клетку finish.

# number of cols in the left part of the grid
cols_in_left_part = 8

#constraints for the cols of the grid
cols_constr =[3,3,2,1,4,3,2,3,6,3,4,3,5,2,2,3]

#constraints for the rows in the left part of the grid
left_rows_constr = [1,1,4,5,6,4]

#constraints for the 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)

Входные данные мы затем передадим в функцию search.

def search(start, finish, cols_in_left_part, cols_constr, left_rows_constr, right_rows_constr):
    """Function for finding a path in the grid for the puzzle Tracks
       from MUMS Puzzle Hunt 2008 competition."""
    cols_constr = list(cols_constr)
    left_rows_constr = list(left_rows_constr)
    right_rows_constr = list(right_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_part:
        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 according to the start cell
    if cols_constr[start_col] > 0 and active_rows_constr[start_row] > 0:
        cols_constr[start_col] -= 1
        active_rows_constr[start_row] -= 1
    else:
        raise ValueError("Start cell shoud have non-zero values of constraints.")
    path = depth_first_search((start,), finish, cols_in_left_part,
                              cols_constr, active_rows_constr, inactive_rows_constr)
    return path

Эта функция по расположению стартовой клетки определяет, какой набор ограничений для строк будет активным, а какой неактивным на момент начала поиска. После этого она обновляет ограничения для столбцов и строк, запускает поиск в глубину и возвращает его результат.

def depth_first_search(path, finish, cols_in_left_part, cols_constr, active_rows_constr, inactive_rows_constr):
    """Function that performs depth-first search in the grid from a current cell to the finish cell
       according to the given constraints."""
    current_cell = path[-1]
    # if current cell is a finish cell and constraints are satisfied, than path is found
    if current_cell == finish and sum(cols_constr) == 0:
        return path
    # find perspective adjacent cells for the current cell with corresponding constraints
    next_state = get_next_state(current_cell, finish, cols_in_left_part, cols_constr, active_rows_constr, inactive_rows_constr)
    for (adjacent_cell, next_cols_constr, next_active_rows_constr, next_inactive_rows_constr) in next_state:
        # we assume, that path is acyclic
        if adjacent_cell not in path:
            extended_path = path + (adjacent_cell,)
            final_path = depth_first_search(extended_path, finish, cols_in_left_part,
                                            next_cols_constr, next_active_rows_constr, next_inactive_rows_constr)
            if final_path:
                return final_path
    return False

Функция поиска в глубину сначала определяет текущую клетку пути. Затем она проверяет, совпадает ли текущая клетка с финишной. Если это так, то необходимо проверить, удовлетворены ли ограничения. При прокладывании пути мы не будем рассматривать маршруты, которые нарушают ограничения. Поэтому достаточно будет проверить только ограничения для столбцов. Если их сумма равна нулю, то задача является решенной, и функция вернет текущий путь. Если же текущий путь не является решением, то функция передаст текущую клетку и другие данные в функцию get_next_state. Эта функция для текущей клетки генерирует смежные с ней клетки, перспективные для дальнейшего поиска, а также ограничения для столбцов и строк, которые получаются при переходе в эти клетки. Мы предполагаем, что искомый путь является ациклическим. Поэтому, прежде чем перейти к поиску пути через одну из смежных клеток, мы проверяем, что не проходили через нее ранее. Если путь через какую-либо смежную клетку приводит к решению задачи, то функция поиска в глубину вернет соответствующий путь. В противном случае функция вернет False.

Далее рассмотрим функцию get_next_state.

def get_next_state(cell, finish, cols_in_left_part, cols_constr, active_rows_constr, inactive_rows_constr):
    """Function that for the given cell, in accordance with the given constraints,
       generate possible adjacent cells, perspective for subsequent search,
       with constraints, corresponding to passage to that cells."""
    num_cols = len(cols_constr)
    num_rows = len(active_rows_constr)
    col, row = cell[0], cell[1]
    for direction in ('horizontal','vertical'):
        for move in (+1,-1):
            next_active_rows_constr = active_rows_constr
            next_inactive_rows_constr = inactive_rows_constr
            if direction == 'horizontal':
                next_col = col + move
                #next col is inside grid
                if next_col >= 0 and next_col < num_cols:
                    next_row = 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 the rows
                if (col == cols_in_left_part - 1 and move == +1) or (col == cols_in_left_part and move == -1):
                    next_active_rows_constr, next_inactive_rows_constr = next_inactive_rows_constr, next_active_rows_constr                 
            elif direction == 'vertical':
                next_row = row + move
                # next row is inside grid
                if next_row >=0 and next_row < num_rows:
                    next_col = col
                else:
                    continue
            # extract values of constraints for the next col and next row
            next_col_value = cols_constr[next_col]
            next_row_value = next_active_rows_constr[next_row]
            # constraints are allow to make the move
            if next_col_value > 0 and next_row_value > 0:
                # constraints for cols is impossible to satisfy
                if next_col_value == 1:
                    finish_col = finish[0]
                    if (next_col <= finish_col and sum(cols_constr[:next_col])>0
                        or
                        next_col >= finish_col and sum(cols_constr[next_col+1:])>0):
                        continue
                # constraints for rows is impossible to satisfy
                if next_row_value == 1 and next_inactive_rows_constr[next_row] == 0:
                    finish_row = finish[1]
                    if (next_row <= finish_row and
                        (sum(next_active_rows_constr[:next_row])>0 or sum(next_inactive_rows_constr[:next_row])>0)
                        or
                        next_row >= finish_row and
                        (sum(next_active_rows_constr[next_row+1:])>0 or sum(next_inactive_rows_constr[next_row+1:])>0)):
                        continue                   
                adjacent_cell = (next_col, next_row)
                next_cols_constr = list(cols_constr)
                next_active_rows_constr = list(next_active_rows_constr)
                next_cols_constr[next_col] -= 1
                next_active_rows_constr[next_row] -= 1
                yield (adjacent_cell, next_cols_constr, next_active_rows_constr, next_inactive_rows_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_part, 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))

Далее необходимо с помощью этого пути извлечь сообщение из нижнего поля. Представим нижнее поле как кортеж из кортежей, каждый из которых будет представлять одну строку. Для обозначения пустых клеток будем использовать нуль.

# bottom grid from the puzzle, where 0 denotes an empty cell
bottom_grid = ((0,0,8,6,0,8,0,0,0,0,0,0,0,2,0,9),
               (0,1,0,3,0,0,0,1,0,7,0,9,0,0,4,0),
               (7,0,4,0,6,0,9,0,5,4,0,3,4,0,1,0),
               (2,5,3,3,0,0,5,0,0,0,5,0,0,8,2,0),
               (0,0,5,0,0,5,0,0,0,5,0,0,6,3,0,0),
               (0,4,0,5,7,0,2,7,8,9,0,8,2,0,0,2))

Рассмотрим теперь функцию extract_message.

def extract_message(grid, path):
    """Function that extract message from the given grid according to the given 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 cell_value > 0 and (col,row) in path:
                message += str(cell_value)
            else:
                message += '-'
        # add newline character after each row
        message += '\n'
    return message

Сначала эта функция определяет количество строк и столбцов поля. Для извлечения сообщения она по очереди рассматривает строки поля в обратном порядке. Если какая-либо клетка данной строки является частью пути и содержит цифру больше нуля, то к сообщению добавляется эта цифра. В противном случае, к сообщению добавляется символ '-'. После рассмотрения каждой строки поля функция добавляет к сообщению символ новой строки.

Теперь остается только добавить к нашей программе команды для нахождения пути, извлечения сообщения и его вывода.

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_part, cols_constr, left_rows_constr, right_rows_constr)
    message = extract_message(bottom_grid, path)
    print(message)

Результатом работы программы является уже знакомое сообщение.

---57--78--82--2
--5--5---5---3--
-5----5---5---2-
7---6---5---4---
----------------
----------------

Код программы целиком можно найти здесь.