A Programmng Exercise in 40 characters or more

A Programmng Exercise in 40 charaters or more

1. randall davis, csail 1 Today What’s better than S 3 ? F 3 : your Free Food Finder R 3 : Representations, representations, reps… Efficiency consequences

2. Today’s task Think of F 3 as a game Moving around on a grid But the grid contents can change randall davis, csail 2

3. The game as graph search Nodes: current state of the entire game List of lists of strings Overall board, each row as a sublist Each string describes the contents of a square board1 = [["S", " ", " ", " ", "F "]] board2 = [ ["F", “ ", " ", " ", " "], ["W", "W", "S", "W", "F"], [" ", " ", " ", "W", " "], ] Goal state? randall davis, csail 3

4. Maze Description Language randall davis, csail 4 _______ _______ |L |_ __|___ | | L L _ L_|_|___L|| |||__| _|_ | |_| |L ___L | L_L_|| L__L__ ||L|_ |_| L | |__||| | _|| |L_L _ LL_||L || L__ L L _ |_L_||| |_____| |L__| _| L L _ |_||_ | L | | ___L LL |LL || |||___ |_L_ |L| ||L |__|L_ ||| | |L |L |_| |||||| L_L_ |L _||||||| L____L_|L_LL__L| | L |

5. find_path randall davis, csail 5 def find_path ( neighbors_function , start, goal_test ): """ Return the shortest path through a graph from a given starting state to any state that satisfies a given goal condition. Parameters: * neighbors_function (state) is a function which returns a list of legal neighbor states * start is the starting state for the search * goal_test (state) is a function which returns True if the given state is a goal state for the search, and False otherwise . Returns: a tuple of states showing the shortest path from start to a state satisfying goal_test (state), or None there none NOTE state representation is up to the caller, but it must be hashable . """

6. find_path randall davis, csail 6 if goal_test (start): return (start,) agenda = [(start,)] visited = {start} while agenda: this_path = agenda.pop (0) terminal_state = this_path [-1] for neighbor in neighbors_function ( terminal_state ): if neighbor not in visited: new_path = this_path + (neighbor,) if goal_test (neighbor): return new_path agenda.append ( new_path ) visited.add (neighbor)

7. randall davis, csail 7 def make_state_from_board (board): pass def goal(state): pass def neighbors(state): pass start = make_state_from_board ( initial_board ) path = find_path (neighbors, start, goal)

8. randall davis, csail 8 def neighbors(state): possible_moves = [(1, 0), [-1 ,0], [0,1], [0,-1]] return [ move(state, dr , dc) for dr,dc in possible_moves if can_move (state, dr , dc) ] def can_move (state, dr , dc): r,c = find_student (state) newr,newc = r+dr,c+dc return 0<= newr < len (state) and 0<= newc < len (state[0]) and state[ newr ][ newc ] != 'W' return 0<= newr < len (state) and 0<= newc < len (state[0]) and state[ newr ][ newc ] != 'W'

9. randall davis, csail 9 def move(state, dr , dc): r,c = find_student (state) newr,newc = r+dr,c+dc next_board = [[v for v in row] for row in state] next_board [r][c] = ' ' next_board [ newr ][ newc ] = 'S' return make_state_from_board ( next_board )