CMPT 120 - (Mini-)Assignment 2 - Maze Solver

This (mini-)assignment 2 is much smaller in scope compared to assignment 1, which required a good deal of work.

This assignment will be the topic of the work during week 12's lab, and the TAs should be used to ask for help.

Modalities

The deadline is Saturday April 12th at 11:55pm. Although this is past the end of the term, which ends on April 9th, since this is meant as a way to revise the final we are exceptionally revising the deadline. Full commented solutions will be posted at midnight - so you may immediately learn. Thus no late submissions will be accepted.

The program MUST run (when opened in IDLE, and executed using F5, it must not cause an error from the get go), or the grade will be an automatic zero.

This assignment can be done in group, but submission should be individual. It is highly recommended you work at least in part alone on this assignment: it is short enough that this should not be a hindrance, and it is meant as a recap of many aspects of the course and to prepare you for the final; so if you don't do it entirely yourself, you will not get the benefit of this study tool.

The assignment consists of one Python source code on Coursys (eventually, if you attempt one of the advanced tasks, you might need to submit a second file - for instance if you write a second code file for the simulations; only in this case may you submit a second file).

The main Python source code file must begin with the lines:

########################################
### MAZE SOLVER (CMPT 120 Assignment #2)
### Date: <date>
### Team (name and SFU ID):
###   - <name of first person> (<sfu id of first person>)
###   - ...
########################################

For instance:

########################################
### MAZE SOLVER (CMPT 120 Assignment #2)
### Date: April 1st 2014
### Team (name and SFU ID):
###   - Jeremie Lumbroso (jlumbros)
###   - Peggy Wen (peggyw)
###   - Seymour Hoffman (seyhoff)
########################################

The main tasks will allow a team to get full marks for this assignment. The advanced tasks should only be undertaken by students with a quiz 1 score beyond 6.50; and it is mandatory for students with a quiz 1 score of 10.00 to complete at least one advanced task.

Questions should be asked on the help list: cmpt-120-help@sfu.ca.

Main goal

Using what you have learned on lists, and files, you must code the following aspects:

• read from a file "maze.txt", a maze that is described using the "#" character for a wall, the " " (space) for a corridor (a place one which you can walk), the "M" (space) character for the minotaur;
• convert that file into a list of list, a matrix, where the wall is represented by the integer -1, the corridor by the integer 0, and the minotaur by the integer 2
• then, using a simple version of an algorithm called "Flood Fill", you have your program solve the maze and return one of the following answers:
  • "ALIVE" if there is a way to get from the starting point to the exit without running into the minotaur;
  • "STUCK" if there is no way to get from the starting point to the exit (i.e., you are blocked by a wall);
  • "DEAD" if there is a way to get from the starting point to the exit, but it passes in front of the minotaur.
• you then write this answer in a file "answer-maze.txt".

Grading: the assignment will be graded on 10 points + 5 extra points:

• +3 points if your program runs;
• +3 points if your program correctly detects whether a maze is "ALIVE" or "STUCK" (for this stage, it is okay to return "STUCK" instead of "DEAD" and to completely ignore the minotaur);
• +6 points if your program correctly detect whether the minotaur lies somewhere on the path to the exit, and correctly detects when the answer is "DEAD";
• +3 points if you make advanced variation (which should be posted as a separate file) - no specific advanced task given here, use your imagination (alright, here is an example: how about writing to the file the length of the shortest path?).

Note that although this assignment is graded on 10 points as assignment 1 was, it will be weighted less than the latter. Indeed assignment 1 required a significant amount of additional work and will be worth more. (Probably 65% for assignment 1 and 35% for assignment 2 - but will be adjusted in favor of students.)

Reading the file

The file will be formatted in this way:

###########
          #
# # ### # #
# # # # # #
# ### # # #
#   # # # #
# ### ### #
# #M      #
# ##### # #
#     # #  
###########

The entrance is the white square in the first column of the second row; the exit is in the last column of the first to last row. The maze may or may not contain a M for the minotaur. For clarity, though these characters S and E will not in the file, the starting point is marked S in the following example and exit is marked E:

###########
S         #
# # ### # #
# # # # # #
# ### # # #
#   # # # #
# ### ### #
# #M      #
# ##### # #
#     # # E
###########

