commit 22b224afef94eab71352e8015192559203e7bc4a
parent 069ee1e78513394cbe798aafb7b643100bf93556
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Tue, 4 Jan 2022 21:33:02 -0500
Solution to day 24, part 2
Diffstat:
| D | day24_input.txt | | | 252 | ------------------------------------------------------------------------------- |
| A | day24_part2.py | | | 50 | ++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 50 insertions(+), 252 deletions(-)
diff --git a/day24_input.txt b/day24_input.txt
@@ -1,252 +0,0 @@
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 15
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 15
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 15
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 10
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 12
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 2
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 13
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 16
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -12
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 12
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 10
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 11
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -9
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 5
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 14
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 16
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 1
-add x 13
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 6
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -14
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 15
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -11
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 3
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -2
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 12
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -16
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 10
-mul y x
-add z y
-inp w
-mul x 0
-add x z
-mod x 26
-div z 26
-add x -14
-eql x w
-eql x 0
-mul y 0
-add y 25
-mul y x
-add y 1
-mul z y
-mul y 0
-add y w
-add y 13
-mul y x
-add z y
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()
