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