Advent of Code - 2021
This is a solution to Day 24 of Advent of Code 2021.
Day 24 - Arithmetic Logic Unit
Magic smoke starts leaking from the submarine's arithmetic logic unit (ALU). Without the ability to perform basic arithmetic and logic functions, the submarine can't produce cool patterns with its Christmas lights!
It also can't navigate. Or run the oxygen system.
Don't worry, though - you probably have enough oxygen left to give you enough time to build a new ALU.
The ALU is a four-dimensional processing unit: it has integer variables w, x, y, and z. These variables all start with the value 0. The ALU also supports six instructions:
inp a- Read an input value and write it to variable a.add a b- Add the value of a to the value of b, then store the result in variable a.mul a b- Multiply the value of a by the value of b, then store the result in variable a.div a b- Divide the value of a by the value of b, truncate the result to an integer, then store the result in variable a. (Here, "truncate" means to round the value toward zero.)mod a b- Divide the value of a by the value of b, then store the remainder in variable a. (This is also called the modulo operation.)eql a b- If the value of a and b are equal, then store the value 1 in variable a. Otherwise, store the value 0 in variable a.In all of these instructions, a and b are placeholders; a will always be the variable where the result of the operation is stored (one of w, x, y, or z), while b can be either a variable or a number. Numbers can be positive or negative, but will always be integers.
The ALU has no jump instructions; in an ALU program, every instruction is run exactly once in order from top to bottom. The program halts after the last instruction has finished executing.
(Program authors should be especially cautious; attempting to execute div with b=0 or attempting to execute mod with a<0 or b<=0 will cause the program to crash and might even damage the ALU. These operations are never intended in any serious ALU program.)
For example, here is an ALU program which takes an input number, negates it, and stores it in x:
inp x>mul x -1Here is an ALU program which takes two input numbers, then sets z to 1 if the second input number is three times larger than the first input number, or sets z to 0 otherwise:
inp z inp x mul z 3 eql z xHere is an ALU program which takes a non-negative integer as input, converts it into binary, and stores the lowest (1's) bit in z, the second-lowest (2's) bit in y, the third-lowest (4's) bit in x, and the fourth-lowest (8's) bit in w:
inp w add z w mod z 2 div w 2 add y w mod y 2 div w 2 add x w mod x 2 div w 2 mod w 2Once you have built a replacement ALU, you can install it in the submarine, which will immediately resume what it was doing when the ALU failed: validating the submarine's model number. To do this, the ALU will run the MOdel Number Automatic Detector program (MONAD, your puzzle input).
Submarine model numbers are always fourteen-digit numbers consisting only of digits 1 through 9. The digit 0 cannot appear in a model number.
When MONAD checks a hypothetical fourteen-digit model number, it uses fourteen separate inp instructions, each expecting a single digit of the model number in order of most to least significant. (So, to check the model number 13579246899999, you would give 1 to the first inp instruction, 3 to the second inp instruction, 5 to the third inp instruction, and so on.) This means that when operating MONAD, each input instruction should only ever be given an integer value of at least 1 and at most 9.
Then, after MONAD has finished running all of its instructions, it will indicate that the model number was valid by leaving a 0 in variable z. However, if the model number was invalid, it will leave some other non-zero value in z.
MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of the MONAD documentation was eaten by a tanuki. You'll need to figure out what MONAD does some other way.
To enable as many submarine features as possible, find the largest valid fourteen-digit model number that contains no 0 digits. What is the largest model number accepted by MONAD?
Read input
from utils import read_input
program = read_input(24)Part 1
For Christmas Eve, I managed to write a working computer to execute these ALU programs but since the problem space is in hundreds of trillions, it cannot run to find a solution. And since it was Christmas, I decided to leave it at that and enjoy Christmas meal with my family instead of spending the day coding. Because there are things more important than gaining virtual stars.
My approach to these type of problems is to create a function for each possible command and have them all take the same amount of parameters. This way they can be run dynamically.
def ALU_input(register, value, memory):
memory[register] = int(value)
return memory
def ALU_add(registerA, registerB, memory):
if registerB in MEMORY:
memory[registerA] = memory[registerA] + memory[registerB]
else:
memory[registerA] = memory[registerA] + int(registerB)
return memory
def ALU_multiply(registerA, registerB, memory):
if registerB in MEMORY:
memory[registerA] = memory[registerA] * memory[registerB]
else:
memory[registerA] = memory[registerA] * int(registerB)
return memory
def ALU_divide(registerA, registerB, memory):
if registerB in memory:
memory[registerA] = memory[registerA] // memory[registerB]
else:
memory[registerA] = memory[registerA] // int(registerB)
return memory
def ALU_modulo(registerA, registerB, memory):
if registerB in memory:
memory[registerA] = memory[registerA] % memory[registerB]
else:
memory[registerA] = memory[registerA] % int(registerB)
return memory
def ALU_equals(registerA, registerB, memory):
if registerB in memory:
if memory[registerA] == memory[registerB]:
memory[registerA] = 1
else:
memory[registerA] = 0
else:
if memory[registerA] == int(registerB):
memory[registerA] = 1
else:
memory[registerA] = 0
return memory
COMMANDS = {
'inp': ALU_input,
'add': ALU_add,
'mul': ALU_multiply,
'div': ALU_divide,
'mod': ALU_modulo,
'eql': ALU_equals
}
MEMORY = {
'w': 0,
'x': 0,
'y': 0,
'z': 0
}My attempt was to have a cache that has a string as key (for example "99") and the state of the program at the end of that input stage (in this case, after two 9s inputted) as the value. This works but ended growing too big and crashing my computer. It would need a cache pruning system that would always just keep 13 values in it (so when the first number changes to 8, the "9" cache key would be deleted as we're counting down and there will never be a start of 9 again).
I didn't have time to implement that and to see if that would have been successful. But in theory, that combined with parallel running would at least in theory reach a result in some time.
cache = {}
def is_next_input(line_number, program):
if line_number+1 == len(program):
return False
return program[line_number+1][:3] == 'inp'
def find_largest_cache(model_number):
while len(model_number) > 0:
if model_number in cache:
return True, cache[model_number]
model_number = model_number[:-1]
return False, ()
def execute(program, model_number):
memory = MEMORY.copy()
input_index = 0
line_number = 0
line = None
in_cache, cached = find_largest_cache(model_number)
if in_cache:
line_number, input_index, memory = cached
while line_number < len(program):
line = program[line_number]
cmd, params = line[:3], line[3:].strip().split()
if cmd == 'inp':
cache_key = model_number[:input_index+1]
value = model_number[input_index]
input_index += 1
if cache_key in cache:
#print("::found::", cache_key, cache[cache_key])
line_number, input_index, memory = cache[cache_key]
continue
params.append(value)
memory = COMMANDS[cmd](*params, memory)
if is_next_input(line_number, program):
cache_key = model_number[:input_index]
#print('>>store>>', cache_key, (line_number + 1, input_index, memory))
cache[cache_key] = (line_number + 1, input_index, memory.copy())
line_number += 1
return memorydef find_largest_valid_model_number(program):
model_number = 99999999999999
while True:
model = str(model_number)
assert len(model) == 14
if '0' in model:
model_number -= 1
continue
memory = dict(execute(program, model))
if memory['z'] == 0:
return model_number
model_number -= 1find_largest_valid_model_number(program)Unfinished
The above code will crash your computer when it runs out of memory so don't attempt running it.