This should be worked using Python.  The code will be given and you edit some section and write the report.

There are .zip file and the word files what I attached below. 

.zip file is coded file. You should edit some section following instruction. 

The word file include the instruction for the work and  the form of report. 

Though the word file is 6 pages, the most of content is attached picture and the form of report and well- explained to do easily

You should give me code file as .zip and the report following the form. 

homework_1_search/autograder.py
# autograder.py
# ————-
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).

# imports from python standard library
import grading
import imp
import optparse
import os
import re
import sys
import projectParams
import random
random.seed(0)
try:
from pacman import GameState
except:
pass
# register arguments and set default values
def readCommand(argv):
parser = optparse.OptionParser(description = ‘Run public tests on student code’)
parser.set_defaults(generateSolutions=False, edxOutput=False, gsOutput=False, muteOutput=False, printTestCase=False, noGraphics=False)
parser.add_option(‘–test-directory’,
dest = ‘testRoot’,
default = ‘test_cases’,
help = ‘Root test directory which contains subdirectories corresponding to each question’)
parser.add_option(‘–student-code’,
dest = ‘studentCode’,
default = projectParams.STUDENT_CODE_DEFAULT,
help = ‘comma separated list of student code files’)
parser.add_option(‘–code-directory’,
dest = ‘codeRoot’,
default = “”,
help = ‘Root directory containing the student and testClass code’)
parser.add_option(‘–test-case-code’,
dest = ‘testCaseCode’,
default = projectParams.PROJECT_TEST_CLASSES,
help = ‘class containing testClass classes for this project’)
parser.add_option(‘–generate-solutions’,
dest = ‘generateSolutions’,
action = ‘store_true’,
help = ‘Write solutions generated to .solution file’)
parser.add_option(‘–edx-output’,
dest = ‘edxOutput’,
action = ‘store_true’,
help = ‘Generate edX output files’)
parser.add_option(‘–gradescope-output’,
dest = ‘gsOutput’,
action = ‘store_true’,
help = ‘Generate GradeScope output files’)
parser.add_option(‘–mute’,
dest = ‘muteOutput’,
action = ‘store_true’,
help = ‘Mute output from executing tests’)
parser.add_option(‘–print-tests’, ‘-p’,
dest = ‘printTestCase’,
action = ‘store_true’,
help = ‘Print each test case before running them.’)
parser.add_option(‘–test’, ‘-t’,
dest = ‘runTest’,
default = None,
help = ‘Run one particular test. Relative to test root.’)
parser.add_option(‘–question’, ‘-q’,
dest = ‘gradeQuestion’,
default = None,
help = ‘Grade one particular question.’)
parser.add_option(‘–no-graphics’,
dest = ‘noGraphics’,
action = ‘store_true’,
help = ‘No graphics display for pacman games.’)
(options, args) = parser.parse_args(argv)
return options

# confirm we should author solution files
def confirmGenerate():
print(‘WARNING: this action will overwrite any solution files.’)
print(‘Are you sure you want to proceed? (yes/no)’)
while True:
ans = sys.stdin.readline().strip()
if ans == ‘yes’:
break
elif ans == ‘no’:
sys.exit(0)
else:
print(‘please answer either “yes” or “no”‘)

# TODO: Fix this so that it tracebacks work correctly
# Looking at source of the traceback module, presuming it works
# the same as the intepreters, it uses co_filename. This is,
# however, a readonly attribute.
def setModuleName(module, filename):
functionType = type(confirmGenerate)
classType = type(optparse.Option)
for i in dir(module):
o = getattr(module, i)
if hasattr(o, ‘__file__’): continue
if type(o) == functionType:
setattr(o, ‘__file__’, filename)
elif type(o) == classType:
setattr(o, ‘__file__’, filename)
# TODO: assign member __file__’s?
#print(i, type(o))

#from cStringIO import StringIO
def loadModuleString(moduleSource):
# Below broken, imp doesn’t believe its being passed a file:
# ValueError: load_module arg#2 should be a file or None
#
#f = StringIO(moduleCodeDict[k])
#tmp = imp.load_module(k, f, k, (“.py”, “r”, imp.PY_SOURCE))
tmp = imp.new_module(k)
exec(moduleCodeDict[k] in tmp.__dict__)
setModuleName(tmp, k)
return tmp
import py_compile
def loadModuleFile(moduleName, filePath):
with open(filePath, ‘r’) as f:
return imp.load_module(moduleName, f, “%s.py” % moduleName, (“.py”, “r”, imp.PY_SOURCE))

def readFile(path, root=””):
“Read file from disk at specified path and return as string”
with open(os.path.join(root, path), ‘r’) as handle:
return handle.read()

#######################################################################
# Error Hint Map
#######################################################################
# TODO: use these
ERROR_HINT_MAP = {
‘q1’: {
““: “””
We noticed that your project threw an IndexError on q1.
While many things may cause this, it may have been from
assuming a certain number of successors from a state space
or assuming a certain number of actions available from a given
state. Try making your code more general (no hardcoded indices)
and submit again!
“””
},
‘q3’: {
““: “””
We noticed that your project threw an AttributeError on q3.
While many things may cause this, it may have been from assuming
a certain size or structure to the state space. For example, if you have
a line of code assuming that the state is (x, y) and we run your code
on a state space with (x, y, z), this error could be thrown. Try
making your code more general and submit again!
“””
}
}
import pprint
def splitStrings(d):
d2 = dict(d)
for k in d:
if k[0:2] == “__”:
del d2[k]
continue
if d2[k].find(“\n”) >= 0:
d2[k] = d2[k].split(“\n”)
return d2

def printTest(testDict, solutionDict):
pp = pprint.PrettyPrinter(indent=4)
print(“Test case:”)
for line in testDict[“__raw_lines__”]:
print(” |”, line)
print(“Solution:”)
for line in solutionDict[“__raw_lines__”]:
print(” |”, line)

def runTest(testName, moduleDict, printTestCase=False, display=None):
import testParser
import testClasses
for module in moduleDict:
setattr(sys.modules[__name__], module, moduleDict[module])
testDict = testParser.TestParser(testName + “.test”).parse()
solutionDict = testParser.TestParser(testName + “.solution”).parse()
test_out_file = os.path.join(‘%s.test_output’ % testName)
testDict[‘test_out_file’] = test_out_file
testClass = getattr(projectTestClasses, testDict[‘class’])
questionClass = getattr(testClasses, ‘Question’)
question = questionClass({‘max_points’: 0}, display)
testCase = testClass(question, testDict)
if printTestCase:
printTest(testDict, solutionDict)
# This is a fragile hack to create a stub grades object
grades = grading.Grades(projectParams.PROJECT_NAME, [(None,0)])
testCase.execute(grades, moduleDict, solutionDict)

# returns all the tests you need to run in order to run question
def getDepends(testParser, testRoot, question):
allDeps = [question]
questionDict = testParser.TestParser(os.path.join(testRoot, question, ‘CONFIG’)).parse()
if ‘depends’ in questionDict:
depends = questionDict[‘depends’].split()
for d in depends:
# run dependencies first
allDeps = getDepends(testParser, testRoot, d) + allDeps
return allDeps
# get list of questions to grade
def getTestSubdirs(testParser, testRoot, questionToGrade):
problemDict = testParser.TestParser(os.path.join(testRoot, ‘CONFIG’)).parse()
if questionToGrade != None:
questions = getDepends(testParser, testRoot, questionToGrade)
if len(questions) > 1:
print(‘Note: due to dependencies, the following tests will be run: %s’ % ‘ ‘.join(questions))
return questions
if ‘order’ in problemDict:
return problemDict[‘order’].split()
return sorted(os.listdir(testRoot))

# evaluate student code
def evaluate(generateSolutions, testRoot, moduleDict, exceptionMap=ERROR_HINT_MAP,
edxOutput=False, muteOutput=False, gsOutput=False,
printTestCase=False, questionToGrade=None, display=None):
# imports of testbench code. note that the testClasses import must follow
# the import of student code due to dependencies
import testParser
import testClasses
for module in moduleDict:
setattr(sys.modules[__name__], module, moduleDict[module])
questions = []
questionDicts = {}
test_subdirs = getTestSubdirs(testParser, testRoot, questionToGrade)
for q in test_subdirs:
subdir_path = os.path.join(testRoot, q)
if not os.path.isdir(subdir_path) or q[0] == ‘.’:
continue
# create a question object
questionDict = testParser.TestParser(os.path.join(subdir_path, ‘CONFIG’)).parse()
questionClass = getattr(testClasses, questionDict[‘class’])
question = questionClass(questionDict, display)
questionDicts[q] = questionDict
# load test cases into question
tests = filter(lambda t: re.match(‘[^#~.].*\.test\Z’, t), os.listdir(subdir_path))
tests = map(lambda t: re.match(‘(.*)\.test\Z’, t).group(1), tests)
for t in sorted(tests):
test_file = os.path.join(subdir_path, ‘%s.test’ % t)
solution_file = os.path.join(subdir_path, ‘%s.solution’ % t)
test_out_file = os.path.join(subdir_path, ‘%s.test_output’ % t)
testDict = testParser.TestParser(test_file).parse()
if testDict.get(“disabled”, “false”).lower() == “true”:
continue
testDict[‘test_out_file’] = test_out_file
testClass = getattr(projectTestClasses, testDict[‘class’])
testCase = testClass(question, testDict)
def makefun(testCase, solution_file):
if generateSolutions:
# write solution file to disk
return lambda grades: testCase.writeSolution(moduleDict, solution_file)
else:
# read in solution dictionary and pass as an argument
testDict = testParser.TestParser(test_file).parse()
solutionDict = testParser.TestParser(solution_file).parse()
if printTestCase:
return lambda grades: printTest(testDict, solutionDict) or testCase.execute(grades, moduleDict, solutionDict)
else:
return lambda grades: testCase.execute(grades, moduleDict, solutionDict)
question.addTestCase(testCase, makefun(testCase, solution_file))
# Note extra function is necessary for scoping reasons
def makefun(question):
return lambda grades: question.execute(grades)
setattr(sys.modules[__name__], q, makefun(question))
questions.append((q, question.getMaxPoints()))
grades = grading.Grades(projectParams.PROJECT_NAME, questions,
gsOutput=gsOutput, edxOutput=edxOutput, muteOutput=muteOutput)
if questionToGrade == None:
for q in questionDicts:
for prereq in questionDicts[q].get(‘depends’, ”).split():
grades.addPrereq(q, prereq)
grades.grade(sys.modules[__name__], bonusPic = projectParams.BONUS_PIC)
return grades.points

def getDisplay(graphicsByDefault, options=None):
graphics = graphicsByDefault
if options is not None and options.noGraphics:
graphics = False
if graphics:
try:
import graphicsDisplay
return graphicsDisplay.PacmanGraphics(1, frameTime=.05)
except ImportError:
pass
import textDisplay
return textDisplay.NullGraphics()

if __name__ == ‘__main__’:
options = readCommand(sys.argv)
if options.generateSolutions:
confirmGenerate()
codePaths = options.studentCode.split(‘,’)
# moduleCodeDict = {}
# for cp in codePaths:
# moduleName = re.match(‘.*?([^/]*)\.py’, cp).group(1)
# moduleCodeDict[moduleName] = readFile(cp, root=options.codeRoot)
# moduleCodeDict[‘projectTestClasses’] = readFile(options.testCaseCode, root=options.codeRoot)
# moduleDict = loadModuleDict(moduleCodeDict)
moduleDict = {}
for cp in codePaths:
moduleName = re.match(‘.*?([^/]*)\.py’, cp).group(1)
moduleDict[moduleName] = loadModuleFile(moduleName, os.path.join(options.codeRoot, cp))
moduleName = re.match(‘.*?([^/]*)\.py’, options.testCaseCode).group(1)
moduleDict[‘projectTestClasses’] = loadModuleFile(moduleName, os.path.join(options.codeRoot, options.testCaseCode))

if options.runTest != None:
runTest(options.runTest, moduleDict, printTestCase=options.printTestCase, display=getDisplay(True, options))
else:
evaluate(options.generateSolutions, options.testRoot, moduleDict,
gsOutput=options.gsOutput,
edxOutput=options.edxOutput, muteOutput=options.muteOutput, printTestCase=options.printTestCase,
questionToGrade=options.gradeQuestion, display=getDisplay(options.gradeQuestion!=None, options))

homework_1_search/commands.txt
python pacman.py
python pacman.py –layout testMaze –pacman GoWestAgent
python pacman.py –layout tinyMaze –pacman GoWestAgent
python pacman.py -h
python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch
python pacman.py -l tinyMaze -p SearchAgent
python pacman.py -l mediumMaze -p SearchAgent
python pacman.py -l bigMaze -z .5 -p SearchAgent
python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5
python eightpuzzle.py
python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5
python pacman.py -l testSearch -p AStarFoodSearchAgent
python pacman.py -l trickySearch -p AStarFoodSearchAgent
python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

homework_1_search/eightpuzzle.py
# eightpuzzle.py
# ————–
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).

import search
import random
# Module Classes
class EightPuzzleState:
“””
The Eight Puzzle is described in the course textbook on
page 64.
This class defines the mechanics of the puzzle itself. The
task of recasting this puzzle as a search problem is left to
the EightPuzzleSearchProblem class.
“””
def __init__( self, numbers ):
“””
Constructs a new eight puzzle from an ordering of numbers.
numbers: a list of integers from 0 to 8 representing an
instance of the eight puzzle. 0 represents the blank
space. Thus, the list
[1, 0, 2, 3, 4, 5, 6, 7, 8]
represents the eight puzzle:
————-
| 1 | | 2 |
————-
| 3 | 4 | 5 |
————-
| 6 | 7 | 8 |
————
The configuration of the puzzle is stored in a 2-dimensional
list (a list of lists) ‘cells’.
“””
self.cells = []
numbers = numbers[:] # Make a copy so as not to cause side-effects.
numbers.reverse()
for row in range( 3 ):
self.cells.append( [] )
for col in range( 3 ):
self.cells[row].append( numbers.pop() )
if self.cells[row][col] == 0:
self.blankLocation = row, col
def isGoal( self ):
“””
Checks to see if the puzzle is in its goal state.
————-
| | 1 | 2 |
————-
| 3 | 4 | 5 |
————-
| 6 | 7 | 8 |
————-
>>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).isGoal()
True
>>> EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).isGoal()
False
“””
current = 0
for row in range( 3 ):
for col in range( 3 ):
if current != self.cells[row][col]:
return False
current += 1
return True
def legalMoves( self ):
“””
Returns a list of legal moves from the current state.
Moves consist of moving the blank space up, down, left or right.
These are encoded as ‘up’, ‘down’, ‘left’ and ‘right’ respectively.
>>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]).legalMoves()
[‘down’, ‘right’]
“””
moves = []
row, col = self.blankLocation
if(row != 0):
moves.append(‘up’)
if(row != 2):
moves.append(‘down’)
if(col != 0):
moves.append(‘left’)
if(col != 2):
moves.append(‘right’)
return moves
def result(self, move):
“””
Returns a new eightPuzzle with the current state and blankLocation
updated based on the provided move.
The move should be a string drawn from a list returned by legalMoves.
Illegal moves will raise an exception, which may be an array bounds
exception.
NOTE: This function *does not* change the current object. Instead,
it returns a new object.
“””
row, col = self.blankLocation
if(move == ‘up’):
newrow = row – 1
newcol = col
elif(move == ‘down’):
newrow = row + 1
newcol = col
elif(move == ‘left’):
newrow = row
newcol = col – 1
elif(move == ‘right’):
newrow = row
newcol = col + 1
else:
raise “Illegal Move”
# Create a copy of the current eightPuzzle
newPuzzle = EightPuzzleState([0, 0, 0, 0, 0, 0, 0, 0, 0])
newPuzzle.cells = [values[:] for values in self.cells]
# And update it to reflect the move
newPuzzle.cells[row][col] = self.cells[newrow][newcol]
newPuzzle.cells[newrow][newcol] = self.cells[row][col]
newPuzzle.blankLocation = newrow, newcol
return newPuzzle
# Utilities for comparison and display
def __eq__(self, other):
“””
Overloads ‘==’ such that two eightPuzzles with the same configuration
are equal.
>>> EightPuzzleState([0, 1, 2, 3, 4, 5, 6, 7, 8]) == \
EightPuzzleState([1, 0, 2, 3, 4, 5, 6, 7, 8]).result(‘left’)
True
“””
for row in range( 3 ):
if self.cells[row] != other.cells[row]:
return False
return True
def __hash__(self):
return hash(str(self.cells))
def __getAsciiString(self):
“””
Returns a display string for the maze
“””
lines = []
horizontalLine = (‘-‘ * (13))
lines.append(horizontalLine)
for row in self.cells:
rowLine = ‘|’
for col in row:
if col == 0:
col = ‘ ‘
rowLine = rowLine + ‘ ‘ + col.__str__() + ‘ |’
lines.append(rowLine)
lines.append(horizontalLine)
return ‘\n’.join(lines)
def __str__(self):
return self.__getAsciiString()
# TODO: Implement The methods in this class
class EightPuzzleSearchProblem(search.SearchProblem):
“””
Implementation of a SearchProblem for the Eight Puzzle domain
Each state is represented by an instance of an eightPuzzle.
“””
def __init__(self,puzzle):
“Creates a new EightPuzzleSearchProblem which stores search information.”
self.puzzle = puzzle
def getStartState(self):
return puzzle
def isGoalState(self,state):
return state.isGoal()
def getSuccessors(self,state):
“””
Returns list of (successor, action, stepCost) pairs where
each succesor is either left, right, up, or down
from the original state and the cost is 1.0 for each
“””
succ = []
for a in state.legalMoves():
succ.append((state.result(a), a, 1))
return succ
def getCostOfActions(self, actions):
“””
actions: A list of actions to take
This method returns the total cost of a particular sequence of actions. The sequence must
be composed of legal moves
“””
return len(actions)
EIGHT_PUZZLE_DATA = [[1, 0, 2, 3, 4, 5, 6, 7, 8],
[1, 7, 8, 2, 3, 4, 5, 6, 0],
[4, 3, 2, 7, 0, 5, 1, 6, 8],
[5, 1, 3, 4, 0, 2, 6, 7, 8],
[1, 2, 5, 7, 6, 8, 0, 4, 3],
[0, 3, 1, 6, 8, 2, 7, 5, 4]]
def loadEightPuzzle(puzzleNumber):
“””
puzzleNumber: The number of the eight puzzle to load.
Returns an eight puzzle object generated from one of the
provided puzzles in EIGHT_PUZZLE_DATA.
puzzleNumber can range from 0 to 5.
>>> print(loadEightPuzzle(0))
————-
| 1 | | 2 |
————-
| 3 | 4 | 5 |
————-
| 6 | 7 | 8 |
————-
“””
return EightPuzzleState(EIGHT_PUZZLE_DATA[puzzleNumber])
def createRandomEightPuzzle(moves=100):
“””
moves: number of random moves to apply
Creates a random eight puzzle by applying
a series of ‘moves’ random moves to a solved
puzzle.
“””
puzzle = EightPuzzleState([0,1,2,3,4,5,6,7,8])
for i in range(moves):
# Execute a random legal move
puzzle = puzzle.result(random.sample(puzzle.legalMoves(), 1)[0])
return puzzle
if __name__ == ‘__main__’:
puzzle = createRandomEightPuzzle(25)
print(‘A random puzzle:’)
print(puzzle)
problem = EightPuzzleSearchProblem(puzzle)
path = search.breadthFirstSearch(problem)
print(‘BFS found a path of %d moves: %s’ % (len(path), str(path)))
curr = puzzle
i = 1
for a in path:
curr = curr.result(a)
print(‘After %d move%s: %s’ % (i, (“”, “s”)[i>1], a))
print(curr)
input(“Press return for the next state…”) # wait for key stroke
i += 1

homework_1_search/game.py
# game.py
# ——-
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).

# game.py
# ——-
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html
from util import *
import time, os
import traceback
import sys
#######################
# Parts worth reading #
#######################
class Agent:
“””
An agent must define a getAction method, but may also define the
following methods which will be called if they exist:
def registerInitialState(self, state): # inspects the starting state
“””
def __init__(self, index=0):
self.index = index
def getAction(self, state):
“””
The Agent will receive a GameState (from either {pacman, capture, sonar}.py) and
must return an action from Directions.{North, South, East, West, Stop}
“””
raiseNotDefined()
class Directions:
NORTH = ‘North’
SOUTH = ‘South’
EAST = ‘East’
WEST = ‘West’
STOP = ‘Stop’
LEFT = {NORTH: WEST,
SOUTH: EAST,
EAST: NORTH,
WEST: SOUTH,
STOP: STOP}
RIGHT = dict([(y,x) for x, y in LEFT.items()])
REVERSE = {NORTH: SOUTH,
SOUTH: NORTH,
EAST: WEST,
WEST: EAST,
STOP: STOP}
class Configuration:
“””
A Configuration holds the (x,y) coordinate of a character, along with its
traveling direction.
The convention for positions, like a graph, is that (0,0) is the lower left corner, x increases
horizontally and y increases vertically. Therefore, north is the direction of increasing y, or (0,1).
“””
def __init__(self, pos, direction):
self.pos = pos
self.direction = direction
def getPosition(self):
return (self.pos)
def getDirection(self):
return self.direction
def isInteger(self):
x,y = self.pos
return x == int(x) and y == int(y)
def __eq__(self, other):
if other == None: return False
return (self.pos == other.pos and self.direction == other.direction)
def __hash__(self):
x = hash(self.pos)
y = hash(self.direction)
return hash(x + 13 * y)
def __str__(self):
return “(x,y)=”+str(self.pos)+”, “+str(self.direction)
def generateSuccessor(self, vector):
“””
Generates a new configuration reached by translating the current
configuration by the action vector. This is a low-level call and does
not attempt to respect the legality of the movement.
Actions are movement vectors.
“””
x, y= self.pos
dx, dy = vector
direction = Actions.vectorToDirection(vector)
if direction == Directions.STOP:
direction = self.direction # There is no stop direction
return Configuration((x + dx, y+dy), direction)
class AgentState:
“””
AgentStates hold the state of an agent (configuration, speed, scared, etc).
“””
def __init__( self, startConfiguration, isPacman ):
self.start = startConfiguration
self.configuration = startConfiguration
self.isPacman = isPacman
self.scaredTimer = 0
self.numCarrying = 0
self.numReturned = 0
def __str__( self ):
if self.isPacman:
return “Pacman: ” + str( self.configuration )
else:
return “Ghost: ” + str( self.configuration )
def __eq__( self, other ):
if other == None:
return False
return self.configuration == other.configuration and self.scaredTimer == other.scaredTimer
def __hash__(self):
return hash(hash(self.configuration) + 13 * hash(self.scaredTimer))
def copy( self ):
state = AgentState( self.start, self.isPacman )
state.configuration = self.configuration
state.scaredTimer = self.scaredTimer
state.numCarrying = self.numCarrying
state.numReturned = self.numReturned
return state
def getPosition(self):
if self.configuration == None: return None
return self.configuration.getPosition()
def getDirection(self):
return self.configuration.getDirection()
class Grid:
“””
A 2-dimensional array of objects backed by a list of lists. Data is accessed
via grid[x][y] where (x,y) are positions on a Pacman map with x horizontal,
y vertical and the origin (0,0) in the bottom left corner.
The __str__ method constructs an output that is oriented like a pacman board.
“””
def __init__(self, width, height, initialValue=False, bitRepresentation=None):
if initialValue not in [False, True]: raise Exception(‘Grids can only contain booleans’)
self.CELLS_PER_INT = 30
self.width = width
self.height = height
self.data = [[initialValue for y in range(height)] for x in range(width)]
if bitRepresentation:
self._unpackBits(bitRepresentation)
def __getitem__(self, i):
return self.data[i]
def __setitem__(self, key, item):
self.data[key] = item
def __str__(self):
out = [[str(self.data[x][y])[0] for x in range(self.width)] for y in range(self.height)]
out.reverse()
return ‘\n’.join([”.join(x) for x in out])
def __eq__(self, other):
if other == None: return False
return self.data == other.data
def __hash__(self):
# return hash(str(self))
base = 1
h = 0
for l in self.data:
for i in l:
if i:
h += base
base *= 2
return hash(h)
def copy(self):
g = Grid(self.width, self.height)
g.data = [x[:] for x in self.data]
return g
def deepCopy(self):
return self.copy()
def shallowCopy(self):
g = Grid(self.width, self.height)
g.data = self.data
return g
def count(self, item =True ):
return sum([x.count(item) for x in self.data])
def asList(self, key = True):
list = []
for x in range(self.width):
for y in range(self.height):
if self[x][y] == key: list.append( (x,y) )
return list
def packBits(self):
“””
Returns an efficient int list representation
(width, height, bitPackedInts…)
“””
bits = [self.width, self.height]
currentInt = 0
for i in range(self.height * self.width):
bit = self.CELLS_PER_INT – (i % self.CELLS_PER_INT) – 1
x, y = self._cellIndexToPosition(i)
if self[x][y]:
currentInt += 2 ** bit
if (i + 1) % self.CELLS_PER_INT == 0:
bits.append(currentInt)
currentInt = 0
bits.append(currentInt)
return tuple(bits)
def _cellIndexToPosition(self, index):
x = index // self.height
y = index % self.height
return x, y
def _unpackBits(self, bits):
“””
Fills in data from a bit-level representation
“””
cell = 0
for packed in bits:
for bit in self._unpackInt(packed, self.CELLS_PER_INT):
if cell == self.width * self.height: break
x, y = self._cellIndexToPosition(cell)
self[x][y] = bit
cell += 1
def _unpackInt(self, packed, size):
bools = []
if packed < 0: raise ValueError("must be a positive integer") for i in range(size): n = 2 ** (self.CELLS_PER_INT - i - 1) if packed >= n:
bools.append(True)
packed -= n
else:
bools.append(False)
return bools
def reconstituteGrid(bitRep):
if type(bitRep) is not type((1,2)):
return bitRep
width, height = bitRep[:2]
return Grid(width, height, bitRepresentation= bitRep[2:])
####################################
# Parts you shouldn’t have to read #
####################################
class Actions:
“””
A collection of static methods for manipulating move actions.
“””
# Directions
_directions = {Directions.NORTH: (0, 1),
Directions.SOUTH: (0, -1),
Directions.EAST: (1, 0),
Directions.WEST: (-1, 0),
Directions.STOP: (0, 0)}
_directionsAsList = _directions.items()
TOLERANCE = .001
def reverseDirection(action):
if action == Directions.NORTH:
return Directions.SOUTH
if action == Directions.SOUTH:
return Directions.NORTH
if action == Directions.EAST:
return Directions.WEST
if action == Directions.WEST:
return Directions.EAST
return action
reverseDirection = staticmethod(reverseDirection)
def vectorToDirection(vector):
dx, dy = vector
if dy > 0:
return Directions.NORTH
if dy < 0: return Directions.SOUTH if dx < 0: return Directions.WEST if dx > 0:
return Directions.EAST
return Directions.STOP
vectorToDirection = staticmethod(vectorToDirection)
def directionToVector(direction, speed = 1.0):
dx, dy = Actions._directions[direction]
return (dx * speed, dy * speed)
directionToVector = staticmethod(directionToVector)
def getPossibleActions(config, walls):
possible = []
x, y = config.pos
x_int, y_int = int(x + 0.5), int(y + 0.5)
# In between grid points, all agents must continue straight
if (abs(x – x_int) + abs(y – y_int) > Actions.TOLERANCE):
return [config.getDirection()]
for dir, vec in Actions._directionsAsList:
dx, dy = vec
next_y = y_int + dy
next_x = x_int + dx
if not walls[next_x][next_y]: possible.append(dir)
return possible
getPossibleActions = staticmethod(getPossibleActions)
def getLegalNeighbors(position, walls):
x,y = position
x_int, y_int = int(x + 0.5), int(y + 0.5)
neighbors = []
for dir, vec in Actions._directionsAsList:
dx, dy = vec
next_x = x_int + dx
if next_x < 0 or next_x == walls.width: continue next_y = y_int + dy if next_y < 0 or next_y == walls.height: continue if not walls[next_x][next_y]: neighbors.append((next_x, next_y)) return neighbors getLegalNeighbors = staticmethod(getLegalNeighbors) def getSuccessor(position, action): dx, dy = Actions.directionToVector(action) x, y = position return (x + dx, y + dy) getSuccessor = staticmethod(getSuccessor) class GameStateData: """ """ def __init__( self, prevState = None ): """ Generates a new data packet by copying information from its predecessor. """ if prevState != None: self.food = prevState.food.shallowCopy() self.capsules = prevState.capsules[:] self.agentStates = self.copyAgentStates( prevState.agentStates ) self.layout = prevState.layout self._eaten = prevState._eaten self.score = prevState.score self._foodEaten = None self._foodAdded = None self._capsuleEaten = None self._agentMoved = None self._lose = False self._win = False self.scoreChange = 0 def deepCopy( self ): state = GameStateData( self ) state.food = self.food.deepCopy() state.layout = self.layout.deepCopy() state._agentMoved = self._agentMoved state._foodEaten = self._foodEaten state._foodAdded = self._foodAdded state._capsuleEaten = self._capsuleEaten return state def copyAgentStates( self, agentStates ): copiedStates = [] for agentState in agentStates: copiedStates.append( agentState.copy() ) return copiedStates def __eq__( self, other ): """ Allows two states to be compared. """ if other == None: return False # TODO Check for type of other if not self.agentStates == other.agentStates: return False if not self.food == other.food: return False if not self.capsules == other.capsules: return False if not self.score == other.score: return False return True def __hash__( self ): """ Allows states to be keys of dictionaries. """ for i, state in enumerate( self.agentStates ): try: int(hash(state)) except TypeError as e: print(e) #hash(state) return int((hash(tuple(self.agentStates)) + 13*hash(self.food) + 113* hash(tuple(self.capsules)) + 7 * hash(self.score)) % 1048575 ) def __str__( self ): width, height = self.layout.width, self.layout.height map = Grid(width, height) if type(self.food) == type((1,2)): self.food = reconstituteGrid(self.food) for x in range(width): for y in range(height): food, walls = self.food, self.layout.walls map[x][y] = self._foodWallStr(food[x][y], walls[x][y]) for agentState in self.agentStates: if agentState == None: continue if agentState.configuration == None: continue x,y = [int( i ) for i in nearestPoint( agentState.configuration.pos )] agent_dir = agentState.configuration.direction if agentState.isPacman: map[x][y] = self._pacStr( agent_dir ) else: map[x][y] = self._ghostStr( agent_dir ) for x, y in self.capsules: map[x][y] = 'o' return str(map) + ("\nScore: %d\n" % self.score) def _foodWallStr( self, hasFood, hasWall ): if hasFood: return '.' elif hasWall: return '%' else: return ' ' def _pacStr( self, dir ): if dir == Directions.NORTH: return 'v' if dir == Directions.SOUTH: return '^' if dir == Directions.WEST: return '>‘
return ‘<' def _ghostStr( self, dir ): return 'G' if dir == Directions.NORTH: return 'M' if dir == Directions.SOUTH: return 'W' if dir == Directions.WEST: return '3' return 'E' def initialize( self, layout, numGhostAgents ): """ Creates an initial game state from a layout array (see layout.py). """ self.food = layout.food.copy() #self.capsules = [] self.capsules = layout.capsules[:] self.layout = layout self.score = 0 self.scoreChange = 0 self.agentStates = [] numGhosts = 0 for isPacman, pos in layout.agentPositions: if not isPacman: if numGhosts == numGhostAgents: continue # Max ghosts reached already else: numGhosts += 1 self.agentStates.append( AgentState( Configuration( pos, Directions.STOP), isPacman) ) self._eaten = [False for a in self.agentStates] try: import boinc _BOINC_ENABLED = True except: _BOINC_ENABLED = False class Game: """ The Game manages the control flow, soliciting actions from agents. """ def __init__( self, agents, display, rules, startingIndex=0, muteAgents=False, catchExceptions=False ): self.agentCrashed = False self.agents = agents self.display = display self.rules = rules self.startingIndex = startingIndex self.gameOver = False self.muteAgents = muteAgents self.catchExceptions = catchExceptions self.moveHistory = [] self.totalAgentTimes = [0 for agent in agents] self.totalAgentTimeWarnings = [0 for agent in agents] self.agentTimeout = False import io self.agentOutput = [io.StringIO() for agent in agents] def getProgress(self): if self.gameOver: return 1.0 else: return self.rules.getProgress(self) def _agentCrash( self, agentIndex, quiet=False): "Helper method for handling agent crashes" if not quiet: traceback.print_exc() self.gameOver = True self.agentCrashed = True self.rules.agentCrash(self, agentIndex) OLD_STDOUT = None OLD_STDERR = None def mute(self, agentIndex): if not self.muteAgents: return global OLD_STDOUT, OLD_STDERR import io OLD_STDOUT = sys.stdout OLD_STDERR = sys.stderr sys.stdout = self.agentOutput[agentIndex] sys.stderr = self.agentOutput[agentIndex] def unmute(self): if not self.muteAgents: return global OLD_STDOUT, OLD_STDERR # Revert stdout/stderr to originals sys.stdout = OLD_STDOUT sys.stderr = OLD_STDERR def run( self ): """ Main control loop for game play. """ self.display.initialize(self.state.data) self.numMoves = 0 ###self.display.initialize(self.state.makeObservation(1).data) # inform learning agents of the game start for i in range(len(self.agents)): agent = self.agents[i] if not agent: self.mute(i) # this is a null agent, meaning it failed to load # the other team wins print("Agent %d failed to load" % i, file=sys.stderr) self.unmute() self._agentCrash(i, quiet=True) return if ("registerInitialState" in dir(agent)): self.mute(i) if self.catchExceptions: try: timed_func = TimeoutFunction(agent.registerInitialState, int(self.rules.getMaxStartupTime(i))) try: start_time = time.time() timed_func(self.state.deepCopy()) time_taken = time.time() - start_time self.totalAgentTimes[i] += time_taken except TimeoutFunctionException: print("Agent %d ran out of time on startup!" % i, file=sys.stderr) self.unmute() self.agentTimeout = True self._agentCrash(i, quiet=True) return except Exception as data: self._agentCrash(i, quiet=False) self.unmute() return else: agent.registerInitialState(self.state.deepCopy()) ## TODO: could this exceed the total time self.unmute() agentIndex = self.startingIndex numAgents = len( self.agents ) while not self.gameOver: # Fetch the next agent agent = self.agents[agentIndex] move_time = 0 skip_action = False # Generate an observation of the state if 'observationFunction' in dir( agent ): self.mute(agentIndex) if self.catchExceptions: try: timed_func = TimeoutFunction(agent.observationFunction, int(self.rules.getMoveTimeout(agentIndex))) try: start_time = time.time() observation = timed_func(self.state.deepCopy()) except TimeoutFunctionException: skip_action = True move_time += time.time() - start_time self.unmute() except Exception as data: self._agentCrash(agentIndex, quiet=False) self.unmute() return else: observation = agent.observationFunction(self.state.deepCopy()) self.unmute() else: observation = self.state.deepCopy() # Solicit an action action = None self.mute(agentIndex) if self.catchExceptions: try: timed_func = TimeoutFunction(agent.getAction, int(self.rules.getMoveTimeout(agentIndex)) - int(move_time)) try: start_time = time.time() if skip_action: raise TimeoutFunctionException() action = timed_func( observation ) except TimeoutFunctionException: print("Agent %d timed out on a single move!" % agentIndex, file=sys.stderr) self.agentTimeout = True self._agentCrash(agentIndex, quiet=True) self.unmute() return move_time += time.time() - start_time if move_time > self.rules.getMoveWarningTime(agentIndex):
self.totalAgentTimeWarnings[agentIndex] += 1
print(“Agent %d took too long to make a move! This is warning %d” % (agentIndex, self.totalAgentTimeWarnings[agentIndex]), file=sys.stderr)
if self.totalAgentTimeWarnings[agentIndex] > self.rules.getMaxTimeWarnings(agentIndex):
print(“Agent %d exceeded the maximum number of warnings: %d” % (agentIndex, self.totalAgentTimeWarnings[agentIndex]), file=sys.stderr)
self.agentTimeout = True
self._agentCrash(agentIndex, quiet=True)
self.unmute()
return
self.totalAgentTimes[agentIndex] += move_time
#print(“Agent: %d, time: %f, total: %f” % (agentIndex, move_time, self.totalAgentTimes[agentIndex]))
if self.totalAgentTimes[agentIndex] > self.rules.getMaxTotalTime(agentIndex):
print(“Agent %d ran out of time! (time: %1.2f)” % (agentIndex, self.totalAgentTimes[agentIndex]), file=sys.stderr)
self.agentTimeout = True
self._agentCrash(agentIndex, quiet=True)
self.unmute()
return
self.unmute()
except Exception as data:
self._agentCrash(agentIndex)
self.unmute()
return
else:
action = agent.getAction(observation)
self.unmute()
# Execute the action
self.moveHistory.append( (agentIndex, action) )
if self.catchExceptions:
try:
self.state = self.state.generateSuccessor( agentIndex, action )
except Exception as data:
self.mute(agentIndex)
self._agentCrash(agentIndex)
self.unmute()
return
else:
self.state = self.state.generateSuccessor( agentIndex, action )
# Change the display
self.display.update( self.state.data )
###idx = agentIndex – agentIndex % 2 + 1
###self.display.update( self.state.makeObservation(idx).data )
# Allow for game specific conditions (winning, losing, etc.)
self.rules.process(self.state, self)
# Track progress
if agentIndex == numAgents + 1: self.numMoves += 1
# Next agent
agentIndex = ( agentIndex + 1 ) % numAgents
if _BOINC_ENABLED:
boinc.set_fraction_done(self.getProgress())
# inform a learning agent of the game result
for agentIndex, agent in enumerate(self.agents):
if “final” in dir( agent ) :
try:
self.mute(agentIndex)
agent.final( self.state )
self.unmute()
except Exception as data:
if not self.catchExceptions: raise data
self._agentCrash(agentIndex)
self.unmute()
return
self.display.finish()

