import sys from typing import List import math from fractions import Fraction class PrimeSource: def __init__(self): self.size = 32 self.primes = list(PrimeSource.primes_sieve2(self.size)) def enlarge(self): self.size *= 2 # print(f'growing to {self.size}') self.primes = list(PrimeSource.primes_sieve2(self.size)) def decompose(self, innumber: int): if innumber == 0: return [] result = [] number = innumber prime_idx = -1 while True: if prime_idx+1 >= len(self.primes): self.enlarge() prime_idx += 1 result.append(0) current_prime = self.primes[prime_idx] while number % current_prime == 0: number = number // current_prime result[prime_idx] += 1 # print(number, result) if number == 1: return result def primes_sieve2(limit): a = [True] * limit # Initialize the primality list a[0] = a[1] = False for (i, isprime) in enumerate(a): if isprime: yield i for n in range(i*i, limit, i): # Mark factors non-prime a[n] = False ps = PrimeSource() DEBUG_MODES = { "SHOW_STACK": False, "SHOW_CONSTANTS": False, "SHOW_SUBROUTINE_TRANSITIONS": False, "SHOW_COMMANDS": False, "SHOW_STACK_OPERATIONS": False, "SHOW_SUBROUTINE_STACK": False } class Command: def __init__(self, command: List[int]): self.command = command class Subroutine: subidx = 0 def __init__(self, definition: List[Command]): self.savedidx = Subroutine.subidx Subroutine.subidx += 1 self.definition = definition def __repr__(self) -> str: return f"Subroutine {self.savedidx} (len={len(self.definition)})" class Machine: def __init__(self): self.constants = [] self.stack = [] self.subroutine_stack = [] def process_next_command(self, command: List[int]): match command: # PUTTING case [1, 1]: # PUT_INT 0 self.push(0) case [1, 1, *ints]: # PUT_INT self.push(math.prod(ints)) case [1, 2, *ints]: # PUT_STRING self.push(Machine.make_string(ints)) case [1, 3, quot, denom]: # PUT_FRACT self.push(Fraction(quot, denom)) case [1, 4, *ints]: # PUT_COMMAND self.push(Command(ints)) # COMPOSITE_OBJECTS case [2, 1, length]: # COMBINE_INTO_ARRAY arr = [] for _ in range(length): arr.append(self.pop()) self.push(arr) case [2, 2, length]: # COMBINE_INTO_SUBROUTINE arr = [] for _ in range(length): arr.append(self.pop()) self.push(Subroutine(arr)) case [2, 3]: # UNCOMBINE_ARRAY arr = self.pop() for elem in arr: self.push(elem) self.push(len(arr)) case [2, 4]: # UNCOMBINE_SUBROUTINE sub = self.pop() for elem in sub.definition: self.push(elem) self.push(len(sub.definition)) # SUBROUTINES AND COMMANDS case [3, 1]: # INVOKE unconditional sub = self.pop() self.run_subroutine(sub) case [3, 1, condition]: # INVOKE sub = self.pop() match condition: case 0: # unconditional (for wimp mode) self.run_subroutine(sub) case 1: # if zero behind if self.stack[-1] == 0: self.run_subroutine(sub) case 2: # if zero behind, popping behind = self.pop() if behind == 0: self.run_subroutine(sub) case 3: # if less than zero if self.stack[-1] < 0: self.run_subroutine(sub) case 4: # if less than zero, popping behind = self.pop() if behind < 0: self.run_subroutine(sub) case 5: #if more than zero if self.stack[-1] > 0: self.run_subroutine(sub) case 6: #if more than zero, popping behind = self.pop() if behind > 0: self.run_subroutine(sub) case [3, 2]: # RETURN unconditional return [] case [3, 2, condition]: # RETURN match condition: case 0: # unconditional (for wimp mode) return [] case 1: # if zero behind if self.stack[-1] == 0: return [] case 2: # if zero behind, popping behind = self.pop() if behind == 0: return [] case 3: # if less than zero if self.stack[-1] < 0: return [] case 4: # if less than zero, popping if self.pop() < 0: return [] case 5: # if more than zero if self.stack[-1] > 0: return [] case 6: # if more than zero, popping if self.pop() > 0: return [] case [3, 3, condition, *atoms]: # RETURN_THEN_DO match condition: case 0: # unconditional return atoms case 1: # if zero behind if self.stack[-1] == 0: return atoms case 2: # if zero behind, popping behind = self.pop() if behind == 0: return atoms case 3: # if less than zero if self.stack[-1] < 0: return atoms case 4: # if less than zero, popping if self.pop() < 0: return atoms case 5: # if more than zero, popping if self.stack[-1] > 0: return atoms case 6: # if more than zero, popping if self.pop() > 0: return atoms case [3, 4]: # PUSH_CURRENT_SUBROUTINE self.push(self.subroutine_stack[-1]) case [3, 5]: # RUN_COMMAND command = self.pop() self.run_code_sequence([command.command]) # CONSTANT_LIST case [4, 1]: # PUSH_CONSTANT_LIST self.constants.append(self.pop()) if DEBUG_MODES['SHOW_CONSTANTS']: print(f"CONSTANT_PUSH: {self.constants[-1]}") self.push(len(self.constants) - 1) case [4, 2]: # BRING_CONSTANT 0 if DEBUG_MODES['SHOW_CONSTANTS']: print(f"BRING_CONSTANT 0") self.push(self.constants[0]) case [4, 2, idx]: # BRING_CONSTANT if DEBUG_MODES['SHOW_CONSTANTS']: print(f"BRING_CONSTANT {idx}") self.push(self.constants[idx]) case [4, 3]: # INVOKE_CONSTANT 0 if DEBUG_MODES['SHOW_CONSTANTS']: print(f"INVOKE_CONSTANT 0") self.run_subroutine(self.constants[0]) case [4, 3, idx]: # INVOKE_CONSTANT if DEBUG_MODES['SHOW_CONSTANTS']: print(f"INVOKE_CONSTANT {idx}") self.run_subroutine(self.constants[idx]) # IO case [5, 1]: # PRINT print(self.pop()) case [5, 2]: # INPUT self.push(input()) case [5, 3]: # INPUT_WITH_PROMPT prompt = self.pop() self.push(input(prompt)) case [5, 4]: # PRINT_NO_NEWLINE print(self.pop(), end="") # STACK_MANIP case [6, 1]: # DUPE self.push(self.stack[-1]) case [6, 2]: # SWAP a = self.pop() b = self.pop() if DEBUG_MODES['SHOW_STACK_OPERATIONS']: print(f"SWAP: {a} <-> {b}") self.push(a) self.push(b) case [6, 3]: # POP self.pop() case [6, 4, depth]: # ROT if DEBUG_MODES['SHOW_STACK_OPERATIONS']: print(f"ROTATE: {depth}") arr = [] for _ in range(depth): arr.append(self.pop()) arr = arr[depth:] + arr[:depth] for el in arr: self.push(el) case [6, 5]: # STACK_SIZE self.push(len(self.stack)) # MATH case [7, 1]: # INC self.stack[-1] += 1 case [7, 2]: # DEC self.stack[-1] -= 1 case [7, 3]: # ADD a = self.pop() b = self.pop() self.push(b + a) case [7, 4]: # SUB a = self.pop() b = self.pop() self.push(b - a) case [7, 5]: # MULT a = self.pop() b = self.pop() self.push(b * a) case [7, 6]: # DIV a = self.pop() b = self.pop() self.push(b // a) # CONV case [8, 1]: # TO_INT pre = self.pop() self.push(int(pre)) case [8, 2]: # TO_STR pre = self.pop() self.push(str(pre)) case [8, 3]: # CODEPOINTS_TO_STR pre = self.pop() self.push(''.join([chr(i) for i in pre])) case [8, 4]: # STR_TO_CODEPOINTS pre = self.pop() self.push([ord(c) for c in pre]) case [8, 5]: # INTS_TO_COMMAND ints = self.pop() self.push(Command(ints)) case [8, 6]: # COMMAND_TO_INTS command = self.pop() self.push(command.command) # DEBUG case [9, 1]: # TOGGLE_SHOW_STACK DEBUG_MODES['SHOW_STACK'] = not DEBUG_MODES['SHOW_STACK'] case [9, 2]: # TOGGLE_SHOW_CONSTANTS DEBUG_MODES['SHOW_CONSTANTS'] = not DEBUG_MODES['SHOW_CONSTANTS'] case [9, 3]: # TOGGLE_SHOW_SUBROUTINE_TRANSTIONS DEBUG_MODES['SHOW_SUBROUTINE_TRANSITIONS'] = not DEBUG_MODES['SHOW_SUBROUTINE_TRANSITIONS'] case [9, 4]: # TOGGLE_SHOW_COMMANDS DEBUG_MODES['SHOW_COMMANDS'] = not DEBUG_MODES['SHOW_COMMANDS'] case [9, 5]: # TOGGLE_SHOW_STACK_OPERATIONS DEBUG_MODES['SHOW_STACK_OPERATIONS'] = not DEBUG_MODES['SHOW_STACK_OPERATIONS'] case [9, 6]: # TOGGLE_SHOW_SUBROUTINE_STACK DEBUG_MODES['SHOW_SUBROUTINE_STACK'] = not DEBUG_MODES['SHOW_SUBROUTINE_STACK'] # END def run_subroutine(self, subroutine: Subroutine): if DEBUG_MODES['SHOW_SUBROUTINE_TRANSITIONS']: print("START", subroutine) self.subroutine_stack.append(subroutine) then_do = self.run_code_sequence([c.command for c in subroutine.definition]) self.subroutine_stack.pop() if then_do is not None and len(then_do) > 0: self.process_next_command(then_do) if DEBUG_MODES['SHOW_SUBROUTINE_TRANSITIONS']: print("STOP", subroutine) def run_code_sequence(self, commands: List[Command]): for command in commands: if DEBUG_MODES['SHOW_COMMANDS']: print(f"COMMAND START: {command}") if DEBUG_MODES['SHOW_SUBROUTINE_STACK']: print(f"SUBROUTINE STACK: {self.subroutine_stack}") res = self.process_next_command(command) if DEBUG_MODES['SHOW_STACK']: print(f"STACK: {self.stack}") if DEBUG_MODES['SHOW_COMMANDS']: print(f"COMMAND END: {command}") if res is not None: return res def push(self, obj): if DEBUG_MODES['SHOW_STACK_OPERATIONS']: print(f"PUSH: {obj}") self.stack.append(obj) def pop(self): res = self.stack.pop() if DEBUG_MODES['SHOW_STACK_OPERATIONS']: print(f"POP: {res}") return res def make_string(command: List[int]): return ''.join([chr(c) for c in command]) def correct_line(line: str): return line.split('#')[0].strip() def read_raw_dcmp(filename: str): with open(filename, 'r') as f: lines = [correct_line(line) for line in f.readlines()] nonemptyLines = [line for line in lines if len(line) > 0] return [[int(elem) for elem in line.split(';') if len(elem.strip()) > 0] for line in nonemptyLines] def read_num_dcmp(filename: str): with open(filename, 'r') as f: lines = [line.strip() for line in f.readlines()] numbers = [int(line) for line in lines] factorized = [ps.decompose(number) for number in numbers] return factorized def gen_num_dcmp(commands: List[List[int]]): sys.set_int_max_str_digits(99999) result = [] for command in commands: while len(ps.primes) < len(command): ps.enlarge() result.append(math.prod([p**e for p, e in zip(ps.primes, command)])) return '\n'.join([str(e) for e in result]) def gen_raw_dcmp(commands: List[List[int]]): return '\n'.join([';'.join([str(i) for i in command]) for command in commands]) if __name__ == "__main__": if len(sys.argv) < 2: print("Not enough arguments") exit() if sys.argv[1] == 'wimp': if len(sys.argv) < 3: print("Not enough arguments") exit() filename = sys.argv[2] if filename.endswith('.wimpdcmp'): raw_code = read_raw_dcmp(filename) print(gen_num_dcmp(raw_code)) elif filename.endswith('.dcmp'): raw_code = read_num_dcmp(filename) print(gen_raw_dcmp(raw_code)) else: filename = sys.argv[1] if filename.endswith('.wimpdcmp') or filename.endswith('.wdcmp'): raw_code = read_raw_dcmp(filename) elif filename.endswith('.dcmp'): raw_code = read_num_dcmp(filename) machine = Machine() machine.run_code_sequence(raw_code)