from utils import (

is_in, argmin, argmax, argmax_random_tie, probability,

weighted_sample_with_replacement, memoize, print_table, DataFile, Stack,

FIFOQueue, PriorityQueue, name

)

from grid import distance

from collections import defaultdict

import math

import random

import sys

import bisect

infinity = float('inf')

class Problem(object):

raise NotImplementedError

class Node:

return hash(self.state)

class SimpleProblemSolvingAgentProgram:

raise NotImplementedError

def tree_search(problem, frontier):

return None

def graph_search(problem, frontier):

return None

def breadth_first_tree_search(problem):

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

return tree_search(problem, FIFOQueue())

def depth_first_tree_search(problem):

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

return tree_search(problem, Stack())

def depth_first_graph_search(problem):

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

return graph_search(problem, Stack())

def breadth_first_search(problem):

return None

def best_first_graph_search(problem, f):

return None

def uniform_cost_search(problem):

"[Figure 3.14]"

return best_first_graph_search(problem, lambda node: node.path_cost)

def depth_limited_search(problem, limit=50):

return recursive_dls(Node(problem.initial), problem, limit)

def iterative_deepening_search(problem):

return result

greedy_best_first_graph_search = best_first_graph_search

def astar_search(problem, h=None):

return best_first_graph_search(problem, lambda n: n.path_cost + h(n))

def recursive_best_first_search(problem, h=None):

return result

def hill_climbing(problem):

return current.state

def exp_schedule(k=20, lam=0.005, limit=100):

"One possible schedule function for simulated annealing"

return lambda t: (k * math.exp(-lam * t) if t < limit else 0)

def simulated_annealing(problem, schedule=exp_schedule()):

current = next

def and_or_graph_search(problem):

return or_search(problem.initial, problem, [])

class OnlineDFSAgent:

return percept

class OnlineSearchProblem(Problem):

return False

class LRTAStarAgent:

return self.problem.c(s, a, s1) + self.problem.h(s1)

def genetic_search(problem, fitness_fn, ngen=1000, pmut=0.1, n=20):

return genetic_algorithm(states[:n], problem.value, ngen, pmut)

def genetic_algorithm(population, fitness_fn, ngen=1000, pmut=0.1):

return argmax(population, key=fitness_fn)

class GAState:

raise NotImplementedError

class Graph:

return list(self.dict.keys())

def UndirectedGraph(dict=None):

"Build a Graph where every edge (including future ones) goes both ways."

return Graph(dict=dict, directed=False)

def RandomGraph(nodes=list(range(10)), min_links=2, width=400, height=300,

return g

romania_map = UndirectedGraph(dict(

Urziceni=dict(Vaslui=142)))

romania_map.locations = dict(

Arad=(91, 492), Bucharest=(400, 327), Craiova=(253, 288),

Drobeta=(165, 299), Eforie=(562, 293), Fagaras=(305, 449),

Giurgiu=(375, 270), Hirsova=(534, 350), Iasi=(473, 506),

Lugoj=(165, 379), Mehadia=(168, 339), Neamt=(406, 537),

Oradea=(131, 571), Pitesti=(320, 368), Rimnicu=(233, 410),

Sibiu=(207, 457), Timisoara=(94, 410), Urziceni=(456, 350),

Vaslui=(509, 444), Zerind=(108, 531))

vacumm_world = Graph(dict(

))

one_dim_state_space = Graph(dict(

))

one_dim_state_space.least_costs = dict(

State_1=8,

State_2=9,

State_3=2,

State_4=2,

State_5=4,

State_6=3)

australia_map = UndirectedGraph(dict(

NSW=dict(Q=1, V=1)))

australia_map.locations = dict(WA=(120, 24), NT=(135, 20), SA=(135, 30),

Q=(145, 20), NSW=(145, 32), T=(145, 42),

V=(145, 37))

class GraphProblem(Problem):

return infinity

class GraphProblemStochastic(GraphProblem):

raise NotImplementedError

class NQueensProblem(Problem):

for col in range(len(state)))

ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

cubes16 = ['FORIXB', 'MOQABJ', 'GURILW', 'SETUPL',

'CMPDAE', 'ACITAO', 'SLCRAE', 'ROMASH',

'NODESW', 'HEFIYE', 'ONUDTK', 'TEVIGN',

'ANEDVZ', 'PINESH', 'ABILYT', 'GKYLEU']

def random_boggle(n=4):

return list(map(random.choice, cubes))

boyan_best = list('RSTCSDEIAEGNLRPEATESMSSID')

def print_boggle(board):

print()

def boggle_neighbors(n2, cache={}):

return neighbors

def exact_sqrt(n2):

return n

class Wordlist: