Day 7, part 2 - Solving (but not the puzzle)

In part 1, we didn’t even attempt yet to solve the puzzle. We are, however, building a fairly solid foundation to do so, so let’s keep going. We ended with saying that we need:

A list of wires

typedef struct {
    wire_t** wires;
    int n;
    int capacity;
} list_wires_t;

list_wires_t* list_wires_create(int initial_capacity){
    list_wires_t* list = malloc(sizeof(list_wires_t));
    
    list->n = 0;
    list->capacity = initial_capacity;

    list->wires = malloc(sizeof(wire_t*)*list->capacity);

    return list;
}

void list_wires_destroy(list_wires_t* list){
    for (int i=0; i < list->n; i++)
        wire_destroy(list->wires[i]);
    free(list->wires);
    free(list);
}

void list_wires_add(list_wires_t* list, wire_t* wire){
    if (list->n == list->capacity){
        list->wires = realloc(list->wires, sizeof(wire_t*)*list->capacity*2);
        list->capacity *= 2;
    }
    list->wires[list->n] = wire;
    list->n++;
}

To test it, we can update the test_dependency_map test, adding also a print method for convenience:

void list_wires_print(list_wires_t* list){
    printf("List of %d wires:\n", list->n);
    for (int i=0; i < list->n; i++){
        wire_print(list->wires[i]);
    }
}

void test_dependency_map(){
    list_wires_t* list = list_wires_create(6);
    
    wire_t* w123 = wire_create("w123", (uint16_t) 123, true);
    wire_t* w4 = wire_create("w4", (uint16_t) 4, true);
    wire_t* c = wire_create("c", 0, false);
    wire_t* dd = wire_create("dd", 0, false);
    wire_t* bb = wire_create("bb", 0, false);
    wire_t* a = wire_create("a", 0, false);

    list_wires_add(list, w123);
    list_wires_add(list, w4);
    list_wires_add(list, c);
    list_wires_add(list, dd);
    list_wires_add(list, bb);
    list_wires_add(list, a);

    wire_add_dependency(c, a);
    wire_add_dependency(c, bb);
    wire_add_dependency(dd, c);
    wire_add_dependency(dd, w123);
    wire_add_dependency(bb, w4);
    wire_add_dependency(a, bb);

    list_wires_print(list);
    list_wires_destroy(list);
}

Solving wires

I was initially thinking about going through the wire list multiple times, solving only wires which only depends on already-solved wires, until all are solved. But since the puzzle only asks for the solution of one specific wire, I think I’d rather go recursive: try to solve the wire, and recursively solve the dependencies as needed.

I realize as I started writing this function that I may have forgotten a little detail: I don’t record the operation anywhere in the wire_t at the moment. Oops. Before worrying about that, though, I’d still write the solver. I’ll just assume that every operation is the binary AND for the moment:

void wire_solve(wire_t* wire){
    if (wire->is_set)
        return;

    for (int i = 0; i < wire->n_dependencies; i++)
        if (!wire->dependencies[i]->is_set)
            wire_solve(wire->dependencies[i]);
    
    // apply the operation on the wire. Let's just do a "&" for now
    uint16_t value = wire->dependencies[0]->value;
    for (int i = 1; i < wire->n_dependencies; i++){
        value = value & wire->dependencies[i]->value;
    }
    wire->value = value;
    wire->is_set = true;

    return;
}

I can try it on my test input, but now I have to determine the result manually for all &. Let’s go back to the wiring and use the new definition:

list_wires_print(list);

wire_solve(c);
printf("After solving c:\n");
list_wires_print(list);

I should have values for c, bb and a, but not for dd, which is not necessary for solving c.

After solving c:
List of 6 wires:
w123: [], value=123
w4: [], value=4
c: [a,bb,], value=4
dd: [c,w123,], value=?
bb: [w4,], value=4
a: [bb,], value=4

Which… well, I see that I didn’t write my example properly, I only made a depend on bb. Adding:

void test_dependency_map(){
    //...
    wire_t* w3 = wire_create("w3", (uint16_t) 3, true);

    //...
    list_wires_add(list, w3);

    //...
    wire_add_dependency(a, w3);
}