This maze will be contained in file "maze.txt": you must open the file, read its lines, and create a variable maze that contains a list of list in the following format (be careful this is not the same as was asked in Lecture 27):

[[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, -1],
 [-1,  0, -1,  0, -1, -1, -1,  0, -1,  0, -1],
 [-1,  0, -1,  0, -1,  0, -1,  0, -1,  0, -1],
 [-1,  0, -1, -1, -1,  0, -1,  0, -1,  0, -1],
 [-1,  0,  0,  0, -1,  0, -1,  0, -1,  0, -1],
 [-1,  0, -1, -1, -1,  0, -1, -1, -1,  0, -1],
 [-1,  0, -1,  0,  0,  0,  0,  0,  0,  0, -1],
 [-1,  0, -1, -1, -1, -1, -1,  0, -1,  0, -1],
 [-1,  0,  0,  0,  0,  0, -1,  0, -1,  0,  0],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]]

We will refer to individual squares/coordinates as cells of the maze.

Above, I have created a newline for each sublist because that is more readable, but Python will print out the above matrix in the following way:

[[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1], [-1, 0, -1, 0, -1, -1, -1, 0, -1, 0, -1], [-1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1], [-1, 0, -1, -1, -1, 0, -1, 0, -1, 0, -1], [-1, 0, 0, 0, -1, 0, -1, 0, -1, 0, -1], [-1, 0, -1, -1, -1, 0, -1, -1, -1, 0, -1], [-1, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1], [-1, 0, -1, -1, -1, -1, -1, 0, -1, 0, -1], [-1, 0, 0, 0, 0, 0, -1, 0, -1, 0, 0], [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]]

Flood Fill algorithm

You will use a simple version of the Flood Fill algorithm. In this algorithm, we throw a metaphorical bucket of paint at the starting point and we let the paint flow and see if it ever reaches the exit. (This is the same method that is used in drawing program, when you use the bucket of paint to fill a closed shape.)

Here is how you will apply this Flood Fill algorithm; say that you have a source_color (an integer) and a dest_color (an integer):

• set the starting cell to the dest_color
• do a nested for loop iterating over the indices of the columns, and the indices of the row
• so we look at every cell: suppose the current cell is in row r and column c, if the cell directly above (if it exists) or the cell directly left (if it exists) (or the right, or below, etc.) is either equal to dest_color, then if the current cell is equal to source_color then we change it to dest_color
• we repeat this operation as many time as the max of the height and width of the grid

You will define a function flood_fill which will not return anything, but will modify the list maze:

def flood_fill(maze, start_row, start_column, source_color, dest_color):
  ...

For instance, using the variable maze given above (see below for what START_ROW and START_COLUMN are):

