from collections import deque
class State:
def __init__(self, data=(3,3,1)):
assert self._valid(data)
self.data = data
def __hash__(self):
return hash(self.data)
def __eq__(self, other):
return self.data == other.data
def _valid(self, data):
if data[0] < 0 or data[0] > 3 or data[1] < 0 or data[1] > 3 or data[2] < 0 or data[2] > 1:
return False
if (data[0] > 0 and data[1] > data[0]) or (data[0] < 3 and data[0] > data[1]):
return False
return True
def goal(self):
return self.data[0] == 0 and self.data[1] == 0
def transitions(self):
for boat in (-1, 1):
for m, c in ((2,0), (1,0), (1,1), (0,1), (0,2)):
newdata = (self.data[0] + boat*m, self.data[1] + boat*c, self.data[2]+boat)
if self._valid(newdata):
yield State(newdata), "%d%d%s" % (m, c, "> <"[boat+1])
seen = {}
queue = deque()
initial = State()
queue.append((initial,[]))
seen[initial] = -1
while(len(queue)):
state, history = queue.popleft()
for newstate, transition in state.transitions():
if newstate.goal():
print ', '.join(history+[transition])
else:
if newstate not in seen or seen[newstate] >= len(history):
seen[newstate] = len(history)
queue.append((newstate,history+[transition]))
--
The world's dullest web page
![]](images/rt_edge3.gif){kind=small}
![[XML]](images/rssblue.gif){kind=small}
![[P]](images/print3.gif){kind=small}
