import re
from collections import defaultdict

class BasicInterpreter:
    def __init__(self, program_lines):
        self.program = self.parse_program(program_lines)
        self.variables = {}
        self.visited_states = defaultdict(set)
        self.execution_trace = []

    def parse_program(self, lines):
        program = {}
        for line in lines:
            match = re.match(r'^(\d+)\s+(.*)$', line.strip())
            if match:
                line_num = int(match.group(1))
                command = match.group(2)
                program[line_num] = command
        return dict(sorted(program.items()))

    def eval_expr(self, expr):
        expr = expr.replace("true", "True").replace("false", "False")
        for var in self.variables:
            expr = expr.replace(var, str(self.variables[var]))
        return eval(expr)

    def run(self):
        line_nums = list(self.program.keys())
        pc = line_nums[0]

        while True:
            state_key = (pc, tuple(sorted(self.variables.items())))
            if state_key in self.visited_states[pc]:
                print("\n🔁 Non-halting loop detected:")
                for trace in self.execution_trace:
                    print(trace)
                print("⛔ Program does not halt.")
                return
            self.visited_states[pc].add(state_key)

            command = self.program[pc]
            self.execution_trace.append(f"{pc}: {command} | vars: {self.variables}")

            if command.startswith("set"):
                var, expr = command[4:].split("=", 1)
                var = var.strip()
                self.variables[var] = self.eval_expr(expr.strip())
            elif command.startswith("print"):
                expr = command[6:].strip()
                print(f"{pc}: PRINT {self.eval_expr(expr)}")
            elif command.startswith("goto"):
                pc = int(command[5:].strip())
                continue
            elif command.startswith("if"):
                cond, goto_part = command[3:].split("goto")
                if self.eval_expr(cond.strip()):
                    pc = int(goto_part.strip())
                    continue
            elif command == "end":
                print("✅ Program halts.")
                return

            # Move to next line
            line_nums_sorted = sorted(self.program.keys())
            idx = line_nums_sorted.index(pc)
            if idx + 1 < len(line_nums_sorted):
                pc = line_nums_sorted[idx + 1]
            else:
                print("✅ Program halts.")
                return

program1 = [
    "10 set x = 0",
    "20 if x < 2 goto 40",
    "30 end",
    "40 print x",
    "50 set x = x + 1",
    "60 goto 20"
]
BasicInterpreter(program1).run()

program2 = [
    "10 set x = 0",
    "20 print x",
    "30 set x = (x + 1) % 5",
    "40 goto 20"
]
BasicInterpreter(program2).run()