day24_part1.py (6659B)
1 #!/usr/bin/env python 2 """Advent of Code 2021, day 24 (part 1): Arithmetic Logic Unit 3 Emulate and validate input for a simple ALU""" 4 5 # This one is tricky. Emulating the ALU is straightforward, but validating the 6 # input could blow up. Since there are 9^14 (~2^44) different model numbers, 7 # running through these is infeasible. The approach I'm taking right now is 8 # breaking the program into 14 different sections, divided by `inp` 9 # instruction. At the end of each section, we'll determine for preceding 10 # inputted values: 11 # * Which inputs are invalid (due to dividing by or taking modulus of 0) 12 # * The mapping from each _valid_ input to register values 13 14 from typing import Tuple, List, Union, Dict, NewType, cast 15 from functools import reduce 16 import re 17 18 from utils import get_puzzle_input 19 20 REGISTER_TO_INDEX = {'w': 0, 'x': 1, 'y': 2, 'z': 3} 21 22 Expression = NewType( 23 'Expression', 24 Tuple[str, str, Union[None, int, str]] 25 ) 26 27 # Only four registers in the ALU 28 RegisterState = NewType( 29 'RegisterState', 30 Tuple[int, int, int, int] 31 ) 32 33 def parse_input(input_string: str) -> List[Expression]: 34 """Honestly this just splits the string into a bunch of tuples, the only 35 fancy thing it does is deal with the third section smartly""" 36 instructions = [] 37 for expression in (l.split(' ') for l in input_string.rstrip('\n').split('\n')): 38 if len(expression) == 2: 39 instructions.append(Expression((expression[0], expression[1], None))) 40 elif re.match(r'[-+]?\d+', expression[2]) is not None: 41 instructions.append(Expression((expression[0], expression[1], 42 int(expression[2])))) 43 else: 44 instructions.append(cast(Expression, tuple(expression))) 45 return instructions 46 47 def split_instructions(instructions: List[Expression]) -> List[List[Expression]]: 48 """Split the instructions into sections, each beginning with an `inp` 49 command""" 50 instructions_list: List[List[Expression]] = [] 51 for expression in instructions: 52 if expression[0] == 'inp': 53 instructions_list.append([]) 54 instructions_list[-1].append(expression) 55 return instructions_list 56 57 def run_instruction(expression: Expression, register_state: RegisterState, 58 instruction_input: Union[int, None] = None) -> RegisterState: 59 """Run an instruction and update the registers""" 60 instruction, target, operand = expression 61 target_idx = REGISTER_TO_INDEX[target] 62 register_list = list(register_state) 63 64 operand_value: Union[int, None] 65 if isinstance(operand, str): 66 operand_value = register_list[REGISTER_TO_INDEX[operand]] 67 else: 68 operand_value = operand 69 70 # Note that if the operand is 0 and mod or div, we'll get a 71 # ZeroDivisionError, which is fine! 72 assert instruction == 'inp' or operand_value is not None 73 if instruction == 'inp': 74 if instruction_input is None: 75 raise RuntimeError("`inp` command with no input") 76 register_list[target_idx] = instruction_input 77 elif instruction == 'add': 78 register_list[target_idx] += cast(int, operand_value) 79 elif instruction == 'mul': 80 register_list[target_idx] *= cast(int, operand_value) 81 elif instruction == 'div': 82 register_list[target_idx] //= cast(int, operand_value) 83 elif instruction == 'mod': 84 if register_list[target_idx] < 0 or cast(int, operand_value) < 0: 85 raise ZeroDivisionError('ALU mod involving a negative number') 86 register_list[target_idx] %= cast(int, operand_value) 87 elif instruction == 'eql': 88 register_list[target_idx] = int( 89 register_list[target_idx] == cast(int, operand_value) 90 ) 91 else: 92 raise RuntimeError('Unimplemented instruction') 93 94 return cast(RegisterState, tuple(register_list)) 95 96 def run_routine(routine: List[Expression], register_state: RegisterState, 97 instruction_input: Union[int, None] = None) -> RegisterState: 98 """Run a list of instructions (typically beginning with an `inp` 99 instruction and ending before another)""" 100 return reduce(lambda r, e: run_instruction(e, r, instruction_input), 101 routine, 102 register_state) 103 104 def run_routine_fast(routine: List[Expression], register_state: RegisterState, 105 instruction_input: int) -> RegisterState: 106 """Run puzzle input routines--note that this doesn't read the actual 107 instructions and doesn't work in the general case (as `run_rouine` does)""" 108 # It is, however, almost 22 times faster though 109 w_register = instruction_input 110 z_register = register_state[3] 111 x_register = int(w_register != z_register % 26 + cast(int, routine[5][2])) 112 z_register //= cast(int, routine[4][2]) # 1 or 26 113 z_register *= 25 * x_register + 1 # Also 1 or 26 114 y_register = (w_register + cast(int, routine[15][2])) * x_register 115 z_register += y_register 116 return RegisterState((w_register, x_register, y_register, z_register)) 117 118 def test_inputs(routines: List[List[Expression]]) -> int: 119 """Return the highest value that results in a valid state of the ALU""" 120 # This operates on the assumption (gleaned through inspection) that only 121 # the z register actually gets carried forward from one block of 122 # instructions to another. So this finds the z value associated with each 123 # input at every step of the way, pruning input combinations that result in 124 # a z value that is obtained with a higher input combination 125 z_to_input = {0: 0} 126 for routine in routines: 127 new_z_to_input: Dict[int, int] = {} 128 for z_in, previous_inputs in z_to_input.items(): 129 for instruction_input in range(1, 10): 130 registers = run_routine_fast(routine, 131 RegisterState((0, 0, 0, z_in)), 132 instruction_input) 133 z_out = registers[3] 134 input_sequence = previous_inputs * 10 + instruction_input 135 if z_out not in new_z_to_input \ 136 or new_z_to_input[z_out] < input_sequence: 137 new_z_to_input[z_out] = input_sequence 138 z_to_input = new_z_to_input 139 return z_to_input[0] 140 141 def solve_puzzle(input_string: str) -> int: 142 """Return the numeric solution to the puzzle""" 143 return test_inputs(split_instructions(parse_input(input_string))) 144 145 def main() -> None: 146 """Run when the file is called as a script""" 147 print("Largest possible model number:", 148 solve_puzzle(get_puzzle_input(24))) 149 150 if __name__ == "__main__": 151 main()