Solution to AOC 2021 Day 24

aoc_24_2021.py

import math
import numpy as np
data = open("/home/yassinealouini/Documents/code/advent_of_code/aoc/year_2021/data/24.txt").read().rstrip()


OPERATIONS = {"add": lambda x: sum(x), "mul": lambda x: math.prod(x), 
              "div": lambda x: x[0] // x[1], "mod": lambda x: x[0] % x[1], 
              "inp": lambda x: x[1],
              "eql": lambda x: int(x[0] == x[1])}


STORAGE = {"w": 0, "x": 0, "y": 0, "z": 0}

def get_monad(data):
    monad = []
    for row in data.rstrip().split("\n"):
        splitted = row.split(" ")
        operation = splitted[0]
        values = splitted[1:]
        monad.append((operation, values))

    return monad

def run(inputs, storage, monad):
    storage = storage.copy()
    for operation, values in monad:
        to_store = values[0]
        storage.get("z")
        new_values = []
        for v in  values:
            new_v = storage.get(v)
            if new_v is None:
                new_values.append(int(v))
            else:
                new_values.append(new_v)
        if operation == "inp":
            new_input = inputs.pop(0)
            new_values.append(new_input)
        storage[to_store] = OPERATIONS[operation](new_values)
    return storage["z"]
    # How to parse values?

MONAD = get_monad(data)
# Too much iterations. :p
# for number in product(range(9, 0, -1), repeat=14):
#     res = run(list(number), STORAGE, MONAD)
#     print(res)
#     if res == 0:
#         print("Valid")
#         print(number)
#         print(int("".join(number)))
#         break

# By inspecting the input and matching the 6 following blocks,
# we can see that each block from input to input
# has the same structure except the 3 numbers in [].
# These are at indices: 4, 5, and 15 for each block from 0 to 17.
# Let's denote these z_v, x_v, and y_v
# So what is the equation of each block? Done by pen and paper.

# block 1
"""
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 [2]
mul y x
add z y
"""

# block 2
"""
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 [4]
mul y x
add z y
""" 

# block 3

"""
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 [8]
mul y x
add z y
"""

# block 4
"""
inp w
mul x 0
add x z
mod x 26
div z [1]
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 [7]
mul y x
add z y
"""

# block 5

"""
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 [12]
mul y x
add z y
"""

# block 6

"""
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 [7]
mul y x
add z y
"""



