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 grid for hopscotch was shown below.

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

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

The bottom grid 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 grid 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 grid 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 grid had to be overlayed on the bottom grid. After that it was possible to extract the message from the bottom grid as follows: if a path from the top grid passed through a cell of the bottom grid, 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 grid and then use it to extract a message from the bottom grid. Let's try to write such a program in Python.

Let's start by finding a path for the top grid. The input data for this problem will be: the number of columns in the left part of the grid; 3 lists of numbers that represent the constraints for the columns, rows on the left part of the grid, and rows on the right part of the grid 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 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)

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

This function determines, based on the location of the starting cell, which set of row constraints will be active and which will be inactive at the beginning of the search. It then updates the column and row constraints, runs the depth-first search and returns the result.

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

The depth-first search function first determine the current cell of 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 get_next_state function. This function generates 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 get_next_state function.

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)

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 grid. For vertical movement the function checks, whether the corresponding row is part of the grid. For horizontal movement the function additionally checks, whether we are moving from one part of the grid 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 column constraints and active row constraints and yield corresponding tuple.

Now we can start the search with the following command.

path = search(start,finish, cols_in_left_part, 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 grid. Let's represent the bottom grid as a tuple of tuples, each of which will represent one row. We will use zero to denote empty cells.

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

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

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

First, this function determines the number of rows and columns in the grid. To extract a message it examines the rows of the grid 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 grid 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 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)

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.