KyungHyun Lim

ML/AI/SW Developer

BAEK3954 Brainf**k 인터프리터 (Python)

Oct 22, 2021

Algorithm

1. 문제 설명

문제 링크

Brainfk 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오. 무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다. Brainfk 인터프리터는 정수를 담는 하나의 배열(unsigned 8-bit 정수)과, 그 배열의 칸 하나를 가리키는 포인터로 이루어져 있다. Brainfk 프로그램은 다음과 같이 8개의 명령어로 이루어져 있다.
각 테스트 케이스에 대해서, 프로그램이 종료된다면 “Terminates”를, 무한 루프에 빠지게 된다면 “Loops”를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([와 ]의 위치) 프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

조건
첫째 줄에 테스트 케이스의 개수 t (0 < t ≤ 20)가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 sm, sc, si가 주어진다. sm은 메모리(배열)의 크기이고, sc는 프로그램 코드의 크기, si는 입력의 크기이다. (0 < sm ≤ 100,000, 0 < sc, si < 4096)
둘째 줄에는 Brainf**k 프로그램이 주어진다. 프로그램은 sc개의 문자로 이루어져 있다.
셋째 줄에는 프로그램의 입력이 주어진다. (공백이 아니면서 출력할 수 있는 문자만 주어진다)

2. 풀이

처음에는 동일한 명령어에 동일한 값으로 다시 실행하면 무한루프가 발생하지 않을까? 생각했다. 그래서 visited를 이용해서 명령어당 256가지 리스트를 만들어줘서 방문 표시를 해 풀이를 해보았다. 하지만 곧, 같은 값으로 동일한 령어에 도달해도 무한루프가 아닐 수 있다는 것을 알 수 있었다.
일단은 명령어별로 깔끔하게 구현하는 것을 목표로 삼았다.
알고리즘은 단순하게 50,000,000 번을 수행한 후에도 프로그램이 종료되지 않았으면 무한루프에 빠져있다고 가정한다!

3. 코드

python

def make_roop_pair(instructions):
    dictionary = {}
    temps = []
    for idx, ins in enumerate(instructions):
        if ins == '[':
            temps.append(idx)
        elif ins == ']':
            post_index = temps.pop()
            dictionary[idx] = post_index
            dictionary[post_index] = idx

    return dictionary

def minus_operation(array, array_pointer):
    array[array_pointer] = (array[array_pointer] - 1) % 256

def plus_operation(array, array_pointer):
    array[array_pointer] =  (array[array_pointer] + 1) % 256
    
def move_array_pointer(array_pointer, sm, dir):
    if dir == 'left':
        array_pointer = (array_pointer - 1) % sm
    elif dir == 'right':
        array_pointer = (array_pointer + 1) % sm
    return array_pointer

def insert_character(characters, character_pointer, array, array_pointer):
    if character_pointer >= len(characters):
        array[array_pointer] = 255
    else:
        array[array_pointer] = ord(characters[character_pointer])
    character_pointer += 1
    return character_pointer

def instruction_jump(type, instruction_pointer, array, array_pointer, loop_stack, loop_dict, visited):
    visited[instruction_pointer] = True
    if type == '[':
        if array[array_pointer] == 0:
            instruction_pointer = loop_dict[instruction_pointer]
        else:
            loop_stack.append(instruction_pointer)
    elif type == ']':
        if array[array_pointer] != 0:
            instruction_pointer = loop_dict[instruction_pointer]
        else:
            loop_stack.pop()
    return instruction_pointer
    
# 50000만번을 돌려서 빠져나오지 못한 가장 바깥 괄호
def run(sm, array, instructions, characters, loop_dict):
    visited = [False]*len(instructions)
    loop_stack = []
    array_pointer = 0   # 배열을 가르키는 포인터
    character_pointer = 0 # 입력 문자를 가르키는 포인터
    instruction_pointer = 0
    instruction_count = 0
    closed = 0

    # 명령어 실행
    while True:
        if instruction_count >= 50000000: 
            break
        if instruction_pointer >= len(instructions):
            break 

        if instructions[instruction_pointer] == '-': minus_operation(array, array_pointer)
        elif instructions[instruction_pointer] == '+': plus_operation(array, array_pointer)
        elif instructions[instruction_pointer] == '<': array_pointer = move_array_pointer(array_pointer, sm, 'left')
        elif instructions[instruction_pointer] == '>': array_pointer = move_array_pointer(array_pointer, sm, 'right')
        elif instructions[instruction_pointer] == ',': character_pointer = insert_character(characters, character_pointer, array, array_pointer)
        elif instructions[instruction_pointer] in ['[', ']']: 
            if instructions[instruction_pointer] == ']':
                closed = max(closed, instruction_pointer)
            instruction_pointer = instruction_jump(instructions[instruction_pointer], instruction_pointer, array, array_pointer, loop_stack, loop_dict, visited)
                   
        instruction_pointer += 1
        instruction_count += 1
        
    if instruction_pointer == len(instructions):
        return [True]
    else:
        return [False, loop_dict[closed], closed]
    # if instruction_count >= 50000000 and loop_stack:    
    #     if visited[loop_stack[0]] and visited[loop_dict[loop_stack[0]]]:
    #         return [False, loop_stack[0], loop_dict[loop_stack[0]]]
    #     else:
    #         return [False, loop_stack[-1], loop_dict[loop_stack[-1]]]
    # else:
    #     return [True]

if __name__=='__main__':
    answers = []

    # 0. 테스트 개수
    Tc = int(input())
    
    for i in range(Tc):
        # 1. 입력받기
        sm, sc, si = map(int, input().split())
        array = [0 for _ in range(sm)]
        instructions = input()
        characters = input()

        # 2. loop pair 만들기
        loop_dict = make_roop_pair(instructions)

        # 3. 테스트 수행
        results = run(sm, array, instructions, characters, loop_dict)

        if results[0]:
            answers.append('Terminates')
        else:
            answers.append(f'Loops {results[1]} {results[2]}')

    for answer in answers:
        print(answer)