"""(Chapter 6)"""
from __future__ import generators
from __future__ import nested_scopes
import random, time, bisect, math, string
from utils import *
import search
# Graphs
class Graph:
"""A graph connects nodes (verticies) by edges (links). Each edge can also
have a length associated with it. The constructor call is something like:
g = Graph({'A': {'B': 1, 'C': 2})
this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from
A to B, and an edge of length 2 from A to C. You can also do:
g = Graph({'A': {'B': 1, 'C': 2}, directed=false)
This makes an undirected graph, so inverse links are also added. The graph
stays undirected; if you add more links with g.connect('B', 'C', 3), then
inverse link is also added. You can use g.nodes() to get a list of nodes,
g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the
length of the link from A to B. 'Lengths' can actually be any object at
all, and nodes can be any hashable object."""
def __init__(self, dict=None, directed=true):
self.dict = dict or {}
self.directed = directed
if not directed: self.make_undirected()
def make_undirected(self):
"Make a digraph into an undirected graph by adding symmetric edges."
for a in self.dict.keys():
for (b, distance) in self.dict[a].items():
self.connect1(b, a, distance)
def connect(self, A, B, distance=1):
"""Add a link from A and B of given distance, and also add the inverse
link if the graph is undirected."""
self.connect1(A, B, distance)
if not self.directed: self.connect1(B, A, distance)
def connect1(self, A, B, distance):
"Add a link from A to B of given distance, in one direction only."
self.dict.setdefault(A,{})[B] = distance
def get(self, a, b=None):
"""Return a link distance or a dict of {node: distance} entries.
.get(a,b) returns the distance or None;
.get(a) returns a dict of {node: distance} entries, possibly {}."""
links = self.dict.setdefault(a, {})
if b is None: return links
else: return links.get(b)
def nodes(self):
"Return a list of nodes in the graph."
return 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=range(10), min_links=2, width=400, height=300,
curvature=lambda: random.uniform(1.1, 1.5)):
"""Construct a random graph, with the specified nodes, and random links.
The nodes are laid out randomly on a (width x height) rectangle.
Then each node is connected to the min_links nearest neighbors.
Because inverse links are added, some nodes will have more connections.
The distance between nodes is the hypotenuse times curvature(),
where curvature() defaults to a random number between 1.1 and 1.5."""
g = UndirectedGraph()
g.locations = {}
## Build the cities
for node in nodes:
g.locations[node] = (random.randrange(width), random.randrange(height))
## Build roads from each city to at least min_links nearest neighbors.
for i in range(min_links):
for node in nodes:
if len(g.get(node)) < min_links:
here = g.locations[node]
def distance_to_node(n):
if n is node or g.get(node,n): return infinity
return distance(g.locations[n], here)
neighbor = argmin(nodes, distance_to_node)
d = distance(g.locations[neighbor], here) * curvature()
g.connect(node, neighbor, int(d))
return g
romania = UndirectedGraph(Dict(
A=Dict(Z=75, S=140, T=118),
B=Dict(U=85, P=101, G=90, F=211),
C=Dict(D=120, R=146, P=138),
D=Dict(M=75),
E=Dict(H=86),
F=Dict(S=99),
H=Dict(U=98),
I=Dict(V=92, N=87),
L=Dict(T=111, M=70),
O=Dict(Z=71, S=151),
P=Dict(R=97),
R=Dict(S=80),
U=Dict(V=142)))
romania.locations = Dict(
A=( 91, 492), B=(400, 327), C=(253, 288), D=(165, 299),
E=(562, 293), F=(305, 449), G=(375, 270), H=(534, 350),
I=(473, 506), L=(165, 379), M=(168, 339), N=(406, 537),
O=(131, 571), P=(320, 368), R=(233, 410), S=(207, 457),
T=( 94, 410), U=(456, 350), V=(509, 444), Z=(108, 531))
australia = UndirectedGraph(Dict(
T=Dict(),
SA=Dict(WA=1, NT=1, Q=1, NSW=1, V=1),
NT=Dict(WA=1, Q=1),
NSW=Dict(Q=1, V=1)))
class GraphProblem(search.Problem):
"The problem of searching a graph from one node to another."
def __init__(self, initial, goal, graph):
search.Problem.__init__(self, initial, goal)
self.graph = graph
def succ(self, A):
"Return a list of (action, result) pairs."
return [(B, B) for B in self.graph.get(A).keys()]
def path_cost(self, cost_so_far, A, action, B):
return cost_so_far + (self.graph.get(A,B) or infinity)
def h(self, node):
"h function is straight-line distance from a node's state to goal."
locs = getattr(self.graph, 'locations')
if locs:
return int(distance(locs[node.state], locs[self.goal]))
else:
return infinity
class InstrumentedProblem(search.Problem):
"""Delegates to a problem, and keeps statistics."""
def __init__(self, problem):
self.problem = problem
self.succs = self.goal_tests = self.states = 0
self.found = None
def succ(self, state):
"Return a list of (action, state) pairs reachable from this state."
result = self.problem.succ(state)
self.succs += 1; self.states += len(result)
return result
def goal_test(self, state):
"Return true if the state is a goal. By default, compare to self.goal."
self.goal_tests += 1
result = self.problem.goal_test(state)
if result: self.found = state
return result
def __getattr__(self, attr):
if attr in ('succs', 'goal_tests', 'states'):
return self.__dict__[attr]
else:
return getattr(self.problem, attr)
def __repr__(self):
return '<%3d/%3d/%3d/%s>' % (self.succs, self.goal_tests,
self.states, str(self.found)[0:4])
def compare(problems=[GraphProblem('A', 'B', romania),
GraphProblem('O', 'N', romania)],
header=['', 'Romania(A,B)', 'Romania(O, N)'],
searchers=[search.breadth_first_tree_search,
#search.depth_first_tree_search,
search.breadth_first_graph_search,
#search.depth_first_graph_search
search.iterative_deepening_search,
search.astar_search
]):
def do(searcher, problem):
p = InstrumentedProblem(problem)
searcher(p)
return p
table = [[name(s)] + [do(s, p) for p in problems] for s in searchers]
print_table(table, header)
# Inverse Boggle
class Boggle:
"""Find all the words in a Boggle board.
Ex: b = Boggle(); b.solve(); b.solve()"""
def __init__(self, wordlist=None):
global the_wordlist
if wordlist is None:
if the_wordlist is None:
the_wordlist = Wordlist("wordlist")
wordlist = the_wordlist
self.wordlist = wordlist
self.wordlist_words = wordlist.words
self.found = {}
def solve(self, board=None):
"Find all the words in the given board (default to a random board)."
if board is None: board = BoggleBoard()
self.board = board
self.neighbors = compute_neighbors(len(board))
self.found = {}
for i in range(len(board)):
lo, hi = self.wordlist.bounds[board[i]]
self.find(lo, hi, i, [], '')
return self
def count(self):
"Return the number of words found on the last board."
return len(self.found)
def words(self):
"Return the list of words found on the last board."
return self.found.keys()
def score(self):
return sum([Boggle.scores[len(w)] for w in self.words()])
def __repr__(self):
return '<Boggle: %d words, %d points>' % (self.count(), self.score())
## private:
scores = [0, 0, 0, 1, 1, 2, 3, 5] + ([11] * 30)
def find(self, lo, hi, i, visited, sofar):
if i in visited: return
prefix, word = self.lookup(sofar, lo, hi)
if prefix:
if word: self.found[word] = 1;
visited.append(i)
c = self.board[i]
if c == 'Q': c = 'QU'
sofar += c
for j in self.neighbors[visited[-1]]:
self.find(prefix, hi, j, visited, sofar)
visited.pop()
def lookup(self, sofar, lo, hi):
p = bisect.bisect_left(self.wordlist_words, sofar, lo, hi)
if p >= len(self.wordlist_words): return None, None
elif self.wordlist_words[p] == sofar: return p, sofar
elif self.wordlist_words[p].startswith(sofar): return p, None
else: return None, None
"""'inverse boggle': search for high-scoring boggle (word game) boards.
A good domain for iterative-repair and related search tehniques, as suggested
by Justin Boyan. """
cubes16 = ['FORIXB', 'MOQABJ', 'GURILW', 'SETUPL',
'CMPDAE', 'ACITAO', 'SLCRAE', 'ROMASH',
'NODESW', 'HEFIYE', 'ONUDTK', 'TEVIGN',
'ANEDVZ', 'PINESH', 'ABILYT', 'GKYLEU']
def BoggleBoard(input=4):
"""Coerce input to a Boggle board, usually a random one.
Input can be either an existing board, a string of letters, or an integer
representing the length of the side of the board. Default is 4."""
if isinstance(input, types.ListType):
board = input
elif isinstance(input, types.StringType):
board = [c.upper() for c in input if c in string.letters]
else:
if input == 4:
cubes = cubes16
else:
cubes = [random.choice(cubes16) for i in range(input ** 2)]
random.shuffle(cubes)
board = map(random.choice, cubes)
exact_sqrt(len(board))
return board
def print_board(board):
n2 = len(board); n = exact_sqrt(n2)
for i in range(n2):
if i % n == 0: print
if board[i] == 'Q': print 'Qu',
else: print str(board[i]) + ' ',
print
def compute_neighbors(n2):
n = exact_sqrt(n2)
neighbors = [None] * n2
for i in range(n2):
neighbors[i] = []
on_top = i < n
on_bottom = i >= n2 - n
on_left = i % n == 0
on_right = (i+1) % n == 0
if not on_top:
neighbors[i].append(i - n)
if not on_left: neighbors[i].append(i - n - 1)
if not on_right: neighbors[i].append(i - n + 1)
if not on_bottom:
neighbors[i].append(i + n)
if not on_left: neighbors[i].append(i + n - 1)
if not on_right: neighbors[i].append(i + n + 1)
if not on_left: neighbors[i].append(i - 1)
if not on_right: neighbors[i].append(i + 1)
return neighbors
compute_neighbors = memoize(compute_neighbors)
def exact_sqrt(n2):
"If n2 is a perfect square, return its square root, else raise error."
n = int(math.sqrt(n2))
assert n * n == n2
return n
boyan = BoggleBoard('RSTCS DEIAE GNLRP EATES MSSID')
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
class Wordlist:
def __init__(self, filename, min_len=3):
lines = open(filename).read().upper().split()
self.words = [word.strip() for word in lines if len(word) >= min_len]
self.words.sort()
self.bounds = {}
for c in alphabet:
c2 = chr(ord(c) + 1)
self.bounds[c] = (bisect.bisect(self.words, c),
bisect.bisect(self.words, c2))
def __contains__(self, word): return bisect.bisect(self.words, word)
def __repr__(self): return '<Wordlist with %d words>' % len(self.words)
def __len__(self): return len(self.words)
the_wordlist = None ## Will hold a Wordlist loaded from a file
class BoggleProblem(search.Problem):
pass
# Just for fun, Another word game:
class Words:
def __init__(self, filename, min_len=3):
self.dicts = [{} for i in range(30)]
for word in open(filename).read().upper().split():
self.dicts[len(word)][sort(word)] = word
def lookup(self, word):
return self.dicts[len(word)].get(word)
class Words:
def __init__(self, filename, min_len=3):
self.dicts = [{} for i in range(30)]
for word in open(filename).read().upper().split():
self.dicts[len(word)][sort(word)] = word
def lookup(self, word):
return self.dicts[len(word)].get(word)
def ladders():
global the_words
try:
the_words
except NameError:
the_words = Words("wordlist")
for subdict in reverse(the_words.dicts[:]):
for (key, word) in subdict.items():
for result in ladder(key, [word]):
yield result
def ladder(key, sofar):
if len(key) == 2:
yield sofar
else:
for c in unique(key):
key_1 = key.replace(c, '', 1)
word = the_words.lookup(key_1)
if word:
sofar.append(word)
for x in ladder(key_1, sofar): yield x
sofar.pop()
#['INDETERMINATIONS', 'INTERMEDIATIONS', 'DETERMINATIONS',
# 'ANTIMODERNIST', 'TERMINATIONS', 'NITROSAMINE', 'ANTINOMIES',
# 'NOMINATES', 'MENTIONS', 'MENTION', 'INTONE', 'TONNE',
# 'NONE', 'ONE', 'ON']
# _docex = """"""
# Copyright (c) 2002,
Peter Norvig
# See also AI
Programming (Python),
Python.org
Tutorial,
Language Ref,
Libraries.