Write and run your first Turing machine.
What to build
A program that runs a bit-flipping Turing machine on each word and reports the result and the number of steps.
Requirements
- The machine moves right, flipping each bit, and halts when it reads a blank; that last move counts as a step.
- Print
result R steps S, with ε for an empty result.
Input
Line 1: n. Then n binary words (a word may be an empty line).
Output
n lines.
Constraints
n ≤ 10; words have at most 40 bits.
Example
Input:
2
0110
1
Output:
result 1001 steps 5
result 0 steps 2
Why it works
Each step handles exactly one cell, so a word of length k takes k flipping steps plus one step to read the blank.
Examples
Example 1 · Input
2 0110 1
Expected output
result 1001 steps 5 result 0 steps 2
Example 2 · Input
1 000
Expected output
result 111 steps 4
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
One working state: on 0 write 1, on 1 write 0, and move right; on a blank, halt.
Hint 2
Count every move, including the one that reads the blank and halts.
Solution
Show one correct solution (try it yourself first)
delta = {("flip", "0"): ("flip", "1", 1), ("flip", "1"): ("flip", "0", 1), ("flip", "_"): ("halt", "_", 0)}
for _ in range(int(input())):
tape = dict(enumerate(input()))
state, head, steps = "flip", 0, 0
while state != "halt":
state, write, move = delta[(state, tape.get(head, "_"))]
tape[head] = write
head += move
steps += 1
result = "".join(tape[i] for i in sorted(tape)).strip("_")
print("result", result or "ε", "steps", steps)