Skip to content

Instantly share code, notes, and snippets.

@wchargin
Created Jun 27, 2021
Embed
What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment