# Implementation of a 2-symbol, 5-state Turing machine.

# Could be easily modified to run any given Turing machine.

# SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.
# For more information, please refer to <https://unlicense.org/>
# SPDX-License-Identifier: Unlicense

state = '1'
head = 0
tape = {}

def read():
    global tape, head
    return tape.setdefault(head, 'B')

def write(x):
    global tape, head
    tape[head] = x

trans = {
  '1B': '21L',
  '11': '21R',
  '2B': '31L',
  '21': '31R',
  '3B': '41L',
  '31': '41R',
  '4B': '51L',
  '41': '51R',
  '5B': 'S1L',
  '51': '1BR',
}

step = 0
prev = None
rep = 1
with open('bbrep.out', 'w') as f:
    while True:
        value = read()
        r = state + value
        if prev is None:
            prev = r
            rep = 1
        elif r == prev:
            rep += 1
        else:
            f.write('%s*%d\n' % (prev, rep))
            prev = r
            rep = 1
        if state == 'S':
            break
        x = trans[r]
        state = x[0]
        write(x[1])
        dir = x[2]
        if dir == 'L':
          head -= 1
        if dir == 'R':
          head += 1
        step += 1
        #if step % 100000 == 0:
        #    print step
    f.write('%s*%d\n' % (prev, rep))

print(step)