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)