pebbles.py

def multiset(components):
    return tuple(sorted(components))

START = multiset([3, 5, 7])

def next_states(state):
    result = set()
    for i in range(len(state)):
        if state[i] == 0:
            continue
        next_state = list(state)
        for j in range(next_state[i]):
            next_state[i] = j
            if set(next_state) != {0}:
                result.add(multiset(next_state))
    return frozenset(result)

def transitions(start):
    result = {}
    frontier = {start}
    while frontier:
        new_frontier = set()
        for s in frontier:
            result[s] = next_states(s)
            new_frontier.update(result[s])
        new_frontier -= set(result)
        frontier = new_frontier
    return result

def solve(trans):
    values = {}
    # omega brute force
    while len(values) < len(trans):
        for (s, ss) in trans.items():
            next_values = {values.get(k) for k in ss}
            if not all(v is not None for v in next_values):
                continue
            values[s] = -1 if (not next_values or min(next_values) == 1) else 1
    return values

def graph(start):
    trans = transitions(start)
    values = solve(trans)
    print("digraph {")
    nodename = lambda st: "st_" + "_".join(str(s) for s in st)
    for (st, value) in values.items():
        print("%s [label=\"%s\", shape=box, style=filled, fillcolor=\"%s\"];" % (nodename(st), str(st), "#99ff99" if value > 0 else "#ffcccc" if value < 0 else "#9999ff"))
    for (a, bs) in trans.items():
        for b in bs:
            (va, vb) = (values[a], values[b])
            color = "black" if va > 0 and vb < 0 else "#00000033"
            print("%s -> %s [color=\"%s\"];" % (nodename(a), nodename(b), color))
    print("}")

if __name__ == "__main__":
    graph(START)