Theory: A machine that flips bits

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)

Lesson: Turing machines →