>>> flood_fill(maze, START_ROW, START_COLUMN, 0, 1)
>>> print maze
[[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
 [ 1,  1,  1,  1,  1,  1,  1,  1,  1,  1, -1],
 [-1,  1, -1,  1, -1, -1, -1,  1, -1,  1, -1],
 [-1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1],
 [-1,  1, -1, -1, -1,  1, -1,  1, -1,  1, -1],
 [-1,  1,  1,  1, -1,  1, -1,  1, -1,  1, -1],
 [-1,  1, -1, -1, -1,  1, -1, -1, -1,  1, -1],
 [-1,  1, -1,  1,  1,  1,  1,  1,  1,  1, -1],
 [-1,  1, -1, -1, -1, -1, -1,  1, -1,  1, -1],
 [-1,  1,  1,  1,  1,  1, -1,  1, -1,  1,  1],
 [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]]

(I have put every sub-list on a different line, in truth Python would print a mess without going to the line.)

To make sure you have implemented this algorithm correctly, you should try it out on the example I just gave, to see if you obtain the same matrix in the end.

Solving the maze

Solving the maze will involve doing several flood fills.

• at the beginning the exit cell contains a 0;
• flood_fill(maze, START_ROW, START_COLUMN, 0, 1)
• if the exit cell now contains a 1, then there is a path from the entrance to the exit, that does not have to go through the minotaur;
• if the exit cell still contains a 0, then either there is no path from the entrance to the exit, or this path goes through a minotaur (which has a different value, so it since the first flood fill only changes cells that are originally 0, it will not "walk over" the minotaur).

To understand how to solve the minotaur question (which is difficult), you might need to look at the picture below with a drawing program such as MS Paint on Windows, or Paintbrush on Mac OS X. In these drawing programs, open the picture below, and try to use the "Paint Bucket" tool to color the exit, BUT only clicking near the entrance. Using a clever sequence of "Paint Bucket" fills, you should be able to color the exit in the same color as the entrance (both of them red).

Using constants

For this assignment, you are forbidden to use hard-coded values. Hard-coded values are when you are told to use, for instance, the value -1 to represent a wall, and you use -1 everywhere in your code.

You can instead, at the very top of your Python code file, define a constant.

Constants are variables that you are never supposed to change, once they have been assigned for the first time. It is useful (and a pretty widespread convention) to use ALL CAPITAL LETTERS for the names of constants.

WALL = -1
MINOTAUR = 2
...

And then whenever you would use -1 in reference to a wall, you instead use the constant WALL. For instance, if you had written, something like this:

if ch == "#":
  line_lst.append(-1)

you would instead write:

if ch == "#":
  line_lst.append(WALL)

Another good example, is that the start and end position should also be expressed as constants:

START_ROW = 1
START_COLUMN = 0
END_ROW =...
...

Or the color fills above should be coded using constants as well. For instance, when you do the first flood fill, you should use a constant, for instance WALKED_1...

Here are a few advantages of this approach:

• readibility: if you use constants properly, your code will be much easier to understand when other people read it (or when you read it a few days, or weeks later, when you are no longer familiar with the specific details of the code);
• convenience: using the value -1 for walls does not make much sense, so it is not impossible that you might make a few mistakes, and sometimes type 1 when you mean -1 (or something else, like get it confused with 0 the value for corridors); in this case, your program is not going to work, and it is going to be very difficult to find where the error is coming from - but using constants will save you from making this kind of mistake;
• flexibility: using constants makes it easier to modify your code if you ever need to change how it works - what if we decide to later code walls by -10 - if we were using hard-coded values (that means, using -1 everywhere), we would have to careful go over the code to change everything - and probably forget some; with a constant, you would just have to change its value, and everywhere you use it will automatically use the new value.

Using constants instead of hard-coded values is one of several techniques that improve code legibility, which is probably one of the most important skills a computer programmer should have - and one that is sorely lacking from a lot of professional programmers (which greatly hinders their performance).

Annex: test mazes

Below are some test mazes. All these mazes can be solved (and should return "ALIVE"). It is your responsibility to modify them, and add some blocking walls or a minotaur to test whether your program works correctly in the other situations.

• 10x10 maze
• 10x50 maze
• 50x10 maze
• 30x30 maze
• 100x100 maze
• 150x150 maze

Annex: code to draw a maze

The following code might be useful to draw a maze with the turtle module. It needs you to have correctly loaded the maze, and also to have correctly defined the constant WALL (see above for details about constants).

This visualization function should help you debug your program if it does not work (much like PythonTutor helps you find out what is wrong in previous programs).

Its limitation is that it does not: a) draw progress (when you are flooding the maze), and b) draw the minotaur. These are features you could add yourself. Consult the documentation for turtle.fillcolor to find out how you can change the color of the squares (for instance to do a red square for the minotaur, a gray square for cells you have walked on, etc.)

def square(side, filled=False):
  import turtle
  if filled:
    turtle.fill(True)
    for i in range(4):
      turtle.fd(side)
      turtle.rt(90)
    turtle.fill(False)

def draw_maze_turtle(maze):
  import turtle
  side = 10
  turtle.reset()
  turtle.speed("fastest")
  turtle.ht()
  for i in range(len(maze)):
    for j in range(len(maze[0])):
      square(side, maze[i][j] == WALL)
      turtle.pu()
      turtle.fd(side)
      turtle.pd()
    turtle.pu()
    turtle.rt(180)
    turtle.fd(len(maze[0])*side)
    turtle.lt(90)
    turtle.fd(side)
    turtle.lt(90)
    turtle.pd()
  turtle.done()