Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Program rozwiązujący zagadkę o misjonarzach i kanibalach dla ich dowolnej liczby oraz dowolnej pojemności łódki.
def mutations(state, boat_size):
m_left, k_left, boat, m_right, k_right = state
sign, other_side = (-1, "R") if boat == "L" else (1, "L")
naive_mutations = [
(m_left + sign * m_diff, k_left + sign * k_diff,
other_side,
m_right - sign * m_diff, k_right - sign * k_diff)
for m_diff in range(boat_size + 1)
for k_diff in range(boat_size + 1)
if 1 <= m_diff + k_diff <= boat_size
if m_diff >= k_diff or m_diff == 0
]
return filter(lambda (a, b, _, x, y): (b >= a == 0 or a >= b >= 0) and
(y >= x == 0 or x >= y >= 0),
naive_mutations)
def main(missionaries, cannibals, boat_size):
start_state = (missionaries, cannibals, "L", 0, 0)
final_state = (0, 0, "R", missionaries, cannibals)
states = {start_state}
ancestors = {start_state: None}
while True:
new_states = set(
(new_state, state)
for state in states
for new_state in mutations(state, boat_size)
if new_state not in states
)
if new_states:
for new_state, ancestor in new_states:
ancestors[new_state] = ancestor
states.add(new_state)
else:
break
current = final_state
solution = [current]
while ancestors.get(current):
solution.append(ancestors[current])
current = ancestors[current]
return solution[::-1]
if __name__ == "__main__":
def draw_state(state_to_draw):
ml, kl, boat, mr, kr = state_to_draw
left = " ".join(["M"] * ml + ["K"] * kl)
right = " ".join(["M"] * mr + ["K"] * kr)
print '{:12s} | {}'.format(left, right)
solution_path = main(missionaries=3, cannibals=3, boat_size=2)
for solution_state in solution_path:
draw_state(solution_state)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment