Написание интерпретатора Smallf*ck
проблема, которую я пытаюсь решить, это ката Codewars: https://www.codewars.com/kata/58678d29dbca9a68d80000d7/train/python
Я прохожу 123 из 124 тестов, но тот, который я терплю неудачу, связан с тем, как я обрабатываю вложенные циклы. Я просто не могу найти способ воспроизвести проблему, потому что они не показывают вам тестовый ввод. Любая помощь приветствуется; вот что у меня есть для проблемы до сих пор:
import re
def interpreter(code, tape):
#Filter out non-command characters
code_pure = re.findall(r"(\>|\<|\*|\[|\])", code)
sf = "".join(code_pure)
#Convert tape to list so that elements are mutable
tape_list = []
for bit in tape:
tape_list.append(bit)
#Keep track of pointer and instruction position
pointer = 0
instr = 0
brack_pos = [] #Contains positions of "[" brackets
while instr < len(sf):
#If pointer goes out of bounds then end the program
if pointer >= len(tape_list) or pointer < 0:
return "".join(tape_list)
#"*" flips the current bit
if sf[instr] == "*":
if tape_list[pointer] == "1":
tape_list[pointer] = "0"
elif tape_list[pointer] == "0":
tape_list[pointer] = "1"
instr += 1
#Move right one bit
elif sf[instr] == ">":
pointer += 1
instr += 1
#Move left one bit
elif sf[instr] == "<":
pointer -= 1
instr += 1
elif sf[instr] == "[":
#If pointer is on 0, skip the loop
if tape_list[pointer] == "0":
brack_cnt = 1
while brack_cnt != 0:
instr += 1
if sf[instr] == "[":
brack_cnt += 1
elif sf[instr] == "]":
brack_cnt -= 1
instr += 1
#If pointer is 1, step into the loop
elif tape_list[pointer] != "0":
brack_pos.append(instr)
instr += 1
elif sf[instr] == "]":
if tape_list[pointer] == "0":
instr += 1
elif tape_list[pointer] != "0":
instr = brack_pos[-1]
brack_pos.pop()
return "".join(tape_list)
Я думаю, что вижу проблему. В этом последнем блоке if, где вы проверяете sf[instr] == "]", вы никогда не удаляете соответствующую позицию «[» при переходе за «]». Таким образом, во вложенном цикле внешний цикл вместо этого вернется к этому внутреннему «[». т.е. brack_pos.pop() должно произойти в обоих случаях.
@CerealСпасибо большое! Это оказалось проблемой, теперь я прохожу все тестовые случаи. Если вы хотите опубликовать свой комментарий как фактическое решение, я с радостью отмечу его правильным. Еще раз спасибо!
@Elision Конечно, подойдет
Ответы 1
Проблема заключается в проверке последнего блока if на sf[instr] == "]", где brack_pos.pop() выполняется только при возврате к открывающей скобке, а не при перемещении за закрывающую скобку. т.е. brack_pos.pop() должен быть безусловным.
Кажется, забавное упражнение, кстати, вот что я придумал:
def interpreter(code, tape):
# Implement your interpreter here
tape = list(tape)
# Find matching brackets
jump = [0]*len(code)
open_bracket_stack = []
for i,c in enumerate(code):
if c == '[':
open_bracket_stack.append(i)
elif c == ']':
matching = open_bracket_stack.pop()
jump[i] = matching
jump[matching] = i
code_ptr = 0
tape_ptr = 0
while(code_ptr < len(code) and tape_ptr < len(tape) and tape_ptr >= 0):
c = code[code_ptr]
if c == '>':
tape_ptr += 1
elif c == '<':
tape_ptr -= 1
elif c == '*':
tape[tape_ptr] = '1' if tape[tape_ptr] == '0' else '0'
elif c == '[' and tape[tape_ptr] == '0':
code_ptr = jump[code_ptr]
elif c == ']' and tape[tape_ptr] == '1':
code_ptr = jump[code_ptr]
code_ptr += 1
return "".join(tape)
Пожалуйста, поместите часть задания (или соответствующее содержание) также в вопрос. Ссылка может не работать в будущем, но ТАК, и ваш вопрос останется там навсегда. :)