import os
import doctest
import sys
if '.' not in sys.path:
sys.path.insert(0, '.')
from search import search
# NO OTHER IMPORTS!
##################################################
# Problem 1
##################################################
def foo(L):
# keep seen and seenagain as sets, rather than keeping as lists and
# converting back and forth
seen = set()
seenagain = set()
for i in L:
if i not in seen:
seen.add(i)
elif i not in seenagain:
seenagain.add(i)
# the extra check for whether something already appears in the output is
# redundant, since any repeats would be in seenagain
return [i for i in L if i not in seenagain]
# importantly, we could do other things here (keeping a dictionary of counts,
# for example, and filtering based on that), but the above represents a fairly
# minimal change to the code with a really big speedup.
##################################################
# Problem 2
##################################################
def get_islands(graph):
# make a new graph that has both directions explicitly represented (not
# necessary, but simplifies things a lot)
newgraph = {}
for g in graph:
newgraph.setdefault(g, set()).update(graph[g])
for v in graph[g]:
newgraph.setdefault(v, set()).add(g)
# helper function to run a DFS to find all nodes that can be reached from a
# starting location n (BFS would also work)
def all_connected(n):
visited = {n}
agenda = [n]
while agenda:
next_ = agenda.pop()
for c in newgraph[next_]:
if c not in visited:
visited.add(c)
agenda.append(c)
return visited
# nodes whose islands have not been found yet (initialized to all nodes)
remaining_nodes = set(newgraph)
# all of the islands we've found so far
islands = []
while remaining_nodes:
# pick a random node and find its island, then remove those nodes from
# our agenda. keep repeating that process until every node has been
# considered.
next_island = all_connected(remaining_nodes.pop())
islands.append(next_island)
remaining_nodes -= next_island
return islands
##################################################
# Problem 3
##################################################
def setup_cats_and_dogs(cats, dogs):
# importantly, our state representation needs to store a few pieces of
# information; if we don't have all of this in our state representation,
# the problem can't be solved by the search function as written:
#
# * how many cats and dogs on each bank
# * which side of the river is Pat on
#
# our state representation also needs to be hashable because of the details
# of the search implementation (which stores states in a visited set)
#
# there are multiple different ways we could represent each of these. two
# implementations follow. in the first solution, we use strings of 'c' and
# 'd' characters to represent how many cats and dogs are on each side of
# the river, and a boolean to indicate whether Pat is on the east side of
# the river or not.
start_state = ('c'*cats + 'd'*dogs, '', False)
def successors(state):
this, other, east = state
# here, "this" refers to the animals on the same side as pat, and
# "other" refers to the animals on the opposite side, regardless of
# where pat is.
out = []
possibilities = 'd', 'c', 'dd', 'cc', 'cd'
for p in possibilities:
if p not in this:
# if the move we want to make is not a substring of the animals
# on this side of the river, there aren't enough cats and/or
# dogs here to perform that move, so skip it
continue
# compute the new animals on this side (by removing animals) and
# the other side (by adding them)
new_this = this.replace(p, '', 1)
new_other = ''.join(sorted(other + p))
if not _safe(new_this):
# if the resulting combination of animals is not safe (see
# helper function below), skip it
continue
# add the new state (note that we switch which side pat is on, and
# also swap the order of the animal sets (since pat moved, "this"
# -> "other" and "other" -> "this"
out.append((new_other, new_this, not east))
return out
def _safe(bank):
if 'c' not in bank:
return True
if 'd' not in bank:
return True
return abs(bank.count('c') - bank.count('d')) < 2
def goal_test(state):
# check that pat is on the proper side of the river (state[2] is True
# in this case), and that no animals are on the opposite bank
return (not state[1]) and state[2]
return successors, start_state, goal_test
def interpret_result(path):
if path is None:
return None
out = []
# for each pair of adjacent states in the path, determine how many cats and
# dogs moved, and add an appropriate string to our output.
for i, j in zip(path, path[1:]):
out.append(abs(i[0].count('c') - j[1].count('c'))*'c' + abs(i[0].count('d') - j[1].count('d'))*'d')
return out
def cats_and_dogs(cats, dogs):
result = search(*setup_cats_and_dogs(cats, dogs))
return interpret_result(result)
##################################################
# Problem 3 Alternative Implementation
##################################################
def setup_cats_and_dogs(cats, dogs):
# here we store tuples of integers for the numbers of animals on each side
# of the river, something like:
# ((cats_left, dogs_left), (cats_right, dogs_right), pat_side)
start_state = ((cats, dogs), (0, 0), 0)
def successors(state):
out = []
# all possible actions we could take (combinations of animals we could
# take across the river)
possibilities = (0, 1), (1, 0), (1, 1), (0, 2), (2, 0)
pat = state[-1]
cats_with_p, dogs_with_p = state[pat]
cats_other, dogs_other = state[not pat]
for (d_cats, d_dogs) in possibilities:
if d_cats > cats_with_p or d_dogs > dogs_with_p:
# there aren't enough cats and/or dogs here to perform this
# move, so skip it
continue
new_cats_other = cats_with_p - d_cats
new_dogs_other = dogs_with_p - d_dogs
new_cats_with_p = cats_other + d_cats
new_dogs_with_p = dogs_other + d_dogs
if (new_cats_other
and new_dogs_other
and abs(new_cats_other - new_dogs_other) >= 2):
continue
if pat:
new_state = (
(new_cats_with_p, new_dogs_with_p),
(new_cats_other, new_dogs_other),
not pat
)
else:
new_state = (
(new_cats_other, new_dogs_other),
(new_cats_with_p, new_dogs_with_p),
not pat
)
out.append(new_state)
return out
def goal_test(state):
# check that pat is on the proper side of the river (state[2] is True
# in this case), and that no animals are on the opposite bank
return state[2] and set(state[0]) == {0}
return successors, start_state, goal_test
def interpret_result(path):
if path is None:
return None
out = []
for i, j in zip(path, path[1:]):
cl, dl = i[0]
cln, dln = j[0]
out.append('c'*abs(cln-cl) + 'd'*abs(dln-dl))
return out
def cats_and_dogs(cats, dogs):
result = search(*setup_cats_and_dogs(cats, dogs))
return interpret_result(result)
if __name__ == '__main__':
doctest.testmod()