homework_1_search/ghostAgents.py
# ghostAgents.py
# ————–
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).

from game import Agent
from game import Actions
from game import Directions
import random
from util import manhattanDistance
import util
class GhostAgent( Agent ):
def __init__( self, index ):
self.index = index
def getAction( self, state ):
dist = self.getDistribution(state)
if len(dist) == 0:
return Directions.STOP
else:
return util.chooseFromDistribution( dist )
def getDistribution(self, state):
“Returns a Counter encoding a distribution over actions from the provided state.”
util.raiseNotDefined()
class RandomGhost( GhostAgent ):
“A ghost that chooses a legal action uniformly at random.”
def getDistribution( self, state ):
dist = util.Counter()
for a in state.getLegalActions( self.index ): dist[a] = 1.0
dist.normalize()
return dist
class DirectionalGhost( GhostAgent ):
“A ghost that prefers to rush Pacman, or flee when scared.”
def __init__( self, index, prob_attack=0.8, prob_scaredFlee=0.8 ):
self.index = index
self.prob_attack = prob_attack
self.prob_scaredFlee = prob_scaredFlee
def getDistribution( self, state ):
# Read variables from state
ghostState = state.getGhostState( self.index )
legalActions = state.getLegalActions( self.index )
pos = state.getGhostPosition( self.index )
isScared = ghostState.scaredTimer > 0
speed = 1
if isScared: speed = 0.5
actionVectors = [Actions.directionToVector( a, speed ) for a in legalActions]
newPositions = [( pos[0]+a[0], pos[1]+a[1] ) for a in actionVectors]
pacmanPosition = state.getPacmanPosition()
# Select best actions given the state
distancesToPacman = [manhattanDistance( pos, pacmanPosition ) for pos in newPositions]
if isScared:
bestScore = max( distancesToPacman )
bestProb = self.prob_scaredFlee
else:
bestScore = min( distancesToPacman )
bestProb = self.prob_attack
bestActions = [action for action, distance in zip( legalActions, distancesToPacman ) if distance == bestScore]
# Construct distribution
dist = util.Counter()
for a in bestActions: dist[a] = bestProb / len(bestActions)
for a in legalActions: dist[a] += ( 1-bestProb ) / len(legalActions)
dist.normalize()
return dist

homework_1_search/grading.py
# grading.py
# ———-
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).

