Spinning switches

switches.py

#!/usr/bin/python3

# https://github.com/shainer/spinning-switches citing a problem from
# “So you think you've got problems?” by Alex Bellos.
# This is optimizing for minimum number of operations in the worst case.

def allrot(x):
  return [((x << i) | (x >> (4 - i))) & 0b1111 for i in range(4)]

def normal(x):
  return min(allrot(x))

def apply(s, a):
  return frozenset(normal(a ^ j)
                   for i in s for j in allrot(i)
                   if (a ^ j) != win)

def format_set(s):
  return ", ".join("{:04b}".format(i) for i in sorted(s))

initial = frozenset(normal(i) for i in range(15))
actions = frozenset(normal(i) for i in range(1, 16))
win = 0b1111
emptyset = frozenset([])

src = set([initial])
seen = {initial: (0, [])}
depth = 0
while emptyset not in src:
  depth += 1
  dst = set()
  for a in actions:
    for s in src:
      d = apply(s, a)
      prev = seen.setdefault(d, (depth, []))
      if prev[0] == depth:
        prev[1].append((s,a))
        dst.add(d)
  src = dst

print("Need {} actions in the worst case.".format(depth))

def paths(x):
  _, sa = seen[x]
  if not sa:
    return [()]
  res = []
  for s, a in sa:
    res.extend(r + (a,) for r in paths(s))
  return res

for p in paths(emptyset):
  print("")
  print(", ".join("{:04b}".format(a) for a in p))
  s = initial
  print("       initial state {}".format(format_set(s)))
  for a in p:
    s = apply(s, a)
    print("action {:04b} => state {}".format(a, format_set(s)))

switches.txt

1111, 0101, 1111, 0011, 1111, 0101, 1111, 0001, 1111, 0101, 1111, 0011, 1111, 0101, 1111
       initial state 0000, 0001, 0011, 0101, 0111
action 1111 => state 0001, 0011, 0101, 0111
action 0101 => state 0000, 0001, 0011, 0111
action 1111 => state 0001, 0011, 0111
action 0011 => state 0000, 0001, 0101, 0111
action 1111 => state 0001, 0101, 0111
action 0101 => state 0000, 0001, 0111
action 1111 => state 0001, 0111
action 0001 => state 0000, 0011, 0101
action 1111 => state 0011, 0101
action 0101 => state 0000, 0011
action 1111 => state 0011
action 0011 => state 0000, 0101
action 1111 => state 0101
action 0101 => state 0000
action 1111 => state 

1111, 0101, 1111, 0011, 1111, 0101, 1111, 0111, 1111, 0101, 1111, 0011, 1111, 0101, 1111
       initial state 0000, 0001, 0011, 0101, 0111
action 1111 => state 0001, 0011, 0101, 0111
action 0101 => state 0000, 0001, 0011, 0111
action 1111 => state 0001, 0011, 0111
action 0011 => state 0000, 0001, 0101, 0111
action 1111 => state 0001, 0101, 0111
action 0101 => state 0000, 0001, 0111
action 1111 => state 0001, 0111
action 0111 => state 0000, 0011, 0101
action 1111 => state 0011, 0101
action 0101 => state 0000, 0011
action 1111 => state 0011
action 0011 => state 0000, 0101
action 1111 => state 0101
action 0101 => state 0000
action 1111 => state 

switches2.py

#!/usr/bin/python3

# https://github.com/shainer/spinning-switches citing a problem from
# “So you think you've got problems?” by Alex Bellos.
# This is optimizing for minimum number of operations in the worst case.
#
# Compared to switches.py this caters for larger number of switches, and
# generates graphviz dot files for the result.

emptyset = frozenset([])

class Instance:

  def __init__(self, n):
    self.n = n
    self.fmt = "{{:0{}b}}".format(n).format
    self.win = (1 << n) - 1
    self.initial = frozenset(self.normal(i) for i in range(self.win))
    self.actions = frozenset(self.normal(i) for i in range(1, self.win + 1))
    self.seen = None

  def allrot(self, x):
    return [((x << i) | (x >> (self.n - i))) & self.win for i in range(self.n)]

  def normal(self, x):
    return min(self.allrot(x))

  def apply(self, s, a):
    return frozenset(self.normal(a ^ j)
                     for i in s for j in self.allrot(i)
                     if (a ^ j) != self.win)

  def format_set(self, s, sep=", "):
    return sep.join(self.fmt(i) for i in sorted(s))


  def min_worst_case(self):
    src = set([self.initial])
    seen = {self.initial: (0, [])}
    depth = 0
    while src and emptyset not in src:
      depth += 1
      dst = set()
      for a in self.actions:
        for s in src:
          d = self.apply(s, a)
          prev = seen.setdefault(d, (depth, []))
          if prev[0] == depth:
            prev[1].append((s,a))
            dst.add(d)
      src = dst
    if not src:
      raise Exception("Did not reach a solution for n={}".format(self.n))
    self.seen = seen
    print("With {} switches we need {} actions in the worst case.".format(
        self.n, depth))

  def paths(self, x):
    _, sa = self.seen[x]
    if not sa:
      return [()]
    res = []
    for s, a in sa:
      res.extend(r + (a,) for r in self.paths(s))
    return res

  def print_res(self):
    for p in self.paths(emptyset):
      print("")
      print(", ".join(self.fmt(a) for a in p))
      s = self.initial
      print("   {}initial state {}".format(" " * self.n, self.format_set(s)))
      for a in p:
        s = self.apply(s, a)
        print("action {} => state {}".format(self.fmt(a), self.format_set(s)))
    print("")

  def write_dot(self):
    useful = set()
    level = set([emptyset])
    while level:
      useful.update(level)
      level = set(s for x in level for s, a in self.seen[x][1])
    inorder = sorted(useful, key=self.format_set)
    nodename = {}
    num_edges = 0
    fn = "switches{}.dot".format(self.n)
    with open(fn, "wt") as f:
      f.write("digraph {\n")
      for i, s in enumerate(inorder):
        name = "n{:04d}".format(i)
        nodename[s] = name
        f.write('  {} [label="{}"]\n'.format(
            name, self.format_set(s, "\\n") if s else "DONE"))
      for x in inorder:
        in_edges = {}
        for s, a in self.seen[x][1]:
          in_edges.setdefault(s, set()).add(a)
        for s in sorted(in_edges, key=self.format_set):
          f.write('  {} -> {} [label="{}"]\n'.format(
              nodename[s], nodename[x], self.format_set(in_edges[s], "\\n")))
          num_edges += 1
      f.write("}\n")
    print("Graph with {} nodes and {} edges written to {}".format(
        len(inorder), num_edges, fn))
    print("")


for n in range(1, 10):
  inst = Instance(n)
  try:
    inst.min_worst_case()
  except:
    print("No solution with {} switches".format(n))
    print("")
    continue
  if n < 8:
    inst.print_res()
  inst.write_dot()

switches4.svg

switches8.svg