def compute_one_block(x_v, y_v, z_v, input, previous_z):
    # When this condition ((previous_z % 26 + x_v) == input)) on x happens, 
    # x is 0 so the remaining value is small
    # which is what we want to happen so that the final z is 0.
    x = 0 if ((previous_z % 26 + x_v) == input) else 1
    z = (previous_z // z_v) * (25 * x + 1) + x * (input  + y_v)
    return z

# When x is 0, compute_one_block becomes:
# z = previous_z // z_v
# When x is 1, compute_one_block becomes:
# z = (input + y_v) + 26 * (previous_z // z_v)

# Parsing the input to get the different x_v, y_v, and z_vs
X_V = []
Y_V = []
Z_V = []
# each block is of length 18.
for row_id, row in enumerate(data.split("\n")):
    if (row_id % 18 == 4):
        z_v = int(row.split(" ")[-1])
        Z_V.append(z_v)
    if (row_id % 18 == 5):
        x_v = int(row.split(" ")[-1])
        X_V.append(x_v)
    if (row_id % 18 == 15):
        y_v = int(row.split(" ")[-1])
        Y_V.append(y_v)
# As much values as the input, so 14.
assert len(X_V) == 14
assert len(Y_V) == 14
assert len(Z_V) == 14
print(Z_V, Y_V, X_V)
# How does the compute_one_block behaves on the
# given X_V, Y_V, and Z_V values?
# For Z_V only two possible values: 1 and 26
# each 7 times.
print("Values of Z_V with counts", np.unique(Z_V, return_counts=True))
# Let's see values of X_V when Z_V is 1:
print("X_V values when Z_V == 1", [x for x, z in zip(X_V, Z_V) if z == 1])
# These are positive values and since the input is positive,
# x is 1 (we will never equal the input) there 
# so the equation further simplies to:
# z = (input  + y_v) + 26 * previous_z
print("Indices for which Z_v is 1", [index for index, z in enumerate(Z_V) if z == 1])
# Let's see values of X_V when Z_V is 26: 
print("X_V values when Z_V == 26", [x for x, z in zip(X_V, Z_V) if z == 26])
# These are negative or 0 values so we can make the x equal to 0 by
# providing the correct input and thus the equation further simplifies to:
# z = previous_z // 26.
# This makes z decrease.
# By alternating between these two types, we can make z equal to 0.
Z_26_indices = [index for index, z in enumerate(Z_V) if z == 26]
Z_1_indices = [index for index, z in enumerate(Z_V) if z == 1]
print("Indices for which Z_v is 26", Z_26_indices)
# So at these indices, we need to have input - x_v = previous_z % 26
print("Values of X_V at indices where Z_v is 26", [X_V[i] for i in Z_26_indices])
# Let N be the number we are looking for with N[0] its leading digit, N[1]
# the second leading and so on.
# Then N[5] - X_V[5] = previous_z % 26
# The previous_z was for N[4] and it was a step that increases so we take
# The previous Z happen to be of type 1 so modulo 26, is equal to (input + y_v)
# If it wasn't, we need to get back as many times untel we get an (input + y_v)
# Then this is removed from the previous_z.
# Thus N[5] - X_V[5] = N[4] + Y_V[4]
# which simplifies to N[5] - N[4] = Y_V[4] + X_V[5]
print("At Z_1 indices, z increases", Z_1_indices)
print("Y_V at Z_1 indices", [Y_V[i] for i in Z_1_indices])
print("At Z_1 indices, z can decrease with the correct input", Z_26_indices)
print("Y_V at Z_26 indices", [Y_V[i] for i in Z_26_indices])
# TODO: Can be made programatically.
# We finally get 7 equations:
# N[5] - N[4] = X_V[5] + Y_V[4]
# N[6] - N[3] = X_V[6] + Y_V[3]
# N[8] - N[7] = X_V[8] + Y_V[7]
# N[10] - N[9] = X_V[10] + Y_V[9]
# N[11] - N[2] = X_V[11] + Y_V[2]
# N[12] - N[1] = X_V[12] + Y_V[1]
# N[13] - N[0] = X_V[13] + Y_V[0]
N = [0 for _ in range(14)]
# We want the largest number so we set the left number
# in the difference to 9 if the sum is >= 0
# otherwise the right number.
diff_indices = [(5, 4), (6, 3), (8, 7), (10, 9), (11, 2), (12, 1), (13, 0)]
for diff_index in diff_indices:
    l, r = diff_index
    print(f"Differences N[{l}] - N[{r}] is", X_V[l] + Y_V[r])
    if X_V[l] + Y_V[r] >= 0:
        N[l] = 9
        N[r] = 9 - (X_V[l] + Y_V[r])
    else:
        N[r] = 9
        N[l] = 9 + (X_V[l] + Y_V[r])
print("Solution to part I", "".join([str(n) for n in N]))
# We now want the smallest number so we set the left number
# in the difference to 1 if the sum is <= 0
# otherwise the right number to 1.
for diff_index in diff_indices:
    l, r = diff_index
    print(f"Differences N[{l}] - N[{r}] is", X_V[l] + Y_V[r])
    if X_V[l] + Y_V[r] <= 0:
        N[l] = 1
        N[r] = 1 - (X_V[l] + Y_V[r])
    else:
        N[r] = 1
        N[l] = 1 + (X_V[l] + Y_V[r])
print("Solution to part II", "".join([str(n) for n in N]))