# ferryman.py (Source)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80``` ```""" Drawing the Ferryman problem using graphviz. I experimented a bit with using global variables instead of passing them through functions to reduce lines of code. Very confusing :) """ from graphviz import Digraph from collections import namedtuple ILLEGAL_COUPLES = [('W','S'),['S','K']] dot = Digraph(comment='The Ferryman Problem', format="png", engine="dot") visited = set() stack = list() stack.append(('FKSW', '', '')) def add_edge(next_state): dot.edge(str(current_state), str(next_state)) stack.append(next_state) def check_for_end(): if right_bank == "FKSW": dot.edge(str(current_state), "Win") return True for bank in [left_bank, right_bank]: if 'F' in bank: continue for couple in ILLEGAL_COUPLES: if all(map(lambda s: s in bank, couple)): reason = f'{couple} eats {couple}' dot.edge(str(current_state), "Lose", label=reason) return True return False def next_states_from_bank(bank): if not 'F' in bank: return new_bank = bank.replace("F", "") # Ferryman moves alone without passenger. yield new_bank, "F" # Ferryman moves with passenger for t in new_bank: yield new_bank.replace(t, ""), f'F{t}' order = lambda s: "".join(sorted(s)) dot.node('Lose', 'Lose') # Simple BFS :) while stack: current_state = stack.pop() if current_state in visited: continue dot.node(str(current_state), str(current_state)) visited.add(current_state) print() print(current_state) left_bank, ferry, right_bank = current_state print(current_state) if check_for_end(): print("end") continue if 'F' in ferry: new_states = [(order(left_bank + ferry), "", right_bank), (left_bank, "", order(ferry + right_bank))] else: new_states = [(new_bank, new_ferry, right_bank) for (new_bank, new_ferry) in next_states_from_bank(left_bank)] new_states += [(left_bank, new_ferry, new_bank) for (new_bank, new_ferry) in next_states_from_bank(right_bank)] list(map(add_edge, new_states)) dot.render('output/ferryman.gv', view=True) ```