Solution to the puzzle Tracks.

Tracks is one of the interesting puzzles of the Melbourne University Puzzle Hunt 2008 competition. This task was part of the fifth act of the game and was preceded by the short narrative, that continued the plot. In accordance with it the night in the country turned out to be restless; and instead of sleeping, you spent it watching in horror the street riots on TV. As the next day approaches, the situation improves somewhat, and you decide to leave the house to get some fresh air. On the street you notice some kids, playing hopscotch on the road, oblivious to all other concerns. As you walk closer, hoping some of their serenity will rub off on you, the hopscotch outlines carelessly chalked into the road stand out at you. This doesn’t look like any game of hopscotch you’ve ever played...

That field for hopscotch was shown below.

It consisted of two fields of the same size, divided into cells by horizontal and vertical lines. Thus, each field consisted of 6 rows and 16 columns. In addition both fields were vertically divided in the middle into two equal parts. 

In the top field there was a cell labeled start and a cell labeled finish. To each column of the top field, as well as each row in the left and right parts of it, was assigned a number.

The bottom field contained a large number of digits from 1 to 9, which were rather chaotically placed in some of its cells.

The author of this puzzle was Stephen Muirhead, who at the time was publicity officer of the Melbourne University Mathematics and Statistics Society (MUMS). It is interesting to note that Stephen Muirhead is also the author of a long and interesting article about WikiLeaks founder, and likely creator of the Cicada 3301 mystery, Julian Assange and his involvement in the community while studying at the University of Melbourne, which appeared in Paradox magazine, published by the community, in 2010.

The meaning of the top field was quite obvious: the participants of the game were asked to find a path from the start cell to the finish cell, and the numbers for the columns and rows indicated how many times the required path should pass through a given column or given row. This task is quite interesting and uncomplicated: the path can be gradually constructed by parts, based on logical reasoning.

However, the meaning of the bottom field was not so obvious.

The day after the puzzle was released, the first hint for it appeared:

«Track (noun): 1) a path, route, or course; or 2) a single piece of music as a part of a larger collection.»

And a day later a second hint appeared:

«Try to overlay the tracks on top of each other.»

Thus, the path from the top field had to be overlayed on the bottom field. After that it was possible to extract the message from the bottom field as follows: if a path from the top field passed through a cell of the bottom field, containing a digit, then this digit should also occupy the corresponding place in the message. Otherwise the corresponding place should have been left empty. Below you can see the message, extracted by this way.

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

Now it was necessary to somehow connect it with some piece of music. To do this, one had to interpret the message as guitar tab and play it on this musical instrument.

This was the beginning of the famous track "Stairway to Heaven" by Led Zeppelin, released on the album "Led Zeppelin IV" in 1971.

Thus, the answer to the puzzle was STAIRWAY TO HEAVEN.

An interesting challenge for this puzzle is to write a program that can automatically find a path for the top field and then use it to extract a message from the bottom field. Let's try to write such a program in Python.

Let's start by finding a path for the top field. The input data for this problem will be: the number of columns in the left part of the field; 3 lists of numbers that represent the constraints for the columns, rows on the left part of the field, and rows on the right part of the field respectively; a tuple of 2 numbers denoting the start cell and a tuple of 2 numbers denoting the finish cell.

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

#constraints for the cols of the field
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 field
left_rows_constr = [1,1,4,5,6,4]

#constraints for the rows in the right part of the field
right_rows_constr = [5,2,2,7,6,6]

# start cell
start = (0,0)

# finish cell
finish = (15,5)

We will then pass the input data to the search function.

