Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# samorajp/misjonarze.py

Created Feb 27, 2016
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)
to join this conversation on GitHub. Already have an account? Sign in to comment