Loading

new-riddle.py

  1. import itertools
  2.  
  3.  
  4. def pk(*args):
  5.     print(*args)
  6.     return args[-1]
  7.  
  8.  
  9. def solve(tab, seed=None):
  10.     if seed is None:
  11.         solutions = []
  12.     else:
  13.         solutions = seed
  14.  
  15.     combinations = []
  16.     for i in range(1, len(tab) + 1):
  17.         combinations.extend(''.join(x) for x in itertools.combinations(tab, i))
  18.  
  19.     for c in combinations:
  20.         print('combination', c)
  21.     print(len(combinations))
  22.     assert len(combinations) == 2**len(tab) - 1
  23.  
  24.     for combination in combinations:
  25.         print('combination', combination)
  26.         for solution in solutions:
  27.             if any(solution.startswith(pk('p', p)) for p in (''.join(x) for x in itertools.permutations(combination))):
  28.                 pk('existing solution', solution)
  29.                 break
  30.         else:
  31.             # there is no existing solution that is "permutation prefix" of the combination
  32.             candidates = ["".join(x) for x in itertools.permutations(tab) if "".join(x) not in solutions]
  33.             for candidate in candidates:
  34.                 if any(candidate.startswith(p) for p in (''.join(x) for x in itertools.permutations(combination))):
  35.                     solutions.append(candidate)
  36.                     break
  37.             else:
  38.                 print(combination)
  39.                 assert False, "should not happen, because..."
  40.         print('solutions', solutions)
  41.     return solutions
  42.  
  43.  
  44. tab = '0123'
  45. rotations = [(tab[i:] + tab[:i]) for i in range(len(tab))]
  46. for x in solve(tab, rotations):
  47.     print(x)