def search(start, finish, cols_in_left_part,
           cols_constr, left_rows_constr, right_rows_constr):
    """Function for finding a path in the field 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)
    # compute number of cols and rows in the field
    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_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, num_cols, num_rows, cols_in_left_part,
                              cols_constr, active_rows_constr, inactive_rows_constr, ())
    return path

The search function first determines, how many columns and rows the field contains. Then, based on the location of the starting cell and the number of columns on the left part of the field, the function selects which set of constraints for rows will be active and which will be inactive at the beginning of  search. The function then updates the constraints for the columns and rows, based on the location of the starting cell. The function then runs the depth-first search and returns its result.

def depth_first_search(current_cell, finish, num_cols, num_rows, cols_in_left_part,
                       cols_constr, active_rows_constr, inactive_rows_constr, current_path):
    """Function that performs depth-first search in the field
       from a current cell to the finish cell, according to the given constraints."""
    current_path += (current_cell,)
    # if current cell is a finish cell and constraints satisfied, than path is found
    if current_cell == finish and sum(cols_constr) == 0:
        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_part,
                                                                     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_part,
                                          next_cols_constr, next_active_rows_constr, next_inactive_rows_constr, current_path)
                if path:
                    return path
    return False

The depth-first search function first adds the current cell of search to the path. Then it checks, whether the current cell matches the finish cell. If so, it is necessary to check whether the constraints are satisfied. During construction of the path we will not consider routes that violate the constraints. Therefore, it will be enough to check only the constraints for the columns. If their sum is equal to zero, then the problem is solved, and the function will return the current path. If the current path is not a solution, then the function will pass the current cell and other data to the find_adjacent_cells_with_constr function. This function finds adjacent cells for the current cell, that are promising for further search, as well as the constraints for the columns and rows, that are obtained when moving to these cells. We assume, that the required path is acyclic. Therefore, before moving on to finding a path through one of the adjacent cells, we check, that we have not passed through it before. If the path through any adjacent cell leads to a solution to the problem, then the depth-first search function will return the corresponding path. Otherwise the function will return False.

Next let's look at the find_adjacent_cells_with_constr function.

def find_adjacent_cells_with_constr(cell, finish, num_cols, num_rows, cols_in_left_part,
                                    cols_constr, active_rows_constr, inactive_rows_constr):
    """Function that for a given cell, in accordance with the given constraints,
       will find set of possible adjacent cells, perspective for subsequent search,
       with constraints, corresponding to passage to that cells."""
    col, row = cell[0], cell[1]
    adjacent_cells_with_constr = ()
    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 field
                if next_col >= 0 and next_col < num_cols:
                    next_row = row
                else:
                    continue
                # we move from the left part of the field 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 field
                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 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
                adjacent_cells_with_constr += ((adjacent_cell, next_cols_constr, next_active_rows_constr, next_inactive_rows_constr),)
    return adjacent_cells_with_constr

This function considers 2 directions of movement (horizontal and vertical) and 2 movement options (+1 and -1). For horizontal movement the function checks, whether the corresponding column is part of the field. For vertical movement the function checks, whether the corresponding row is part of the field. For horizontal movement the function additionally checks, whether we are moving from one part of the field to another. If this is the case, then it is necessary to swap the active and inactive constraints for the rows. After that it is necessary to check whether the constraints for the adjacent cell are greater than zero.

At this stage we can significantly speed up the search, if we will immediately discard adjacent cells that, although they do not violate the constraints, are not of interest for further search.

Let's consider the columns first. Suppose that after moving to some adjacent cell, the value of the constraints for its column will be equal to zero. Let us denote the column index of this adjacent cell as N and the column index of the finishing cell as F. If N <= F and there is a column with index K, where K < N, for which the constraints are not equal to zero, then this path cannot lead to a solution to the problem. Similarly, if N >= F and there is a column with index K, where K > N, for which the constraints are not equal to zero, then this path cannot lead to a solution to the problem.

We have a similar situation for rows. Suppose that after moving to some adjacent cell, the value of the active constraints for its row will be equal to zero. In addition, suppose that the value of inactive constraints for this row is also equal to zero. Let's denote the row index of this adjacent cell as N and the row index of the finishing cell as F. If N <= F and there is a row with index K, where K < N, for which active or inactive constraints are not equal to zero, then this path cannot lead to a solution to the problem. Similarly, if N >= F and there is a row with index K, where K > N, for which active or inactive constraints are not equal to zero, then this path cannot lead to a solution to the problem.

We will not use all these unpromising cells for further search. If an adjacent cell is promising, then we update the corresponding column constraints and active row constraints and then add the cell along with the constraints to the tuple, returned by the function.

Now we can start the search with the following command.

path = search(start, finish, cols_in_left_rows, cols_constr, left_rows_constr, right_rows_constr)

As a result we will get the following path.

((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))

Next, we need to use this path to extract the message from the bottom field. Let's represent the bottom field as a tuple of tuples, each of which will represent one row. We will use zero to denote empty cells.

# bottom field from the puzzle, where 0 denotes an empty cell
bottom_field = ((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))

Let's now take a look at the extract_message function.

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

First, this function determines the number of rows and columns in the field. To extract a message it examines the rows of the field in reverse order. If a cell in a given row is part of the path and contains a digit greater than zero, then that digit is added to the message. Otherwise the '-' character is added to the message. After examining each row of the field the function adds a newline character to the message.

Now all that remains is to add commands to our program to find the path, extract the message and print it.

if __name__ == '__main__':
    # find path in the upper field and extract and print corresponding message from the bottom field of the puzzle
    path = search(start, finish, cols_in_left_part, cols_constr, left_rows_constr, right_rows_constr)
    message = extract_message(bottom_field, path)
    print(message)

The result of the program is an already familiar message.

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

The full program code can be found here.