“Common code for autograders”
import cgi
import time
import sys
import json
import traceback
import pdb
from collections import defaultdict
import util
class Grades:
“A data structure for project grades, along with formatting code to display them”
def __init__(self, projectName, questionsAndMaxesList,
gsOutput=False, edxOutput=False, muteOutput=False):
“””
Defines the grading scheme for a project
projectName: project name
questionsAndMaxesDict: a list of (question name, max points per question)
“””
self.questions = [el[0] for el in questionsAndMaxesList]
self.maxes = dict(questionsAndMaxesList)
self.points = Counter()
self.messages = dict([(q, []) for q in self.questions])
self.project = projectName
self.start = time.localtime()[1:6]
self.sane = True # Sanity checks
self.currentQuestion = None # Which question we’re grading
self.edxOutput = edxOutput
self.gsOutput = gsOutput # GradeScope output
self.mute = muteOutput
self.prereqs = defaultdict(set)
#print(‘Autograder transcript for %s’ % self.project)
print(‘Starting on %d-%d at %d:%02d:%02d’ % self.start)
def addPrereq(self, question, prereq):
self.prereqs[question].add(prereq)
def grade(self, gradingModule, exceptionMap = {}, bonusPic = False):
“””
Grades each question
gradingModule: the module with all the grading functions (pass in with sys.modules[__name__])
“””
completedQuestions = set([])
for q in self.questions:
print(‘\nQuestion %s’ % q)
print(‘=’ * (9 + len(q)))
print
self.currentQuestion = q
incompleted = self.prereqs[q].difference(completedQuestions)
if len(incompleted) > 0:
prereq = incompleted.pop()
print(
“””*** NOTE: Make sure to complete Question %s before working on Question %s,
*** because Question %s builds upon your answer for Question %s.
“”” % (prereq, q, q, prereq))
continue
if self.mute: util.mutePrint()
try:
util.TimeoutFunction(getattr(gradingModule, q),1800)(self) # Call the question’s function
#TimeoutFunction(getattr(gradingModule, q),1200)(self) # Call the question’s function
except Exception as inst:
self.addExceptionMessage(q, inst, traceback)
self.addErrorHints(exceptionMap, inst, q[1])
except:
self.fail(‘FAIL: Terminated with a string exception.’)
finally:
if self.mute: util.unmutePrint()
if self.points[q] >= self.maxes[q]:
completedQuestions.add(q)
print(‘\n### Question %s: %d/%d ###\n’ % (q, self.points[q], self.maxes[q]))

print(‘\nFinished at %d:%02d:%02d’ % time.localtime()[3:6])
print(“\nProvisional grades\n==================”)
for q in self.questions:
print(‘Question %s: %d/%d’ % (q, self.points[q], self.maxes[q]))
print(‘——————‘)
print(‘Total: %d/%d’ % (self.points.totalCount(), sum(self.maxes.values())))
if bonusPic and self.points.totalCount() == 25:
print(“””
ALL HAIL GRANDPAC.
LONG LIVE THE GHOSTBUSTING KING.
— —- —
| \ / + \ / |
| + \–/ \–/ + |
| + + |
| + + + |
@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
\ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
\ / @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
V \ @@@@@@@@@@@@@@@@@@@@@@@@@@@@
\ / @@@@@@@@@@@@@@@@@@@@@@@@@@
V @@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@
/\ @@@@@@@@@@@@@@@@@@@@@@
/ \ @@@@@@@@@@@@@@@@@@@@@@@@@
/\ / @@@@@@@@@@@@@@@@@@@@@@@@@@@
/ \ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
/ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@
“””)
print(“””
Your grades are NOT yet registered. To register your grades, make sure
to follow your instructor’s guidelines to receive credit on your project.
“””)
if self.edxOutput:
self.produceOutput()
if self.gsOutput:
self.produceGradeScopeOutput()
def addExceptionMessage(self, q, inst, traceback):
“””
Method to format the exception message, this is more complicated because
we need to cgi.escape the traceback but wrap the exception in a

 tag
    """
    self.fail('FAIL: Exception raised: %s' % inst)
    self.addMessage('')
    for line in traceback.format_exc().split('\n'):
        self.addMessage(line)
  def addErrorHints(self, exceptionMap, errorInstance, questionNum):
    typeOf = str(type(errorInstance))
    questionName = 'q' + questionNum
    errorHint = ''
    # question specific error hints
    if exceptionMap.get(questionName):
      questionMap = exceptionMap.get(questionName)
      if (questionMap.get(typeOf)):
        errorHint = questionMap.get(typeOf)
    # fall back to general error messages if a question specific
    # one does not exist
    if (exceptionMap.get(typeOf)):
      errorHint = exceptionMap.get(typeOf)
    # dont include the HTML if we have no error hint
    if not errorHint:
      return ''
    for line in errorHint.split('\n'):
      self.addMessage(line)
  def produceGradeScopeOutput(self):
    out_dct = {}
    # total of entire submission
    total_possible = sum(self.maxes.values())
    total_score = sum(self.points.values())
    out_dct['score'] = total_score
    out_dct['max_score'] = total_possible
    out_dct['output'] = "Total score (%d / %d)" % (total_score, total_possible)
    # individual tests
    tests_out = []
    for name in self.questions:
      test_out = {}
      # test name
      test_out['name'] = name
      # test score
      test_out['score'] = self.points[name]
      test_out['max_score'] = self.maxes[name]
      # others
      is_correct = self.points[name] >= self.maxes[name]
      test_out['output'] = "  Question {num} ({points}/{max}) {correct}".format(
          num=(name[1] if len(name) == 2 else name),
          points=test_out['score'],
          max=test_out['max_score'],
          correct=('X' if not is_correct else ''),
      )
      test_out['tags'] = []
      tests_out.append(test_out)
    out_dct['tests'] = tests_out
    # file output
    with open('gradescope_response.json', 'w') as outfile:
        json.dump(out_dct, outfile)
    return
  def produceOutput(self):
    edxOutput = open('edx_response.html', 'w')
    edxOutput.write("
")
    # first sum
    total_possible = sum(self.maxes.values())
    total_score = sum(self.points.values())
    checkOrX = ''
    if (total_score >= total_possible):
        checkOrX = ''
    header = """
        

            Total score ({total_score} / {total_possible})
        
    """.format(total_score = total_score,
      total_possible = total_possible,
      checkOrX = checkOrX
    )
    edxOutput.write(header)
    for q in self.questions:
      if len(q) == 2:
          name = q[1]
      else:
          name = q
      checkOrX = ''
      if (self.points[q] >= self.maxes[q]):
        checkOrX = ''
      #messages = '\n
\n'.join(self.messages[q])
      messages = "
%s
" % '\n'.join(self.messages[q])

      output = """



            Question {q} ({points}/{max}) {checkOrX}
          

          {messages}
        

      """.format(q = name,

        max = self.maxes[q],

        messages = messages,

        checkOrX = checkOrX,

        points = self.points[q]

      )

      # print("*** output for Question %s " % q[1])

      # print(output)

      edxOutput.write(output)

    edxOutput.write("
")

    edxOutput.close()

    edxOutput = open('edx_grade', 'w')

    edxOutput.write(str(self.points.totalCount()))

    edxOutput.close()

  def fail(self, message, raw=False):

    "Sets sanity check bit to false and outputs a message"

    self.sane = False

    self.assignZeroCredit()

    self.addMessage(message, raw)

  def assignZeroCredit(self):

    self.points[self.currentQuestion] = 0

  def addPoints(self, amt):

    self.points[self.currentQuestion] += amt

  def deductPoints(self, amt):

    self.points[self.currentQuestion] -= amt

  def assignFullCredit(self, message="", raw=False):

    self.points[self.currentQuestion] = self.maxes[self.currentQuestion]

    if message != "":

      self.addMessage(message, raw)

  def addMessage(self, message, raw=False):

    if not raw:

        # We assume raw messages, formatted for HTML, are printed separately

        if self.mute: util.unmutePrint()

        print('*** ' + message)

        if self.mute: util.mutePrint()

        message = cgi.escape(message)

    self.messages[self.currentQuestion].append(message)

  def addMessageToEmail(self, message):

    print("WARNING**** addMessageToEmail is deprecated %s" % message)

    for line in message.split('\n'):

      pass

      #print('%%% ' + line + ' %%%')

      #self.messages[self.currentQuestion].append(line)
class Counter(dict):

  """

  Dict with default 0

  """

  def __getitem__(self, idx):

    try:

      return dict.__getitem__(self, idx)

    except KeyError:

      return 0

  def totalCount(self):

    """

    Returns the sum of counts for all keys.

    """

    return sum(self.values())
homework_1_search/graphicsDisplay.py

# graphicsDisplay.py

# ------------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
from graphicsUtils import *

import math, time

from game import Directions

###########################

#  GRAPHICS DISPLAY CODE  #

###########################

# Most code by Dan Klein and John Denero written or rewritten for cs188, UC Berkeley.

# Some code from a Pacman implementation by LiveWires, and used / modified with permission.

DEFAULT_GRID_SIZE = 30.0

INFO_PANE_HEIGHT = 35

BACKGROUND_COLOR = formatColor(0,0,0)

WALL_COLOR = formatColor(0.0/255.0, 51.0/255.0, 255.0/255.0)

INFO_PANE_COLOR = formatColor(.4,.4,0)

SCORE_COLOR = formatColor(.9, .9, .9)

PACMAN_OUTLINE_WIDTH = 2

PACMAN_CAPTURE_OUTLINE_WIDTH = 4

GHOST_COLORS = []

GHOST_COLORS.append(formatColor(.9,0,0)) # Red

GHOST_COLORS.append(formatColor(0,.3,.9)) # Blue

GHOST_COLORS.append(formatColor(.98,.41,.07)) # Orange

GHOST_COLORS.append(formatColor(.1,.75,.7)) # Green

GHOST_COLORS.append(formatColor(1.0,0.6,0.0)) # Yellow

GHOST_COLORS.append(formatColor(.4,0.13,0.91)) # Purple

TEAM_COLORS = GHOST_COLORS[:2]

GHOST_SHAPE = [

    ( 0,    0.3 ),

    ( 0.25, 0.75 ),

    ( 0.5,  0.3 ),

    ( 0.75, 0.75 ),

    ( 0.75, -0.5 ),

    ( 0.5,  -0.75 ),

    (-0.5,  -0.75 ),

    (-0.75, -0.5 ),

    (-0.75, 0.75 ),

    (-0.5,  0.3 ),

    (-0.25, 0.75 )

  ]

GHOST_SIZE = 0.65

SCARED_COLOR = formatColor(1,1,1)

GHOST_VEC_COLORS = [colorToVector(c) for c in GHOST_COLORS]

PACMAN_COLOR = formatColor(255.0/255.0,255.0/255.0,61.0/255)

PACMAN_SCALE = 0.5

#pacman_speed = 0.25

# Food

FOOD_COLOR = formatColor(1,1,1)

FOOD_SIZE = 0.1

# Laser

LASER_COLOR = formatColor(1,0,0)

LASER_SIZE = 0.02

# Capsule graphics

CAPSULE_COLOR = formatColor(1,1,1)

CAPSULE_SIZE = 0.25

# Drawing walls

WALL_RADIUS = 0.15

class InfoPane:

    def __init__(self, layout, gridSize):

        self.gridSize = gridSize

        self.width = (layout.width) * gridSize

        self.base = (layout.height + 1) * gridSize

        self.height = INFO_PANE_HEIGHT

        self.fontSize = 24

        self.textColor = PACMAN_COLOR

        self.drawPane()

    def toScreen(self, pos, y = None):

        """

          Translates a point relative from the bottom left of the info pane.

        """

        if y == None:

            x,y = pos

        else:

            x = pos

        x = self.gridSize + x # Margin

        y = self.base + y

        return x,y

    def drawPane(self):

        self.scoreText = text( self.toScreen(0, 0  ), self.textColor, "SCORE:    0", "Times", self.fontSize, "bold")

    def initializeGhostDistances(self, distances):

        self.ghostDistanceText = []

        size = 20

        if self.width < 240:
            size = 12
        if self.width < 160:
            size = 10
        for i, d in enumerate(distances):
            t = text( self.toScreen(self.width//2 + self.width//8 * i, 0), GHOST_COLORS[i+1], d, "Times", size, "bold")
            self.ghostDistanceText.append(t)
    def updateScore(self, score):
        changeText(self.scoreText, "SCORE: % 4d" % score)
    def setTeam(self, isBlue):
        text = "RED TEAM"
        if isBlue: text = "BLUE TEAM"
        self.teamText = text( self.toScreen(300, 0  ), self.textColor, text, "Times", self.fontSize, "bold")
    def updateGhostDistances(self, distances):
        if len(distances) == 0: return
        if 'ghostDistanceText' not in dir(self): self.initializeGhostDistances(distances)
        else:
            for i, d in enumerate(distances):
                changeText(self.ghostDistanceText[i], d)
    def drawGhost(self):
        pass
    def drawPacman(self):
        pass
    def drawWarning(self):
        pass
    def clearIcon(self):
        pass
    def updateMessage(self, message):
        pass
    def clearMessage(self):
        pass

class PacmanGraphics:
    def __init__(self, zoom=1.0, frameTime=0.0, capture=False):
        self.have_window = 0
        self.currentGhostImages = {}
        self.pacmanImage = None
        self.zoom = zoom
        self.gridSize = DEFAULT_GRID_SIZE * zoom
        self.capture = capture
        self.frameTime = frameTime
    def checkNullDisplay(self):
        return False
    def initialize(self, state, isBlue = False):
        self.isBlue = isBlue
        self.startGraphics(state)
        # self.drawDistributions(state)
        self.distributionImages = None  # Initialized lazily
        self.drawStaticObjects(state)
        self.drawAgentObjects(state)
        # Information
        self.previousState = state
    def startGraphics(self, state):
        self.layout = state.layout
        layout = self.layout
        self.width = layout.width
        self.height = layout.height
        self.make_window(self.width, self.height)
        self.infoPane = InfoPane(layout, self.gridSize)
        self.currentState = layout
    def drawDistributions(self, state):
        walls = state.layout.walls
        dist = []
        for x in range(walls.width):
            distx = []
            dist.append(distx)
            for y in range(walls.height):
                ( screen_x, screen_y ) = self.to_screen( (x, y) )
                block = square( (screen_x, screen_y),
                                0.5 * self.gridSize,
                                color = BACKGROUND_COLOR,
                                filled = 1, behind=2)
                distx.append(block)
        self.distributionImages = dist
    def drawStaticObjects(self, state):
        layout = self.layout
        self.drawWalls(layout.walls)
        self.food = self.drawFood(layout.food)
        self.capsules = self.drawCapsules(layout.capsules)
        refresh()
    def drawAgentObjects(self, state):
        self.agentImages = [] # (agentState, image)
        for index, agent in enumerate(state.agentStates):
            if agent.isPacman:
                image = self.drawPacman(agent, index)
                self.agentImages.append( (agent, image) )
            else:
                image = self.drawGhost(agent, index)
                self.agentImages.append( (agent, image) )
        refresh()
    def swapImages(self, agentIndex, newState):
        """
          Changes an image from a ghost to a pacman or vis versa (for capture)
        """
        prevState, prevImage = self.agentImages[agentIndex]
        for item in prevImage: remove_from_screen(item)
        if newState.isPacman:
            image = self.drawPacman(newState, agentIndex)
            self.agentImages[agentIndex] = (newState, image )
        else:
            image = self.drawGhost(newState, agentIndex)
            self.agentImages[agentIndex] = (newState, image )
        refresh()
    def update(self, newState):
        agentIndex = newState._agentMoved
        agentState = newState.agentStates[agentIndex]
        if self.agentImages[agentIndex][0].isPacman != agentState.isPacman: self.swapImages(agentIndex, agentState)
        prevState, prevImage = self.agentImages[agentIndex]
        if agentState.isPacman:
            self.animatePacman(agentState, prevState, prevImage)
        else:
            self.moveGhost(agentState, agentIndex, prevState, prevImage)
        self.agentImages[agentIndex] = (agentState, prevImage)
        if newState._foodEaten != None:
            self.removeFood(newState._foodEaten, self.food)
        if newState._capsuleEaten != None:
            self.removeCapsule(newState._capsuleEaten, self.capsules)
        self.infoPane.updateScore(newState.score)
        if 'ghostDistances' in dir(newState):
            self.infoPane.updateGhostDistances(newState.ghostDistances)
    def make_window(self, width, height):
        grid_width = (width-1) * self.gridSize
        grid_height = (height-1) * self.gridSize
        screen_width = 2*self.gridSize + grid_width
        screen_height = 2*self.gridSize + grid_height + INFO_PANE_HEIGHT
        begin_graphics(screen_width,
                       screen_height,
                       BACKGROUND_COLOR,
                       "CS188 Pacman")
    def drawPacman(self, pacman, index):
        position = self.getPosition(pacman)
        screen_point = self.to_screen(position)
        endpoints = self.getEndpoints(self.getDirection(pacman))
        width = PACMAN_OUTLINE_WIDTH
        outlineColor = PACMAN_COLOR
        fillColor = PACMAN_COLOR
        if self.capture:
            outlineColor = TEAM_COLORS[index % 2]
            fillColor = GHOST_COLORS[index]
            width = PACMAN_CAPTURE_OUTLINE_WIDTH
        return [circle(screen_point, PACMAN_SCALE * self.gridSize,
                       fillColor = fillColor, outlineColor = outlineColor,
                       endpoints = endpoints,
                       width = width)]
    def getEndpoints(self, direction, position=(0,0)):
        x, y = position
        pos = x - int(x) + y - int(y)
        width = 30 + 80 * math.sin(math.pi* pos)
        delta = width / 2
        if (direction == 'West'):
            endpoints = (180+delta, 180-delta)
        elif (direction == 'North'):
            endpoints = (90+delta, 90-delta)
        elif (direction == 'South'):
            endpoints = (270+delta, 270-delta)
        else:
            endpoints = (0+delta, 0-delta)
        return endpoints
    def movePacman(self, position, direction, image):
        screenPosition = self.to_screen(position)
        endpoints = self.getEndpoints( direction, position )
        r = PACMAN_SCALE * self.gridSize
        moveCircle(image[0], screenPosition, r, endpoints)
        refresh()
    def animatePacman(self, pacman, prevPacman, image):
        if self.frameTime < 0:
            print('Press any key to step forward, "q" to play')
            keys = wait_for_keys()
            if 'q' in keys:
                self.frameTime = 0.1
        if self.frameTime > 0.01 or self.frameTime < 0:
            start = time.time()
            fx, fy = self.getPosition(prevPacman)
            px, py = self.getPosition(pacman)
            frames = 4.0
            for i in range(1,int(frames) + 1):
                pos = px*i/frames + fx*(frames-i)/frames, py*i/frames + fy*(frames-i)/frames
                self.movePacman(pos, self.getDirection(pacman), image)
                refresh()
                sleep(abs(self.frameTime) / frames)
        else:
            self.movePacman(self.getPosition(pacman), self.getDirection(pacman), image)
        refresh()
    def getGhostColor(self, ghost, ghostIndex):
        if ghost.scaredTimer > 0:

            return SCARED_COLOR

        else:

            return GHOST_COLORS[ghostIndex]

    def drawGhost(self, ghost, agentIndex):

        pos = self.getPosition(ghost)

        dir = self.getDirection(ghost)

        (screen_x, screen_y) = (self.to_screen(pos) )

        coords = []

        for (x, y) in GHOST_SHAPE:

            coords.append((x*self.gridSize*GHOST_SIZE + screen_x, y*self.gridSize*GHOST_SIZE + screen_y))

        colour = self.getGhostColor(ghost, agentIndex)

        body = polygon(coords, colour, filled = 1)

        WHITE = formatColor(1.0, 1.0, 1.0)

        BLACK = formatColor(0.0, 0.0, 0.0)

        dx = 0

        dy = 0

        if dir == 'North':

            dy = -0.2

        if dir == 'South':

            dy = 0.2

        if dir == 'East':

            dx = 0.2

        if dir == 'West':

            dx = -0.2

        leftEye = circle((screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2, WHITE, WHITE)

        rightEye = circle((screen_x+self.gridSize*GHOST_SIZE*(0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2, WHITE, WHITE)

        leftPupil = circle((screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08, BLACK, BLACK)

        rightPupil = circle((screen_x+self.gridSize*GHOST_SIZE*(0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08, BLACK, BLACK)

        ghostImageParts = []

        ghostImageParts.append(body)

        ghostImageParts.append(leftEye)

        ghostImageParts.append(rightEye)

        ghostImageParts.append(leftPupil)

        ghostImageParts.append(rightPupil)

        return ghostImageParts

    def moveEyes(self, pos, dir, eyes):

        (screen_x, screen_y) = (self.to_screen(pos) )

        dx = 0

        dy = 0

        if dir == 'North':

            dy = -0.2

        if dir == 'South':

            dy = 0.2

        if dir == 'East':

            dx = 0.2

        if dir == 'West':

            dx = -0.2

        moveCircle(eyes[0],(screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2)

        moveCircle(eyes[1],(screen_x+self.gridSize*GHOST_SIZE*(0.3+dx/1.5), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy/1.5)), self.gridSize*GHOST_SIZE*0.2)

        moveCircle(eyes[2],(screen_x+self.gridSize*GHOST_SIZE*(-0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08)

        moveCircle(eyes[3],(screen_x+self.gridSize*GHOST_SIZE*(0.3+dx), screen_y-self.gridSize*GHOST_SIZE*(0.3-dy)), self.gridSize*GHOST_SIZE*0.08)

    def moveGhost(self, ghost, ghostIndex, prevGhost, ghostImageParts):

        old_x, old_y = self.to_screen(self.getPosition(prevGhost))

        new_x, new_y = self.to_screen(self.getPosition(ghost))

        delta = new_x - old_x, new_y - old_y

        for ghostImagePart in ghostImageParts:

            move_by(ghostImagePart, delta)

        refresh()

        if ghost.scaredTimer > 0:

            color = SCARED_COLOR

        else:

            color = GHOST_COLORS[ghostIndex]

        edit(ghostImageParts[0], ('fill', color), ('outline', color))

        self.moveEyes(self.getPosition(ghost), self.getDirection(ghost), ghostImageParts[-4:])

        refresh()

    def getPosition(self, agentState):

        if agentState.configuration == None: return (-1000, -1000)

        return agentState.getPosition()

    def getDirection(self, agentState):

        if agentState.configuration == None: return Directions.STOP

        return agentState.configuration.getDirection()

    def finish(self):

        end_graphics()

    def to_screen(self, point):

        ( x, y ) = point

        #y = self.height - y

        x = (x + 1)*self.gridSize

        y = (self.height  - y)*self.gridSize

        return ( x, y )

    # Fixes some TK issue with off-center circles

    def to_screen2(self, point):

        ( x, y ) = point

        #y = self.height - y

        x = (x + 1)*self.gridSize

        y = (self.height  - y)*self.gridSize

        return ( x, y )

    def drawWalls(self, wallMatrix):

        wallColor = WALL_COLOR

        for xNum, x in enumerate(wallMatrix):

            if self.capture and (xNum * 2) < wallMatrix.width: wallColor = TEAM_COLORS[0]
            if self.capture and (xNum * 2) >= wallMatrix.width: wallColor = TEAM_COLORS[1]

            for yNum, cell in enumerate(x):

                if cell: # There's a wall here

                    pos = (xNum, yNum)

                    screen = self.to_screen(pos)

                    screen2 = self.to_screen2(pos)

                    # draw each quadrant of the square based on adjacent walls

                    wIsWall = self.isWall(xNum-1, yNum, wallMatrix)

                    eIsWall = self.isWall(xNum+1, yNum, wallMatrix)

                    nIsWall = self.isWall(xNum, yNum+1, wallMatrix)

                    sIsWall = self.isWall(xNum, yNum-1, wallMatrix)

                    nwIsWall = self.isWall(xNum-1, yNum+1, wallMatrix)

                    swIsWall = self.isWall(xNum-1, yNum-1, wallMatrix)

                    neIsWall = self.isWall(xNum+1, yNum+1, wallMatrix)

                    seIsWall = self.isWall(xNum+1, yNum-1, wallMatrix)

                    # NE quadrant

                    if (not nIsWall) and (not eIsWall):

                        # inner circle

                        circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (0,91), 'arc')

                    if (nIsWall) and (not eIsWall):

                        # vertical line

                        line(add(screen, (self.gridSize*WALL_RADIUS, 0)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(-0.5)-1)), wallColor)

                    if (not nIsWall) and (eIsWall):

                        # horizontal line

                        line(add(screen, (0, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5+1, self.gridSize*(-1)*WALL_RADIUS)), wallColor)

                    if (nIsWall) and (eIsWall) and (not neIsWall):

                        # outer circle

                        circle(add(screen2, (self.gridSize*2*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (180,271), 'arc')

                        line(add(screen, (self.gridSize*2*WALL_RADIUS-1, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5+1, self.gridSize*(-1)*WALL_RADIUS)), wallColor)

                        line(add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS+1)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(-0.5))), wallColor)

                    # NW quadrant

                    if (not nIsWall) and (not wIsWall):

                        # inner circle

                        circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (90,181), 'arc')

                    if (nIsWall) and (not wIsWall):

                        # vertical line

                        line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, 0)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(-0.5)-1)), wallColor)

                    if (not nIsWall) and (wIsWall):

                        # horizontal line

                        line(add(screen, (0, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5)-1, self.gridSize*(-1)*WALL_RADIUS)), wallColor)

                    if (nIsWall) and (wIsWall) and (not nwIsWall):

                        # outer circle

                        circle(add(screen2, (self.gridSize*(-2)*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (270,361), 'arc')

                        line(add(screen, (self.gridSize*(-2)*WALL_RADIUS+1, self.gridSize*(-1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5), self.gridSize*(-1)*WALL_RADIUS)), wallColor)

                        line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(-2)*WALL_RADIUS+1)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(-0.5))), wallColor)

                    # SE quadrant

                    if (not sIsWall) and (not eIsWall):

                        # inner circle

                        circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (270,361), 'arc')

                    if (sIsWall) and (not eIsWall):

                        # vertical line

                        line(add(screen, (self.gridSize*WALL_RADIUS, 0)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(0.5)+1)), wallColor)

                    if (not sIsWall) and (eIsWall):

                        # horizontal line

                        line(add(screen, (0, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5+1, self.gridSize*(1)*WALL_RADIUS)), wallColor)

                    if (sIsWall) and (eIsWall) and (not seIsWall):

                        # outer circle

                        circle(add(screen2, (self.gridSize*2*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (90,181), 'arc')

                        line(add(screen, (self.gridSize*2*WALL_RADIUS-1, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*0.5, self.gridSize*(1)*WALL_RADIUS)), wallColor)

                        line(add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS-1)), add(screen, (self.gridSize*WALL_RADIUS, self.gridSize*(0.5))), wallColor)

                    # SW quadrant

                    if (not sIsWall) and (not wIsWall):

                        # inner circle

                        circle(screen2, WALL_RADIUS * self.gridSize, wallColor, wallColor, (180,271), 'arc')

                    if (sIsWall) and (not wIsWall):

                        # vertical line

                        line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, 0)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(0.5)+1)), wallColor)

                    if (not sIsWall) and (wIsWall):

                        # horizontal line

                        line(add(screen, (0, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5)-1, self.gridSize*(1)*WALL_RADIUS)), wallColor)

                    if (sIsWall) and (wIsWall) and (not swIsWall):

                        # outer circle

                        circle(add(screen2, (self.gridSize*(-2)*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS)), WALL_RADIUS * self.gridSize-1, wallColor, wallColor, (0,91), 'arc')

                        line(add(screen, (self.gridSize*(-2)*WALL_RADIUS+1, self.gridSize*(1)*WALL_RADIUS)), add(screen, (self.gridSize*(-0.5), self.gridSize*(1)*WALL_RADIUS)), wallColor)

                        line(add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(2)*WALL_RADIUS-1)), add(screen, (self.gridSize*(-1)*WALL_RADIUS, self.gridSize*(0.5))), wallColor)

    def isWall(self, x, y, walls):

        if x < 0 or y < 0:
            return False
        if x >= walls.width or y >= walls.height:

            return False

        return walls[x][y]

    def drawFood(self, foodMatrix ):

        foodImages = []

        color = FOOD_COLOR

        for xNum, x in enumerate(foodMatrix):

            if self.capture and (xNum * 2) <= foodMatrix.width: color = TEAM_COLORS[0]
            if self.capture and (xNum * 2) > foodMatrix.width: color = TEAM_COLORS[1]

            imageRow = []

            foodImages.append(imageRow)

            for yNum, cell in enumerate(x):

                if cell: # There's food here

                    screen = self.to_screen((xNum, yNum ))

                    dot = circle( screen,

                                  FOOD_SIZE * self.gridSize,

                                  outlineColor = color, fillColor = color,

                                  width = 1)

                    imageRow.append(dot)

                else:

                    imageRow.append(None)

        return foodImages

    def drawCapsules(self, capsules ):

        capsuleImages = {}

        for capsule in capsules:

            ( screen_x, screen_y ) = self.to_screen(capsule)

            dot = circle( (screen_x, screen_y),

                              CAPSULE_SIZE * self.gridSize,

                              outlineColor = CAPSULE_COLOR,

                              fillColor = CAPSULE_COLOR,

                              width = 1)

            capsuleImages[capsule] = dot

        return capsuleImages

    def removeFood(self, cell, foodImages ):

        x, y = cell

        remove_from_screen(foodImages[x][y])

    def removeCapsule(self, cell, capsuleImages ):

        x, y = cell

        remove_from_screen(capsuleImages[(x, y)])

    def drawExpandedCells(self, cells):

        """

        Draws an overlay of expanded grid positions for search agents

        """

        n = float(len(cells))

        baseColor = [1.0, 0.0, 0.0]

        self.clearExpandedCells()

        self.expandedCells = []

        for k, cell in enumerate(cells):

            screenPos = self.to_screen( cell)

            cellColor = formatColor(*[(n-k) * c * .5 / n + .25 for c in baseColor])

            block = square(screenPos,

                     0.5 * self.gridSize,

                     color = cellColor,

                     filled = 1, behind=2)

            self.expandedCells.append(block)

            if self.frameTime < 0:
                refresh()
    def clearExpandedCells(self):
        if 'expandedCells' in dir(self) and len(self.expandedCells) > 0:

            for cell in self.expandedCells:

                remove_from_screen(cell)
    def updateDistributions(self, distributions):

        "Draws an agent's belief distributions"

        # copy all distributions so we don't change their state

        distributions = map(lambda x: x.copy(), distributions)

        if self.distributionImages == None:

            self.drawDistributions(self.previousState)

        for x in range(len(self.distributionImages)):

            for y in range(len(self.distributionImages[0])):

                image = self.distributionImages[x][y]

                weights = [dist[ (x,y) ] for dist in distributions]

                if sum(weights) != 0:

                    pass

                # Fog of war

                color = [0.0,0.0,0.0]

                colors = GHOST_VEC_COLORS[1:] # With Pacman

                if self.capture: colors = GHOST_VEC_COLORS

                for weight, gcolor in zip(weights, colors):

                    color = [min(1.0, c + 0.95 * g * weight ** .3) for c,g in zip(color, gcolor)]

                changeColor(image, formatColor(*color))

        refresh()

class FirstPersonPacmanGraphics(PacmanGraphics):

    def __init__(self, zoom = 1.0, showGhosts = True, capture = False, frameTime=0):

        PacmanGraphics.__init__(self, zoom, frameTime=frameTime)

        self.showGhosts = showGhosts

        self.capture = capture

    def initialize(self, state, isBlue = False):

        self.isBlue = isBlue

        PacmanGraphics.startGraphics(self, state)

        # Initialize distribution images

        walls = state.layout.walls

        dist = []

        self.layout = state.layout

        # Draw the rest

        self.distributionImages = None  # initialize lazily

        self.drawStaticObjects(state)

        self.drawAgentObjects(state)

        # Information

        self.previousState = state

    def lookAhead(self, config, state):

        if config.getDirection() == 'Stop':

            return

        else:

            pass

            # Draw relevant ghosts

            allGhosts = state.getGhostStates()

            visibleGhosts = state.getVisibleGhosts()

            for i, ghost in enumerate(allGhosts):

                if ghost in visibleGhosts:

                    self.drawGhost(ghost, i)

                else:

                    self.currentGhostImages[i] = None

    def getGhostColor(self, ghost, ghostIndex):

        return GHOST_COLORS[ghostIndex]

    def getPosition(self, ghostState):

        if not self.showGhosts and not ghostState.isPacman and ghostState.getPosition()[1] > 1:

            return (-1000, -1000)

        else:

            return PacmanGraphics.getPosition(self, ghostState)

def add(x, y):

    return (x[0] + y[0], x[1] + y[1])
# Saving graphical output

# -----------------------

# Note: to make an animated gif from this postscript output, try the command:

# convert -delay 7 -loop 1 -compress lzw -layers optimize frame* out.gif

# convert is part of imagemagick (freeware)

SAVE_POSTSCRIPT = False

POSTSCRIPT_OUTPUT_DIR = 'frames'

FRAME_NUMBER = 0

import os

def saveFrame():

    "Saves the current graphical output as a postscript file"

    global SAVE_POSTSCRIPT, FRAME_NUMBER, POSTSCRIPT_OUTPUT_DIR

    if not SAVE_POSTSCRIPT: return

    if not os.path.exists(POSTSCRIPT_OUTPUT_DIR): os.mkdir(POSTSCRIPT_OUTPUT_DIR)

    name = os.path.join(POSTSCRIPT_OUTPUT_DIR, 'frame_%08d.ps' % FRAME_NUMBER)

    FRAME_NUMBER += 1

    writePostscript(name) # writes the current canvas
homework_1_search/graphicsUtils.py

# graphicsUtils.py

# ----------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
import sys

import math

import random

import string

import time

import types

import tkinter

import os.path

_Windows = sys.platform == 'win32'  # True if on Win95/98/NT

_root_window = None      # The root window for graphics output

_canvas = None      # The canvas which holds graphics

_canvas_xs = None      # Size of canvas object

_canvas_ys = None

_canvas_x = None      # Current position on canvas

_canvas_y = None

_canvas_col = None      # Current colour (set to black below)

_canvas_tsize = 12

_canvas_tserifs = 0

def formatColor(r, g, b):

    return '#%02x%02x%02x' % (int(r * 255), int(g * 255), int(b * 255))

def colorToVector(color):

    return list(map(lambda x: int(x, 16) / 256.0, [color[1:3], color[3:5], color[5:7]]))

if _Windows:

    _canvas_tfonts = ['times new roman', 'lucida console']

else:

    _canvas_tfonts = ['times', 'lucidasans-24']

    pass # XXX need defaults here

def sleep(secs):

    global _root_window

    if _root_window == None:

        time.sleep(secs)

    else:

        _root_window.update_idletasks()

        _root_window.after(int(1000 * secs), _root_window.quit)

        _root_window.mainloop()

def begin_graphics(width=640, height=480, color=formatColor(0, 0, 0), title=None):

    global _root_window, _canvas, _canvas_x, _canvas_y, _canvas_xs, _canvas_ys, _bg_color

    # Check for duplicate call

    if _root_window is not None:

        # Lose the window.

        _root_window.destroy()

    # Save the canvas size parameters

    _canvas_xs, _canvas_ys = width - 1, height - 1

    _canvas_x, _canvas_y = 0, _canvas_ys

    _bg_color = color

    # Create the root window

    _root_window = tkinter.Tk()

    _root_window.protocol('WM_DELETE_WINDOW', _destroy_window)

    _root_window.title(title or 'Graphics Window')

    _root_window.resizable(0, 0)

    # Create the canvas object

    try:

        _canvas = tkinter.Canvas(_root_window, width=width, height=height)

        _canvas.pack()

        draw_background()

        _canvas.update()

    except:

        _root_window = None

        raise

    # Bind to key-down and key-up events

    _root_window.bind( "", _keypress )

    _root_window.bind( "", _keyrelease )

    _root_window.bind( "", _clear_keys )

    _root_window.bind( "", _clear_keys )

    _root_window.bind( "", _leftclick )

    _root_window.bind( "", _rightclick )

    _root_window.bind( "", _rightclick )

    _root_window.bind( "", _ctrl_leftclick)

    _clear_keys()

_leftclick_loc = None

_rightclick_loc = None

_ctrl_leftclick_loc = None

def _leftclick(event):

    global _leftclick_loc

    _leftclick_loc = (event.x, event.y)

def _rightclick(event):

    global _rightclick_loc

    _rightclick_loc = (event.x, event.y)

def _ctrl_leftclick(event):

    global _ctrl_leftclick_loc

    _ctrl_leftclick_loc = (event.x, event.y)

def wait_for_click():

    while True:

        global _leftclick_loc

        global _rightclick_loc

        global _ctrl_leftclick_loc

        if _leftclick_loc != None:

            val = _leftclick_loc

            _leftclick_loc = None

            return val, 'left'

        if _rightclick_loc != None:

            val = _rightclick_loc

            _rightclick_loc = None

            return val, 'right'

        if _ctrl_leftclick_loc != None:

            val = _ctrl_leftclick_loc

            _ctrl_leftclick_loc = None

            return val, 'ctrl_left'

        sleep(0.05)

def draw_background():

    corners = [(0,0), (0, _canvas_ys), (_canvas_xs, _canvas_ys), (_canvas_xs, 0)]

    polygon(corners, _bg_color, fillColor=_bg_color, filled=True, smoothed=False)

def _destroy_window(event=None):

    sys.exit(0)

#    global _root_window

#    _root_window.destroy()

#    _root_window = None

    #print("DESTROY")

def end_graphics():

    global _root_window, _canvas, _mouse_enabled

    try:

        try:

            sleep(1)

            if _root_window != None:

                _root_window.destroy()

        except SystemExit as e:

            print('Ending graphics raised an exception:', e)

    finally:

        _root_window = None

        _canvas = None

        _mouse_enabled = 0

        _clear_keys()

def clear_screen(background=None):

    global _canvas_x, _canvas_y

    _canvas.delete('all')

    draw_background()

    _canvas_x, _canvas_y = 0, _canvas_ys

def polygon(coords, outlineColor, fillColor=None, filled=1, smoothed=1, behind=0, width=1):

    c = []

    for coord in coords:

        c.append(coord[0])

        c.append(coord[1])

    if fillColor == None: fillColor = outlineColor

    if filled == 0: fillColor = ""

    poly = _canvas.create_polygon(c, outline=outlineColor, fill=fillColor, smooth=smoothed, width=width)

    if behind > 0:

        _canvas.tag_lower(poly, behind) # Higher should be more visible

    return poly

def square(pos, r, color, filled=1, behind=0):

    x, y = pos

    coords = [(x - r, y - r), (x + r, y - r), (x + r, y + r), (x - r, y + r)]

    return polygon(coords, color, color, filled, 0, behind=behind)

def circle(pos, r, outlineColor, fillColor=None, endpoints=None, style='pieslice', width=2):

    x, y = pos

    x0, x1 = x - r - 1, x + r

    y0, y1 = y - r - 1, y + r

    if endpoints == None:

        e = [0, 359]

    else:

        e = list(endpoints)

    while e[0] > e[1]: e[1] = e[1] + 360

    return _canvas.create_arc(x0, y0, x1, y1, outline=outlineColor, fill=fillColor or outlineColor,

                              extent=e[1] - e[0], start=e[0], style=style, width=width)

def image(pos, file="../../blueghost.gif"):

    x, y = pos

    # img = PhotoImage(file=file)

    return _canvas.create_image(x, y, image = tkinter.PhotoImage(file=file), anchor = tkinter.NW)
def refresh():

    _canvas.update_idletasks()

def moveCircle(id, pos, r, endpoints=None):

    global _canvas_x, _canvas_y

    x, y = pos

#    x0, x1 = x - r, x + r + 1

#    y0, y1 = y - r, y + r + 1

    x0, x1 = x - r - 1, x + r

    y0, y1 = y - r - 1, y + r

    if endpoints == None:

        e = [0, 359]

    else:

        e = list(endpoints)

    while e[0] > e[1]: e[1] = e[1] + 360

    if os.path.isfile('flag'):

        edit(id, ('extent', e[1] - e[0]))

    else:

        edit(id, ('start', e[0]), ('extent', e[1] - e[0]))

    move_to(id, x0, y0)

def edit(id, *args):

    _canvas.itemconfigure(id, **dict(args))

def text(pos, color, contents, font='Helvetica', size=12, style='normal', anchor="nw"):

    global _canvas_x, _canvas_y

    x, y = pos

    font = (font, str(size), style)

    return _canvas.create_text(x, y, fill=color, text=contents, font=font, anchor=anchor)

def changeText(id, newText, font=None, size=12, style='normal'):

    _canvas.itemconfigure(id, text=newText)

    if font != None:

        _canvas.itemconfigure(id, font=(font, '-%d' % size, style))

def changeColor(id, newColor):

    _canvas.itemconfigure(id, fill=newColor)

def line(here, there, color=formatColor(0, 0, 0), width=2):

    x0, y0 = here[0], here[1]

    x1, y1 = there[0], there[1]

    return _canvas.create_line(x0, y0, x1, y1, fill=color, width=width)

##############################################################################

### Keypress handling ########################################################

##############################################################################

# We bind to key-down and key-up events.

_keysdown = {}

_keyswaiting = {}

# This holds an unprocessed key release.  We delay key releases by up to

# one call to keys_pressed() to get round a problem with auto repeat.

_got_release = None

def _keypress(event):

    global _got_release

    #remap_arrows(event)

    _keysdown[event.keysym] = 1

    _keyswaiting[event.keysym] = 1

#    print(event.char, event.keycode)

    _got_release = None

def _keyrelease(event):

    global _got_release

    #remap_arrows(event)

    try:

        del _keysdown[event.keysym]

    except:

        pass

    _got_release = 1

def remap_arrows(event):

    # TURN ARROW PRESSES INTO LETTERS (SHOULD BE IN KEYBOARD AGENT)

    if event.char in ['a', 's', 'd', 'w']:

        return

    if event.keycode in [37, 101]: # LEFT ARROW (win / x)

        event.char = 'a'

    if event.keycode in [38, 99]: # UP ARROW

        event.char = 'w'

    if event.keycode in [39, 102]: # RIGHT ARROW

        event.char = 'd'

    if event.keycode in [40, 104]: # DOWN ARROW

        event.char = 's'

def _clear_keys(event=None):

    global _keysdown, _got_release, _keyswaiting

    _keysdown = {}

    _keyswaiting = {}

    _got_release = None

def keys_pressed(d_o_e=lambda arg: _root_window.dooneevent(arg),

                 d_w=tkinter._tkinter.DONT_WAIT):

    d_o_e(d_w)

    if _got_release:

        d_o_e(d_w)

    return _keysdown.keys()

def keys_waiting():

    global _keyswaiting

    keys = _keyswaiting.keys()

    _keyswaiting = {}

    return keys

# Block for a list of keys...

def wait_for_keys():

    keys = []

    while keys == []:

        keys = keys_pressed()

        sleep(0.05)

    return keys

def remove_from_screen(x,

                       d_o_e=lambda arg: _root_window.dooneevent(arg),

                       d_w=tkinter._tkinter.DONT_WAIT):

    _canvas.delete(x)

    d_o_e(d_w)

def _adjust_coords(coord_list, x, y):

    for i in range(0, len(coord_list), 2):

        coord_list[i] = coord_list[i] + x

        coord_list[i + 1] = coord_list[i + 1] + y

    return coord_list

def move_to(object, x, y=None,

            d_o_e=lambda arg: _root_window.dooneevent(arg),

            d_w=tkinter._tkinter.DONT_WAIT):

    if y is None:

        try: x, y = x

        except: raise  'incomprehensible coordinates'

    horiz = True

    newCoords = []

    current_x, current_y = _canvas.coords(object)[0:2] # first point

    for coord in  _canvas.coords(object):

        if horiz:

            inc = x - current_x

        else:

            inc = y - current_y

        horiz = not horiz

        newCoords.append(coord + inc)

    _canvas.coords(object, *newCoords)

    d_o_e(d_w)

def move_by(object, x, y=None,

            d_o_e=lambda arg: _root_window.dooneevent(arg),

            d_w=tkinter._tkinter.DONT_WAIT, lift=False):

    if y is None:

        try: x, y = x

        except: raise Exception('incomprehensible coordinates')

    horiz = True

    newCoords = []

    for coord in  _canvas.coords(object):

        if horiz:

            inc = x

        else:

            inc = y

        horiz = not horiz

        newCoords.append(coord + inc)

    _canvas.coords(object, *newCoords)

    d_o_e(d_w)

    if lift:

        _canvas.tag_raise(object)

def writePostscript(filename):

    "Writes the current canvas to a postscript file."

    psfile = open(filename, 'w')

    psfile.write(_canvas.postscript(pageanchor='sw',

                     y='0.c',

                     x='0.c'))

    psfile.close()

ghost_shape = [

    (0, - 0.5),

    (0.25, - 0.75),

    (0.5, - 0.5),

    (0.75, - 0.75),

    (0.75, 0.5),

    (0.5, 0.75),

    (- 0.5, 0.75),

    (- 0.75, 0.5),

    (- 0.75, - 0.75),

    (- 0.5, - 0.5),

    (- 0.25, - 0.75)

  ]

if __name__ == '__main__':

    begin_graphics()

    clear_screen()

    ghost_shape = [(x * 10 + 20, y * 10 + 20) for x, y in ghost_shape]

    g = polygon(ghost_shape, formatColor(1, 1, 1))

    move_to(g, (50, 50))

    circle((150, 150), 20, formatColor(0.7, 0.3, 0.0), endpoints=[15, - 15])

    sleep(2)
homework_1_search/keyboardAgents.py

# keyboardAgents.py

# -----------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
from game import Agent

from game import Directions

import random

class KeyboardAgent(Agent):

    """

    An agent controlled by the keyboard.

    """

    # NOTE: Arrow keys also work.

    WEST_KEY  = 'a'

    EAST_KEY  = 'd'

    NORTH_KEY = 'w'

    SOUTH_KEY = 's'

    STOP_KEY = 'q'

    def __init__( self, index = 0 ):

        self.lastMove = Directions.STOP

        self.index = index

        self.keys = []

    def getAction( self, state):

        from graphicsUtils import keys_waiting

        from graphicsUtils import keys_pressed

        keys = list(keys_waiting()) + list(keys_pressed())

        if keys != []:

            self.keys = keys

        legal = state.getLegalActions(self.index)

        move = self.getMove(legal)

        if move == Directions.STOP:

            # Try to move in the same direction as before

            if self.lastMove in legal:

                move = self.lastMove

        if (self.STOP_KEY in self.keys) and Directions.STOP in legal: move = Directions.STOP

        if move not in legal:

            move = random.choice(legal)

        self.lastMove = move

        return move

    def getMove(self, legal):

        move = Directions.STOP

        if   (self.WEST_KEY in self.keys or 'Left' in self.keys) and Directions.WEST in legal:  move = Directions.WEST

        if   (self.EAST_KEY in self.keys or 'Right' in self.keys) and Directions.EAST in legal: move = Directions.EAST

        if   (self.NORTH_KEY in self.keys or 'Up' in self.keys) and Directions.NORTH in legal:   move = Directions.NORTH

        if   (self.SOUTH_KEY in self.keys or 'Down' in self.keys) and Directions.SOUTH in legal: move = Directions.SOUTH

        return move

class KeyboardAgent2(KeyboardAgent):

    """

    A second agent controlled by the keyboard.

    """

    # NOTE: Arrow keys also work.

    WEST_KEY  = 'j'

    EAST_KEY  = "l"

    NORTH_KEY = 'i'

    SOUTH_KEY = 'k'

    STOP_KEY = 'u'

    def getMove(self, legal):

        move = Directions.STOP

        if   (self.WEST_KEY in self.keys) and Directions.WEST in legal:  move = Directions.WEST

        if   (self.EAST_KEY in self.keys) and Directions.EAST in legal: move = Directions.EAST

        if   (self.NORTH_KEY in self.keys) and Directions.NORTH in legal:   move = Directions.NORTH

        if   (self.SOUTH_KEY in self.keys) and Directions.SOUTH in legal: move = Directions.SOUTH

        return move
homework_1_search/layout.py

# layout.py

# ---------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
from util import manhattanDistance

from game import Grid

import os

import random

from functools import reduce

VISIBILITY_MATRIX_CACHE = {}

class Layout:

    """

    A Layout manages the static information about the game board.

    """

    def __init__(self, layoutText):

        self.width = len(layoutText[0])

        self.height= len(layoutText)

        self.walls = Grid(self.width, self.height, False)

        self.food = Grid(self.width, self.height, False)

        self.capsules = []

        self.agentPositions = []

        self.numGhosts = 0

        self.processLayoutText(layoutText)

        self.layoutText = layoutText

        self.totalFood = len(self.food.asList())

        # self.initializeVisibilityMatrix()

    def getNumGhosts(self):

        return self.numGhosts

    def initializeVisibilityMatrix(self):

        global VISIBILITY_MATRIX_CACHE

        if reduce(str.__add__, self.layoutText) not in VISIBILITY_MATRIX_CACHE:

            from game import Directions

            vecs = [(-0.5,0), (0.5,0),(0,-0.5),(0,0.5)]

            dirs = [Directions.NORTH, Directions.SOUTH, Directions.WEST, Directions.EAST]

            vis = Grid(self.width, self.height, {Directions.NORTH:set(), Directions.SOUTH:set(), Directions.EAST:set(), Directions.WEST:set(), Directions.STOP:set()})

            for x in range(self.width):

                for y in range(self.height):

                    if self.walls[x][y] == False:

                        for vec, direction in zip(vecs, dirs):

                            dx, dy = vec

                            nextx, nexty = x + dx, y + dy

                            while (nextx + nexty) != int(nextx) + int(nexty) or not self.walls[int(nextx)][int(nexty)] :

                                vis[x][y][direction].add((nextx, nexty))

                                nextx, nexty = x + dx, y + dy

            self.visibility = vis

            VISIBILITY_MATRIX_CACHE[reduce(str.__add__, self.layoutText)] = vis

        else:

            self.visibility = VISIBILITY_MATRIX_CACHE[reduce(str.__add__, self.layoutText)]

    def isWall(self, pos):

        x, col = pos

        return self.walls[x][col]

    def getRandomLegalPosition(self):

        x = random.choice(range(self.width))

        y = random.choice(range(self.height))

        while self.isWall( (x, y) ):

            x = random.choice(range(self.width))

            y = random.choice(range(self.height))

        return (x,y)

    def getRandomCorner(self):

        poses = [(1,1), (1, self.height - 2), (self.width - 2, 1), (self.width - 2, self.height - 2)]

        return random.choice(poses)

    def getFurthestCorner(self, pacPos):

        poses = [(1,1), (1, self.height - 2), (self.width - 2, 1), (self.width - 2, self.height - 2)]

        dist, pos = max([(manhattanDistance(p, pacPos), p) for p in poses])

        return pos

    def isVisibleFrom(self, ghostPos, pacPos, pacDirection):

        row, col = [int(x) for x in pacPos]

        return ghostPos in self.visibility[row][col][pacDirection]

    def __str__(self):

        return "\n".join(self.layoutText)

    def deepCopy(self):

        return Layout(self.layoutText[:])

    def processLayoutText(self, layoutText):

        """

        Coordinates are flipped from the input format to the (x,y) convention here

        The shape of the maze.  Each character

        represents a different type of object.

         % - Wall

         . - Food

         o - Capsule

         G - Ghost

         P - Pacman

        Other characters are ignored.

        """

        maxY = self.height - 1

        for y in range(self.height):

            for x in range(self.width):

                layoutChar = layoutText[maxY - y][x]

                self.processLayoutChar(x, y, layoutChar)

        self.agentPositions.sort()

        self.agentPositions = [ ( i == 0, pos) for i, pos in self.agentPositions]

    def processLayoutChar(self, x, y, layoutChar):

        if layoutChar == '%':

            self.walls[x][y] = True

        elif layoutChar == '.':

            self.food[x][y] = True

        elif layoutChar == 'o':

            self.capsules.append((x, y))

        elif layoutChar == 'P':

            self.agentPositions.append( (0, (x, y) ) )

        elif layoutChar in ['G']:

            self.agentPositions.append( (1, (x, y) ) )

            self.numGhosts += 1

        elif layoutChar in  ['1', '2', '3', '4']:

            self.agentPositions.append( (int(layoutChar), (x,y)))

            self.numGhosts += 1

def getLayout(name, back = 2):

    if name.endswith('.lay'):

        layout = tryToLoad('layouts/' + name)

        if layout == None: layout = tryToLoad(name)

    else:

        layout = tryToLoad('layouts/' + name + '.lay')

        if layout == None: layout = tryToLoad(name + '.lay')

    if layout == None and back >= 0:

        curdir = os.path.abspath('.')

        os.chdir('..')

        layout = getLayout(name, back -1)

        os.chdir(curdir)

    return layout

def tryToLoad(fullname):

    if(not os.path.exists(fullname)): return None

    f = open(fullname)

    try: return Layout([line.strip() for line in f])

    finally: f.close()
homework_1_search/layouts/bigCorners.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%.      %                         %.%

%         %%%%% % %%% %%% %%%%%%% % %

%       %       % %     %     % %   %

%%%%% %%%%% %%% % % % %%% %%%%% % %%%

%   % % % %   % % % %   % %     %   %

% %%% % % % %%% %%%%% %%% % %%% %%% %

%       %     %   %   %     % % %   %

%%% %%%%%%%%% %%%%%%% %%% %%% % % % %

%             %       % %   %     % %

% % %%%%% % %%% % % %%% % %%% %%% % %

% % %     % % % % %     %   % % % % %

% % % %%%%%%% % %%%%%%%%% %%% % %%% %

% % % %     %   %     %     %   %   %

%%% %%% % %%%%% %%%%% %%% %%% %%%%% %

%     % %               % %   % % % %

% % % % %  %  %%% %%% %%% % % % % % %

% % % % % %%  % % % % %   % % %     %

% % %%%%%  %  %%% %%% % %%% %%% %%%%%

%       %  %  % % % % %       % %   %

% %%% % %  %  %%% %%% %%%%%%%%% % %%%

%   % %                   %   % %   %

% %%% %%%%%%%%%%%%%%%%%%%%% % % %%% %

% %                         %       %

% % % %%%%% %%% % % % % %%%%%%%%%%%%%

% % %   %     % % % %       %   % % %

% % %%% %%% % % % %%%%%%%%% %%% % % %

% %   % %   % % %P  % %   % % %     %

% %%% %%% %%% % %%% % % %%%%% % %%%%%

%       %   %     %       %   % %   %

%%% % %%%%% %%%%% %%% %%% % %%% % %%%

% % % % % % % %     % %   % %   % % %

% % %%% % % % % %%%%%%%%% % % % % % %

%       %                     %     %

% %   % %%% %%% %%%%%%% %%% %%% %%% %

%.%   %       %           %     %  .%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/bigMaze.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%       % % %           %   %     % %

% %%%%%%% % %%% % %%% %%% %%%%%%% % %

%       %       % %     %     % %   %

%%%%% %%%%% %%% % % % %%% %%%%% % %%%

%   % % % %   % % % %   % %   % %   %

% %%% % % % %%% %%%%% %%% % %%% %%% %

%       %     %   %   %     % % %   %

%%% %%%%%%%%% %%%%%%% %%% %%% % % % %

%             %       % %   %     % %

% % %%%%% % %%% % % %%% % %%% %%% % %

% % %     % % % % %     %   % % % % %

% % % %%%%%%% % %%%%%%%%% %%% % %%% %

% % % %     %   %     %     %   %   %

%%% %%% % %%%%% %%%%% %%% %%% %%%%% %

%     % % %     % %     % %   % % % %

% % % % % %%% %%% %%% %%% % % % % % %

% % % % %                 % % %     %

%%% %%%%%%% % % %%%%% %%% % %%% %%%%%

%       % % % %     %   %     % %   %

%%%%% % % %%%%%%%%% %%%%%%%%%%% % %%%

%   % %           % %     %   % %   %

% %%% %%%%% %%%%%%%%% %%%%% % % %%% %

% %   %      %        %     %       %

% % % %%%%% %%% % % % % %%%%%%%%%%%%%

% % %   %     % % % %       %   % % %

% % %%% %%% % % % %%%%%%%%% %%% % % %

% %   % %   % % %   % %   % % %     %

% %%% %%% %%%%% %%% % % %%%%% % %%%%%

%       %   %     % %     %   % %   %

%%% % %%%%% %%%%% %%% %%% % %%% % %%%

% % % % % % % %     % %   % %   % % %

% % %%% % % % % %%%%%%%%% % % % % % %

%   %   %   %                 %     %

% % % % %%% %%% %%%%%%% %%% %%% %%% %

%.% % %       %   %       %   % %  P%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/bigSafeSearch.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%.%.........%% G %  o%%%%.....%

%.%.%%%%%%%.%%%%%% %%%%%%%.%%.%

%............%...%............%

%%%%%...%%%..     ..%.%...%.%%%

%o%%%.%%%%%.%%%%%%%.%%%.%.%%%%%

%    ..........Po...%...%.   o%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/bigSearch.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%.....%.................%.....%

%.%%%.%.%%%.%%%%%%%.%%%.%.....%

%.%...%.%......%......%.%.....%

%...%%%.%.%%%%.%.%%%%...%%%...%

%%%.%.%.%.%......%..%.%...%.%%%

%...%.%%%.%.%%% %%%.%.%%%.%...%

%.%%%.......%     %.......%%%.%

%...%.%%%%%.%%%%%%%.%.%%%.%...%

%%%.%...%.%....%....%.%...%.%%%

%...%%%.%.%%%%.%.%%%%.%.%%%...%

%.......%......%......%.....%.%

%.....%.%%%.%%%%%%%.%%%.%.%%%.%

%.....%........P....%...%.....%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/boxSearch.lay

%%%%%%%%%%%%%%

%. . . . . % %

%          % %

%. . . . . %G%

%          % %

%. . . . . % %

%          % %

%. . . . . % %

%     P    %G%

%. . . . . % %

%          % %

%. . . . . % %

%          % %

%%%%%%%%%%%%%%
homework_1_search/layouts/capsuleClassic.lay

%%%%%%%%%%%%%%%%%%%

%G.       G   ....%

%.% % %%%%%% %.%%.%

%.%o% %   o% %.o%.%

%.%%%.%  %%% %..%.%

%.....  P    %..%G%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/contestClassic.lay

%%%%%%%%%%%%%%%%%%%%

%o...%........%...o%

%.%%.%.%%..%%.%.%%.%

%...... G GG%......%

%.%.%%.%% %%%.%%.%.%

%.%....% ooo%.%..%.%

%.%.%%.% %% %.%.%%.%

%o%......P....%....%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/contoursMaze.lay

%%%%%%%%%%%%%%%%%%%%%

%                   %

%                   %

%                   %

%                   %

%         P         %

%                   %

%                   %

%                   %

%.                  %

%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/greedySearch.lay

%%%%%%

%....%

% %%.%

% %%.%

%.P .%

%.%%%%

%....%

%%%%%%
homework_1_search/layouts/mediumClassic.lay

%%%%%%%%%%%%%%%%%%%%

%o...%........%....%

%.%%.%.%%%%%%.%.%%.%

%.%..............%.%

%.%.%%.%%  %%.%%.%.%

%......%G  G%......%

%.%.%%.%%%%%%.%%.%.%

%.%..............%.%

%.%%.%.%%%%%%.%.%%.%

%....%...P....%...o%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumCorners.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%.      % % %              %.%

%       % % %%%%%% %%%%%%% % %

%       %        %     % %   %

%%%%% %%%%% %%% %% %%%%% % %%%

%   % % % %   %    %     %   %

% %%% % % % %%%%%%%% %%% %%% %

%       %     %%     % % %   %

%%% % %%%%%%% %%%% %%% % % % %

% %           %%     %     % %

% % %%%%% % %%%% % %%% %%% % %

%   %     %      % %   % %%% %

%.  %P%%%%%      % %%% %    .%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumDottedMaze.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%% %%% %%%%%%%% %

% %%   %   %      %%% %%%   %% ... %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % % %    %%     %% %% ... %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%  ... %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %% ... %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %  ... %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%% ...... %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumMaze.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumSafeSearch.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%.%     ....%% G %%%%%%   o%%.%

%.%o%%%%%%%.%%%%%%%     %%%%%.%

% %%%.%%%%%.%%%%%%%.%%%.%.%%%.%

%    ..........Po...%.........%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumScaryMaze.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                   P%

% %%%%%%%%%%%%%%%%%%% %%%  %%%%%%%%  %

% %%   %   %      %%% %%%    %%GG    %

% %% % % % % %%%% %%%%%%%%%  %%  %%%%%

% %% % % % % %    %%GG       %%      %

% %% % % % % % %%%%%  %%%    %%%%%%  %

% %% % % %   %    %%  %%%%%%%%%      %

% %% % % %%%%%%%% %%         %%  %%%%%

% %% %   %%       %%%%%%%%%  %%      %

%    %%% %% %%%%%%%      %%  %%%%%%  %

%%%%%%      %       %    %%  %%      %

%      %%%%%% %%   %%    %%  %%  %%%%%

% %%%%%%      %       %%%%%  %%      %

%          %%%%       %%%%%  %%%%%%  %

%%%%%%%%   %                 %%%%%%  %

%.         %%%%%%%%%%%%%%%%          %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/mediumSearch.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%............%%%%%............%

%%%.%...%%%.........%.%...%.%%%

%...%%%.%.%%%%.%.%%%%%%.%%%...%

%.%.....%......%......%.....%.%

%.%%%.%%%%%.%%%%%%%.%%%.%.%%%%%

%.....%........P....%...%.....%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/minimaxClassic.lay

%%%%%%%%%

%.P    G%

% %.%G%%%

%G    %%%

%%%%%%%%%
homework_1_search/layouts/oddSearch.lay

%%%%%%%%%%%%%%%%%%%%

%...%.........%%...%

%.%.%.%%%%%%%%%%.%.%

%..................%

%%%%%%%%.%.%%%%%%%P%

%%%%%%%%.......    %

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/openClassic.lay

%%%%%%%%%%%%%%%%%%%%%%%%%

%.. P  ....      ....   %

%..  ...  ...  ...  ... %

%..  ...  ...  ...  ... %

%..    ....      .... G %

%..  ...  ...  ...  ... %

%..  ...  ...  ...  ... %

%..    ....      ....  o%

%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/openMaze.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                  P%

%            %                      %

%            %                      %

%            %                      %

%            %                      %

%            %                      %

%            %      %               %

%            %      %               %

%            %      %               %

%            %      %               %

%            %      %               %

%            %      %               %

%            %      %               %

%%%%%%%%%%%%%%      %%%%%%%%%%%%%%%%%

%            %                      %

%            %                      %

%            %                      %

%                                   %

%                                   %

%                                   %

%.                                  %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/openSearch.lay

%%%%%%%%%%%%%%%%%%%%

%..................%

%..................%

%........P.........%

%..................%

%..................%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/originalClassic.lay

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%............%%............%

%.%%%%.%%%%%.%%.%%%%%.%%%%.%

%o%%%%.%%%%%.%%.%%%%%.%%%%o%

%.%%%%.%%%%%.%%.%%%%%.%%%%.%

%..........................%

%.%%%%.%%.%%%%%%%%.%%.%%%%.%

%.%%%%.%%.%%%%%%%%.%%.%%%%.%

%......%%....%%....%%......%

%%%%%%.%%%%% %% %%%%%.%%%%%%

%%%%%%.%%%%% %% %%%%%.%%%%%%

%%%%%%.%            %.%%%%%%

%%%%%%.% %%%%  %%%% %.%%%%%%

%     .  %G  GG  G%  .     %

%%%%%%.% %%%%%%%%%% %.%%%%%%

%%%%%%.%            %.%%%%%%

%%%%%%.% %%%%%%%%%% %.%%%%%%

%............%%............%

%.%%%%.%%%%%.%%.%%%%%.%%%%.%

%.%%%%.%%%%%.%%.%%%%%.%%%%.%

%o..%%.......  .......%%..o%

%%%.%%.%%.%%%%%%%%.%%.%%.%%%

%%%.%%.%%.%%%%%%%%.%%.%%.%%%

%......%%....%%....%%......%

%.%%%%%%%%%%.%%.%%%%%%%%%%.%

%.............P............%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/powerClassic.lay

%%%%%%%%%%%%%%%%%%%%

%o....o%GGGG%o....o%

%..%...%%  %%...%..%

%.%o.%........%.o%.%

%.o%.%.%%%%%%.%.%o.%

%........P.........%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/smallClassic.lay

%%%%%%%%%%%%%%%%%%%%

%......%G  G%......%

%.%%...%%  %%...%%.%

%.%o.%........%.o%.%

%.%%.%.%%%%%%.%.%%.%

%........P.........%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/smallMaze.lay

%%%%%%%%%%%%%%%%%%%%%%

% %%        % %      %

%    %%%%%% % %%%%%% %

%%%%%%     P  %      %

%    % %%%%%% %% %%%%%

% %%%% %         %   %

%        %%% %%%   % %

%%%%%%%%%%    %%%%%% %

%.         %%        %

%%%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/smallSafeSearch.lay

%%%%%%%%%

%.. % G %

%%% %%%%%

%       %

%%%%%%% %

%       %

% %%%%% %

%     % %

%%%%% % %

%     %o%

% %%%%%%%

%      .%

%%%%%%%.%

%Po    .%

%%%%%%%%%
homework_1_search/layouts/smallSearch.lay

%%%%%%%%%%%%%%%%%%%%

%.           ...P .%

%.%%.%%.%%.%%.%% %.%

% %% %.....      %.%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/testClassic.lay

%%%%%

% . %

%.G.%

% . %

%. .%

%   %

%  .%

%   %

%P .%

%%%%%
homework_1_search/layouts/testMaze.lay

%%%%%%%%%%

%.      P%

%%%%%%%%%%
homework_1_search/layouts/testSearch.lay

%%%%%

%.P %

%%% %

%.  %

%%%%%
homework_1_search/layouts/tinyCorners.lay

%%%%%%%%

%.    .%

%   P  %

% %%%% %

% %    %

% % %%%%

%.%   .%

%%%%%%%%
homework_1_search/layouts/tinyMaze.lay

%%%%%%%

%    P%

% %%% %

%  %  %

%%   %%

%. %%%%

%%%%%%%
homework_1_search/layouts/tinySafeSearch.lay

%%%%%%%%%

% G %...%

%%%%%%% %

%Po     %

%.%%.%%.%

%.%%....%

%%%%%%%%%
homework_1_search/layouts/tinySearch.lay

%%%%%%%%%

%..   ..%

%%%%.%% %

%   P   %

%.%% %%.%

%.%.   .%

%%%%%%%%%
homework_1_search/layouts/trappedClassic.lay

%%%%%%%%

%   P G%

%G%%%%%%

%....  %

%%%%%%%%
homework_1_search/layouts/trickyClassic.lay

%%%%%%%%%%%%%%%%%%%%

%o...%........%...o%

%.%%.%.%%..%%.%.%%.%

%.%.....%..%.....%.%

%.%.%%.%%  %%.%%.%.%

%...... GGGG%.%....%

%.%....%%%%%%.%..%.%

%.%....%  oo%.%..%.%

%.%....% %%%%.%..%.%

%.%...........%..%.%

%.%%.%.%%%%%%.%.%%.%

%o...%...P....%...o%

%%%%%%%%%%%%%%%%%%%%
homework_1_search/layouts/trickySearch.lay

%%%%%%%%%%%%%%%%%%%%

%.           ..%   %

%.%%.%%.%%.%%.%% % %

%        P       % %

%%%%%%%%%%%%%%%%%% %

%.....             %

%%%%%%%%%%%%%%%%%%%%
homework_1_search/pacman.py

# pacman.py

# ---------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
"""

Pacman.py holds the logic for the classic pacman game along with the main

code to run a game.  This file is divided into three sections:

  (i)  Your interface to the pacman world:

          Pacman is a complex environment.  You probably don't want to

          read through all of the code we wrote to make the game runs

          correctly.  This section contains the parts of the code

          that you will need to understand in order to complete the

          project.  There is also some code in game.py that you should

          understand.

  (ii)  The hidden secrets of pacman:

          This section contains all of the logic code that the pacman

          environment uses to decide who can move where, who dies when

          things collide, etc.  You shouldn't need to read this section

          of code, but you can if you want.

  (iii) Framework to start a game:

          The final section contains the code for reading the command

          you use to set up the game, then starting up a new game, along with

          linking in all the external parts (agent functions, graphics).

          Check this section out to see all the options available to you.

To play your first game, type 'python pacman.py' from the command line.

The keys are 'a', 's', 'd', and 'w' to move (or arrow keys).  Have fun!

"""

from game import GameStateData

from game import Game

from game import Directions

from game import Actions

from util import nearestPoint

from util import manhattanDistance

import util, layout

import sys, types, time, random, os

###################################################

# YOUR INTERFACE TO THE PACMAN WORLD: A GameState #

###################################################

class GameState:

    """

    A GameState specifies the full game state, including the food, capsules,

    agent configurations and score changes.

    GameStates are used by the Game object to capture the actual state of the game and

    can be used by agents to reason about the game.

    Much of the information in a GameState is stored in a GameStateData object.  We

    strongly suggest that you access that data via the accessor methods below rather

    than referring to the GameStateData object directly.

    Note that in classic Pacman, Pacman is always agent 0.

    """

    ####################################################

    # Accessor methods: use these to access state data #

    ####################################################

    # static variable keeps track of which states have had getLegalActions called

    explored = set()

    def getAndResetExplored():

        tmp = GameState.explored.copy()

        GameState.explored = set()

        return tmp

    getAndResetExplored = staticmethod(getAndResetExplored)

    def getLegalActions( self, agentIndex=0 ):

        """

        Returns the legal actions for the agent specified.

        """

#        GameState.explored.add(self)

        if self.isWin() or self.isLose(): return []

        if agentIndex == 0:  # Pacman is moving

            return PacmanRules.getLegalActions( self )

        else:

            return GhostRules.getLegalActions( self, agentIndex )

    def generateSuccessor( self, agentIndex, action):

        """

        Returns the successor state after the specified agent takes the action.

        """

        # Check that successors exist

        if self.isWin() or self.isLose(): raise Exception('Can\'t generate a successor of a terminal state.')

        # Copy current state

        state = GameState(self)

        # Let agent's logic deal with its action's effects on the board

        if agentIndex == 0:  # Pacman is moving

            state.data._eaten = [False for i in range(state.getNumAgents())]

            PacmanRules.applyAction( state, action )

        else:                # A ghost is moving

            GhostRules.applyAction( state, action, agentIndex )

        # Time passes

        if agentIndex == 0:

            state.data.scoreChange += -TIME_PENALTY # Penalty for waiting around

        else:

            GhostRules.decrementTimer( state.data.agentStates[agentIndex] )

        # Resolve multi-agent effects

        GhostRules.checkDeath( state, agentIndex )

        # Book keeping

        state.data._agentMoved = agentIndex

        state.data.score += state.data.scoreChange

        GameState.explored.add(self)

        GameState.explored.add(state)

        return state

    def getLegalPacmanActions( self ):

        return self.getLegalActions( 0 )

    def generatePacmanSuccessor( self, action ):

        """

        Generates the successor state after the specified pacman move

        """

        return self.generateSuccessor( 0, action )

    def getPacmanState( self ):

        """

        Returns an AgentState object for pacman (in game.py)

        state.pos gives the current position

        state.direction gives the travel vector

        """

        return self.data.agentStates[0].copy()

    def getPacmanPosition( self ):

        return self.data.agentStates[0].getPosition()

    def getGhostStates( self ):

        return self.data.agentStates[1:]

    def getGhostState( self, agentIndex ):

        if agentIndex == 0 or agentIndex >= self.getNumAgents():

            raise Exception("Invalid index passed to getGhostState")

        return self.data.agentStates[agentIndex]

    def getGhostPosition( self, agentIndex ):

        if agentIndex == 0:

            raise Exception("Pacman's index passed to getGhostPosition")

        return self.data.agentStates[agentIndex].getPosition()

    def getGhostPositions(self):

        return [s.getPosition() for s in self.getGhostStates()]

    def getNumAgents( self ):

        return len( self.data.agentStates )

    def getScore( self ):

        return float(self.data.score)

    def getCapsules(self):

        """

        Returns a list of positions (x,y) of the remaining capsules.

        """

        return self.data.capsules

    def getNumFood( self ):

        return self.data.food.count()

    def getFood(self):

        """

        Returns a Grid of boolean food indicator variables.

        Grids can be accessed via list notation, so to check

        if there is food at (x,y), just call

        currentFood = state.getFood()

        if currentFood[x][y] == True: ...

        """

        return self.data.food

    def getWalls(self):

        """

        Returns a Grid of boolean wall indicator variables.

        Grids can be accessed via list notation, so to check

        if there is a wall at (x,y), just call

        walls = state.getWalls()

        if walls[x][y] == True: ...

        """

        return self.data.layout.walls

    def hasFood(self, x, y):

        return self.data.food[x][y]

    def hasWall(self, x, y):

        return self.data.layout.walls[x][y]

    def isLose( self ):

        return self.data._lose

    def isWin( self ):

        return self.data._win

    #############################################

    #             Helper methods:               #

    # You shouldn't need to call these directly #

    #############################################

    def __init__( self, prevState = None ):

        """

        Generates a new state by copying information from its predecessor.

        """

        if prevState != None: # Initial state

            self.data = GameStateData(prevState.data)

        else:

            self.data = GameStateData()

    def deepCopy( self ):

        state = GameState( self )

        state.data = self.data.deepCopy()

        return state

    def __eq__( self, other ):

        """

        Allows two states to be compared.

        """

        return hasattr(other, 'data') and self.data == other.data

    def __hash__( self ):

        """

        Allows states to be keys of dictionaries.

        """

        return hash( self.data )

    def __str__( self ):

        return str(self.data)

    def initialize( self, layout, numGhostAgents=1000 ):

        """

        Creates an initial game state from a layout array (see layout.py).

        """

        self.data.initialize(layout, numGhostAgents)

############################################################################

#                     THE HIDDEN SECRETS OF PACMAN                         #

#                                                                          #

# You shouldn't need to look through the code in this section of the file. #

############################################################################

SCARED_TIME = 40    # Moves ghosts are scared

COLLISION_TOLERANCE = 0.7 # How close ghosts must be to Pacman to kill

TIME_PENALTY = 1 # Number of points lost each round

class ClassicGameRules:

    """

    These game rules manage the control flow of a game, deciding when

    and how the game starts and ends.

    """

    def __init__(self, timeout=30):

        self.timeout = timeout

    def newGame( self, layout, pacmanAgent, ghostAgents, display, quiet = False, catchExceptions=False):

        agents = [pacmanAgent] + ghostAgents[:layout.getNumGhosts()]

        initState = GameState()

        initState.initialize( layout, len(ghostAgents) )

        game = Game(agents, display, self, catchExceptions=catchExceptions)

        game.state = initState

        self.initialState = initState.deepCopy()

        self.quiet = quiet

        return game

    def process(self, state, game):

        """

        Checks to see whether it is time to end the game.

        """

        if state.isWin(): self.win(state, game)

        if state.isLose(): self.lose(state, game)

    def win( self, state, game ):

        if not self.quiet: print("Pacman emerges victorious! Score: %d" % state.data.score)

        game.gameOver = True

    def lose( self, state, game ):

        if not self.quiet: print("Pacman died! Score: %d" % state.data.score)

        game.gameOver = True

    def getProgress(self, game):

        return float(game.state.getNumFood()) / self.initialState.getNumFood()

    def agentCrash(self, game, agentIndex):

        if agentIndex == 0:

            print("Pacman crashed")

        else:

            print("A ghost crashed")

    def getMaxTotalTime(self, agentIndex):

        return self.timeout

    def getMaxStartupTime(self, agentIndex):

        return self.timeout

    def getMoveWarningTime(self, agentIndex):

        return self.timeout

    def getMoveTimeout(self, agentIndex):

        return self.timeout

    def getMaxTimeWarnings(self, agentIndex):

        return 0

class PacmanRules:

    """

    These functions govern how pacman interacts with his environment under

    the classic game rules.

    """

    PACMAN_SPEED=1

    def getLegalActions( state ):

        """

        Returns a list of possible actions.

        """

        return Actions.getPossibleActions( state.getPacmanState().configuration, state.data.layout.walls )

    getLegalActions = staticmethod( getLegalActions )

    def applyAction( state, action ):

        """

        Edits the state to reflect the results of the action.

        """

        legal = PacmanRules.getLegalActions( state )

        if action not in legal:

            raise Exception("Illegal action " + str(action))

        pacmanState = state.data.agentStates[0]

        # Update Configuration

        vector = Actions.directionToVector( action, PacmanRules.PACMAN_SPEED )

        pacmanState.configuration = pacmanState.configuration.generateSuccessor( vector )

        # Eat

        next = pacmanState.configuration.getPosition()

        nearest = nearestPoint( next )

        if manhattanDistance( nearest, next ) <= 0.5 :
            # Remove food
            PacmanRules.consume( nearest, state )
    applyAction = staticmethod( applyAction )
    def consume( position, state ):
        x,y = position
        # Eat food
        if state.data.food[x][y]:
            state.data.scoreChange += 10
            state.data.food = state.data.food.copy()
            state.data.food[x][y] = False
            state.data._foodEaten = position
            # TODO: cache numFood?
            numFood = state.getNumFood()
            if numFood == 0 and not state.data._lose:
                state.data.scoreChange += 500
                state.data._win = True
        # Eat capsule
        if( position in state.getCapsules() ):
            state.data.capsules.remove( position )
            state.data._capsuleEaten = position
            # Reset all ghosts' scared timers
            for index in range( 1, len( state.data.agentStates ) ):
                state.data.agentStates[index].scaredTimer = SCARED_TIME
    consume = staticmethod( consume )
class GhostRules:
    """
    These functions dictate how ghosts interact with their environment.
    """
    GHOST_SPEED=1.0
    def getLegalActions( state, ghostIndex ):
        """
        Ghosts cannot stop, and cannot turn around unless they
        reach a dead end, but can turn 90 degrees at intersections.
        """
        conf = state.getGhostState( ghostIndex ).configuration
        possibleActions = Actions.getPossibleActions( conf, state.data.layout.walls )
        reverse = Actions.reverseDirection( conf.direction )
        if Directions.STOP in possibleActions:
            possibleActions.remove( Directions.STOP )
        if reverse in possibleActions and len( possibleActions ) > 1:

            possibleActions.remove( reverse )

        return possibleActions

    getLegalActions = staticmethod( getLegalActions )

    def applyAction( state, action, ghostIndex):

        legal = GhostRules.getLegalActions( state, ghostIndex )

        if action not in legal:

            raise Exception("Illegal ghost action " + str(action))

        ghostState = state.data.agentStates[ghostIndex]

        speed = GhostRules.GHOST_SPEED

        if ghostState.scaredTimer > 0: speed /= 2.0

        vector = Actions.directionToVector( action, speed )

        ghostState.configuration = ghostState.configuration.generateSuccessor( vector )

    applyAction = staticmethod( applyAction )

    def decrementTimer( ghostState):

        timer = ghostState.scaredTimer

        if timer == 1:

            ghostState.configuration.pos = nearestPoint( ghostState.configuration.pos )

        ghostState.scaredTimer = max( 0, timer - 1 )

    decrementTimer = staticmethod( decrementTimer )

    def checkDeath( state, agentIndex):

        pacmanPosition = state.getPacmanPosition()

        if agentIndex == 0: # Pacman just moved; Anyone can kill him

            for index in range( 1, len( state.data.agentStates ) ):

                ghostState = state.data.agentStates[index]

                ghostPosition = ghostState.configuration.getPosition()

                if GhostRules.canKill( pacmanPosition, ghostPosition ):

                    GhostRules.collide( state, ghostState, index )

        else:

            ghostState = state.data.agentStates[agentIndex]

            ghostPosition = ghostState.configuration.getPosition()

            if GhostRules.canKill( pacmanPosition, ghostPosition ):

                GhostRules.collide( state, ghostState, agentIndex )

    checkDeath = staticmethod( checkDeath )

    def collide( state, ghostState, agentIndex):

        if ghostState.scaredTimer > 0:

            state.data.scoreChange += 200

            GhostRules.placeGhost(state, ghostState)

            ghostState.scaredTimer = 0

            # Added for first-person

            state.data._eaten[agentIndex] = True

        else:

            if not state.data._win:

                state.data.scoreChange -= 500

                state.data._lose = True

    collide = staticmethod( collide )

    def canKill( pacmanPosition, ghostPosition ):

        return manhattanDistance( ghostPosition, pacmanPosition ) <= COLLISION_TOLERANCE
    canKill = staticmethod( canKill )
    def placeGhost(state, ghostState):
        ghostState.configuration = ghostState.start
    placeGhost = staticmethod( placeGhost )
#############################
# FRAMEWORK TO START A GAME #
#############################
def default(str):
    return str + ' [Default: %default]'
def parseAgentArgs(str):
    if str == None: return {}
    pieces = str.split(',')
    opts = {}
    for p in pieces:
        if '=' in p:
            key, val = p.split('=')
        else:
            key,val = p, 1
        opts[key] = val
    return opts
def readCommand( argv ):
    """
    Processes the command used to run pacman from the command line.
    """
    from optparse import OptionParser
    usageStr = """
    USAGE:      python pacman.py

    EXAMPLES:   (1) python pacman.py

                    - starts an interactive game

                (2) python pacman.py --layout smallClassic --zoom 2

                OR  python pacman.py -l smallClassic -z 2

                    - starts an interactive game on a smaller board, zoomed in

    """

    parser = OptionParser(usageStr)

    parser.add_option('-n', '--numGames', dest='numGames', type='int',

                      help=default('the number of GAMES to play'), metavar='GAMES', default=1)

    parser.add_option('-l', '--layout', dest='layout',

                      help=default('the LAYOUT_FILE from which to load the map layout'),

                      metavar='LAYOUT_FILE', default='mediumClassic')

    parser.add_option('-p', '--pacman', dest='pacman',

                      help=default('the agent TYPE in the pacmanAgents module to use'),

                      metavar='TYPE', default='KeyboardAgent')

    parser.add_option('-t', '--textGraphics', action='store_true', dest='textGraphics',

                      help='Display output as text only', default=False)

    parser.add_option('-q', '--quietTextGraphics', action='store_true', dest='quietGraphics',

                      help='Generate minimal output and no graphics', default=False)

    parser.add_option('-g', '--ghosts', dest='ghost',

                      help=default('the ghost agent TYPE in the ghostAgents module to use'),

                      metavar = 'TYPE', default='RandomGhost')

    parser.add_option('-k', '--numghosts', type='int', dest='numGhosts',

                      help=default('The maximum number of ghosts to use'), default=4)

    parser.add_option('-z', '--zoom', type='float', dest='zoom',

                      help=default('Zoom the size of the graphics window'), default=1.0)

    parser.add_option('-f', '--fixRandomSeed', action='store_true', dest='fixRandomSeed',

                      help='Fixes the random seed to always play the same game', default=False)

    parser.add_option('-r', '--recordActions', action='store_true', dest='record',

                      help='Writes game histories to a file (named by the time they were played)', default=False)

    parser.add_option('--replay', dest='gameToReplay',

                      help='A recorded game file (pickle) to replay', default=None)

    parser.add_option('-a','--agentArgs',dest='agentArgs',

                      help='Comma separated values sent to agent. e.g. "opt1=val1,opt2,opt3=val3"')

    parser.add_option('-x', '--numTraining', dest='numTraining', type='int',

                      help=default('How many episodes are training (suppresses output)'), default=0)

    parser.add_option('--frameTime', dest='frameTime', type='float',

                      help=default('Time to delay between frames; <0 means keyboard'), default=0.1)
    parser.add_option('-c', '--catchExceptions', action='store_true', dest='catchExceptions',
                      help='Turns on exception handling and timeouts during games', default=False)
    parser.add_option('--timeout', dest='timeout', type='int',
                      help=default('Maximum length of time an agent can spend computing in a single game'), default=30)
    options, otherjunk = parser.parse_args(argv)
    if len(otherjunk) != 0:
        raise Exception('Command line input not understood: ' + str(otherjunk))
    args = dict()
    # Fix the random seed
    if options.fixRandomSeed: random.seed('cs188')
    # Choose a layout
    args['layout'] = layout.getLayout( options.layout )
    if args['layout'] == None: raise Exception("The layout " + options.layout + " cannot be found")
    # Choose a Pacman agent
    noKeyboard = options.gameToReplay == None and (options.textGraphics or options.quietGraphics)
    pacmanType = loadAgent(options.pacman, noKeyboard)
    agentOpts = parseAgentArgs(options.agentArgs)
    if options.numTraining > 0:

        args['numTraining'] = options.numTraining

        if 'numTraining' not in agentOpts: agentOpts['numTraining'] = options.numTraining

    pacman = pacmanType(**agentOpts) # Instantiate Pacman with agentArgs

    args['pacman'] = pacman

    # Don't display training games

    if 'numTrain' in agentOpts:

        options.numQuiet = int(agentOpts['numTrain'])

        options.numIgnore = int(agentOpts['numTrain'])

    # Choose a ghost agent

    ghostType = loadAgent(options.ghost, noKeyboard)

    args['ghosts'] = [ghostType( i+1 ) for i in range( options.numGhosts )]

    # Choose a display format

    if options.quietGraphics:

        import textDisplay

        args['display'] = textDisplay.NullGraphics()

    elif options.textGraphics:

        import textDisplay

        textDisplay.SLEEP_TIME = options.frameTime

        args['display'] = textDisplay.PacmanGraphics()

    else:

        import graphicsDisplay

        args['display'] = graphicsDisplay.PacmanGraphics(options.zoom, frameTime = options.frameTime)

    args['numGames'] = options.numGames

    args['record'] = options.record

    args['catchExceptions'] = options.catchExceptions

    args['timeout'] = options.timeout

    # Special case: recorded games don't use the runGames method or args structure

    if options.gameToReplay != None:

        print('Replaying recorded game %s.' % options.gameToReplay)

        import pickle

        f = open(options.gameToReplay, 'rb')

        try: recorded = pickle.load(f)

        finally: f.close()

        recorded['display'] = args['display']

        replayGame(**recorded)

        sys.exit(0)

    return args

def loadAgent(pacman, nographics):

    # Looks through all pythonPath Directories for the right module,

    pythonPathStr = os.path.expandvars("$PYTHONPATH")

    if pythonPathStr.find(';') == -1:

        pythonPathDirs = pythonPathStr.split(':')

    else:

        pythonPathDirs = pythonPathStr.split(';')

    pythonPathDirs.append('.')

    for moduleDir in pythonPathDirs:

        if not os.path.isdir(moduleDir): continue

        moduleNames = [f for f in os.listdir(moduleDir) if f.endswith('gents.py')]

        for modulename in moduleNames:

            try:

                module = __import__(modulename[:-3])

            except ImportError:

                continue

            if pacman in dir(module):

                if nographics and modulename == 'keyboardAgents.py':

                    raise Exception('Using the keyboard requires graphics (not text display)')

                return getattr(module, pacman)

    raise Exception('The agent ' + pacman + ' is not specified in any *Agents.py.')

def replayGame( layout, actions, display ):

    import pacmanAgents, ghostAgents

    rules = ClassicGameRules()

    agents = [pacmanAgents.GreedyAgent()] + [ghostAgents.RandomGhost(i+1) for i in range(layout.getNumGhosts())]

    game = rules.newGame( layout, agents[0], agents[1:], display )

    state = game.state

    display.initialize(state.data)

    for action in actions:

            # Execute the action

        state = state.generateSuccessor( *action )

        # Change the display

        display.update( state.data )

        # Allow for game specific conditions (winning, losing, etc.)

        rules.process(state, game)

    display.finish()

def runGames( layout, pacman, ghosts, display, numGames, record, numTraining = 0, catchExceptions=False, timeout=30 ):

    import __main__

    __main__.__dict__['_display'] = display

    rules = ClassicGameRules(timeout)

    games = []

    for i in range( numGames ):

        beQuiet = i < numTraining
        if beQuiet:
                # Suppress output and graphics
            import textDisplay
            gameDisplay = textDisplay.NullGraphics()
            rules.quiet = True
        else:
            gameDisplay = display
            rules.quiet = False
        game = rules.newGame( layout, pacman, ghosts, gameDisplay, beQuiet, catchExceptions)
        game.run()
        if not beQuiet: games.append(game)
        if record:
            import time, pickle
            fname = ('recorded-game-%d' % (i + 1)) +  '-'.join([str(t) for t in time.localtime()[1:6]])
            f = open(fname, 'wb')
            components = {'layout': layout, 'actions': game.moveHistory}
            pickle.dump(components, f)
            f.close()
    if (numGames-numTraining) > 0:

        scores = [game.state.getScore() for game in games]

        wins = [game.state.isWin() for game in games]

        winRate = wins.count(True)/ float(len(wins))

        print('Average Score:', sum(scores) / float(len(scores)))

        print('Scores:       ', ', '.join([str(score) for score in scores]))

        print('Win Rate:      %d/%d (%.2f)' % (wins.count(True), len(wins), winRate))

        print('Record:       ', ', '.join([ ['Loss', 'Win'][int(w)] for w in wins]))

    return games

if __name__ == '__main__':

    """

    The main function called when pacman.py is run

    from the command line:

    > python pacman.py

    See the usage string for more details.

    > python pacman.py --help

    """

    args = readCommand( sys.argv[1:] ) # Get game components based on input

    runGames( **args )

    # import cProfile

    # cProfile.run("runGames( **args )")

    pass
homework_1_search/pacmanAgents.py

# pacmanAgents.py

# ---------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
from pacman import Directions

from game import Agent

import random

import game

import util

class LeftTurnAgent(game.Agent):

    "An agent that turns left at every opportunity"

    def getAction(self, state):

        legal = state.getLegalPacmanActions()

        current = state.getPacmanState().configuration.direction

        if current == Directions.STOP: current = Directions.NORTH

        left = Directions.LEFT[current]

        if left in legal: return left

        if current in legal: return current

        if Directions.RIGHT[current] in legal: return Directions.RIGHT[current]

        if Directions.LEFT[left] in legal: return Directions.LEFT[left]

        return Directions.STOP

class GreedyAgent(Agent):

    def __init__(self, evalFn="scoreEvaluation"):

        self.evaluationFunction = util.lookup(evalFn, globals())

        assert self.evaluationFunction != None

    def getAction(self, state):

        # Generate candidate actions

        legal = state.getLegalPacmanActions()

        if Directions.STOP in legal: legal.remove(Directions.STOP)

        successors = [(state.generateSuccessor(0, action), action) for action in legal]

        scored = [(self.evaluationFunction(state), action) for state, action in successors]

        bestScore = max(scored)[0]

        bestActions = [pair[1] for pair in scored if pair[0] == bestScore]

        return random.choice(bestActions)

def scoreEvaluation(state):

    return state.getScore()
homework_1_search/projectParams.py

# projectParams.py

# ----------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
STUDENT_CODE_DEFAULT = 'searchAgents.py,search.py'

PROJECT_TEST_CLASSES = 'searchTestClasses.py'

PROJECT_NAME = 'Project 1: Search'

BONUS_PIC = False
homework_1_search/search.py

# search.py

# ---------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
"""

In search.py, you will implement generic search algorithms which are called by

Pacman agents (in searchAgents.py).

"""

import util

class SearchProblem:

    """

    This class outlines the structure of a search problem, but doesn't implement

    any of the methods (in object-oriented terminology: an abstract class).

    You do not need to change anything in this class, ever.

    """

    def getStartState(self):

        """

        Returns the start state for the search problem.

        """

        util.raiseNotDefined()

    def isGoalState(self, state):

        """

          state: Search state

        Returns True if and only if the state is a valid goal state.

        """

        util.raiseNotDefined()

    def getSuccessors(self, state):

        """

          state: Search state

        For a given state, this should return a list of triples, (successor,

        action, stepCost), where 'successor' is a successor to the current

        state, 'action' is the action required to get there, and 'stepCost' is

        the incremental cost of expanding to that successor.

        """

        util.raiseNotDefined()

    def getCostOfActions(self, actions):

        """

         actions: A list of actions to take

        This method returns the total cost of a particular sequence of actions.

        The sequence must be composed of legal moves.

        """

        util.raiseNotDefined()
def tinyMazeSearch(problem):

    """

    Returns a sequence of moves that solves tinyMaze.  For any other maze, the

    sequence of moves will be incorrect, so only use this for tinyMaze.

    """

    from game import Directions

    s = Directions.SOUTH

    w = Directions.WEST

    return  [s, s, w, s, w, w, s, w]

def depthFirstSearch(problem):

    """

    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the

    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to

    understand the search problem that is being passed in:

    print("Start:", problem.getStartState())

    print("Is the start a goal?", problem.isGoalState(problem.getStartState()))

    print("Start's successors:", problem.getSuccessors(problem.getStartState()))

    """

    "*** YOUR CODE HERE ***"

    util.raiseNotDefined()

def breadthFirstSearch(problem):

    """Search the shallowest nodes in the search tree first."""

    "*** YOUR CODE HERE ***"

    util.raiseNotDefined()

def uniformCostSearch(problem):

    """Search the node of least total cost first.

    Important functions to implement

    1 - PriorityQueue

    2 - problem.getStartState()

    3 - problem.isGoalState(xy)

    4 - problem.getSuccessors(xy)

    5 - problem.getCostOfActions(new_path)

    """

    "*** YOUR CODE HERE ***"

    util.raiseNotDefined()
def nullHeuristic(state, problem=None):

    """

    A heuristic function estimates the cost from the current state to the nearest

    goal in the provided SearchProblem.  This heuristic is trivial.

    """

    return 0

def aStarSearch(problem, heuristic=nullHeuristic):

    """Search the node that has the lowest combined cost and heuristic first."""

    "*** YOUR CODE HERE ***"
# Abbreviations

bfs = breadthFirstSearch

dfs = depthFirstSearch

astar = aStarSearch

ucs = uniformCostSearch
homework_1_search/searchAgents.py

# searchAgents.py

# ---------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
"""

This file contains all of the agents that can be selected to control Pacman.  To

select an agent, use the '-p' option when running pacman.py.  Arguments can be

passed to your agent using '-a'.  For example, to load a SearchAgent that uses

depth first search (dfs), run the following command:

> python pacman.py -p SearchAgent -a fn=depthFirstSearch

Commands to invoke other search strategies can be found in the project

description.

Please only change the parts of the file you are asked to.  Look for the lines

that say

"*** YOUR CODE HERE ***"

The parts you fill in start about 3/4 of the way down.  Follow the project

description for details.

Good luck and happy searching!

"""

from game import Directions

from game import Agent

from game import Actions

import util

import time

import search

class GoWestAgent(Agent):

    "An agent that goes West until it can't."

    def getAction(self, state):

        "The agent receives a GameState (defined in pacman.py)."

        if Directions.WEST in state.getLegalPacmanActions():

            return Directions.WEST

        else:

            return Directions.STOP

#######################################################

# This portion is written for you, but will only work #

#       after you fill in parts of search.py          #

#######################################################

class SearchAgent(Agent):

    """

    This very general search agent finds a path using a supplied search

    algorithm for a supplied search problem, then returns actions to follow that

    path.

    As a default, this agent runs DFS on a PositionSearchProblem to find

    location (1,1)

    Options for fn include:

      depthFirstSearch or dfs

      breadthFirstSearch or bfs
    Note: You should NOT change any code in SearchAgent

    """

    def __init__(self, fn='depthFirstSearch', prob='PositionSearchProblem', heuristic='nullHeuristic'):

        # Warning: some advanced Python magic is employed below to find the right functions and problems

        # Get the search function from the name and heuristic

        if fn not in dir(search):

            raise AttributeError(fn + ' is not a search function in search.py.')

        func = getattr(search, fn)

        if 'heuristic' not in func.__code__.co_varnames:

            print('[SearchAgent] using function ' + fn)

            self.searchFunction = func

        else:

            if heuristic in globals().keys():

                heur = globals()[heuristic]

            elif heuristic in dir(search):

                heur = getattr(search, heuristic)

            else:

                raise AttributeError(heuristic + ' is not a function in searchAgents.py or search.py.')

            print('[SearchAgent] using function %s and heuristic %s' % (fn, heuristic))

            # Note: this bit of Python trickery combines the search algorithm and the heuristic

            self.searchFunction = lambda x: func(x, heuristic=heur)

        # Get the search problem type from the name

        if prob not in globals().keys() or not prob.endswith('Problem'):

            raise AttributeError(prob + ' is not a search problem type in SearchAgents.py.')

        self.searchType = globals()[prob]

        print('[SearchAgent] using problem type ' + prob)

    def registerInitialState(self, state):

        """

        This is the first time that the agent sees the layout of the game

        board. Here, we choose a path to the goal. In this phase, the agent

        should compute the path to the goal and store it in a local variable.

        All of the work is done in this method!

        state: a GameState object (pacman.py)

        """

        if self.searchFunction == None: raise Exception("No search function provided for SearchAgent")

        starttime = time.time()

        problem = self.searchType(state) # Makes a new search problem

        self.actions  = self.searchFunction(problem) # Find a path

        totalCost = problem.getCostOfActions(self.actions)

        print('Path found with total cost of %d in %.1f seconds' % (totalCost, time.time() - starttime))

        if '_expanded' in dir(problem): print('Search nodes expanded: %d' % problem._expanded)

    def getAction(self, state):

        """

        Returns the next action in the path chosen earlier (in

        registerInitialState).  Return Directions.STOP if there is no further

        action to take.

        state: a GameState object (pacman.py)

        """

        if 'actionIndex' not in dir(self): self.actionIndex = 0

        i = self.actionIndex

        self.actionIndex += 1

        if i < len(self.actions):
            return self.actions[i]
        else:
            return Directions.STOP
class PositionSearchProblem(search.SearchProblem):
    """
    A search problem defines the state space, start state, goal test, successor
    function and cost function.  This search problem can be used to find paths
    to a particular point on the pacman board.
    The state space consists of (x,y) positions in a pacman game.
    Note: this search problem is fully specified; you should NOT change it.
    """
    def __init__(self, gameState, costFn = lambda x: 1, goal=(1,1), start=None, warn=True, visualize=True):
        """
        Stores the start and goal.
        gameState: A GameState object (pacman.py)
        costFn: A function from a search state (tuple) to a non-negative number
        goal: A position in the gameState
        """
        self.walls = gameState.getWalls()
        self.startState = gameState.getPacmanPosition()
        if start != None: self.startState = start
        self.goal = goal
        self.costFn = costFn
        self.visualize = visualize
        if warn and (gameState.getNumFood() != 1 or not gameState.hasFood(*goal)):
            print('Warning: this does not look like a regular search maze')
        # For display purposes
        self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE
    def getStartState(self):
        return self.startState
    def isGoalState(self, state):
        isGoal = state == self.goal
        # For display purposes only
        if isGoal and self.visualize:
            self._visitedlist.append(state)
            import __main__
            if '_display' in dir(__main__):
                if 'drawExpandedCells' in dir(__main__._display): #@UndefinedVariable
                    __main__._display.drawExpandedCells(self._visitedlist) #@UndefinedVariable
        return isGoal
    def getSuccessors(self, state):
        """
        Returns successor states, the actions they require, and a cost of 1.
         As noted in search.py:
             For a given state, this should return a list of triples,
         (successor, action, stepCost), where 'successor' is a
         successor to the current state, 'action' is the action
         required to get there, and 'stepCost' is the incremental
         cost of expanding to that successor
        """
        successors = []
        for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            x,y = state
            dx, dy = Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            if not self.walls[nextx][nexty]:
                nextState = (nextx, nexty)
                cost = self.costFn(nextState)
                successors.append( ( nextState, action, cost) )
        # Bookkeeping for display purposes
        self._expanded += 1 # DO NOT CHANGE
        if state not in self._visited:
            self._visited[state] = True
            self._visitedlist.append(state)
        return successors
    def getCostOfActions(self, actions):
        """
        Returns the cost of a particular sequence of actions. If those actions
        include an illegal move, return 999999.
        """
        if actions == None: return 999999
        x,y= self.getStartState()
        cost = 0
        for action in actions:
            # Check figure out the next state and see whether its' legal
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]: return 999999
            cost += self.costFn((x,y))
        return cost
class StayEastSearchAgent(SearchAgent):
    """
    An agent for position search with a cost function that penalizes being in
    positions on the West side of the board.
    The cost function for stepping into a position (x,y) is 1/2^x.
    """
    def __init__(self):
        self.searchFunction = search.uniformCostSearch
        costFn = lambda pos: .5 ** pos[0]
        self.searchType = lambda state: PositionSearchProblem(state, costFn, (1, 1), None, False)
class StayWestSearchAgent(SearchAgent):
    """
    An agent for position search with a cost function that penalizes being in
    positions on the East side of the board.
    The cost function for stepping into a position (x,y) is 2^x.
    """
    def __init__(self):
        self.searchFunction = search.uniformCostSearch
        costFn = lambda pos: 2 ** pos[0]
        self.searchType = lambda state: PositionSearchProblem(state, costFn)
def manhattanHeuristic(position, problem, info={}):
    "The Manhattan distance heuristic for a PositionSearchProblem"
    xy1 = position
    xy2 = problem.goal
    return abs(xy1[0] - xy2[0]) + abs(xy1[1] - xy2[1])
def euclideanHeuristic(position, problem, info={}):
    "The Euclidean distance heuristic for a PositionSearchProblem"
    xy1 = position
    xy2 = problem.goal
    return ( (xy1[0] - xy2[0]) ** 2 + (xy1[1] - xy2[1]) ** 2 ) ** 0.5
#####################################################
# This portion is incomplete.  Time to write code!  #
#####################################################
class CornersProblem(search.SearchProblem):
    """
    This search problem finds paths through all four corners of a layout.
    state is represented by a tuple (pos,visited), where pos is the position of pacman
    and visited is a tuple where vistied[i] = 0 means i^th corner is not yet visited.
    You can change state space and successor function if required
    """
    def __init__(self, startingGameState):
        """
        Stores the walls, pacman's starting position and corners.
        """
        self.walls = startingGameState.getWalls()
        self.startingPosition = startingGameState.getPacmanPosition()
        top, right = self.walls.height-2, self.walls.width-2
        self.corners = ((1,1), (1,top), (right, 1), (right, top))
        for corner in self.corners:
            if not startingGameState.hasFood(*corner):
                print('Warning: no food in corner ' + str(corner))
        self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded
        # Please add any code here which you would like to use
        # in initializing the problem
    def getStartState(self):
        """
        Returns the start state (in your state space, not the full Pacman state
        space)
        """
        pos = self.startingPosition
        visited = [0,0,0,0]
        for i in range(len(self.corners)):
                    if(self.corners[i] == pos):
                        visited[i] = 1
        visited = tuple(visited)
        startState = (pos,visited)
        return startState
    def isGoalState(self, state):
        """
        Returns whether this search state is a goal state of the problem.
        """
        if(0  in state[1]):
            return False;
        return True;
    def getSuccessors(self, state):
        """
        Returns successor states, the actions they require, and a cost of 1.
         As noted in search.py:
            For a given state, this should return a list of triples, (successor,
            action, stepCost), where 'successor' is a successor to the current
            state, 'action' is the action required to get there, and 'stepCost'
            is the incremental cost of expanding to that successor
        """
        successors = []
        for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            # Add a successor state to the successor list if the action is legal
            # Here's a code snippet for figuring out whether a new position hits a wall:
            x = state[0][0]
            y = state[0][1]
            dx, dy = Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            hitsWall = self.walls[nextx][nexty]
            if(not hitsWall):
                next_pos =  (nextx,nexty)
                next_visited =  list(state[1])
                for i in range(len(self.corners)):
                    if(self.corners[i] == next_pos):
                        next_visited[i] = 1
                next_visited = tuple(next_visited)
                nextState = (next_pos,next_visited)
                cost = 1
                successors.append( ( nextState, action, cost) )
        self._expanded += 1 # DO NOT CHANGE
        return successors
    def getCostOfActions(self, actions):
        """
        Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999.  This is implemented for you.
        """
        if actions == None: return 999999
        x,y= self.startingPosition
        for action in actions:
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]: return 999999
        return len(actions)

def cornersHeuristic(state, problem):
    """
    A heuristic for the CornersProblem that you defined.
      state:   The current search state
               (a data structure you chose in your search problem)
      problem: The CornersProblem instance for this layout.
    This function should always return a number that is a lower bound on the
    shortest path from the state to a goal of the problem; i.e.  it should be
    admissible (as well as consistent).
    """
    corners = problem.corners # These are the corner coordinates
    walls = problem.walls # These are the walls of the maze, as a Grid (game.py)
    "*** YOUR CODE HERE ***"
    from util import manhattanDistance
    # Goal state #
    if problem.isGoalState(state):
        return 0
    else:
        distancesFromGoals = [] # Calculate all distances from goals(not visited corners)
        for index,item in enumerate(state[1]):
            if item == 0: # Not visited corner
                # Use manhattan method #
                distancesFromGoals.append(manhattanDistance(state[0],corners[index]))
        # Worst case. This guess should be higher than real. Pick higher distance #
        return max(distancesFromGoals)
class AStarCornersAgent(SearchAgent):
    "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic"
    def __init__(self):
        self.searchFunction = lambda prob: search.aStarSearch(prob, cornersHeuristic)
        self.searchType = CornersProblem
class FoodSearchProblem:
    """
    A search problem associated with finding the a path that collects all of the
    food (dots) in a Pacman game.
    A search state in this problem is a tuple ( pacmanPosition, foodGrid ) where
      pacmanPosition: a tuple (x,y) of integers specifying Pacman's position
      foodGrid:       a Grid (see game.py) of either True or False, specifying remaining food
    """
    def __init__(self, startingGameState):
        self.start = (startingGameState.getPacmanPosition(), startingGameState.getFood())
        self.walls = startingGameState.getWalls()
        self.startingGameState = startingGameState
        self._expanded = 0 # DO NOT CHANGE
        self.heuristicInfo = {} # A dictionary for the heuristic to store information
    def getStartState(self):
        return self.start
    def isGoalState(self, state):
        return state[1].count() == 0
    def getSuccessors(self, state):
        "Returns successor states, the actions they require, and a cost of 1."
        successors = []
        self._expanded += 1 # DO NOT CHANGE
        for direction in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            x,y = state[0]
            dx, dy = Actions.directionToVector(direction)
            nextx, nexty = int(x + dx), int(y + dy)
            if not self.walls[nextx][nexty]:
                nextFood = state[1].copy()
                nextFood[nextx][nexty] = False
                successors.append( ( ((nextx, nexty), nextFood), direction, 1) )
        return successors
    def getCostOfActions(self, actions):
        """Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999"""
        x,y= self.getStartState()[0]
        cost = 0
        for action in actions:
            # figure out the next state and see whether it's legal
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]:
                return 999999
            cost += 1
        return cost
class AStarFoodSearchAgent(SearchAgent):
    "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic"
    def __init__(self):
        self.searchFunction = lambda prob: search.aStarSearch(prob, foodHeuristic)
        self.searchType = FoodSearchProblem
def foodHeuristic(state, problem):
    """
    Your heuristic for the FoodSearchProblem goes here.
    This heuristic must be consistent to ensure correctness.  First, try to come
    up with an admissible heuristic; almost all admissible heuristics will be
    consistent as well.
    If using A* ever finds a solution that is worse uniform cost search finds,
    your heuristic is *not* consistent, and probably not admissible!  On the
    other hand, inadmissible or inconsistent heuristics may find optimal
    solutions, so be careful.
    The state is a tuple ( pacmanPosition, foodGrid ) where foodGrid is a Grid
    (see game.py) of either True or False. You can call foodGrid.asList() to get
    a list of food coordinates instead.
    If you want access to info like walls, capsules, etc., you can query the
    problem.  For example, problem.walls gives you a Grid of where the walls
    are.
    If you want to *store* information to be reused in other calls to the
    heuristic, there is a dictionary called problem.heuristicInfo that you can
    use. For example, if you only want to count the walls once and store that
    value, try: problem.heuristicInfo['wallCount'] = problem.walls.count()
    Subsequent calls to this heuristic can access
    problem.heuristicInfo['wallCount']
    """
    position, foodGrid = state
    "*** YOUR CODE HERE ***"
    return 0
class ClosestDotSearchAgent(SearchAgent):
    "Search for all food using a sequence of searches"
    def registerInitialState(self, state):
        self.actions = []
        currentState = state
        while(currentState.getFood().count() > 0):

            nextPathSegment = self.findPathToClosestDot(currentState) # The missing piece

            self.actions += nextPathSegment

            for action in nextPathSegment:

                legal = currentState.getLegalActions()

                if action not in legal:

                    t = (str(action), str(currentState))

                    raise Exception('findPathToClosestDot returned an illegal move: %s!\n%s' % t)

                currentState = currentState.generateSuccessor(0, action)

        self.actionIndex = 0

        print('Path found with cost %d.' % len(self.actions))

    def findPathToClosestDot(self, gameState):

        """

        Returns a path (a list of actions) to the closest dot, starting from

        gameState.

        """

        # Here are some useful elements of the startState

        startPosition = gameState.getPacmanPosition()

        food = gameState.getFood()

        walls = gameState.getWalls()

        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"

        util.raiseNotDefined()

class AnyFoodSearchProblem(PositionSearchProblem):

    """

    A search problem for finding a path to any food.

    This search problem is just like the PositionSearchProblem, but has a

    different goal test, which you need to fill in below.  The state space and

    successor function do not need to be changed.

    The class definition above, AnyFoodSearchProblem(PositionSearchProblem),

    inherits the methods of the PositionSearchProblem.

    You can use this search problem to help you fill in the findPathToClosestDot

    method.

    """

    def __init__(self, gameState):

        "Stores information from the gameState.  You don't need to change this."

        # Store the food for later reference

        self.food = gameState.getFood()

        # Store info for the PositionSearchProblem (no need to change this)

        self.walls = gameState.getWalls()

        self.startState = gameState.getPacmanPosition()

        self.costFn = lambda x: 1

        self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE

    def isGoalState(self, state):

        """

        The state is Pacman's position. Fill this in with a goal test that will

        complete the problem definition.

        """

        x,y = state

        "*** YOUR CODE HERE ***"

        util.raiseNotDefined()

def mazeDistance(point1, point2, gameState):

    """

    Returns the maze distance between any two points, using the search functions

    you have already built. The gameState can be any game state -- Pacman's

    position in that state is ignored.

    Example usage: mazeDistance( (2,4), (5,6), gameState)

    This might be a useful helper function for your ApproximateSearchAgent.

    """

    x1, y1 = point1

    x2, y2 = point2

    walls = gameState.getWalls()

    assert not walls[x1][y1], 'point1 is a wall: ' + str(point1)

    assert not walls[x2][y2], 'point2 is a wall: ' + str(point2)

    prob = PositionSearchProblem(gameState, start=point1, goal=point2, warn=False, visualize=False)

    return len(search.bfs(prob))
homework_1_search/searchTestClasses.py

# searchTestClasses.py

# --------------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
import sys

import re

import testClasses

import textwrap

# import project specific code

import layout

import pacman

from search import SearchProblem

# helper function for printing solutions in solution files

def wrap_solution(solution):

    if type(solution) == type([]):

        return '\n'.join(textwrap.wrap(' '.join(solution)))

    else:

        return str(solution)
def followAction(state, action, problem):

  for successor1, action1, cost1 in problem.getSuccessors(state):

    if action == action1: return successor1

  return None

def followPath(path, problem):

  state = problem.getStartState()

  states = [state]

  for action in path:

    state = followAction(state, action, problem)

    states.append(state)

  return states

def checkSolution(problem, path):

  state = problem.getStartState()

  for action in path:

    state = followAction(state, action, problem)

  return problem.isGoalState(state)

# Search problem on a plain graph

class GraphSearch(SearchProblem):

    # Read in the state graph; define start/end states, edges and costs

    def __init__(self, graph_text):

        self.expanded_states = []

        lines = graph_text.split('\n')

        r = re.match('start_state:(.*)', lines[0])

        if r == None:

            print("Broken graph:")

            print('"""%s"""' % graph_text)

            raise Exception("GraphSearch graph specification start_state not found or incorrect on line 0")

        self.start_state = r.group(1).strip()

        r = re.match('goal_states:(.*)', lines[1])

        if r == None:

            print("Broken graph:")

            print('"""%s"""' % graph_text)

            raise Exception("GraphSearch graph specification goal_states not found or incorrect on line 1")

        goals = r.group(1).split()

        self.goals = [str.strip(g) for g in goals]

        self.successors = {}

        all_states = set()

        self.orderedSuccessorTuples = []

        for l in lines[2:]:

            if len(l.split()) == 3:

                start, action, next_state = l.split()

                cost = 1

            elif len(l.split()) == 4:

                start, action, next_state, cost = l.split()

            else:

                print("Broken graph:")

                print('"""%s"""' % graph_text)

                raise Exception("Invalid line in GraphSearch graph specification on line:" + l)

            cost = float(cost)

            self.orderedSuccessorTuples.append((start, action, next_state, cost))

            all_states.add(start)

            all_states.add(next_state)

            if start not in self.successors:

                self.successors[start] = []

            self.successors[start].append((next_state, action, cost))

        for s in all_states:

            if s not in self.successors:

                self.successors[s] = []

    # Get start state

    def getStartState(self):

        return self.start_state

    # Check if a state is a goal state

    def isGoalState(self, state):

        return state in self.goals

    # Get all successors of a state

    def getSuccessors(self, state):

        self.expanded_states.append(state)

        return list(self.successors[state])

    # Calculate total cost of a sequence of actions

    def getCostOfActions(self, actions):

        total_cost = 0

        state = self.start_state

        for a in actions:

            successors = self.successors[state]

            match = False

            for (next_state, action, cost) in successors:

                if a == action:

                    state = next_state

                    total_cost += cost

                    match = True

            if not match:

                print('invalid action sequence')

                sys.exit(1)

        return total_cost

    # Return a list of all states on which 'getSuccessors' was called

    def getExpandedStates(self):

        return self.expanded_states

    def __str__(self):

        print(self.successors)

        edges = ["%s %s %s %s" % t for t in self.orderedSuccessorTuples]

        return \

"""start_state: %s

goal_states: %s

%s""" % (self.start_state, " ".join(self.goals), "\n".join(edges))
def parseHeuristic(heuristicText):

    heuristic = {}

    for line in heuristicText.split('\n'):

        tokens = line.split()

        if len(tokens) != 2:

            print("Broken heuristic:")

            print('"""%s"""' % heuristicText)

            raise Exception("GraphSearch heuristic specification broken at tokens:" + str(tokens))

        state, h = tokens

        heuristic[state] = float(h)

    def graphHeuristic(state, problem=None):

        if state in heuristic:

            return heuristic[state]

        else:

            import pprint

            pp = pprint.PrettyPrinter(indent=4)

            print("Heuristic:")

            pp.pprint(heuristic)

            raise Exception("Graph heuristic called with invalid state: " + str(state))

    return graphHeuristic
class GraphSearchTest(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(GraphSearchTest, self).__init__(question, testDict)

        self.graph_text = testDict['graph']

        self.alg = testDict['algorithm']

        self.diagram = testDict['diagram']

        self.exactExpansionOrder = testDict.get('exactExpansionOrder', 'True').lower() == "true"

        if 'heuristic' in testDict:

            self.heuristic = parseHeuristic(testDict['heuristic'])

        else:

            self.heuristic = None

    # Note that the return type of this function is a tripple:

    # (solution, expanded states, error message)

    def getSolInfo(self, search):

        alg = getattr(search, self.alg)

        problem = GraphSearch(self.graph_text)

        if self.heuristic != None:

            solution = alg(problem, self.heuristic)

        else:

            solution = alg(problem)

        if type(solution) != type([]):

            return None, None, 'The result of %s must be a list. (Instead, it is %s)' % (self.alg, type(solution))

        return solution, problem.getExpandedStates(), None

    # Run student code.  If an error message is returned, print error and return false.

    # If a good solution is returned, printn the solution and return true; otherwise,

    # print both the correct and student's solution and return false.

    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        gold_solution = [str.split(solutionDict['solution']), str.split(solutionDict['rev_solution'])]

        gold_expanded_states = [str.split(solutionDict['expanded_states']), str.split(solutionDict['rev_expanded_states'])]

        solution, expanded_states, error = self.getSolInfo(search)

        if error != None:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('\t%s' % error)

            return False

        if solution in gold_solution and (not self.exactExpansionOrder or expanded_states in gold_expanded_states):

            grades.addMessage('PASS: %s' % self.path)

            grades.addMessage('\tsolution:\t\t%s' % solution)

            grades.addMessage('\texpanded_states:\t%s' % expanded_states)

            return True

        else:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('\tgraph:')

            for line in self.diagram.split('\n'):

                grades.addMessage('\t    %s' % (line,))

            grades.addMessage('\tstudent solution:\t\t%s' % solution)

            grades.addMessage('\tstudent expanded_states:\t%s' % expanded_states)

            grades.addMessage('')

            grades.addMessage('\tcorrect solution:\t\t%s' % gold_solution[0])

            grades.addMessage('\tcorrect expanded_states:\t%s' % gold_expanded_states[0])

            grades.addMessage('\tcorrect rev_solution:\t\t%s' % gold_solution[1])

            grades.addMessage('\tcorrect rev_expanded_states:\t%s' % gold_expanded_states[1])

            return False

    def writeSolution(self, moduleDict, filePath):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        # open file and write comments

        handle = open(filePath, 'w')

        handle.write('# This is the solution file for %s.\n' % self.path)

        handle.write('# This solution is designed to support both right-to-left\n')

        handle.write('# and left-to-right implementations.\n')

        # write forward solution

        solution, expanded_states, error = self.getSolInfo(search)

        if error != None: raise Exception("Error in solution code: %s" % error)

        handle.write('solution: "%s"\n' % ' '.join(solution))

        handle.write('expanded_states: "%s"\n' % ' '.join(expanded_states))

        # reverse and write backwards solution

        search.REVERSE_PUSH = not search.REVERSE_PUSH

        solution, expanded_states, error = self.getSolInfo(search)

        if error != None: raise Exception("Error in solution code: %s" % error)

        handle.write('rev_solution: "%s"\n' % ' '.join(solution))

        handle.write('rev_expanded_states: "%s"\n' % ' '.join(expanded_states))

        # clean up

        search.REVERSE_PUSH = not search.REVERSE_PUSH

        handle.close()

        return True
class PacmanSearchTest(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(PacmanSearchTest, self).__init__(question, testDict)

        self.layout_text = testDict['layout']

        self.alg = testDict['algorithm']

        self.layoutName = testDict['layoutName']

        # TODO: sensible to have defaults like this?

        self.leewayFactor = float(testDict.get('leewayFactor', '1'))

        self.costFn = eval(testDict.get('costFn', 'None'))

        self.searchProblemClassName = testDict.get('searchProblemClass', 'PositionSearchProblem')

        self.heuristicName = testDict.get('heuristic', None)
    def getSolInfo(self, search, searchAgents):

        alg = getattr(search, self.alg)

        lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')])

        start_state = pacman.GameState()

        start_state.initialize(lay, 0)

        problemClass = getattr(searchAgents, self.searchProblemClassName)

        problemOptions = {}

        if self.costFn != None:

            problemOptions['costFn'] = self.costFn

        problem = problemClass(start_state, **problemOptions)

        heuristic = getattr(searchAgents, self.heuristicName) if self.heuristicName != None else None

        if heuristic != None:

            solution = alg(problem, heuristic)

        else:

            solution = alg(problem)

        if type(solution) != type([]):

            return None, None, 'The result of %s must be a list. (Instead, it is %s)' % (self.alg, type(solution))

        from game import Directions

        dirs = Directions.LEFT.keys()

        if [el in dirs for el in solution].count(False) != 0:

            return None, None, 'Output of %s must be a list of actions from game.Directions' % self.alg

        expanded = problem._expanded

        return solution, expanded, None

    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        gold_solution = [str.split(solutionDict['solution']), str.split(solutionDict['rev_solution'])]

        gold_expanded = max(int(solutionDict['expanded_nodes']), int(solutionDict['rev_expanded_nodes']))

        solution, expanded, error = self.getSolInfo(search, searchAgents)

        if error != None:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('%s' % error)

            return False

        # FIXME: do we want to standardize test output format?

        if solution not in gold_solution:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('Solution not correct.')

            grades.addMessage('\tstudent solution length: %s' % len(solution))

            grades.addMessage('\tstudent solution:\n%s' % wrap_solution(solution))

            grades.addMessage('')

            grades.addMessage('\tcorrect solution length: %s' % len(gold_solution[0]))

            grades.addMessage('\tcorrect (reversed) solution length: %s' % len(gold_solution[1]))

            grades.addMessage('\tcorrect solution:\n%s' % wrap_solution(gold_solution[0]))

            grades.addMessage('\tcorrect (reversed) solution:\n%s' % wrap_solution(gold_solution[1]))

            return False

        if expanded > self.leewayFactor * gold_expanded and expanded > gold_expanded + 1:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('Too many node expanded; are you expanding nodes twice?')

            grades.addMessage('\tstudent nodes expanded: %s' % expanded)

            grades.addMessage('')

            grades.addMessage('\tcorrect nodes expanded: %s (leewayFactor %s)' % (gold_expanded, self.leewayFactor))

            return False

        grades.addMessage('PASS: %s' % self.path)

        grades.addMessage('\tpacman layout:\t\t%s' % self.layoutName)

        grades.addMessage('\tsolution length: %s' % len(solution))

        grades.addMessage('\tnodes expanded:\t\t%s' % expanded)

        return True
    def writeSolution(self, moduleDict, filePath):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        # open file and write comments

        handle = open(filePath, 'w')

        handle.write('# This is the solution file for %s.\n' % self.path)

        handle.write('# This solution is designed to support both right-to-left\n')

        handle.write('# and left-to-right implementations.\n')

        handle.write('# Number of nodes expanded must be with a factor of %s of the numbers below.\n' % self.leewayFactor)

        # write forward solution

        solution, expanded, error = self.getSolInfo(search, searchAgents)

        if error != None: raise Exception("Error in solution code: %s" % error)

        handle.write('solution: """\n%s\n"""\n' % wrap_solution(solution))

        handle.write('expanded_nodes: "%s"\n' % expanded)

        # write backward solution

        search.REVERSE_PUSH = not search.REVERSE_PUSH

        solution, expanded, error = self.getSolInfo(search, searchAgents)

        if error != None: raise Exception("Error in solution code: %s" % error)

        handle.write('rev_solution: """\n%s\n"""\n' % wrap_solution(solution))

        handle.write('rev_expanded_nodes: "%s"\n' % expanded)

        # clean up

        search.REVERSE_PUSH = not search.REVERSE_PUSH

        handle.close()

        return True
from game import Actions

def getStatesFromPath(start, path):

    "Returns the list of states visited along the path"

    vis = [start]

    curr = start

    for a in path:

        x,y = curr

        dx, dy = Actions.directionToVector(a)

        curr = (int(x + dx), int(y + dy))

        vis.append(curr)

    return vis

class CornerProblemTest(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(CornerProblemTest, self).__init__(question, testDict)

        self.layoutText = testDict['layout']

        self.layoutName = testDict['layoutName']

    def solution(self, search, searchAgents):

        lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')])

        gameState = pacman.GameState()

        gameState.initialize(lay, 0)

        problem = searchAgents.CornersProblem(gameState)

        path = search.bfs(problem)

        gameState = pacman.GameState()

        gameState.initialize(lay, 0)

        visited = getStatesFromPath(gameState.getPacmanPosition(), path)

        top, right = gameState.getWalls().height-2, gameState.getWalls().width-2

        missedCorners = [p for p in ((1,1), (1,top), (right, 1), (right, top)) if p not in visited]

        return path, missedCorners

    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        gold_length = int(solutionDict['solution_length'])

        solution, missedCorners = self.solution(search, searchAgents)

        if type(solution) != type([]):

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('The result must be a list. (Instead, it is %s)' % type(solution))

            return False

        if len(missedCorners) != 0:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('Corners missed: %s' % missedCorners)

            return False

        if len(solution) != gold_length:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('Optimal solution not found.')

            grades.addMessage('\tstudent solution length:\n%s' % len(solution))

            grades.addMessage('')

            grades.addMessage('\tcorrect solution length:\n%s' % gold_length)

            return False

        grades.addMessage('PASS: %s' % self.path)

        grades.addMessage('\tpacman layout:\t\t%s' % self.layoutName)

        grades.addMessage('\tsolution length:\t\t%s' % len(solution))

        return True

    def writeSolution(self, moduleDict, filePath):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        # open file and write comments

        handle = open(filePath, 'w')

        handle.write('# This is the solution file for %s.\n' % self.path)

        print("Solving problem", self.layoutName)

        print(self.layoutText)

        path, _ = self.solution(search, searchAgents)

        length = len(path)

        print("Problem solved")

        handle.write('solution_length: "%s"\n' % length)

        handle.close()
# template = """class: "HeuristicTest"

#

# heuristic: "foodHeuristic"

# searchProblemClass: "FoodSearchProblem"

# layoutName: "Test %s"

# layout: \"\"\"

# %s

# \"\"\"

# """

#

# for i, (_, _, l) in enumerate(doneTests + foodTests):

#     f = open("food_heuristic_%s.test" % (i+1), "w")

#     f.write(template % (i+1, "\n".join(l)))

#     f.close()

class HeuristicTest(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(HeuristicTest, self).__init__(question, testDict)

        self.layoutText = testDict['layout']

        self.layoutName = testDict['layoutName']

        self.searchProblemClassName = testDict['searchProblemClass']

        self.heuristicName = testDict['heuristic']

    def setupProblem(self, searchAgents):

        lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')])

        gameState = pacman.GameState()

        gameState.initialize(lay, 0)

        problemClass = getattr(searchAgents, self.searchProblemClassName)

        problem = problemClass(gameState)

        state = problem.getStartState()

        heuristic = getattr(searchAgents, self.heuristicName)

        return problem, state, heuristic

    def checkHeuristic(self, heuristic, problem, state, solutionCost):

        h0 = heuristic(state, problem)

        if solutionCost == 0:

            if h0 == 0:

                return True, ''

            else:

                return False, 'Heuristic failed H(goal) == 0 test'

        if h0 < 0:
            return False, 'Heuristic failed H >= 0 test'

        if not h0 > 0:

            return False, 'Heuristic failed non-triviality test'

        if not h0 <= solutionCost:
            return False, 'Heuristic failed admissibility test'
        for succ, action, stepCost in problem.getSuccessors(state):
            h1 = heuristic(succ, problem)
            if h1 < 0: return False, 'Heuristic failed H >= 0 test'

            if h0 - h1 > stepCost: return False, 'Heuristic failed consistency test'

        return True, ''

    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        solutionCost = int(solutionDict['solution_cost'])

        problem, state, heuristic = self.setupProblem(searchAgents)

        passed, message = self.checkHeuristic(heuristic, problem, state, solutionCost)

        if not passed:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('%s' % message)

            return False

        else:

            grades.addMessage('PASS: %s' % self.path)

            return True

    def writeSolution(self, moduleDict, filePath):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        # open file and write comments

        handle = open(filePath, 'w')

        handle.write('# This is the solution file for %s.\n' % self.path)

        print("Solving problem", self.layoutName, self.heuristicName)

        print(self.layoutText)

        problem, _, heuristic = self.setupProblem(searchAgents)

        path = search.astar(problem, heuristic)

        cost = problem.getCostOfActions(path)

        print("Problem solved")

        handle.write('solution_cost: "%s"\n' % cost)

        handle.close()

        return True
class HeuristicGrade(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(HeuristicGrade, self).__init__(question, testDict)

        self.layoutText = testDict['layout']

        self.layoutName = testDict['layoutName']

        self.searchProblemClassName = testDict['searchProblemClass']

        self.heuristicName = testDict['heuristic']

        self.basePoints = int(testDict['basePoints'])

        self.thresholds = [int(t) for t in testDict['gradingThresholds'].split()]

    def setupProblem(self, searchAgents):

        lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')])

        gameState = pacman.GameState()

        gameState.initialize(lay, 0)

        problemClass = getattr(searchAgents, self.searchProblemClassName)

        problem = problemClass(gameState)

        state = problem.getStartState()

        heuristic = getattr(searchAgents, self.heuristicName)

        return problem, state, heuristic
    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        problem, _, heuristic = self.setupProblem(searchAgents)

        path = search.astar(problem, heuristic)

        expanded = problem._expanded

        if not checkSolution(problem, path):

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('\tReturned path is not a solution.')

            grades.addMessage('\tpath returned by astar: %s' % expanded)

            return False

        grades.addPoints(self.basePoints)

        points = 0

        for threshold in self.thresholds:

            if expanded <= threshold:
                points += 1
        grades.addPoints(points)
        if points >= len(self.thresholds):

            grades.addMessage('PASS: %s' % self.path)

        else:

            grades.addMessage('FAIL: %s' % self.path)

        grades.addMessage('\texpanded nodes: %s' % expanded)

        grades.addMessage('\tthresholds: %s' % self.thresholds)

        return True
    def writeSolution(self, moduleDict, filePath):

        handle = open(filePath, 'w')

        handle.write('# This is the solution file for %s.\n' % self.path)

        handle.write('# File intentionally blank.\n')

        handle.close()

        return True
# template = """class: "ClosestDotTest"

#

# layoutName: "Test %s"

# layout: \"\"\"

# %s

# \"\"\"

# """

#

# for i, (_, _, l) in enumerate(foodTests):

#     f = open("closest_dot_%s.test" % (i+1), "w")

#     f.write(template % (i+1, "\n".join(l)))

#     f.close()

class ClosestDotTest(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(ClosestDotTest, self).__init__(question, testDict)

        self.layoutText = testDict['layout']

        self.layoutName = testDict['layoutName']

    def solution(self, searchAgents):

        lay = layout.Layout([l.strip() for l in self.layoutText.split('\n')])

        gameState = pacman.GameState()

        gameState.initialize(lay, 0)

        path = searchAgents.ClosestDotSearchAgent().findPathToClosestDot(gameState)

        return path

    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        gold_length = int(solutionDict['solution_length'])

        solution = self.solution(searchAgents)

        if type(solution) != type([]):

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('\tThe result must be a list. (Instead, it is %s)' % type(solution))

            return False

        if len(solution) != gold_length:

            grades.addMessage('FAIL: %s' % self.path)

            grades.addMessage('Closest dot not found.')

            grades.addMessage('\tstudent solution length:\n%s' % len(solution))

            grades.addMessage('')

            grades.addMessage('\tcorrect solution length:\n%s' % gold_length)

            return False

        grades.addMessage('PASS: %s' % self.path)

        grades.addMessage('\tpacman layout:\t\t%s' % self.layoutName)

        grades.addMessage('\tsolution length:\t\t%s' % len(solution))

        return True

    def writeSolution(self, moduleDict, filePath):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        # open file and write comments

        handle = open(filePath, 'w')

        handle.write('# This is the solution file for %s.\n' % self.path)

        print("Solving problem", self.layoutName)

        print(self.layoutText)

        length = len(self.solution(searchAgents))

        print("Problem solved")

        handle.write('solution_length: "%s"\n' % length)

        handle.close()

        return True
class CornerHeuristicSanity(testClasses.TestCase):

    def __init__(self, question, testDict):

        super(CornerHeuristicSanity, self).__init__(question, testDict)

        self.layout_text = testDict['layout']

    def execute(self, grades, moduleDict, solutionDict):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        game_state = pacman.GameState()

        lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')])

        game_state.initialize(lay, 0)

        problem = searchAgents.CornersProblem(game_state)

        start_state = problem.getStartState()

        h0 = searchAgents.cornersHeuristic(start_state, problem)

        succs = problem.getSuccessors(start_state)

        # cornerConsistencyA

        for succ in succs:

            h1 = searchAgents.cornersHeuristic(succ[0], problem)

            if h0 - h1 > 1:

                grades.addMessage('FAIL: inconsistent heuristic')

                return False

        heuristic_cost = searchAgents.cornersHeuristic(start_state, problem)

        true_cost = float(solutionDict['cost'])

        # cornerNontrivial

        if heuristic_cost == 0:

            grades.addMessage('FAIL: must use non-trivial heuristic')

            return False

        # cornerAdmissible

        if heuristic_cost > true_cost:

            grades.addMessage('FAIL: Inadmissible heuristic')

            return False

        path = solutionDict['path'].split()

        states = followPath(path, problem)

        heuristics = []

        for state in states:

            heuristics.append(searchAgents.cornersHeuristic(state, problem))

        for i in range(0, len(heuristics) - 1):

            h0 = heuristics[i]

            h1 = heuristics[i+1]

            # cornerConsistencyB

            if h0 - h1 > 1:

                grades.addMessage('FAIL: inconsistent heuristic')

                return False

            # cornerPosH

            if h0 < 0 or h1 <0:
                grades.addMessage('FAIL: non-positive heuristic')
                return False
        # cornerGoalH
        if heuristics[len(heuristics) - 1] != 0:
            grades.addMessage('FAIL: heuristic non-zero at goal')
            return False
        grades.addMessage('PASS: heuristic value less than true cost at start state')
        return True
    def writeSolution(self, moduleDict, filePath):
        search = moduleDict['search']
        searchAgents = moduleDict['searchAgents']
        # write comment
        handle = open(filePath, 'w')
        handle.write('# In order for a heuristic to be admissible, the value\n')
        handle.write('# of the heuristic must be less at each state than the\n')
        handle.write('# true cost of the optimal path from that state to a goal.\n')
        # solve problem and write solution
        lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')])
        start_state = pacman.GameState()
        start_state.initialize(lay, 0)
        problem = searchAgents.CornersProblem(start_state)
        solution = search.astar(problem, searchAgents.cornersHeuristic)
        handle.write('cost: "%d"\n' % len(solution))
        handle.write('path: """\n%s\n"""\n' % wrap_solution(solution))
        handle.close()
        return True

class CornerHeuristicPacman(testClasses.TestCase):
    def __init__(self, question, testDict):
        super(CornerHeuristicPacman, self).__init__(question, testDict)
        self.layout_text = testDict['layout']
    def execute(self, grades, moduleDict, solutionDict):
        search = moduleDict['search']
        searchAgents = moduleDict['searchAgents']
        total = 0
        true_cost = float(solutionDict['cost'])
        thresholds = [int(x) for x in solutionDict['thresholds'].split()]
        game_state = pacman.GameState()
        lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')])
        game_state.initialize(lay, 0)
        problem = searchAgents.CornersProblem(game_state)
        start_state = problem.getStartState()
        if searchAgents.cornersHeuristic(start_state, problem) > true_cost:

            grades.addMessage('FAIL: Inadmissible heuristic')

            return False

        path = search.astar(problem, searchAgents.cornersHeuristic)

        print("path:", path)

        print("path length:", len(path))

        cost = problem.getCostOfActions(path)

        if cost > true_cost:

            grades.addMessage('FAIL: Inconsistent heuristic')

            return False

        expanded = problem._expanded

        points = 0

        for threshold in thresholds:

            if expanded <= threshold:
                points += 1
        grades.addPoints(points)
        if points >= len(thresholds):

            grades.addMessage('PASS: Heuristic resulted in expansion of %d nodes' % expanded)

        else:

            grades.addMessage('FAIL: Heuristic resulted in expansion of %d nodes' % expanded)

        return True

    def writeSolution(self, moduleDict, filePath):

        search = moduleDict['search']

        searchAgents = moduleDict['searchAgents']

        # write comment

        handle = open(filePath, 'w')

        handle.write('# This solution file specifies the length of the optimal path\n')

        handle.write('# as well as the thresholds on number of nodes expanded to be\n')

        handle.write('# used in scoring.\n')

        # solve problem and write solution

        lay = layout.Layout([l.strip() for l in self.layout_text.split('\n')])

        start_state = pacman.GameState()

        start_state.initialize(lay, 0)

        problem = searchAgents.CornersProblem(start_state)

        solution = search.astar(problem, searchAgents.cornersHeuristic)

        handle.write('cost: "%d"\n' % len(solution))

        handle.write('path: """\n%s\n"""\n' % wrap_solution(solution))

        handle.write('thresholds: "2000 1600 1200"\n')

        handle.close()

        return True
homework_1_search/testClasses.py

# testClasses.py

# --------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
# import modules from python standard library

import inspect

import re

import sys
# Class which models a question in a project.  Note that questions have a

# maximum number of points they are worth, and are composed of a series of

# test cases

class Question(object):

    def raiseNotDefined(self):

        print('Method not implemented: %s' % inspect.stack()[1][3])

        sys.exit(1)

    def __init__(self, questionDict, display):

        self.maxPoints = int(questionDict['max_points'])

        self.testCases = []

        self.display = display

    def getDisplay(self):

        return self.display

    def getMaxPoints(self):

        return self.maxPoints

    # Note that 'thunk' must be a function which accepts a single argument,

    # namely a 'grading' object

    def addTestCase(self, testCase, thunk):

        self.testCases.append((testCase, thunk))

    def execute(self, grades):

        self.raiseNotDefined()

# Question in which all test cases must be passed in order to receive credit

class PassAllTestsQuestion(Question):

    def execute(self, grades):

        # TODO: is this the right way to use grades?  The autograder doesn't seem to use it.

        testsFailed = False

        grades.assignZeroCredit()

        for _, f in self.testCases:

            if not f(grades):

                testsFailed = True

        if testsFailed:

            grades.fail("Tests failed.")

        else:

            grades.assignFullCredit()

class ExtraCreditPassAllTestsQuestion(Question):

    def __init__(self, questionDict, display):

        Question.__init__(self, questionDict, display)

        self.extraPoints = int(questionDict['extra_points'])

    def execute(self, grades):

        # TODO: is this the right way to use grades?  The autograder doesn't seem to use it.

        testsFailed = False

        grades.assignZeroCredit()

        for _, f in self.testCases:

            if not f(grades):

                testsFailed = True

        if testsFailed:

            grades.fail("Tests failed.")

        else:

            grades.assignFullCredit()

            grades.addPoints(self.extraPoints)

# Question in which predict credit is given for test cases with a ``points'' property.

# All other tests are mandatory and must be passed.

class HackedPartialCreditQuestion(Question):

    def execute(self, grades):

        # TODO: is this the right way to use grades?  The autograder doesn't seem to use it.

        grades.assignZeroCredit()

        points = 0

        passed = True

        for testCase, f in self.testCases:

            testResult = f(grades)

            if "points" in testCase.testDict:

                if testResult: points += float(testCase.testDict["points"])

            else:

                passed = passed and testResult

        ## FIXME: Below terrible hack to match q3's logic

        if int(points) == self.maxPoints and not passed:

            grades.assignZeroCredit()

        else:

            grades.addPoints(int(points))
class Q6PartialCreditQuestion(Question):

    """Fails any test which returns False, otherwise doesn't effect the grades object.

    Partial credit tests will add the required points."""

    def execute(self, grades):

        grades.assignZeroCredit()

        results = []

        for _, f in self.testCases:

            results.append(f(grades))

        if False in results:

            grades.assignZeroCredit()

class PartialCreditQuestion(Question):

    """Fails any test which returns False, otherwise doesn't effect the grades object.

    Partial credit tests will add the required points."""

    def execute(self, grades):

        grades.assignZeroCredit()

        for _, f in self.testCases:

            if not f(grades):

                grades.assignZeroCredit()

                grades.fail("Tests failed.")

                return False
class NumberPassedQuestion(Question):

    """Grade is the number of test cases passed."""

    def execute(self, grades):

        grades.addPoints([f(grades) for _, f in self.testCases].count(True))
# Template modeling a generic test case

class TestCase(object):

    def raiseNotDefined(self):

        print('Method not implemented: %s' % inspect.stack()[1][3])

        sys.exit(1)

    def getPath(self):

        return self.path

    def __init__(self, question, testDict):

        self.question = question

        self.testDict = testDict

        self.path = testDict['path']

        self.messages = []

    def __str__(self):

        self.raiseNotDefined()

    def execute(self, grades, moduleDict, solutionDict):

        self.raiseNotDefined()

    def writeSolution(self, moduleDict, filePath):

        self.raiseNotDefined()

        return True

    # Tests should call the following messages for grading

    # to ensure a uniform format for test output.

    #

    # TODO: this is hairy, but we need to fix grading.py's interface

    # to get a nice hierarchical project - question - test structure,

    # then these should be moved into Question proper.

    def testPass(self, grades):

        grades.addMessage('PASS: %s' % (self.path,))

        for line in self.messages:

            grades.addMessage('    %s' % (line,))

        return True

    def testFail(self, grades):

        grades.addMessage('FAIL: %s' % (self.path,))

        for line in self.messages:

            grades.addMessage('    %s' % (line,))

        return False

    # This should really be question level?

    #

    def testPartial(self, grades, points, maxPoints):

        grades.addPoints(points)

        extraCredit = max(0, points - maxPoints)

        regularCredit = points - extraCredit

        grades.addMessage('%s: %s (%s of %s points)' % ("PASS" if points >= maxPoints else "FAIL", self.path, regularCredit, maxPoints))

        if extraCredit > 0:

            grades.addMessage('EXTRA CREDIT: %s points' % (extraCredit,))

        for line in self.messages:

            grades.addMessage('    %s' % (line,))

        return True

    def addMessage(self, message):

        self.messages.extend(message.split('\n'))
homework_1_search/testParser.py

# testParser.py

# -------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
import re

import sys

class TestParser(object):

    def __init__(self, path):

        # save the path to the test file

        self.path = path

    def removeComments(self, rawlines):

        # remove any portion of a line following a '#' symbol

        fixed_lines = []

        for l in rawlines:

            idx = l.find('#')

            if idx == -1:

                fixed_lines.append(l)

            else:

                fixed_lines.append(l[0:idx])

        return '\n'.join(fixed_lines)

    def parse(self):

        # read in the test case and remove comments

        test = {}

        with open(self.path) as handle:

            raw_lines = handle.read().split('\n')

        test_text = self.removeComments(raw_lines)

        test['__raw_lines__'] = raw_lines

        test['path'] = self.path

        test['__emit__'] = []

        lines = test_text.split('\n')

        i = 0

        # read a property in each loop cycle

        while(i < len(lines)):
            # skip blank lines
            if re.match('\A\s*\Z', lines[i]):
                test['__emit__'].append(("raw", raw_lines[i]))
                i += 1
                continue
            m = re.match('\A([^"]*?):\s*"([^"]*)"\s*\Z', lines[i])
            if m:
                test[m.group(1)] = m.group(2)
                test['__emit__'].append(("oneline", m.group(1)))
                i += 1
                continue
            m = re.match('\A([^"]*?):\s*"""\s*\Z', lines[i])
            if m:
                msg = []
                i += 1
                while(not re.match('\A\s*"""\s*\Z', lines[i])):
                    msg.append(raw_lines[i])
                    i += 1
                test[m.group(1)] = '\n'.join(msg)
                test['__emit__'].append(("multiline", m.group(1)))
                i += 1
                continue
            print('error parsing test file: %s' % self.path)
            sys.exit(1)
        return test

def emitTestDict(testDict, handle):
    for kind, data in testDict['__emit__']:
        if kind == "raw":
            handle.write(data + "\n")
        elif kind == "oneline":
            handle.write('%s: "%s"\n' % (data, testDict[data]))
        elif kind == "multiline":
            handle.write('%s: """\n%s\n"""\n' % (data, testDict[data]))
        else:
            raise Exception("Bad __emit__")


homework_1_search/test_cases/CONFIG
order: "q1 q2 q3 q4 q5 q6 q7 q8"


homework_1_search/test_cases/q1/CONFIG
max_points: "3"
class: "PassAllTestsQuestion"


homework_1_search/test_cases/q1/graph_backtrack.solution
# This is the solution file for test_cases/q1/graph_backtrack.test.
# This solution is designed to support both right-to-left
# and left-to-right implementations.
solution: "1:A->C 0:C->G"

expanded_states: "A D C"

rev_solution: "1:A->C 0:C->G"

rev_expanded_states: "A B C"
homework_1_search/test_cases/q1/graph_backtrack.test

class: "GraphSearchTest"

algorithm: "depthFirstSearch"

diagram: """

 B

 ^

 |

*A --> C --> G

 |

 V

 D

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This tests whether

you extract the sequence of actions correctly even

if your search backtracks.  If you fail this, your

nodes are not correctly tracking the sequences of

actions required to reach them.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->C C 2.0

A 2:A->D D 4.0

C 0:C->G G 8.0

"""
homework_1_search/test_cases/q1/graph_bfs_vs_dfs.solution

# This is the solution file for test_cases/q1/graph_bfs_vs_dfs.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "2:A->D 0:D->G"

expanded_states: "A D"

rev_solution: "0:A->B 0:B->D 0:D->G"

rev_expanded_states: "A B D"
homework_1_search/test_cases/q1/graph_bfs_vs_dfs.test

# Graph where BFS finds the optimal solution but DFS does not

class: "GraphSearchTest"

algorithm: "depthFirstSearch"

diagram: """

/-- B

|   ^

|   |

|  *A -->[G]

|   |     ^

|   V     |

\-->D ----/

A is the start state, G is the goal.  Arrows

mark possible transitions

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->G G 2.0

A 2:A->D D 4.0

B 0:B->D D 8.0

D 0:D->G G 16.0

"""
homework_1_search/test_cases/q1/graph_infinite.solution

# This is the solution file for test_cases/q1/graph_infinite.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "0:A->B 1:B->C 1:C->G"

expanded_states: "A B C"

rev_solution: "0:A->B 1:B->C 1:C->G"

rev_expanded_states: "A B C"
homework_1_search/test_cases/q1/graph_infinite.test

# Graph where natural action choice leads to an infinite loop

class: "GraphSearchTest"

algorithm: "depthFirstSearch"

diagram: """

 B <--> C

 ^     /|

 |    / |

 V   /  V

*A<-/  [G]
A is the start state, G is the goal.  Arrows mark 
possible state transitions.
"""
# The following section specifies the search problem and the solution.
# The graph is specified by first the set of start states, followed by
# the set of goal states, and lastly by the state transitions which are
# of the form: 
#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

B 0:B->A A 2.0

B 1:B->C C 4.0

C 0:C->A A 8.0

C 1:C->G G 16.0

C 2:C->B B 32.0

"""
homework_1_search/test_cases/q1/graph_manypaths.solution

# This is the solution file for test_cases/q1/graph_manypaths.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "2:A->B2 0:B2->C 0:C->D 2:D->E2 0:E2->F 0:F->G"

expanded_states: "A B2 C D E2 F"

rev_solution: "0:A->B1 0:B1->C 0:C->D 0:D->E1 0:E1->F 0:F->G"

rev_expanded_states: "A B1 C D E1 F"
homework_1_search/test_cases/q1/graph_manypaths.test

class: "GraphSearchTest"

algorithm: "depthFirstSearch"

diagram: """

    B1          E1

   ^  \        ^  \

  /    V      /    V

*A --> C --> D --> F --> [G]

  \    ^      \    ^

   V  /        V  /

    B2          E2

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This graph has multiple

paths to the goal, where nodes with the same state

are added to the fringe multiple times before they

are expanded.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B1 B1 1.0

A 1:A->C C 2.0

A 2:A->B2 B2 4.0

B1 0:B1->C C 8.0

B2 0:B2->C C 16.0

C 0:C->D D 32.0

D 0:D->E1 E1 64.0

D 1:D->F F 128.0

D 2:D->E2 E2 256.0

E1 0:E1->F F 512.0

E2 0:E2->F F 1024.0

F 0:F->G G 2048.0

"""
homework_1_search/test_cases/q1/pacman_1.solution

# This is the solution file for test_cases/q1/pacman_1.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 1.0 of the numbers below.

solution: """

West West West West West West West West West West West West West West

West West West West West West West West West West West West West West

West West West West West South South South South South South South

South South East East East North North North North North North North

East East South South South South South South East East North North

North North North North East East South South South South East East

North North East East East East East East East East South South South

East East East East East East East South South South South South South

South West West West West West West West West West West West West West

West West West West South West West West West West West West West West

"""

expanded_nodes: "146"

rev_solution: """

South South West West West West South South East East East East South

South West West West West South South East East East East South South

West West West West South South South East North East East East South

South South West West West West West West West North North North North

North North North North West West West West West West West North North

North East East East East South East East East North North North West

West North North West West West West West West West West West West

West West West West West West West West West West West West West West

South South South South South South South South South East East East

North North North North North North North East East South South South

South South South East East North North North North North North East

East South South South South East East North North North North East

East East East East South South West West West South South East East

East South South West West West West West West South South West West

West West West South West West West West West South South East East

East East East East East North East East East East East North North

East East East East East East North East East East East East South

South West West West South West West West West West West South South

West West West West West South West West West West West West West West

West

"""

rev_expanded_nodes: "269"
homework_1_search/test_cases/q1/pacman_1.test

# This is a basic depth first search test

class: "PacmanSearchTest"

algorithm: "depthFirstSearch"

# The following specifies the layout to be used

layoutName: "mediumMaze"

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""
homework_1_search/test_cases/q2/CONFIG

max_points: "3"

class: "PassAllTestsQuestion"
homework_1_search/test_cases/q2/graph_backtrack.solution

# This is the solution file for test_cases/q2/graph_backtrack.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->C 0:C->G"

expanded_states: "A B C D"

rev_solution: "1:A->C 0:C->G"

rev_expanded_states: "A D C B"
homework_1_search/test_cases/q2/graph_backtrack.test

class: "GraphSearchTest"

algorithm: "breadthFirstSearch"

diagram: """

 B

 ^

 |

*A --> C --> G

 |

 V

 D

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This tests whether

you extract the sequence of actions correctly even

if your search backtracks.  If you fail this, your

nodes are not correctly tracking the sequences of

actions required to reach them.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->C C 2.0

A 2:A->D D 4.0

C 0:C->G G 8.0

"""
homework_1_search/test_cases/q2/graph_bfs_vs_dfs.solution

# This is the solution file for test_cases/q2/graph_bfs_vs_dfs.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->G"

expanded_states: "A B"

rev_solution: "1:A->G"

rev_expanded_states: "A D"
homework_1_search/test_cases/q2/graph_bfs_vs_dfs.test

# Graph where BFS finds the optimal solution but DFS does not

class: "GraphSearchTest"

algorithm: "breadthFirstSearch"

diagram: """

/-- B

|   ^

|   |

|  *A -->[G]

|   |     ^

|   V     |

\-->D ----/

A is the start state, G is the goal.  Arrows

mark possible transitions

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->G G 2.0

A 2:A->D D 4.0

B 0:B->D D 8.0

D 0:D->G G 16.0

"""
homework_1_search/test_cases/q2/graph_infinite.solution

# This is the solution file for test_cases/q2/graph_infinite.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "0:A->B 1:B->C 1:C->G"

expanded_states: "A B C"

rev_solution: "0:A->B 1:B->C 1:C->G"

rev_expanded_states: "A B C"
homework_1_search/test_cases/q2/graph_infinite.test

# Graph where natural action choice leads to an infinite loop

class: "GraphSearchTest"

algorithm: "breadthFirstSearch"

diagram: """

 B <--> C

 ^     /|

 |    / |

 V   /  V

*A<-/  [G]
A is the start state, G is the goal.  Arrows mark 
possible state transitions.
"""
# The following section specifies the search problem and the solution.
# The graph is specified by first the set of start states, followed by
# the set of goal states, and lastly by the state transitions which are
# of the form: 
#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

B 0:B->A A 2.0

B 1:B->C C 4.0

C 0:C->A A 8.0

C 1:C->G G 16.0

C 2:C->B B 32.0

"""
homework_1_search/test_cases/q2/graph_manypaths.solution

# This is the solution file for test_cases/q2/graph_manypaths.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->C 0:C->D 1:D->F 0:F->G"

expanded_states: "A B1 C B2 D E1 F E2"

rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G"

rev_expanded_states: "A B2 C B1 D E2 F E1"
homework_1_search/test_cases/q2/graph_manypaths.test

class: "GraphSearchTest"

algorithm: "breadthFirstSearch"

diagram: """

    B1          E1

   ^  \        ^  \

  /    V      /    V

*A --> C --> D --> F --> [G]

  \    ^      \    ^

   V  /        V  /

    B2          E2

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This graph has multiple

paths to the goal, where nodes with the same state

are added to the fringe multiple times before they

are expanded.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B1 B1 1.0

A 1:A->C C 2.0

A 2:A->B2 B2 4.0

B1 0:B1->C C 8.0

B2 0:B2->C C 16.0

C 0:C->D D 32.0

D 0:D->E1 E1 64.0

D 1:D->F F 128.0

D 2:D->E2 E2 256.0

E1 0:E1->F F 512.0

E2 0:E2->F F 1024.0

F 0:F->G G 2048.0

"""
homework_1_search/test_cases/q2/pacman_1.solution

# This is the solution file for test_cases/q2/pacman_1.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 1.0 of the numbers below.

solution: """

West West West West West West West West West South South East East

South South South West West West North West West West West South South

South East East East East East East East South South South South South

South South West West West West West West West West West West West

West West West West West West South West West West West West West West

West West

"""

expanded_nodes: "269"

rev_solution: """

West West West West West West West West West South South East East

South South South West West West North West West West West South South

South East East East East East East East South South South South South

South South West West West West West West West West West West West

West West West West West West South West West West West West West West

West West

"""

rev_expanded_nodes: "269"
homework_1_search/test_cases/q2/pacman_1.test

# This is a basic breadth first search test

class: "PacmanSearchTest"

algorithm: "breadthFirstSearch"

# The following specifies the layout to be used

layoutName: "mediumMaze"

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""
homework_1_search/test_cases/q3/CONFIG

class: "PassAllTestsQuestion"

max_points: "3"
homework_1_search/test_cases/q3/graph_backtrack.solution

# This is the solution file for test_cases/q3/graph_backtrack.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->C 0:C->G"

expanded_states: "A B C D"

rev_solution: "1:A->C 0:C->G"

rev_expanded_states: "A B C D"
homework_1_search/test_cases/q3/graph_backtrack.test

class: "GraphSearchTest"

algorithm: "uniformCostSearch"

diagram: """

 B

 ^

 |

*A --> C --> G

 |

 V

 D

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This tests whether

you extract the sequence of actions correctly even

if your search backtracks.  If you fail this, your

nodes are not correctly tracking the sequences of

actions required to reach them.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->C C 2.0

A 2:A->D D 4.0

C 0:C->G G 8.0

"""
homework_1_search/test_cases/q3/graph_bfs_vs_dfs.solution

# This is the solution file for test_cases/q3/graph_bfs_vs_dfs.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->G"

expanded_states: "A B"

rev_solution: "1:A->G"

rev_expanded_states: "A B"
homework_1_search/test_cases/q3/graph_bfs_vs_dfs.test

# Graph where BFS finds the optimal solution but DFS does not

class: "GraphSearchTest"

algorithm: "uniformCostSearch"

diagram: """

/-- B

|   ^

|   |

|  *A -->[G]

|   |     ^

|   V     |

\-->D ----/

A is the start state, G is the goal.  Arrows

mark possible transitions

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->G G 2.0

A 2:A->D D 4.0

B 0:B->D D 8.0

D 0:D->G G 16.0

"""
homework_1_search/test_cases/q3/graph_infinite.solution

# This is the solution file for test_cases/q3/graph_infinite.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "0:A->B 1:B->C 1:C->G"

expanded_states: "A B C"

rev_solution: "0:A->B 1:B->C 1:C->G"

rev_expanded_states: "A B C"
homework_1_search/test_cases/q3/graph_infinite.test

# Graph where natural action choice leads to an infinite loop

class: "GraphSearchTest"

algorithm: "uniformCostSearch"

diagram: """

 B <--> C

 ^     /|

 |    / |

 V   /  V

*A<-/  [G]
A is the start state, G is the goal.  Arrows mark 
possible state transitions.
"""
# The following section specifies the search problem and the solution.
# The graph is specified by first the set of start states, followed by
# the set of goal states, and lastly by the state transitions which are
# of the form: 
#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

B 0:B->A A 2.0

B 1:B->C C 4.0

C 0:C->A A 8.0

C 1:C->G G 16.0

C 2:C->B B 32.0

"""
homework_1_search/test_cases/q3/graph_manypaths.solution

# This is the solution file for test_cases/q3/graph_manypaths.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->C 0:C->D 1:D->F 0:F->G"

expanded_states: "A B1 C B2 D E1 F E2"

rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G"

rev_expanded_states: "A B1 C B2 D E1 F E2"
homework_1_search/test_cases/q3/graph_manypaths.test

class: "GraphSearchTest"

algorithm: "uniformCostSearch"

diagram: """

    B1          E1

   ^  \        ^  \

  /    V      /    V

*A --> C --> D --> F --> [G]

  \    ^      \    ^

   V  /        V  /

    B2          E2

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This graph has multiple

paths to the goal, where nodes with the same state

are added to the fringe multiple times before they

are expanded.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B1 B1 1.0

A 1:A->C C 2.0

A 2:A->B2 B2 4.0

B1 0:B1->C C 8.0

B2 0:B2->C C 16.0

C 0:C->D D 32.0

D 0:D->E1 E1 64.0

D 1:D->F F 128.0

D 2:D->E2 E2 256.0

E1 0:E1->F F 512.0

E2 0:E2->F F 1024.0

F 0:F->G G 2048.0

"""
homework_1_search/test_cases/q3/ucs_0_graph.solution

# This is the solution file for test_cases/q3/ucs_0_graph.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "Right Down Down"

expanded_states: "A B D C G"

rev_solution: "Right Down Down"

rev_expanded_states: "A B D C G"
homework_1_search/test_cases/q3/ucs_0_graph.test

class: "GraphSearchTest"

algorithm: "uniformCostSearch"

diagram: """

          C

          ^

          | 2

     2    V   4

*A <----> B -----> [H]

          |1

     1.5  V  2.5

 G <----- D -----> E

          |

        2 |

          V

         [F]

A is the start state, F and H is the goal.  Arrows mark possible state

transitions.  The number next to the arrow is the cost of that transition.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: H F

A Right B 2.0

B Right H 4.0

B Down D 1.0

B Up C 2.0

B Left A 2.0

C Down B 2.0

D Right E 2.5

D Down F 2.0

D Left G 1.5

"""
homework_1_search/test_cases/q3/ucs_1_problemC.solution

# This is the solution file for test_cases/q3/ucs_1_problemC.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 1.1 of the numbers below.

solution: """

West West West West West West West West West South South East East

South South South West West West North West West West West South South

South East East East East East East East South South South South South

South South West West West West West West West West West West West

West West West West West West South West West West West West West West

West West

"""

expanded_nodes: "269"

rev_solution: """

West West West West West West West West West South South East East

South South South West West West North West West West West South South

South East East East East East East East South South South South South

South South West West West West West West West West West West West

West West West West West West South West West West West West West West

West West

"""

rev_expanded_nodes: "269"
homework_1_search/test_cases/q3/ucs_1_problemC.test

class: "PacmanSearchTest"

algorithm: "uniformCostSearch"

points: "0.5"

# The following specifies the layout to be used

layoutName: "mediumMaze"

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""

leewayFactor: "1.1"

#costFn: "lambda pos: 1"
homework_1_search/test_cases/q3/ucs_2_problemE.solution

# This is the solution file for test_cases/q3/ucs_2_problemE.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 1.1 of the numbers below.

solution: """

South South West West West West South South East East East East South

South West West West West South South East East East East South South

West West West West South South East East East East South South South

West West West West West West West North West West West West West West

West West West West West West West West West West West South West West

West West West West West West West

"""

expanded_nodes: "260"

rev_solution: """

South South West West West West South South East East East East South

South West West West West South South East East East East South South

West West West West South South East East East East South South South

West West West West West West West North West West West West West West

West West West West West West West West West West West South West West

West West West West West West West

"""

rev_expanded_nodes: "260"
homework_1_search/test_cases/q3/ucs_2_problemE.test

class: "PacmanSearchTest"

algorithm: "uniformCostSearch"

points: "0.5"

# The following specifies the layout to be used

layoutName: "mediumMaze"

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""

leewayFactor: "1.1"

costFn: "lambda pos: .5 ** pos[0]"
homework_1_search/test_cases/q3/ucs_3_problemW.solution

# This is the solution file for test_cases/q3/ucs_3_problemW.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 1.1 of the numbers below.

solution: """

West West West West West West West West West West West West West West

West West West West West West West West West West West West West West

West West West West West South South South South South South South

South South East East East North North North North North North North

East East South South South South South South East East North North

North North North North East East South South South South East East

North North East East South South East East East South South West West

West West West West South South West West West West West South West

West West West West South South East East East East East East East

North East East East East East North North East East East East East

East South South West West West West South South West West West West

West South West West West West West West West West West

"""

expanded_nodes: "173"

rev_solution: """

West West West West West West West West West West West West West West

West West West West West West West West West West West West West West

West West West West West South South South South South South South

South South East East East North North North North North North North

East East South South South South South South East East North North

North North North North East East South South South South East East

North North East East South South East East East South South West West

West West West West South South West West West West West South West

West West West West South South East East East East East East East

North East East East East East North North East East East East East

East South South West West West West South South West West West West

West South West West West West West West West West West

"""

rev_expanded_nodes: "173"
homework_1_search/test_cases/q3/ucs_3_problemW.test

class: "PacmanSearchTest"

algorithm: "uniformCostSearch"

points: "0.5"

# The following specifies the layout to be used

layoutName: "mediumMaze"

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""

leewayFactor: "1.1"

costFn: "lambda pos: 2 ** pos[0]"
homework_1_search/test_cases/q3/ucs_4_testSearch.solution

# This is the solution file for test_cases/q3/ucs_4_testSearch.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 2.0 of the numbers below.

solution: """

West East East South South West West

"""

expanded_nodes: "14"

rev_solution: """

West East East South South West West

"""

rev_expanded_nodes: "13"
homework_1_search/test_cases/q3/ucs_4_testSearch.test

class: "PacmanSearchTest"

algorithm: "uniformCostSearch"

points: "0.5"

# The following specifies the layout to be used

layoutName: "testSearch"

layout: """

%%%%%

%.P %

%%% %

%.  %

%%%%%

"""

searchProblemClass: "FoodSearchProblem"

leewayFactor: "2"
homework_1_search/test_cases/q3/ucs_5_goalAtDequeue.solution

# This is the solution file for test_cases/q3/ucs_5_goalAtDequeue.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->B 0:B->C 0:C->G"

expanded_states: "A B C"

rev_solution: "1:A->B 0:B->C 0:C->G"

rev_expanded_states: "A B C"
homework_1_search/test_cases/q3/ucs_5_goalAtDequeue.test

class: "GraphSearchTest"

algorithm: "uniformCostSearch"

diagram: """

    1      1      1

*A ---> B ---> C ---> [G]

 |                     ^

 |         10          |

 \---------------------/

A is the start state, G is the goal.  Arrows mark possible state

transitions.  The number next to the arrow is the cost of that transition.

If you fail this test case, you may be incorrectly testing if a node is a goal

before adding it into the queue, instead of testing when you remove the node

from the queue.  See the algorithm pseudocode in lecture.

"""

graph: """

start_state: A

goal_states: G

A 0:A->G G 10.0

A 1:A->B B 1.0

B 0:B->C C 1.0

C 0:C->G G 1.0

"""

# We only care about the solution, not the expansion order.

exactExpansionOrder: "False"
homework_1_search/test_cases/q4/astar_0.solution

# This is the solution file for test_cases/q4/astar_0.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "Right Down Down"

expanded_states: "A B D C G"

rev_solution: "Right Down Down"

rev_expanded_states: "A B D C G"
homework_1_search/test_cases/q4/astar_0.test

class: "GraphSearchTest"

algorithm: "aStarSearch"

diagram: """

          C

          ^

          | 2

     2    V   4

*A <----> B -----> [H]

          |

     1.5  V  2.5

 G <----- D -----> E

          |

        2 |

          V

         [F]

A is the start state, F and H is the goal.  Arrows mark possible state

transitions.  The number next to the arrow is the cost of that transition.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: H F

A Right B 2.0

B Right H 4.0

B Down D 1.0

B Up C 2.0

B Left A 2.0

C Down B 2.0

D Right E 2.5

D Down F 2.0

D Left G 1.5

"""
homework_1_search/test_cases/q4/astar_1_graph_heuristic.solution

# This is the solution file for test_cases/q4/astar_1_graph_heuristic.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "0 0 2"

expanded_states: "S A D C"

rev_solution: "0 0 2"

rev_expanded_states: "S A D C"
homework_1_search/test_cases/q4/astar_1_graph_heuristic.test

class: "GraphSearchTest"

algorithm: "aStarSearch"

diagram: """

     2     3     2

  S --- A --- C ---> G

  | \       /       ^

3 |  \ 5   / 1     /

  |   \   /       /

  B --- D -------/

     4         5

S is the start state, G is the goal.  Arrows mark possible state

transitions.  The number next to the arrow is the cost of that transition.

The heuristic value of each state is:

	S 6.0

	A 2.5

	B 5.25

	C 1.125

	D 1.0625

	G 0

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: S

goal_states: G

S 0 A 2.0

S 1 B 3.0

S 2 D 5.0

A 0 C 3.0

A 1 S 2.0

B 0 D 4.0

B 1 S 3.0

C 0 A 3.0

C 1 D 1.0

C 2 G 2.0

D 0 B 4.0

D 1 C 1.0

D 2 G 5.0

D 3 S 5.0

"""

heuristic: """

S 6.0

A 2.5

B 5.25

C 1.125

D 1.0625

G 0

"""
homework_1_search/test_cases/q4/astar_2_manhattan.solution

# This is the solution file for test_cases/q4/astar_2_manhattan.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

# Number of nodes expanded must be with a factor of 1.1 of the numbers below.

solution: """

West West West West West West West West West South South East East

South South South West West West North West West West West South South

South East East East East East East East South South South South South

South South West West West West West West West West West West West

West West West West West West South West West West West West West West

West West

"""

expanded_nodes: "221"

rev_solution: """

West West West West West West West West West South South East East

South South South West West West North West West West West South South

South East East East East East East East South South South South South

South South West West West West West West West West West West West

West West West West West West South West West West West West West West

West West

"""

rev_expanded_nodes: "221"
homework_1_search/test_cases/q4/astar_2_manhattan.test

class: "PacmanSearchTest"

algorithm: "aStarSearch"

# The following specifies the layout to be used

layoutName: "mediumMaze"

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%                                 P%

% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %

% %%   %   %      %%%%%%%   %%     %

% %% % % % % %%%% %%%%%%%%% %% %%%%%

% %% % % % %             %% %%     %

% %% % % % % % %%%%  %%%    %%%%%% %

% %  % % %   %    %% %%%%%%%%      %

% %% % % %%%%%%%% %%        %% %%%%%

% %% %   %%       %%%%%%%%% %%     %

%    %%%%%% %%%%%%%      %% %%%%%% %

%%%%%%      %       %%%% %% %      %

%      %%%%%% %%%%% %    %% %% %%%%%

% %%%%%%      %       %%%%% %%     %

%        %%%%%% %%%%%%%%%%% %%  %% %

%%%%%%%%%%                  %%%%%% %

%.         %%%%%%%%%%%%%%%%        %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""

leewayFactor: "1.1"

heuristic: "manhattanHeuristic"
homework_1_search/test_cases/q4/astar_3_goalAtDequeue.solution

# This is the solution file for test_cases/q4/astar_3_goalAtDequeue.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->B 0:B->C 0:C->G"

expanded_states: "A B C"

rev_solution: "1:A->B 0:B->C 0:C->G"

rev_expanded_states: "A B C"
homework_1_search/test_cases/q4/astar_3_goalAtDequeue.test

class: "GraphSearchTest"

algorithm: "aStarSearch"

diagram: """

    1      1      1

*A ---> B ---> C ---> [G]

 |                     ^

 |         10          |

 \---------------------/

A is the start state, G is the goal.  Arrows mark possible state

transitions.  The number next to the arrow is the cost of that transition.

If you fail this test case, you may be incorrectly testing if a node is a goal

before adding it into the queue, instead of testing when you remove the node

from the queue.  See the algorithm pseudocode in lecture.

"""

graph: """

start_state: A

goal_states: G

A 0:A->G G 10.0

A 1:A->B B 1.0

B 0:B->C C 1.0

C 0:C->G G 1.0

"""

# We only care about the solution, not the expansion order.

exactExpansionOrder: "False"
homework_1_search/test_cases/q4/CONFIG

class: "PassAllTestsQuestion"

max_points: "3"
homework_1_search/test_cases/q4/graph_backtrack.solution

# This is the solution file for test_cases/q4/graph_backtrack.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->C 0:C->G"

expanded_states: "A B C D"

rev_solution: "1:A->C 0:C->G"

rev_expanded_states: "A B C D"
homework_1_search/test_cases/q4/graph_backtrack.test

class: "GraphSearchTest"

algorithm: "aStarSearch"

diagram: """

 B

 ^

 |

*A --> C --> G

 |

 V

 D

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This tests whether

you extract the sequence of actions correctly even

if your search backtracks.  If you fail this, your

nodes are not correctly tracking the sequences of

actions required to reach them.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B B 1.0

A 1:A->C C 2.0

A 2:A->D D 4.0

C 0:C->G G 8.0

"""
homework_1_search/test_cases/q4/graph_manypaths.solution

# This is the solution file for test_cases/q4/graph_manypaths.test.

# This solution is designed to support both right-to-left

# and left-to-right implementations.

solution: "1:A->C 0:C->D 1:D->F 0:F->G"

expanded_states: "A B1 C B2 D E1 F E2"

rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G"

rev_expanded_states: "A B1 C B2 D E1 F E2"
homework_1_search/test_cases/q4/graph_manypaths.test

class: "GraphSearchTest"

algorithm: "aStarSearch"

diagram: """

    B1          E1

   ^  \        ^  \

  /    V      /    V

*A --> C --> D --> F --> [G]

  \    ^      \    ^

   V  /        V  /

    B2          E2

A is the start state, G is the goal.  Arrows mark

possible state transitions.  This graph has multiple

paths to the goal, where nodes with the same state

are added to the fringe multiple times before they

are expanded.

"""

# The following section specifies the search problem and the solution.

# The graph is specified by first the set of start states, followed by

# the set of goal states, and lastly by the state transitions which are

# of the form:

#         

graph: """

start_state: A

goal_states: G

A 0:A->B1 B1 1.0

A 1:A->C C 2.0

A 2:A->B2 B2 4.0

B1 0:B1->C C 8.0

B2 0:B2->C C 16.0

C 0:C->D D 32.0

D 0:D->E1 E1 64.0

D 1:D->F F 128.0

D 2:D->E2 E2 256.0

E1 0:E1->F F 512.0

E2 0:E2->F F 1024.0

F 0:F->G G 2048.0

"""
homework_1_search/test_cases/q5/CONFIG

class: "PassAllTestsQuestion"

max_points: "3"

depends: "q2"
homework_1_search/test_cases/q5/corner_tiny_corner.solution

# This is the solution file for test_cases/q5/corner_tiny_corner.test.

solution_length: "28"
homework_1_search/test_cases/q5/corner_tiny_corner.test

class: "CornerProblemTest"

layoutName: "tinyCorner"

layout: """

%%%%%%%%

%.    .%

%   P  %

% %%%% %

% %    %

% % %%%%

%.%   .%

%%%%%%%%

"""
homework_1_search/test_cases/q6/CONFIG

class: "Q6PartialCreditQuestion"

max_points: "3"

depends: "q4"
homework_1_search/test_cases/q6/corner_sanity_1.solution

# In order for a heuristic to be admissible, the value

# of the heuristic must be less at each state than the

# true cost of the optimal path from that state to a goal.

cost: "8"

path: """

North South South East East East North North

"""
homework_1_search/test_cases/q6/corner_sanity_1.test

class: "CornerHeuristicSanity"

points: "1"

# The following specifies the layout to be used

layout: """

%%%%%%

%.  .%

%P   %

%.  .%

%%%%%%

"""
homework_1_search/test_cases/q6/corner_sanity_2.solution

# In order for a heuristic to be admissible, the value

# of the heuristic must be less at each state than the

# true cost of the optimal path from that state to a goal.

cost: "8"

path: """

West North North East East East South South

"""
homework_1_search/test_cases/q6/corner_sanity_2.test

class: "CornerHeuristicSanity"

points: "1"

# The following specifies the layout to be used

layout: """

%%%%%%

%.  .%

% %% %

%.P%.%

%%%%%%

"""
homework_1_search/test_cases/q6/corner_sanity_3.solution

# In order for a heuristic to be admissible, the value

# of the heuristic must be less at each state than the

# true cost of the optimal path from that state to a goal.

cost: "28"

path: """

South South South West West West West East East East East East North

North North North North West West West South South South West West

North North North

"""
homework_1_search/test_cases/q6/corner_sanity_3.test

class: "CornerHeuristicSanity"

points: "1"

# The following specifies the layout to be used

layout: """

%%%%%%%%

%.%   .%

% % %  %

% % %P %

%   %  %

%%%%%  %

%.    .%

%%%%%%%%

"""
homework_1_search/test_cases/q6/medium_corners.solution

# This solution file specifies the length of the optimal path

# as well as the thresholds on number of nodes expanded to be

# used in scoring.

cost: "106"

path: """

North East East East East North North West West West West North North

North North North North North North West West West West South South

East East East East South South South South South South West West

South South South West West East East North North North East East East

East East East East East South South East East East East East North

North East East North North East East North North East East East East

South South South South East East North North East East South South

South South South North North North North North North North West West

North North East East North North

"""

thresholds: "2000 1600 1200"
homework_1_search/test_cases/q6/medium_corners.test

class: "CornerHeuristicPacman"

# The following specifies the layout to be used

layout: """

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%.      % % %              %.%

%       % % %%%%%% %%%%%%% % %

%       %        %     % %   %

%%%%% %%%%% %%% %% %%%%% % %%%

%   % % % %   %    %     %   %

% %%% % % % %%%%%%%% %%% %%% %

%       %     %%     % % %   %

%%% % %%%%%%% %%%% %%% % % % %

% %           %%     %     % %

% % %%%%% % %%%% % %%% %%% % %

%   %     %      % %   % %%% %

%.  %P%%%%%      % %%% %    .%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

"""
homework_1_search/test_cases/q7/CONFIG

class: "PartialCreditQuestion"

max_points: "4"

depends: "q4"
homework_1_search/test_cases/q7/food_heuristic_1.solution

# This is the solution file for test_cases/q7/food_heuristic_1.test.

solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_1.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 1"

layout: """

%%%%%%

%    %

%    %

%P   %

%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_10.solution

# This is the solution file for test_cases/q7/food_heuristic_10.test.

solution_cost: "7"
homework_1_search/test_cases/q7/food_heuristic_10.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 10"

layout: """

%%%%%%%%

%      %

%.  P .%

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_11.solution

# This is the solution file for test_cases/q7/food_heuristic_11.test.

solution_cost: "8"
homework_1_search/test_cases/q7/food_heuristic_11.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 11"

layout: """

%%%%%%%%

%      %

%   P  %

%.  . .%

%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_12.solution

# This is the solution file for test_cases/q7/food_heuristic_12.test.

solution_cost: "1"
homework_1_search/test_cases/q7/food_heuristic_12.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 12"

layout: """

%%%%%%%%

%      %

%    P.%

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_13.solution

# This is the solution file for test_cases/q7/food_heuristic_13.test.

solution_cost: "5"
homework_1_search/test_cases/q7/food_heuristic_13.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 13"

layout: """

%%%%%%%%

%      %

%P.   .%

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_14.solution

# This is the solution file for test_cases/q7/food_heuristic_14.test.

solution_cost: "31"
homework_1_search/test_cases/q7/food_heuristic_14.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 14"

layout: """

%%%%%%%%%%

%        %

% ...%...%

% .%.%.%.%

% .%.%.%.%

% .%.%.%.%

% .%.%.%.%

% .%.%.%.%

%P.%...%.%

%        %

%%%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_15.solution

# This is the solution file for test_cases/q7/food_heuristic_15.test.

solution_cost: "21"
homework_1_search/test_cases/q7/food_heuristic_15.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 15"

layout: """

%%%

% %

% %

% %

% %

% %

%.%

%.%

% %

% %

% %

% %

% %

% %

% %

%.%

% %

%P%

% %

% %

% %

% %

%.%

%%%

"""
homework_1_search/test_cases/q7/food_heuristic_16.solution

# This is the solution file for test_cases/q7/food_heuristic_16.test.

solution_cost: "7"
homework_1_search/test_cases/q7/food_heuristic_16.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 16"

layout: """

%%%%

% .%

%  %

%P %

%  %

% .%

%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_17.solution

# This is the solution file for test_cases/q7/food_heuristic_17.test.

solution_cost: "16"
homework_1_search/test_cases/q7/food_heuristic_17.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 17"

layout: """

%%%%%%%%

%.%....%

%.% %%.%

%.%P%%.%

%...  .%

%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_2.solution

# This is the solution file for test_cases/q7/food_heuristic_2.test.

solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_2.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 2"

layout: """

%%%

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

% %

%P%

% %

% %

% %

% %

% %

%%%

"""
homework_1_search/test_cases/q7/food_heuristic_3.solution

# This is the solution file for test_cases/q7/food_heuristic_3.test.

solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_3.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 3"

layout: """

%%%%

%  %

%  %

%P %

%  %

%  %

%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_4.solution

# This is the solution file for test_cases/q7/food_heuristic_4.test.

solution_cost: "0"
homework_1_search/test_cases/q7/food_heuristic_4.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 4"

layout: """

%%%%%%%%

% %    %

% % %% %

% %P%% %

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_5.solution

# This is the solution file for test_cases/q7/food_heuristic_5.test.

solution_cost: "11"
homework_1_search/test_cases/q7/food_heuristic_5.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 5"

layout: """

%%%%%%

%....%

%....%

%P...%

%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_6.solution

# This is the solution file for test_cases/q7/food_heuristic_6.test.

solution_cost: "5"
homework_1_search/test_cases/q7/food_heuristic_6.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 6"

layout: """

%%%%%%

%   .%

%.P..%

%    %

%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_7.solution

# This is the solution file for test_cases/q7/food_heuristic_7.test.

solution_cost: "7"
homework_1_search/test_cases/q7/food_heuristic_7.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 7"

layout: """

%%%%%%%

%    .%

%. P..%

%     %

%%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_8.solution

# This is the solution file for test_cases/q7/food_heuristic_8.test.

solution_cost: "5"
homework_1_search/test_cases/q7/food_heuristic_8.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 8"

layout: """

%%%%%%

%   .%

%   .%

%P  .%

%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_9.solution

# This is the solution file for test_cases/q7/food_heuristic_9.test.

solution_cost: "6"
homework_1_search/test_cases/q7/food_heuristic_9.test

class: "HeuristicTest"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "Test 9"

layout: """

%%%%%%

% %. %

% %%.%

%P. .%

%%%%%%

"""
homework_1_search/test_cases/q7/food_heuristic_grade_tricky.solution

# This is the solution file for test_cases/q7/food_heuristic_grade_tricky.test.

# File intentionally blank.
homework_1_search/test_cases/q7/food_heuristic_grade_tricky.test

class: "HeuristicGrade"

heuristic: "foodHeuristic"

searchProblemClass: "FoodSearchProblem"

layoutName: "trickySearch"

layout: """

%%%%%%%%%%%%%%%%%%%%

%.           ..%   %

%.%%.%%.%%.%%.%% % %

%        P       % %

%%%%%%%%%%%%%%%%%% %

%.....             %

%%%%%%%%%%%%%%%%%%%%

"""

# One point always, an extra point for each

# threshold passed.

basePoints: "1"

gradingThresholds: "15000 12000 9000 7000"
homework_1_search/test_cases/q8/closest_dot_1.solution

# This is the solution file for test_cases/q8/closest_dot_1.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_1.test

class: "ClosestDotTest"

layoutName: "Test 1"

layout: """

%%%%%%

%....%

%....%

%P...%

%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_10.solution

# This is the solution file for test_cases/q8/closest_dot_10.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_10.test

class: "ClosestDotTest"

layoutName: "Test 10"

layout: """

%%%%%%%%%%

%        %

% ...%...%

% .%.%.%.%

% .%.%.%.%

% .%.%.%.%

% .%.%.%.%

% .%.%.%.%

%P.%...%.%

%        %

%%%%%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_11.solution

# This is the solution file for test_cases/q8/closest_dot_11.test.

solution_length: "2"
homework_1_search/test_cases/q8/closest_dot_11.test

class: "ClosestDotTest"

layoutName: "Test 11"

layout: """

%%%

% %

% %

% %

% %

% %

%.%

%.%

% %

% %

% %

% %

% %

% %

% %

%.%

% %

%P%

% %

% %

% %

% %

%.%

%%%

"""
homework_1_search/test_cases/q8/closest_dot_12.solution

# This is the solution file for test_cases/q8/closest_dot_12.test.

solution_length: "3"
homework_1_search/test_cases/q8/closest_dot_12.test

class: "ClosestDotTest"

layoutName: "Test 12"

layout: """

%%%%

% .%

%  %

%P %

%  %

% .%

%%%%

"""
homework_1_search/test_cases/q8/closest_dot_13.solution

# This is the solution file for test_cases/q8/closest_dot_13.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_13.test

class: "ClosestDotTest"

layoutName: "Test 13"

layout: """

%%%%%%%%

%.%....%

%.% %%.%

%.%P%%.%

%...  .%

%%%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_2.solution

# This is the solution file for test_cases/q8/closest_dot_2.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_2.test

class: "ClosestDotTest"

layoutName: "Test 2"

layout: """

%%%%%%

%   .%

%.P..%

%    %

%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_3.solution

# This is the solution file for test_cases/q8/closest_dot_3.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_3.test

class: "ClosestDotTest"

layoutName: "Test 3"

layout: """

%%%%%%%

%    .%

%. P..%

%     %

%%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_4.solution

# This is the solution file for test_cases/q8/closest_dot_4.test.

solution_length: "3"
homework_1_search/test_cases/q8/closest_dot_4.test

class: "ClosestDotTest"

layoutName: "Test 4"

layout: """

%%%%%%

%   .%

%   .%

%P  .%

%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_5.solution

# This is the solution file for test_cases/q8/closest_dot_5.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_5.test

class: "ClosestDotTest"

layoutName: "Test 5"

layout: """

%%%%%%

% %. %

% %%.%

%P. .%

%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_6.solution

# This is the solution file for test_cases/q8/closest_dot_6.test.

solution_length: "2"
homework_1_search/test_cases/q8/closest_dot_6.test

class: "ClosestDotTest"

layoutName: "Test 6"

layout: """

%%%%%%%%

%      %

%.  P .%

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_7.solution

# This is the solution file for test_cases/q8/closest_dot_7.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_7.test

class: "ClosestDotTest"

layoutName: "Test 7"

layout: """

%%%%%%%%

%      %

%   P  %

%.  . .%

%%%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_8.solution

# This is the solution file for test_cases/q8/closest_dot_8.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_8.test

class: "ClosestDotTest"

layoutName: "Test 8"

layout: """

%%%%%%%%

%      %

%    P.%

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q8/closest_dot_9.solution

# This is the solution file for test_cases/q8/closest_dot_9.test.

solution_length: "1"
homework_1_search/test_cases/q8/closest_dot_9.test

class: "ClosestDotTest"

layoutName: "Test 9"

layout: """

%%%%%%%%

%      %

%P.   .%

%      %

%%%%%%%%

"""
homework_1_search/test_cases/q8/CONFIG

class: "PassAllTestsQuestion"

max_points: "3"
homework_1_search/textDisplay.py

# textDisplay.py

# --------------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
import time

try:

    import pacman

except:

    pass

DRAW_EVERY = 1

SLEEP_TIME = 0 # This can be overwritten by __init__

DISPLAY_MOVES = False

QUIET = False # Supresses output

class NullGraphics:

    def initialize(self, state, isBlue = False):

        pass

    def update(self, state):

        pass

    def checkNullDisplay(self):

        return True

    def pause(self):

        time.sleep(SLEEP_TIME)

    def draw(self, state):

        print(state)

    def updateDistributions(self, dist):

        pass

    def finish(self):

        pass

class PacmanGraphics:

    def __init__(self, speed=None):

        if speed != None:

            global SLEEP_TIME

            SLEEP_TIME = speed

    def initialize(self, state, isBlue = False):

        self.draw(state)

        self.pause()

        self.turn = 0

        self.agentCounter = 0

    def update(self, state):

        numAgents = len(state.agentStates)

        self.agentCounter = (self.agentCounter + 1) % numAgents

        if self.agentCounter == 0:

            self.turn += 1

            if DISPLAY_MOVES:

                ghosts = [pacman.nearestPoint(state.getGhostPosition(i)) for i in range(1, numAgents)]

                print("%4d) P: %-8s" % (self.turn, str(pacman.nearestPoint(state.getPacmanPosition()))),'| Score: %-5d' % state.score,'| Ghosts:', ghosts)

            if self.turn % DRAW_EVERY == 0:

                self.draw(state)

                self.pause()

        if state._win or state._lose:

            self.draw(state)

    def pause(self):

        time.sleep(SLEEP_TIME)

    def draw(self, state):

        print(state)

    def finish(self):

        pass
homework_1_search/util.py

# util.py

# -------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
# util.py

# -------

# Licensing Information:  You are free to use or extend these projects for

# educational purposes provided that (1) you do not distribute or publish

# solutions, (2) you retain this notice, and (3) you provide clear

# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.

#

# Attribution Information: The Pacman AI projects were developed at UC Berkeley.

# The core projects and autograders were primarily created by John DeNero

# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).

# Student side autograding was added by Brad Miller, Nick Hay, and

# Pieter Abbeel (pabbeel@cs.berkeley.edu).
import sys

import inspect

import heapq, random
class FixedRandom:

    def __init__(self):

        fixedState = (3, (2147483648, 507801126, 683453281, 310439348, 2597246090, \

            2209084787, 2267831527, 979920060, 3098657677, 37650879, 807947081, 3974896263, \

            881243242, 3100634921, 1334775171, 3965168385, 746264660, 4074750168, 500078808, \

            776561771, 702988163, 1636311725, 2559226045, 157578202, 2498342920, 2794591496, \

            4130598723, 496985844, 2944563015, 3731321600, 3514814613, 3362575829, 3038768745, \

            2206497038, 1108748846, 1317460727, 3134077628, 988312410, 1674063516, 746456451, \

            3958482413, 1857117812, 708750586, 1583423339, 3466495450, 1536929345, 1137240525, \

            3875025632, 2466137587, 1235845595, 4214575620, 3792516855, 657994358, 1241843248, \

            1695651859, 3678946666, 1929922113, 2351044952, 2317810202, 2039319015, 460787996, \

            3654096216, 4068721415, 1814163703, 2904112444, 1386111013, 574629867, 2654529343, \

            3833135042, 2725328455, 552431551, 4006991378, 1331562057, 3710134542, 303171486, \

            1203231078, 2670768975, 54570816, 2679609001, 578983064, 1271454725, 3230871056, \

            2496832891, 2944938195, 1608828728, 367886575, 2544708204, 103775539, 1912402393, \

            1098482180, 2738577070, 3091646463, 1505274463, 2079416566, 659100352, 839995305, \

            1696257633, 274389836, 3973303017, 671127655, 1061109122, 517486945, 1379749962, \

            3421383928, 3116950429, 2165882425, 2346928266, 2892678711, 2936066049, 1316407868, \

            2873411858, 4279682888, 2744351923, 3290373816, 1014377279, 955200944, 4220990860, \

            2386098930, 1772997650, 3757346974, 1621616438, 2877097197, 442116595, 2010480266, \

            2867861469, 2955352695, 605335967, 2222936009, 2067554933, 4129906358, 1519608541, \

            1195006590, 1942991038, 2736562236, 279162408, 1415982909, 4099901426, 1732201505, \

            2934657937, 860563237, 2479235483, 3081651097, 2244720867, 3112631622, 1636991639, \

            3860393305, 2312061927, 48780114, 1149090394, 2643246550, 1764050647, 3836789087, \

            3474859076, 4237194338, 1735191073, 2150369208, 92164394, 756974036, 2314453957, \

            323969533, 4267621035, 283649842, 810004843, 727855536, 1757827251, 3334960421, \

            3261035106, 38417393, 2660980472, 1256633965, 2184045390, 811213141, 2857482069, \

            2237770878, 3891003138, 2787806886, 2435192790, 2249324662, 3507764896, 995388363, \

            856944153, 619213904, 3233967826, 3703465555, 3286531781, 3863193356, 2992340714, \

            413696855, 3865185632, 1704163171, 3043634452, 2225424707, 2199018022, 3506117517, \

            3311559776, 3374443561, 1207829628, 668793165, 1822020716, 2082656160, 1160606415, \

            3034757648, 741703672, 3094328738, 459332691, 2702383376, 1610239915, 4162939394, \

            557861574, 3805706338, 3832520705, 1248934879, 3250424034, 892335058, 74323433, \

            3209751608, 3213220797, 3444035873, 3743886725, 1783837251, 610968664, 580745246, \

            4041979504, 201684874, 2673219253, 1377283008, 3497299167, 2344209394, 2304982920, \

            3081403782, 2599256854, 3184475235, 3373055826, 695186388, 2423332338, 222864327, \

            1258227992, 3627871647, 3487724980, 4027953808, 3053320360, 533627073, 3026232514, \

            2340271949, 867277230, 868513116, 2158535651, 2487822909, 3428235761, 3067196046, \

            3435119657, 1908441839, 788668797, 3367703138, 3317763187, 908264443, 2252100381, \

            764223334, 4127108988, 384641349, 3377374722, 1263833251, 1958694944, 3847832657, \

            1253909612, 1096494446, 555725445, 2277045895, 3340096504, 1383318686, 4234428127, \

            1072582179, 94169494, 1064509968, 2681151917, 2681864920, 734708852, 1338914021, \

            1270409500, 1789469116, 4191988204, 1716329784, 2213764829, 3712538840, 919910444, \

            1318414447, 3383806712, 3054941722, 3378649942, 1205735655, 1268136494, 2214009444, \

            2532395133, 3232230447, 230294038, 342599089, 772808141, 4096882234, 3146662953, \

            2784264306, 1860954704, 2675279609, 2984212876, 2466966981, 2627986059, 2985545332, \

            2578042598, 1458940786, 2944243755, 3959506256, 1509151382, 325761900, 942251521, \

            4184289782, 2756231555, 3297811774, 1169708099, 3280524138, 3805245319, 3227360276, \

            3199632491, 2235795585, 2865407118, 36763651, 2441503575, 3314890374, 1755526087, \

            17915536, 1196948233, 949343045, 3815841867, 489007833, 2654997597, 2834744136, \

            417688687, 2843220846, 85621843, 747339336, 2043645709, 3520444394, 1825470818, \

            647778910, 275904777, 1249389189, 3640887431, 4200779599, 323384601, 3446088641, \

            4049835786, 1718989062, 3563787136, 44099190, 3281263107, 22910812, 1826109246, \

            745118154, 3392171319, 1571490704, 354891067, 815955642, 1453450421, 940015623, \

            796817754, 1260148619, 3898237757, 176670141, 1870249326, 3317738680, 448918002, \

            4059166594, 2003827551, 987091377, 224855998, 3520570137, 789522610, 2604445123, \

            454472869, 475688926, 2990723466, 523362238, 3897608102, 806637149, 2642229586, \

            2928614432, 1564415411, 1691381054, 3816907227, 4082581003, 1895544448, 3728217394, \

            3214813157, 4054301607, 1882632454, 2873728645, 3694943071, 1297991732, 2101682438, \

            3952579552, 678650400, 1391722293, 478833748, 2976468591, 158586606, 2576499787, \

            662690848, 3799889765, 3328894692, 2474578497, 2383901391, 1718193504, 3003184595, \

            3630561213, 1929441113, 3848238627, 1594310094, 3040359840, 3051803867, 2462788790, \

            954409915, 802581771, 681703307, 545982392, 2738993819, 8025358, 2827719383, \

            770471093, 3484895980, 3111306320, 3900000891, 2116916652, 397746721, 2087689510, \

            721433935, 1396088885, 2751612384, 1998988613, 2135074843, 2521131298, 707009172, \

            2398321482, 688041159, 2264560137, 482388305, 207864885, 3735036991, 3490348331, \

            1963642811, 3260224305, 3493564223, 1939428454, 1128799656, 1366012432, 2858822447, \

            1428147157, 2261125391, 1611208390, 1134826333, 2374102525, 3833625209, 2266397263, \

            3189115077, 770080230, 2674657172, 4280146640, 3604531615, 4235071805, 3436987249, \

            509704467, 2582695198, 4256268040, 3391197562, 1460642842, 1617931012, 457825497, \

            1031452907, 1330422862, 4125947620, 2280712485, 431892090, 2387410588, 2061126784, \

            896457479, 3480499461, 2488196663, 4021103792, 1877063114, 2744470201, 1046140599, \

            2129952955, 3583049218, 4217723693, 2720341743, 820661843, 1079873609, 3360954200, \

            3652304997, 3335838575, 2178810636, 1908053374, 4026721976, 1793145418, 476541615, \

            973420250, 515553040, 919292001, 2601786155, 1685119450, 3030170809, 1590676150, \

            1665099167, 651151584, 2077190587, 957892642, 646336572, 2743719258, 866169074, \

            851118829, 4225766285, 963748226, 799549420, 1955032629, 799460000, 2425744063, \

            2441291571, 1928963772, 528930629, 2591962884, 3495142819, 1896021824, 901320159, \

            3181820243, 843061941, 3338628510, 3782438992, 9515330, 1705797226, 953535929, \

            764833876, 3202464965, 2970244591, 519154982, 3390617541, 566616744, 3438031503, \

            1853838297, 170608755, 1393728434, 676900116, 3184965776, 1843100290, 78995357, \

            2227939888, 3460264600, 1745705055, 1474086965, 572796246, 4081303004, 882828851, \

            1295445825, 137639900, 3304579600, 2722437017, 4093422709, 273203373, 2666507854, \

            3998836510, 493829981, 1623949669, 3482036755, 3390023939, 833233937, 1639668730, \

            1499455075, 249728260, 1210694006, 3836497489, 1551488720, 3253074267, 3388238003, \

            2372035079, 3945715164, 2029501215, 3362012634, 2007375355, 4074709820, 631485888, \

            3135015769, 4273087084, 3648076204, 2739943601, 1374020358, 1760722448, 3773939706, \

            1313027823, 1895251226, 4224465911, 421382535, 1141067370, 3660034846, 3393185650, \

            1850995280, 1451917312, 3841455409, 3926840308, 1397397252, 2572864479, 2500171350, \

            3119920613, 531400869, 1626487579, 1099320497, 407414753, 2438623324, 99073255, \

            3175491512, 656431560, 1153671785, 236307875, 2824738046, 2320621382, 892174056, \

            230984053, 719791226, 2718891946, 624), None)

        self.random = random.Random()

        self.random.setstate(fixedState)

"""

 Data structures useful for implementing SearchAgents

"""

class Stack:

    "A container with a last-in-first-out (LIFO) queuing policy."

    def __init__(self):

        self.list = []

    def push(self,item):

        "Push 'item' onto the stack"

        self.list.append(item)

    def pop(self):

        "Pop the most recently pushed item from the stack"

        return self.list.pop()

    def isEmpty(self):

        "Returns true if the stack is empty"

        return len(self.list) == 0

class Queue:

    "A container with a first-in-first-out (FIFO) queuing policy."

    def __init__(self):

        self.list = []

    def push(self,item):

        "Enqueue the 'item' into the queue"

        self.list.insert(0,item)

    def pop(self):

        """

          Dequeue the earliest enqueued item still in the queue. This

          operation removes the item from the queue.

        """

        return self.list.pop()

    def isEmpty(self):

        "Returns true if the queue is empty"

        return len(self.list) == 0

class PriorityQueue:

    """

      Implements a priority queue data structure. Each inserted item

      has a priority associated with it and the client is usually interested

      in quick retrieval of the lowest-priority item in the queue. This

      data structure allows O(1) access to the lowest-priority item.

    """

    def  __init__(self):

        self.heap = []

        self.count = 0

    def push(self, item, priority):

        entry = (priority, self.count, item)

        heapq.heappush(self.heap, entry)

        self.count += 1

    def pop(self):

        (_, _, item) = heapq.heappop(self.heap)

        return item

    def isEmpty(self):

        return len(self.heap) == 0

    def update(self, item, priority):

        # If item already in priority queue with higher priority, update its priority and rebuild the heap.

        # If item already in priority queue with equal or lower priority, do nothing.

        # If item not in priority queue, do the same thing as self.push.

        for index, (p, c, i) in enumerate(self.heap):

            if i == item:

                if p <= priority:
                    break
                del self.heap[index]
                self.heap.append((priority, c, item))
                heapq.heapify(self.heap)
                break
        else:
            self.push(item, priority)
class PriorityQueueWithFunction(PriorityQueue):
    """
    Implements a priority queue with the same push/pop signature of the
    Queue and the Stack classes. This is designed for drop-in replacement for
    those two classes. The caller has to provide a priority function, which
    extracts each item's priority.
    """
    def  __init__(self, priorityFunction):
        "priorityFunction (item) -> priority"

        self.priorityFunction = priorityFunction      # store the priority function

        PriorityQueue.__init__(self)        # super-class initializer

    def push(self, item):

        "Adds an item to the queue with priority from the priority function"

        PriorityQueue.push(self, item, self.priorityFunction(item))
def manhattanDistance( xy1, xy2 ):

    "Returns the Manhattan distance between points xy1 and xy2"

    return abs( xy1[0] - xy2[0] ) + abs( xy1[1] - xy2[1] )

"""

  Data structures and functions useful for various course projects

  The search project should not need anything below this line.

"""

class Counter(dict):

    """

    A counter keeps track of counts for a set of keys.

    The counter class is an extension of the standard python

    dictionary type.  It is specialized to have number values

    (integers or floats), and includes a handful of additional

    functions to ease the task of counting data.  In particular,

    all keys are defaulted to have value 0.  Using a dictionary:

    a = {}

    print(a['test'])

    would give an error, while the Counter class analogue:

    >>> a = Counter()

    >>> print(a['test'])

    0

    returns the default 0 value. Note that to reference a key

    that you know is contained in the counter,

    you can still use the dictionary syntax:

    >>> a = Counter()

    >>> a['test'] = 2

    >>> print(a['test'])

    2

    This is very useful for counting things without initializing their counts,

    see for example:

    >>> a['blah'] += 1

    >>> print(a['blah'])

    1

    The counter also includes additional functionality useful in implementing

    the classifiers for this assignment.  Two counters can be added,

    subtracted or multiplied together.  See below for details.  They can

    also be normalized and their total count and arg max can be extracted.

    """

    def __getitem__(self, idx):

        self.setdefault(idx, 0)

        return dict.__getitem__(self, idx)

    def incrementAll(self, keys, count):

        """

        Increments all elements of keys by the same count.

        >>> a = Counter()

        >>> a.incrementAll(['one','two', 'three'], 1)

        >>> a['one']

        1

        >>> a['two']

        1

        """

        for key in keys:

            self[key] += count

    def argMax(self):

        """

        Returns the key with the highest value.

        """

        if len(self.keys()) == 0: return None

        all = self.items()

        values = [x[1] for x in all]

        maxIndex = values.index(max(values))

        return all[maxIndex][0]

    def sortedKeys(self):

        """

        Returns a list of keys sorted by their values.  Keys

        with the highest values will appear first.

        >>> a = Counter()

        >>> a['first'] = -2

        >>> a['second'] = 4

        >>> a['third'] = 1

        >>> a.sortedKeys()

        ['second', 'third', 'first']

        """

        sortedItems = self.items()

        compare = lambda x, y:  sign(y[1] - x[1])

        sortedItems.sort(cmp=compare)

        return [x[0] for x in sortedItems]

    def totalCount(self):

        """

        Returns the sum of counts for all keys.

        """

        return sum(self.values())

    def normalize(self):

        """

        Edits the counter such that the total count of all

        keys sums to 1.  The ratio of counts for all keys

        will remain the same. Note that normalizing an empty

        Counter will result in an error.

        """

        total = float(self.totalCount())

        if total == 0: return

        for key in self.keys():

            self[key] = self[key] / total

    def divideAll(self, divisor):

        """

        Divides all counts by divisor

        """

        divisor = float(divisor)

        for key in self:

            self[key] /= divisor

    def copy(self):

        """

        Returns a copy of the counter

        """

        return Counter(dict.copy(self))

    def __mul__(self, y ):

        """

        Multiplying two counters gives the dot product of their vectors where

        each unique label is a vector element.

        >>> a = Counter()

        >>> b = Counter()

        >>> a['first'] = -2

        >>> a['second'] = 4

        >>> b['first'] = 3

        >>> b['second'] = 5

        >>> a['third'] = 1.5

        >>> a['fourth'] = 2.5

        >>> a * b

        14

        """

        sum = 0

        x = self

        if len(x) > len(y):

            x,y = y,x

        for key in x:

            if key not in y:

                continue

            sum += x[key] * y[key]

        return sum

    def __radd__(self, y):

        """

        Adding another counter to a counter increments the current counter

        by the values stored in the second counter.

        >>> a = Counter()

        >>> b = Counter()

        >>> a['first'] = -2

        >>> a['second'] = 4

        >>> b['first'] = 3

        >>> b['third'] = 1

        >>> a += b

        >>> a['first']

        1

        """

        for key, value in y.items():

            self[key] += value

    def __add__( self, y ):

        """

        Adding two counters gives a counter with the union of all keys and

        counts of the second added to counts of the first.

        >>> a = Counter()

        >>> b = Counter()

        >>> a['first'] = -2

        >>> a['second'] = 4

        >>> b['first'] = 3

        >>> b['third'] = 1

        >>> (a + b)['first']

        1

        """

        addend = Counter()

        for key in self:

            if key in y:

                addend[key] = self[key] + y[key]

            else:

                addend[key] = self[key]

        for key in y:

            if key in self:

                continue

            addend[key] = y[key]

        return addend

    def __sub__( self, y ):

        """

        Subtracting a counter from another gives a counter with the union of all keys and

        counts of the second subtracted from counts of the first.

        >>> a = Counter()

        >>> b = Counter()

        >>> a['first'] = -2

        >>> a['second'] = 4

        >>> b['first'] = 3

        >>> b['third'] = 1

        >>> (a - b)['first']

        -5

        """

        addend = Counter()

        for key in self:

            if key in y:

                addend[key] = self[key] - y[key]

            else:

                addend[key] = self[key]

        for key in y:

            if key in self:

                continue

            addend[key] = -1 * y[key]

        return addend

def raiseNotDefined():

    fileName = inspect.stack()[1][1]

    line = inspect.stack()[1][2]

    method = inspect.stack()[1][3]

    print("*** Method not implemented: %s at line %s of %s" % (method, line, fileName))

    sys.exit(1)

def normalize(vectorOrCounter):

    """

    normalize a vector or counter by dividing each value by the sum of all values

    """

    normalizedCounter = Counter()

    if type(vectorOrCounter) == type(normalizedCounter):

        counter = vectorOrCounter

        total = float(counter.totalCount())

        if total == 0: return counter

        for key in counter.keys():

            value = counter[key]

            normalizedCounter[key] = value / total

        return normalizedCounter

    else:

        vector = vectorOrCounter

        s = float(sum(vector))

        if s == 0: return vector

        return [el / s for el in vector]

def nSample(distribution, values, n):

    if sum(distribution) != 1:

        distribution = normalize(distribution)

    rand = [random.random() for i in range(n)]

    rand.sort()

    samples = []

    samplePos, distPos, cdf = 0,0, distribution[0]

    while samplePos < n:
        if rand[samplePos] < cdf:
            samplePos += 1
            samples.append(values[distPos])
        else:
            distPos += 1
            cdf += distribution[distPos]
    return samples
def sample(distribution, values = None):
    if type(distribution) == Counter:
        items = sorted(distribution.items())
        distribution = [i[1] for i in items]
        values = [i[0] for i in items]
    if sum(distribution) != 1:
        distribution = normalize(distribution)
    choice = random.random()
    i, total= 0, distribution[0]
    while choice > total:

        i += 1

        total += distribution[i]

    return values[i]

def sampleFromCounter(ctr):

    items = sorted(ctr.items())

    return sample([v for k,v in items], [k for k,v in items])

def getProbability(value, distribution, values):

    """

      Gives the probability of a value under a discrete distribution

      defined by (distributions, values).

    """

    total = 0.0

    for prob, val in zip(distribution, values):

        if val == value:

            total += prob

    return total

def flipCoin( p ):

    r = random.random()

    return r < p
def chooseFromDistribution( distribution ):
    "Takes either a counter or a list of (prob, key) pairs and samples"
    if type(distribution) == dict or type(distribution) == Counter:
        return sample(distribution)
    r = random.random()
    base = 0.0
    for prob, element in distribution:
        base += prob
        if r <= base: return element
def nearestPoint( pos ):
    """
    Finds the nearest grid point to a position (discretizes).
    """
    ( current_row, current_col ) = pos
    grid_row = int( current_row + 0.5 )
    grid_col = int( current_col + 0.5 )
    return ( grid_row, grid_col )
def sign( x ):
    """
    Returns 1 or -1 depending on the sign of x
    """
    if( x >= 0 ):

        return 1

    else:

        return -1

def arrayInvert(array):

    """

    Inverts a matrix stored as a list of lists.

    """

    result = [[] for i in array]

    for outer in array:

        for inner in range(len(outer)):

            result[inner].append(outer[inner])

    return result

def matrixAsList( matrix, value = True ):

    """

    Turns a matrix into a list of coordinates matching the specified value

    """

    rows, cols = len( matrix ), len( matrix[0] )

    cells = []

    for row in range( rows ):

        for col in range( cols ):

            if matrix[row][col] == value:

                cells.append( ( row, col ) )

    return cells

def lookup(name, namespace):

    """

    Get a method or class from any imported module from its name.

    Usage: lookup(functionName, globals())

    """

    dots = name.count('.')

    if dots > 0:

        moduleName, objName = '.'.join(name.split('.')[:-1]), name.split('.')[-1]

        module = __import__(moduleName)

        return getattr(module, objName)

    else:

        modules = [obj for obj in namespace.values() if str(type(obj)) == ""]

        options = [getattr(module, name) for module in modules if name in dir(module)]

        options += [obj[1] for obj in namespace.items() if obj[0] == name ]

        if len(options) == 1: return options[0]

        if len(options) > 1: raise Exception('Name conflict for %s')

        raise Exception('%s not found as a method or class' % name)

def pause():

    """

    Pauses the output stream awaiting user feedback.

    """

    input("")
# code to handle timeouts

#

# FIXME

# NOTE: TimeoutFuncton is NOT reentrant.  Later timeouts will silently

# disable earlier timeouts.  Could be solved by maintaining a global list

# of active time outs.  Currently, questions which have test cases calling

# this have all student code so wrapped.

#

import signal

import time

class TimeoutFunctionException(Exception):

    """Exception to raise on a timeout"""

    pass
class TimeoutFunction:

    def __init__(self, function, timeout):

        self.timeout = timeout

        self.function = function

    def handle_timeout(self, signum, frame):

        raise TimeoutFunctionException()

    def __call__(self, *args, **keyArgs):

        # If we have SIGALRM signal, use it to cause an exception if and

        # when this function runs too long.  Otherwise check the time taken

        # after the method has returned, and throw an exception then.

        if hasattr(signal, 'SIGALRM'):

            old = signal.signal(signal.SIGALRM, self.handle_timeout)

            signal.alarm(self.timeout)

            try:

                result = self.function(*args, **keyArgs)

            finally:

                signal.signal(signal.SIGALRM, old)

            signal.alarm(0)

        else:

            startTime = time.time()

            result = self.function(*args, **keyArgs)

            timeElapsed = time.time() - startTime

            if timeElapsed >= self.timeout:

                self.handle_timeout(None, None)

        return result
_ORIGINAL_STDOUT = None

_ORIGINAL_STDERR = None

_MUTED = False

class WritableNull:

    def write(self, string):

        pass

def mutePrint():

    global _ORIGINAL_STDOUT, _ORIGINAL_STDERR, _MUTED

    if _MUTED:

        return

    _MUTED = True

    _ORIGINAL_STDOUT = sys.stdout

    #_ORIGINAL_STDERR = sys.stderr

    sys.stdout = WritableNull()

    #sys.stderr = WritableNull()

def unmutePrint():

    global _ORIGINAL_STDOUT, _ORIGINAL_STDERR, _MUTED

    if not _MUTED:

        return

    _MUTED = False

    sys.stdout = _ORIGINAL_STDOUT

    #sys.stderr = _ORIGINAL_STDERR
homework_1_search/VERSION

v1.001
homework_1_search/__pycache__/game.cpython-37.pyc
homework_1_search/__pycache__/ghostAgents.cpython-37.pyc
homework_1_search/__pycache__/grading.cpython-37.pyc
homework_1_search/__pycache__/graphicsDisplay.cpython-37.pyc
homework_1_search/__pycache__/graphicsUtils.cpython-37.pyc
homework_1_search/__pycache__/keyboardAgents.cpython-37.pyc
homework_1_search/__pycache__/layout.cpython-37.pyc
homework_1_search/__pycache__/pacman.cpython-37.pyc
homework_1_search/__pycache__/pacmanAgents.cpython-37.pyc
homework_1_search/__pycache__/projectParams.cpython-37.pyc
homework_1_search/__pycache__/search.cpython-37.pyc
homework_1_search/__pycache__/searchAgents.cpython-37.pyc
homework_1_search/__pycache__/searchTestClasses.cpython-37.pyc
homework_1_search/__pycache__/testClasses.cpython-37.pyc
homework_1_search/__pycache__/testParser.cpython-37.pyc
homework_1_search/__pycache__/util.cpython-37.pyc

Homework 

1
–Search algorithms (Pacman)

Module: CSE 5120 Introduction to Artificial Intelligence

Assessment brief: The code and resources provided in this homework 
Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman’s first step in mastering his domain.
The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore. You can download all the code and supporting files as a zip folder from homework 1 link given on Blackboard.
Your homework is based on two parts as given below:
1. Code implemented for search algorithms in given search.py file (in specific sections as indicated in detail below)
2. A brief report on what you did for each algorithm (i.e., how you implemented with screenshots from autograder script given in the folder) 
File Name
Description
search.py
Where all of your search algorithms will reside.
searchAgents.py
Where all of your search-based agents will reside.
pacman.py
The main file that runs Pacman games. This file describes a Pacman GameState type, which you use in this project.
game.py
The logic behind how the Pacman world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid.
util.py
Useful data structures for implementing search algorithms.
After downloading the code, unzipping it, and changing to the directory, you should be able to play a game of Pacman by running the following command.
python pacman.py
pacman.py supports a number of options (e.g. --layout or -l). You can see the list of all options and their default values via python pacman.py -h.
All the commands you will need in this homework can be found in the file commands.txt for easy copying and pasting. You can use Spyder (installed through Anaconda from week 1 Thursday’s lecture) or other IDE for this work.

Files to Edit and Submit: You will need to edit and submit (search.py) and (searchAgents.py only if required) files to implement your algorithms. Once you have completed the homework, you are welcome to run automated tests using an autograder.py given in the folder before you submit them for accuracy. You do not need to submit autograder.py file in your code submission but will need to test your algorithms with autograder.py to copy screenshots in your report. Please do not change the other files in this distribution or submit any of the original files other than these files.

Academic Dishonesty: Your code will be checked against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, they will be detected easily, so please do not try that and submit your own work only. In case of cheating, the University’s academic policies on cheating and dishonesty will strictly apply which may result from the deduction in your grade to expulsion.

Figure 1: Breadth First and Uniform Cost search algorithms - pseudocode

Figure 2: Tree Search algorithm pseudocode
1

Tasks for homework 1

1.  Understanding the code base (not graded)

In searchAgents.py, you will find a fully implemented SearchAgent, which plans out a path through Pacman's world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented: your task is to implement them.
First, test that the SearchAgent is working correctly by running the following command.
python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch
The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm. This algorithm is implemented in search.py. Pacman should navigate the maze successfully.
Now you will need to implement different search algorithms to help Pacman plan its routes and reach its goal. Remember that a search node must contain not only a state but also the information necessary to reconstruct the path (plan) which gets to that state from the start state.

Important note: All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls).

Important note: Make sure to use the Stack, Queue and PriorityQueue data structures provided to you in util.py! These data structure implementations have particular properties that are required for compatibility with the autograder.

Hint: The algorithms we covered so far are quite similar. DFS, BFS, UCS, and A* algorithms differ only in the details of how the fringe (or frontier) is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit.)
2.  Depth First Search (1%)

Implement the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py.
Your code should be able to solve these tasks quickly.
1. python pacman.py -l tinyMaze -p SearchAgent
2. python pacman.py -l mediumMaze -p SearchAgent
3. python pacman.py -l bigMaze -z .5 -p SearchAgent

Evaluation: Run the following command to test your solution: python autograder.py -q q1. The first 4 test cases are basic test cases. Together they account for 0.8%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.2%.
3.  Breadth First Search (1%)

Implement the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py.
Your code should be able to solve these tasks quickly.
1. python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
2. python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

Evaluation: Run the following command to test your solution: python autograder.py -q q2. The first 4 test cases are basic test cases. Together they account for 0.8%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.2%.
4. Uniform Cost Search (1%)
BFS tries to minimize the number of actions taken, but not necessarily the least-cost path. By varying the cost function, the Pacman can be encouraged to explore different paths. By changing the cost function, we can encourage Pacman to find different paths. For example, we can charge more for dangerous steps in ghost-ridden areas or less for steps in food-rich areas.
Implement the uniform-cost search (UCS) algorithm in the uniformCostSearch function in search.py (the agents and the cost functions are implemented for you).
You should now observe successful behavior in all three of the following layouts.
1. python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
2. python pacman.py -l mediumDottedMaze -p StayEastSearchAgent
3. python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

Evaluation: Run the following command to test your solution: python autograder.py -q q3. The first 4 test cases are basic test cases. Together they account for 0.8%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.2%.
5. A* Search (2%)

Implement the A* search algorithm in the aStarSearch function in search.py. A* takes a heuristic function as an argument.
You need to test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic (already implemented).
python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar, heuristic= manhattanHeuristic

Evaluation: Run the following command to test your solution: python autograder.py -q q4. The first 5 test cases are basic test cases. Together they account for 1.5%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.5%.

Report

Brief description of your work here acknowledging your collaboration with your class fellow (or a friend from other CSE 5120 section), and the capacity at which he/she collaborated with you, followed by the algorithms you implemented.
1. Depth First Search

Your brief explanation (e.g., does DFS expand the shallowest or deepest unexpanded node? did you use Stack, Queue, or PriorityQueue in your code?) with screenshots of your code Evaluation (results from autograder.py)
2. Breadth First Search

Your brief explanation (e.g., does BFS expand the shallowest or deepest unexpanded node? did you use Stack, Queue, or PriorityQueue in your code?) with screenshots of your code Evaluation (results from autograder.py)
3.  Uniform Cost Search

Your brief explanation (e.g., does BFS expand the cheapest or closest node to the goal state? What function did you use to expand the cheapest or closest node in this algorithm and at which line?) with screenshots of your code Evaluation (results from autograder.py)
4. Breadth First Search

Your brief explanation (e.g., does A* use g(n) or h(n)? Where in the code are using retrieving the cost of an unexpanded node to plan and which function did you implement/use to get g(n), h(n), f(n) etc?) with screenshots of your code Evaluation (results from autograder.py)