tm2.py

# coding: utf-8

###
# Small "compiler" for Turing Drawings
# https://maximecb.github.io/Turing-Drawings
#
# Syntax should be fairly obvious from looking at the given code
###

def compile_tm(source_code, colour_map = None):
    # First pass: Parse code
    lines = source_code.splitlines() 
    
    states = {}
    initial_state = ""
    state_name = ""
    symbol_count = 0
    for line in lines:
         # Skip comments, whitespace
        if len(line) == 0 or line[0] == '#':
            continue

        # First line is symbol count
        if symbol_count == 0:
            symbol_count = int(line)
            continue

        if line[0] == "+":
            state_name = line[1:]

            if state_name[-1] == '!':
                state_name = state_name[:-1]
                initial_state = state_name

            states[state_name] = {}
        else:
            symbol_in, movement, next_state, symbol_out = line.split(' ')
            
            # Special symbol x: "all unspecified inputs"
            if symbol_in == 'x':
                for s in range(symbol_count):
                    if str(s) in states[state_name]:
                        continue
                        
                    # Can also use special symbol x for output: Same as input
                    if symbol_out == 'x':
                        states[state_name][str(s)] = (next_state, str(s), movement)
                    else:
                        states[state_name][str(s)] = (next_state, symbol_out, movement)
            else:
                if symbol_out == 'x':
                    states[state_name][symbol_in] = (next_state, symbol_in, movement)
                else:
                    states[state_name][symbol_in] = (next_state, symbol_out, movement)
                
    # Enumerate states
    state_count = 0
    state_numbers = {}
    states_ordered = []

    # Store initial
    state_numbers[initial_state] = 0
    states_ordered.append(initial_state)
    state_count += 1

    # Store rest
    for state in states.keys():
        if state == initial_state:
            continue

        state_numbers[state] = state_count
        states_ordered.append(state)
        state_count += 1
        
    # Movements as numbers
    movement_dict = {
        'l': 1,
        'r': 0,
        'u': 2,
        'd': 3
    }
    
    # Generate string
    tm_commands = [str(state_count), str(symbol_count)]
    for symbol_in in range(symbol_count):
        for state in states_ordered:
            symbol_in_str = str(symbol_in)
            if colour_map != None:
                symbol_in_str = colour_map[symbol_in_str]
            
            next_state, symbol_out, movement = states[state][symbol_in_str]
            
            symbol_out_str = str(symbol_out)            
            if colour_map != None:
                symbol_out_str = colour_map[symbol_out_str]
            
            tm_commands.append(str(state_numbers[next_state]))
            tm_commands.append(symbol_out_str)
            tm_commands.append(str(movement_dict[movement[0]]))
    
    # Done
    return(",".join(tm_commands))

# Code
source_code = """
# Symbol count
4

##
# PART I: Init
##

# Starting off: Fill left line (first state marked by !)
+fill_line_left!
x down fill_line_left 3
3 right fill_line 3

# Part 2: Fill first line
+fill_line
x right fill_line 1
3 down third1_d1 3

# Then, go 3 down 1 right until you hit the line again
+third1_d1
x down third1_d2 x
1 down third2_d1 2

+third1_d2
x down third1_d3 x
1 down third2_d1 2

+third1_d3
x down third1_r x
1 down third2_d1 2

+third1_r
x right third1_d1 x
1 down third2_d1 2

# Same thing again
+third2_d1
x down third2_d2 x
1 right fill_to_2 2

+third2_d2
x down third2_d3 x
1 right fill_to_2 2

+third2_d3
x down third2_r x
1 right fill_to_2 2

+third2_r
x right third2_d1 x
1 right fill_to_2 2

# Now fill until 2 is encountered, skipping 3
+fill_to_2
x right fill_to_2 2
3 right fill_to_2 3
2 right goto_3 2

# Go to first 3 (start of line)
+goto_3
x right goto_3 x
3 up fill_last_begin 3

# Wrap to last line and fill
+fill_last_begin
x right fill_last x

+fill_last
x right fill_last 3
3 down fill_last_end 3

+fill_last_end
x down nextline x

##
# PART 2: Copy-down
##
# Having come from above, go to the first "real" pixel
+nextline
x right copy_above x

# Go up and copy pixel down
+copy_above
x up check_above x
3 right find_twister_start 3

+check_above
0 down check_above_c0 0
1 down check_above_c1 1
2 down check_above_c2 2
x right fill_line_left x

+check_above_c0
x right copy_above 0

+check_above_c1
x right copy_above 1

+check_above_c2
x right copy_above 2

##
# PART 3: Twist it
##
+find_twister_start
x right find_twister_start x
0 right find_twister_end_black 0
1 right find_twister_end_red 1

+find_twister_end_red
x right find_twister_end_red x
0 left add_red 0
2 left add_red 2

+add_red
x right finish_line 0

+find_twister_end_black
x right find_twister_end_black x
1 left add_black 1
2 left add_black 2

+add_black
x right finish_line 1

##
# Part 4: Finish frame
##
+finish_line
x right finish_line x
3 down check_end 3

# Check if right of this is 3 (last line)
+check_end
x right check_end_2 x

+check_end_2
3 down nextframe 3
x left nextline x

+nextframe
x down find_twister_start x
"""

# Make url and print
tm_string = compile_tm(source_code, colour_map = {'0': '0', '1': '2', '2': '1', '3': '3'})
base_url = "https://maximecb.github.io/Turing-Drawings/#"
print(base_url + tm_string)

def decompile_tm(input_string):
    tm_commands = input_string.split(",")
    state_count = int(tm_commands[0])
    symbol_count = int(tm_commands[1])
    
    movement_dict_reverse = {
        '0': 'right',            
        '1': 'left',
        '2': 'up',
        '3': 'down'
    }
    
    program_string = ""
    program_string = program_string + str(symbol_count) + "\n\n"
    
    for state in range(state_count):
        program_string = program_string + "+state_{:03d}".format(int(state))
        
        if state == 0:
            program_string = program_string + "!\n"
        else:
            program_string = program_string + "\n"
            
        for symbol in range(symbol_count):
            idx_start = (symbol * state_count + state) * 3 + 2
            next_state = tm_commands[idx_start]
            output_symbol = tm_commands[idx_start + 1]
            movement = movement_dict_reverse[tm_commands[idx_start + 2]]
            
            program_string = program_string + "{} {} state_{:03d} {}\n".format(
                symbol, 
                movement, 
                int(next_state), 
                output_symbol
            )
        program_string = program_string + "\n"    
    return(program_string)

tm_string = "4,3,2,2,1,3,1,1,2,1,2,1,1,2,1,2,2,1,1,3,0,2,0,1,2,3,3,1,0,3,1,0,0,1,1,0,2,2"
tm_code = decompile_tm(tm_string)
print(tm_code)

# Verify by round-trip
tm_string = compile_tm(tm_code)
print(base_url + tm_string)