54 lines
1.3 KiB
Python
54 lines
1.3 KiB
Python
from collections import deque
|
|
|
|
initial = ". . . "
|
|
|
|
transitions = [
|
|
'S SSS ',
|
|
' SS S ',
|
|
' S S ',
|
|
'S SSS ',
|
|
'S S S',
|
|
' S S ',
|
|
' S SS',
|
|
'S S S',
|
|
]
|
|
|
|
def toggle(c: str) -> str:
|
|
return ' ' if c == '.' else '.'
|
|
|
|
def apply(state: str, transition: str) -> str:
|
|
return ''.join(toggle(c) if t=='S' else c for c, t in zip(state, transition))
|
|
|
|
|
|
|
|
print(apply(initial, transitions[0]))
|
|
|
|
def bfs(start, neighbours_fn, is_finished):
|
|
source = {start: None}
|
|
q = deque([start])
|
|
while q:
|
|
s = q.popleft()
|
|
if is_finished(s):
|
|
steps = [s]
|
|
parent = source[s]
|
|
while parent is not None:
|
|
steps.append(parent)
|
|
parent = source[parent]
|
|
steps = steps[::-1]
|
|
for i in range(len(steps)-1):
|
|
steps[i] = steps[i] + f' {neighbours_fn(steps[i]).index(steps[i+1])}'
|
|
return steps
|
|
for neigh in neighbours_fn(s):
|
|
if neigh in source:
|
|
continue
|
|
source[neigh] = s
|
|
q.append(neigh)
|
|
raise ValueError('impossible')
|
|
|
|
print('\n'.join(bfs(
|
|
initial,
|
|
lambda s: [apply(s, t) for t in transitions],
|
|
lambda s: s==' '
|
|
# lambda s: s==' . '
|
|
)))
|