ferryman.py (Source)

"""
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[0]} eats {couple[1]}'
                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)