List of 7 wires:
w123: [], value=123
w4: [], value=4
c: [a,bb,], value=0
dd: [c,w123,], value=?
bb: [w4,], value=4
a: [bb,w3,], value=0
w3: [], value=3

Looks good to me. Not the cleanest test, but I think we have a good shot at solving this… Once we store the operation and parse the input…

All operations

We’ll store the operations as integers, so let’s define them first, adding a NOOP for the wires where the value is set directly:

#define NOOP 0
#define LOGICAL_AND 1
#define LOGICAL_OR 2
#define LSHIFT 3
#define RSHIFT 4
#define LOGICAL_NOT 5

struct wire_t {
    // ...
    int operation;
};

wire_t* wire_create(char* name, uint16_t value, int operation, bool is_set){
    if (operation < 0 || operation > 5){
        printf("ERROR: invalid operation");
        exit(1);
    }
    // ...
    wire->operation = operation;
    // ...
}

wire_t* w123 = wire_create("w123", (uint16_t) 123, NOOP, true);
wire_t* w4 = wire_create("w4", (uint16_t) 4, NOOP, true);
wire_t* c = wire_create("c", 0, LOGICAL_AND, false);
wire_t* dd = wire_create("dd", 0, LOGICAL_OR, false);
wire_t* bb = wire_create("bb", 0, NOOP, false);
wire_t* a = wire_create("a", 0, LSHIFT, false);
wire_t* w3 = wire_create("w3", (uint16_t) 3, NOOP, true);

We don’t take the operations into account yet, but everything runs. I don’t really like how we set the operation before the dependencies, but I don’t see an easy way to avoid that yet. I’ll think about it later. Let’s put the operations in their own little function now to make things easier.

void dependencies_and(wire_t* wire){
    uint16_t value = wire->dependencies[0]->value;
    for (int i = 1; i < wire->n_dependencies; i++){
        value = value & wire->dependencies[i]->value;
    }
    wire->value = value;
    wire->is_set = true;
}
void dependencies_or(wire_t* wire){
    uint16_t value = wire->dependencies[0]->value;
    for (int i = 1; i < wire->n_dependencies; i++){
        value = value | wire->dependencies[i]->value;
    }
    wire->value = value;
    wire->is_set = true;
}
void dependencies_lshift(wire_t* wire){
    if (wire->n_dependencies != 2){
        printf("ERROR: LSHIFT needs exactly two operands\n");
        exit(1);
    }

    wire->value = wire->dependencies[0]->value << wire->dependencies[1]->value;
    wire->is_set = true;
}
void dependencies_rshift(wire_t* wire){
    if (wire->n_dependencies != 2){
        printf("ERROR: RSHIFT needs exactly two operands\n");
        exit(1);
    }

    wire->value = wire->dependencies[0]->value >> wire->dependencies[1]->value;
    wire->is_set = true;
}
void dependencies_not(wire_t* wire){
    if (wire->n_dependencies != 1){
        printf("ERROR: NOT needs exactly one operand\n");
        exit(1);
    }

    wire->value = ~wire->dependencies[0]->value;
    wire->is_set = true;
}
void dependencies_noop(wire_t* wire){
    if (wire->n_dependencies == 1){
        wire->value = wire->dependencies[0]->value;
    }
}

Not loving that at all, some refactoring will probably be needed later. But I fear I’m too close to actually solving the puzzle to resist moving forward.

void wire_solve(wire_t* wire){
    // ...
    if (wire->operation == NOOP)
        dependencies_noop(wire);
    else if (wire->operation == LOGICAL_AND)
        dependencies_and(wire);
    else if (wire->operation == LOGICAL_OR)
        dependencies_or(wire);
    else if (wire->operation == LSHIFT)
        dependencies_lshift(wire);
    else if (wire->operation == RSHIFT)
        dependencies_rshift(wire);
    // ...
}

Let’s try solving for dd this time, since that’s what I computed manually for my test before. I get a value of 123, which is what I was expecting. Great!