Starter Code:

import random

# DO NOT modify any code in this class!

class Maze(): '''The actual grid of the maze that we are trying to solve.''' MINVAL = 0 # default MAXVAL = 9 # default WALL_CHAR = "*"

def __init__(self, rows, cols): self._rows = rows self._cols = cols self._minval = Maze.MINVAL self._maxval = Maze.MAXVAL

# Testing method - the 2D list representing the maze can be set externally to facilitate testing def _set_maze(self, lst): self._maze = lst

def init_random(self, minval=MINVAL, maxval=MAXVAL): '''Initialize with random values. Optionally pass the min and max values for point values.''' # 2D array: rows,cols self._maze = [[random.randrange(minval, maxval) for i in range(self._cols)] for j in range(self._rows)] self._minval = minval self._maxval = maxval

def add_random_walls(self, percent_obstruction): '''Insert some random "walls" to make the maze non-trivial. The percent_obstruction (float in 0..1) determines the frequency of the walls in the maze. The more walls, the less winning paths and the less recursion will be needed for the solution. But it also means that some mazes will have no possible path from Start to Finish.'''

threshold = int((self._maxval - self._minval) * percent_obstruction) for row in range(self._rows): for col in range(self._cols): if self._maze[row][col]

def __repr__(self): return self._print_maze() def _print_maze(self, winningpath=list()): '''Prints out the grid with values, walls, start and finish squares. Optionally pass the winning list/path of tuples if you want the winning route to be show as '@' characters.''' result = " " for col in range(self._cols): # Add the column headers result += f" {col} " result += " " for row in range(self._rows): result += f" {row} " # Add the row header for col in range(self._cols): if (row, col) == self._start: result += " S " # Start square elif (row, col) == self._finish: result += " F " # Finish square elif (row, col) in winningpath: result += " @ " # Square in winning path else: result += f" {self._maze[row][col]} " # Value square return result + " "

def is_move_in_maze(self, row, col): '''Checks if the potential move is in the maze''' return row >= 0 and row = 0 and col

def is_wall(self, row, col): '''Is the given location a wall''' return self._maze[row][col] == self.WALL_CHAR

def make_move(self, row, col, path): '''Make the given move. Add the row,col to the path and return the value.''' path.append((row,col)) return self._maze[row][col]

def set_start_finish(self, start, finish): '''Set the start and finish squares in the maze''' if not self.is_move_in_maze(start[0], start[1]) or not self.is_move_in_maze(start[0], start[1]): raise RuntimeError("Start and Finish must be in the maze") if start == finish: raise RuntimeError("Start and Finish must be different locations") self._start = start self._finish = finish # Set the start and finish to 0 values self._maze[start[0]][start[1]] = 0 self._maze[finish[0]][finish[1]] = 0

def get_start(self): '''Get the starting square as a tuple''' return self._start

def get_finish(self): '''Get the finish square as a tuple''' return self._finish

import maze

class Game(): '''Holds the game solving logic. Initialize with a fully initialized maze'''

def __init__(self, maze): self._maze = maze

# Creating simple methods (like the next two) to abstract core parts # of your algorithm helps increase the readability of your code. # You will find these two useful in your solution.

def _is_move_available(self, row, col, path): '''If (row, col) is already in the solved path then it is not available''' return (row, col) not in path

def _is_puzzle_solved(self, row, col): '''Is the given row,col the finish square?''' return self._maze.get_finish() == (row, col)

######################################################## # TODO - Main recursive method. Add your algorithm here. def find_route(self, currow, curcol, curscore, curpath): pass

# This block of code will be useful in debugging your algorithm. But you still need # to create unittests to thoroughly testing your code. if __name__ == '__main__': # Here is how you create the maze. Pass the row,col size of the grid. grid = maze.Maze(3, 6) # You have TWO options for initializing the Value and Walls squares. # (1) init_random() and add_random_walls() # * Useful when developing your algorithm without having to create # different grids # * But not easy to use in testcases because you cannot preditably # know what the winning score and path will be each run # (2) _set_maze() # * You have to create the grid manually, but very useful in testing # (Please see the test_game.py file for an example of _set_maze()) grid.init_random(0,9) # Initialze to a random board grid.add_random_walls(0.2) # Make a certian percentage of the maze contain walls

# AFTER you have used one of the two above methods of initializing # the Values and Walls, you must set the Start Finish locations. start = (0,2) finish = (1,1) grid.set_start_finish(start, finish)

# Printing the starting grid for reference will help you in debugging. print(grid) # Print the maze for visual starting reference

# Now instatiate your Game algorithm class game = Game(grid) # Pass in the fully initialize maze grid

# Now initiate your recursize solution to solve the game! # Start from the start row, col... zero score and empty winning path score, path = game.find_route(start[0], start[1], 0, list()) print(f"The winning score is {score} with a path of {path}")

Mod 5 Homework - Recursion In this assignment, you will use recursion to solve a simple maze game. This game contains a two-dimensional grid of squares that serves as the maze. Each square in the maze is either a Point square (containing an integer value), a Wall square (denoted by " ), the Start square (" S ), or the Finish square (" F). The goal is to find the path from Start to Finish that gathers the most "points." The path cannot pass through a wall nor can it double back on itself. The path can only flow horizontally or vertically between two adjacent squares. The path cannot flow diagonally. Here is an example of simple 55 maze. We will use the notation of (row, col) to reference a given square. Notice the Start is at (0,1) and the Finish is as (0,3 and the walls are marked by asterisks. The row and column labels are also provided to help you reference the correct square but are not considered part of the maze. 01234023911S532413F7412832 Shown below is the best (and in this case, only) solution to this example maze. You can see the winning path marked by the @ character. If you count up all the point values originally occupied by the @ squares, the winning total is 49 (which is 5+2+3+9+1+3+1+4+7+3+8+2+1 ). Here is another example, this time a 33 maze that has three possible paths from Start to Finish. All three paths are valid, but the winning path is the one with the score of 16 . We will solve this puzzle using recursion, which allows the computer to try every permutation or possible path. The trick to writing a recursive function is to identify the "stop condition(s)" and then let your function try all options before reaching that stopping condition(s). You have been given the code for the Maze class (maze.py), complete with many attributes and methods that will be useful to your solution. You have also been given the shell of the Game class (game.py), which you will complete. An example test case is contained in test_game.py but you must add more test cases to ensure your recursive algorithm is correct for various edge cases. You can assume that the smallest maze will be 22, but mazes can be square or rectangular (e.g. 42,55,37 ). If the maze has no solution path from Start to Finish, your function should return a score of 1 and an empty List for the winning path. You must use recursion to find the best solution for any given maze