day24_part2.py (2122B)
1 #!/usr/bin/env python 2 """Advent of Code 2021, day 24 (part 2): Arithmetic Logic Unit 3 Emulate and validate input for a simple ALU""" 4 5 # Pretty straightforward update to part 1 6 7 from typing import List, Dict 8 9 from day24_part1 import (Expression, 10 RegisterState, 11 parse_input, 12 split_instructions, 13 run_routine_fast) 14 from utils import get_puzzle_input 15 16 def test_inputs(routines: List[List[Expression]]) -> int: 17 """Return the highest value that results in a valid state of the ALU""" 18 # This operates on the assumption (gleaned through inspection) that only 19 # the z register actually gets carried forward from one block of 20 # instructions to another. So this finds the z value associated with each 21 # input at every step of the way, pruning input combinations that result in 22 # a z value that is obtained with a higher input combination 23 z_to_input = {0: 0} 24 for routine in routines: 25 new_z_to_input: Dict[int, int] = {} 26 for z_in, previous_inputs in z_to_input.items(): 27 for instruction_input in range(1, 10): 28 registers = run_routine_fast(routine, 29 RegisterState((0, 0, 0, z_in)), 30 instruction_input) 31 z_out = registers[3] 32 input_sequence = previous_inputs * 10 + instruction_input 33 # The only thing that changed from Part 1 34 if z_out not in new_z_to_input \ 35 or new_z_to_input[z_out] > input_sequence: 36 new_z_to_input[z_out] = input_sequence 37 z_to_input = new_z_to_input 38 return z_to_input[0] 39 40 def solve_puzzle(input_string: str) -> int: 41 """Return the numeric solution to the puzzle""" 42 return test_inputs(split_instructions(parse_input(input_string))) 43 44 def main() -> None: 45 """Run when the file is called as a script""" 46 print("Smallest possible model number:", 47 solve_puzzle(get_puzzle_input(24))) 48 49 if __name__ == "__main__": 50 main()