Lab 05: A Maze Without Walls (part 1)

In this puzzle, you are given a grid of numbers, presented as a list of lists. the number in each grid square tells you how many steps you can move in one direction. For example, from a square with a number 2, you can move two squares up, two squares down, two square right, or two squares left. The goal, like in a maze is get from a start position to an end position.

Represent the Puzzle

When dealing with a list of lists, if can get a little confusing about how to access individual elements. If we have L = [[1,2], 3,4] , then L[0][1] is 2 . The first index is the row, starting from zero. Increasing this index moves down the grid (this is also how matrices are indexed). The second index is the column number, starting at zero. As a result, it makes sense to indicate a position in the grid using a tuple (r, c) , where r is the row and c is the column.

We will build a puzzle class with the following ADT.

onboard(position) - return True if the (r,c)-pair position is within the bounds of the grid. Return False otherwise.

__getitem__(position) - return the number stored in the (r,c)-pair position .

rdsolve(start, end) - return True if it is possible to get from the position start to the position end using only right and down moves. Return False otherwise.

solve(start, end) - return True if it is possible to get from the position start to the position end . Return False otherwise.

Start by writing a class called Puzzle and store it in a file called puzzle.py . Write an __init__method that takes a list of lists of integers. It should store these lists internally. The initializer shouldraise ValueError if the lists do not all have the same length (only rectangular puzzles are allowed).

Next, implement the onboard method to check if a given row and column (given as a tuple of ints) is within the bounds of the input lists.

__getitem__ is great! Often, we know roughly how we want code to work, before we write it. In this case, we want to make

a puzzle and then we'd like to look at the cells using a nice notation. We'd like code like the following to work.

 puz = Puzzle([[1,1,2],[1,1,0]]) assert(puz[0,2] == 2) 

Note, we're putting the row and column in the square brackets. Python automatically turns pairs like that into tuples, so puz[0,2] is the same as writing puz[(0,2)] , but it looks nicer without the parentheses. To use square brackets with your own classes, you implement a magic method called__getitem__ . Here is a toy example.

 class Foo: def __getitem__(self, index): 

 return index + 1 

 f = Foo() print(f[139]) print(f[2.14]) 

In our case, the type of index will be tuple and it will have both a row and a column. A nice way to unpack a tuple is to do the following.

 mytuple = (5, 12, 13) side1, side2, hypotenuse = mytuple 

The above assignment creates three variables and assigns them the values of the three elements of the tuple. In the case of row and column positions as tuples, we might write r, c = position . This splits the tuple into two variables and is much cleaner than using indices: position[0] and p osition[1] .

The Only Right and Down Version

To warm, up we're going to solve the problem when it's only allowed to move right and down. This will be computed in the rdsolve method that tests if there exists a path from start to end using only right and down moves.

As with all recursive algorithms, start with the base case. Don't forget that you're stuck if you land on a zero that is not the end.

Now, the heart of any recursive solution is the realization that the problem can be reduced to a smaller instance of the same problem. In this case, there are two possible positions you can get to from the start position (by moving right or down). If there is a solution from either of these positions, then there is a solution from start. This is a natural choice for recursion.

Memoize

Now, implement solve . This will be trickier than rdsolve because there is no chance of getting stuck in a loop if you only move right and down. We will want to have a way to make sure that we don't get into the recursion version of an infinite loop (which generally results in a RecursionError ). A handy trick to solve this problem is to store a set that has all the positions we have already visited. Then, each time we visit a new cell, we add it to the set. Each time we make a recursive call, we pass along this set of visited positions. (Be careful to modify the set rather than making copies.) If the start position is already in the visited set, we need not continue our search.

This approach is called memoization. That's not a typo. See the recursion chapter of the book for more info.

The solve method will take the visited set as an argument. The default value should be set to N one .

Important: The following is bad. Don't do it.

 def solve(self, start, end, visited = set()): ... 

The use of visited = set() is a common mistake. It might seem like a handy way to initialize vis ited to an empty set, but it doesn't work twice. The problem is that this initialization happens only when the function is defined and not every time the function is called without the visitedargument. The second time it is called, it will reuse the set from the previous call and you generally don't want that. Instead, set the default to None and initialize visited to an empty set if it is None

.

A note about testing exceptions

Since the __init__ method should raise an exception if the input list of lists is not square, you might be curious to know how to test this.

In the supplied test code you will find the following test.

 def testinitcheckforrect(self): with self.assertRaises(ValueError): 

 Puzzle([[1,2], [1,2,3]]) 

This test uses the with keyword. This is an example of a context manager. The idea is to introduce a block of code where some other code is guaranteed to be executed before and afterwards. In this case, the assertRaises function gives a context manager that will catch the expected exception and signal a failed test if it doesn't find it. The test passes if the exception is raised.

You will also see context managers when reading files. In that case, the context manager is used to make sure that files are closed properly after being opened.

Summary

For this lab, you should implement all the methods in the puzzle ADT given above. The methods sol ve and rdsolve should be recursive and should run in linear time.