Skip to content

Instantly share code, notes, and snippets.

@mitnk
Created December 23, 2012 06:56
Embed
What would you like to do?
有豹子,老虎,狮子,都一大一小,三个大的和小老虎都会划船,其他两个 不会划,每次只能过两个,大吃小(没有大的在保护就被吃掉). 这2个动物怎样才能过河? P.S. 算法还不完美,输出了多余的东东。
#encoding=utf8
"""
有豹子,老虎,狮子,都一大一小,三个大的和小老虎都会划船,其他两个
不会划,每次只能过两个,大吃小(没有大的在保护就被吃掉).
这2个动物怎样才能过河?
"""
from itertools import combinations
def is_bad(L):
if 'a' in L and 'A' not in L:
if 'B' in L or 'C' in L:
return True
if 'b' in L and 'B' not in L:
if 'A' in L or 'C' in L:
return True
if 'c' in L and 'C' not in L:
if 'A' in L or 'B' in L:
return True
return False
def get_ones(L):
assert('o' in L)
result = []
for item in L:
if item == 'o':
continue
if cannot_boat(item):
continue
TMP = L[:]
TMP.remove(item)
if is_bad(TMP):
continue
result.append(item)
return result
def cannot_boat(a):
return a in ('b', 'c')
def get_twos(L):
assert('o' in L)
LL = L[:]
LL.remove('o')
LL = [x for x in combinations(LL, 2)]
result = []
for x, y in LL:
TMP = L[:]
TMP.remove('o')
TMP.remove(x)
TMP.remove(y)
if is_bad(TMP):
continue
if cannot_boat(x) and cannot_boat(y):
continue
result.append((x, y))
return result
def get_key(Left, Right):
L, R = Left[:], Right[:]
L.sort()
R.sort()
key = "%s|%s" % (''.join(L), ''.join(R))
return key
def start():
Left, Right = ['A', 'B', 'C', 'a', 'b', 'c', 'o'], []
solutions = []
result = []
D = {}
flag = False
while 1:
if Left == []:
# All animals on the other side
break
Current = Left if 'o' in Left else Right
if not flag:
for one in get_ones(Current):
solutions.append((one, Left[:], Right[:]))
for two in get_twos(Current):
solutions.append((two, Left[:], Right[:]))
boat, Left, Right = solutions.pop()
flag = False
key = get_key(Left, Right)
D[key] = 1
result.append((boat, Left[:], Right[:]))
Left, Right, eaten = move_to_another_side(boat, Left, Right)
key = get_key(Left, Right)
if eaten or key in D:
result.pop()
flag = True
for boat, X, Y in result:
if len(boat) == 2:
boat = ''.join(boat)
print '%8s' % ''.join(X),
if 'o' in X:
s = "|| (%2s) --> ||" % boat
else:
s = "|| <-- (%2s) ||" % boat
print '%18s' % s,
print '%8s' % ''.join(Y), '\n'
def move_to_another_side(boat, Left, Right):
Current, OtherSide = Left, Right
if 'o' not in Current:
Current, OtherSide = OtherSide, Current
if not isinstance(boat, (list, tuple)):
boat = [boat]
OtherSide.append('o')
for x in boat:
OtherSide.append(x)
for x in boat:
Current.remove(x)
Current.remove('o')
eaten = is_bad(Left) or is_bad(Right)
Left.sort()
Right.sort()
return Left, Right, eaten
if __name__ == "__main__":
start()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment