import os
import sys
import doctest
if '.' not in sys.path:
sys.path.insert(0, '.')
from search import search
# NO OTHER IMPORTS!
##################################################
# Problem 1
##################################################
def mode(x):
# helper function to compute the mode of a list of values, assuming no ties
counts = {i: x.count(i) for i in set(x)}
return max(counts, key=counts.get)
def grid_mode(x):
height = len(x)
width = len(x[0])
def get_neighbors(r, c):
# helper to find the locations of all of the valid neighbors of a cell,
# implemented as a generator (but other implementations would be fine,
# too)
for dr in range(-1, 2):
for dc in range(-1, 2):
nr, nc = r+dr, c+dc
if 0 <= nr < height and 0 <= nc < width:
yield (nr, nc)
# create a new grid of the same size, where the value at each location is
# the mode computed from the original grid
return [[mode([x[nr][nc] for nr, nc in get_neighbors(r, c)]) for c in range(width)] for r in range(height)]
##################################################
# Problem 2
##################################################
def setup_bus_catcher(start_location, bus_schedule_function):
# in order to solve this problem with the search function as written, we
# need to track the time as part of the state as well. so our states here
# will be (r, c, time).
start_state = start_location + (0,)
directions = tuple((r, c) for r in range(-1, 2) for c in range(-1, 2))
def successors(state):
# given this representation, we compute successors by adding 1 to time
# (always) and considering all possible directions we could move)
r, c, t = state
return [(r+dr, c+dc, t+1) for dr, dc in directions]
def goal_test(state):
# check to see if the (r, c) location at this state corresponds to
# where the bus is at the time in this state
return state[:-1] == bus_schedule_function(state[-1])
return successors, start_state, goal_test
def interpret_result(path):
# since we need to return a list of (r, c) tuples, strip the time off of
# each state in the returned path
return [i[:2] for i in path] if path is not None else path
def catch_bus(start_location, bus_schedule_function):
result = search(*setup_bus_catcher(start_location, bus_schedule_function))
return interpret_result(result)
##################################################
# Problem 3
##################################################
with open(os.path.join(os.path.dirname(__file__), 'words.txt')) as f:
ALL_WORDS = {i.strip() for i in f}
def words_at_location(board, loc):
out = set()
height = len(board)
width = len(board[0])
longest_word = max(len(i) for i in ALL_WORDS)
def get_word(locs):
# given a list of locations, return the word represented by that path
# in the current board
return ''.join(board[r][c] for r, c in locs)
def get_neighbors(r, c):
# helper to get neighbors of a given location in the grid
for dr in range(-1, 2):
for dc in range(-1, 2):
nr, nc = r+dr, c+dc
if 0 <= nr < height and 0 <= nc < width:
yield (nr, nc)
def all_paths(start):
# helper function to find _all_ paths through the space with no
# repeats. this is very similar to the graph search process we used
# for pathfinding, but now we can't keep a visited set; and we only
# want to exclude paths if they contain the same location more than
# once.
#
# note that we also cut off the process when we see a path that is
# longer than the longest valid word, but that optimization is not
# necessary.
agenda = [(start,)]
while agenda:
cur_path = agenda.pop()
end = cur_path[-1]
w = get_word(cur_path)
if w in ALL_WORDS:
out.add(w)
if len(cur_path) < longest_word:
for n in get_neighbors(*end):
if n in cur_path:
continue
agenda.append(cur_path + (n,))
all_paths(loc)
return out
if __name__ == "__main__":
doctest.testmod()