commit b9bb6aca87645ca2d1bb28b4e2fe81c9fcdc32ba
parent 50189f6b23b0e0553d41079ba54cc3f588cad4d6
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Tue, 4 Jan 2022 21:36:43 -0500
Merge branch 'day24' into main
Diffstat:
| A | day24_part1.py | | | 151 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | day24_part2.py | | | 50 | ++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 201 insertions(+), 0 deletions(-)
diff --git a/day24_part1.py b/day24_part1.py
@@ -0,0 +1,151 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 24 (part 1): Arithmetic Logic Unit
+Emulate and validate input for a simple ALU"""
+
+# This one is tricky. Emulating the ALU is straightforward, but validating the
+# input could blow up. Since there are 9^14 (~2^44) different model numbers,
+# running through these is infeasible. The approach I'm taking right now is
+# breaking the program into 14 different sections, divided by `inp`
+# instruction. At the end of each section, we'll determine for preceding
+# inputted values:
+# * Which inputs are invalid (due to dividing by or taking modulus of 0)
+# * The mapping from each _valid_ input to register values
+
+from typing import Tuple, List, Union, Dict, NewType, cast
+from functools import reduce
+import re
+
+from utils import get_puzzle_input
+
+REGISTER_TO_INDEX = {'w': 0, 'x': 1, 'y': 2, 'z': 3}
+
+Expression = NewType(
+ 'Expression',
+ Tuple[str, str, Union[None, int, str]]
+)
+
+# Only four registers in the ALU
+RegisterState = NewType(
+ 'RegisterState',
+ Tuple[int, int, int, int]
+)
+
+def parse_input(input_string: str) -> List[Expression]:
+ """Honestly this just splits the string into a bunch of tuples, the only
+ fancy thing it does is deal with the third section smartly"""
+ instructions = []
+ for expression in (l.split(' ') for l in input_string.rstrip('\n').split('\n')):
+ if len(expression) == 2:
+ instructions.append(Expression((expression[0], expression[1], None)))
+ elif re.match(r'[-+]?\d+', expression[2]) is not None:
+ instructions.append(Expression((expression[0], expression[1],
+ int(expression[2]))))
+ else:
+ instructions.append(cast(Expression, tuple(expression)))
+ return instructions
+
+def split_instructions(instructions: List[Expression]) -> List[List[Expression]]:
+ """Split the instructions into sections, each beginning with an `inp`
+ command"""
+ instructions_list: List[List[Expression]] = []
+ for expression in instructions:
+ if expression[0] == 'inp':
+ instructions_list.append([])
+ instructions_list[-1].append(expression)
+ return instructions_list
+
+def run_instruction(expression: Expression, register_state: RegisterState,
+ instruction_input: Union[int, None] = None) -> RegisterState:
+ """Run an instruction and update the registers"""
+ instruction, target, operand = expression
+ target_idx = REGISTER_TO_INDEX[target]
+ register_list = list(register_state)
+
+ operand_value: Union[int, None]
+ if isinstance(operand, str):
+ operand_value = register_list[REGISTER_TO_INDEX[operand]]
+ else:
+ operand_value = operand
+
+ # Note that if the operand is 0 and mod or div, we'll get a
+ # ZeroDivisionError, which is fine!
+ assert instruction == 'inp' or operand_value is not None
+ if instruction == 'inp':
+ if instruction_input is None:
+ raise RuntimeError("`inp` command with no input")
+ register_list[target_idx] = instruction_input
+ elif instruction == 'add':
+ register_list[target_idx] += cast(int, operand_value)
+ elif instruction == 'mul':
+ register_list[target_idx] *= cast(int, operand_value)
+ elif instruction == 'div':
+ register_list[target_idx] //= cast(int, operand_value)
+ elif instruction == 'mod':
+ if register_list[target_idx] < 0 or cast(int, operand_value) < 0:
+ raise ZeroDivisionError('ALU mod involving a negative number')
+ register_list[target_idx] %= cast(int, operand_value)
+ elif instruction == 'eql':
+ register_list[target_idx] = int(
+ register_list[target_idx] == cast(int, operand_value)
+ )
+ else:
+ raise RuntimeError('Unimplemented instruction')
+
+ return cast(RegisterState, tuple(register_list))
+
+def run_routine(routine: List[Expression], register_state: RegisterState,
+ instruction_input: Union[int, None] = None) -> RegisterState:
+ """Run a list of instructions (typically beginning with an `inp`
+ instruction and ending before another)"""
+ return reduce(lambda r, e: run_instruction(e, r, instruction_input),
+ routine,
+ register_state)
+
+def run_routine_fast(routine: List[Expression], register_state: RegisterState,
+ instruction_input: int) -> RegisterState:
+ """Run puzzle input routines--note that this doesn't read the actual
+ instructions and doesn't work in the general case (as `run_rouine` does)"""
+ # It is, however, almost 22 times faster though
+ w_register = instruction_input
+ z_register = register_state[3]
+ x_register = int(w_register != z_register % 26 + cast(int, routine[5][2]))
+ z_register //= cast(int, routine[4][2]) # 1 or 26
+ z_register *= 25 * x_register + 1 # Also 1 or 26
+ y_register = (w_register + cast(int, routine[15][2])) * x_register
+ z_register += y_register
+ return RegisterState((w_register, x_register, y_register, z_register))
+
+def test_inputs(routines: List[List[Expression]]) -> int:
+ """Return the highest value that results in a valid state of the ALU"""
+ # This operates on the assumption (gleaned through inspection) that only
+ # the z register actually gets carried forward from one block of
+ # instructions to another. So this finds the z value associated with each
+ # input at every step of the way, pruning input combinations that result in
+ # a z value that is obtained with a higher input combination
+ z_to_input = {0: 0}
+ for routine in routines:
+ new_z_to_input: Dict[int, int] = {}
+ for z_in, previous_inputs in z_to_input.items():
+ for instruction_input in range(1, 10):
+ registers = run_routine_fast(routine,
+ RegisterState((0, 0, 0, z_in)),
+ instruction_input)
+ z_out = registers[3]
+ input_sequence = previous_inputs * 10 + instruction_input
+ if z_out not in new_z_to_input \
+ or new_z_to_input[z_out] < input_sequence:
+ new_z_to_input[z_out] = input_sequence
+ z_to_input = new_z_to_input
+ return z_to_input[0]
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return test_inputs(split_instructions(parse_input(input_string)))
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ print("Largest possible model number:",
+ solve_puzzle(get_puzzle_input(24)))
+
+if __name__ == "__main__":
+ main()
diff --git a/day24_part2.py b/day24_part2.py
@@ -0,0 +1,50 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 24 (part 2): Arithmetic Logic Unit
+Emulate and validate input for a simple ALU"""
+
+# Pretty straightforward update to part 1
+
+from typing import List, Dict
+
+from day24_part1 import (Expression,
+ RegisterState,
+ parse_input,
+ split_instructions,
+ run_routine_fast)
+from utils import get_puzzle_input
+
+def test_inputs(routines: List[List[Expression]]) -> int:
+ """Return the highest value that results in a valid state of the ALU"""
+ # This operates on the assumption (gleaned through inspection) that only
+ # the z register actually gets carried forward from one block of
+ # instructions to another. So this finds the z value associated with each
+ # input at every step of the way, pruning input combinations that result in
+ # a z value that is obtained with a higher input combination
+ z_to_input = {0: 0}
+ for routine in routines:
+ new_z_to_input: Dict[int, int] = {}
+ for z_in, previous_inputs in z_to_input.items():
+ for instruction_input in range(1, 10):
+ registers = run_routine_fast(routine,
+ RegisterState((0, 0, 0, z_in)),
+ instruction_input)
+ z_out = registers[3]
+ input_sequence = previous_inputs * 10 + instruction_input
+ # The only thing that changed from Part 1
+ if z_out not in new_z_to_input \
+ or new_z_to_input[z_out] > input_sequence:
+ new_z_to_input[z_out] = input_sequence
+ z_to_input = new_z_to_input
+ return z_to_input[0]
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return test_inputs(split_instructions(parse_input(input_string)))
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ print("Smallest possible model number:",
+ solve_puzzle(get_puzzle_input(24)))
+
+if __name__ == "__main__":
+ main()
