Day 7, part 4 - Caution: refactoring needed

Advent of Code 2015

Adrien Foucart

2026-03-11

[Back to index]

Puzzle: https://adventofcode.com/2015/day/7

My solution: https://codeberg.org/adfoucart/aocode15/src/branch/main/src/day7.c

I though I would get the solution in part 3, but I made a critical mistake in my design, which means I need to refactor now.

The problem

Here is my wire_t definition:

struct wire_t {
    char* name;
    uint16_t value;
    struct wire_t** dependencies;
    int n_dependencies;
    int capacity;
    int operation;
    bool is_set;
};
typedef struct wire_t wire_t;

It holds a list of dependencies as pointers to other wires. However, when I’m parsing the instructions to create the wires, I don’t have the pointer to the dependencies, I only have their names. And the corresponding wires may or may not yet have been created. Also my parse_instructions code has become kind of a mess and crashes. So we need to step back a little bit. Let’s reset parse_instructions to something that doesn’t crash first.

wire_t* parse_instruction(char* instruction){
    str_list_t* instr_list = parse_strings_with_string(instruction, " -> ");
    printf("%s :: %s\n", instr_list->str_list[0], instr_list->str_list[1]);

    char* ops = instr_list->str_list[0];
    char* wire_name = instr_list->str_list[1];

    printf("Wire found: %s -> %s\n", ops, wire_name);

    return NULL;
}

And find_value:

uint16_t find_value(char* input, char* wire){
    str_list_t* instructions = parse_strings(input, '\n');
    for (int i=0; i < instructions->n; i++){
        if (strlen(instructions->str_list[i]) == 0)
            continue;
        // printf("%s\n", instructions->str_list[i]);
        wire_t* wire = parse_instruction(instructions->str_list[i]);
        if (wire != NULL){
            wire_print(wire);
        }
    }

    str_list_destroy(instructions);
    return 0;
}

This works.

Refactoring the wires

Let’s change the dependencies from wire_t** to char**, storing the names of the wires.

typedef struct {
    char* name;
    uint16_t value;
    char** dependencies;
    int n_dependencies;
    int capacity;
    int operation;
    bool is_set;
} wire_t;

In the create code, change the corresponding malloc:

wire_t* wire_create(char* name, uint16_t value, int operation, bool is_set){
    // ...
    wire->dependencies = malloc(sizeof(char*)*wire->capacity);
    // ...
}

And in the print code:

void wire_print(wire_t* wire){
    // ...
        printf("%s,", wire->dependencies[i]);
    // ...
}

And finally the add_dependency method:

void wire_add_dependency(wire_t* output, char* input){
    if (output->n_dependencies == output->capacity){
        output->dependencies = realloc(output->dependencies, sizeof(char*)*output->capacity*2);
        output->capacity *= 2;
    }
    output->dependencies[output->n_dependencies] = input;
    output->n_dependencies++;
}

Now I comment out all the solver code, as it will need to be updated, and run the test_dependency_map code without the solver:

void test_dependency_map(){
    list_wires_t* list = list_wires_create(6);
    
    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);

    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);
    list_wires_add(list, w3);

    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");
    wire_add_dependency(a, "w3");

    list_wires_print(list);
    list_wires_destroy(list);
}

Everything is fine.

Updating the solver

The solver will now need access to the list of wires, as we’ll need to find the right wire based on the name. Ideally, I’d need a dictionary-like structure, but given how long I’ve already spent on this puzzle I’ll leave it extremely inefficient for now. Let’s make a finder function in the list.

wire_t* list_wires_find(list_wires_t* list, char* name){
    for (int i=0; i < list->n; i++){
        if (list->wires[i]->name == name){
            return list->wires[i];
        }
    }
    return NULL;
}

Does == work on strings like that? Quick test:

void test_dependency_map(){
    // ...
    wire_t* bb = wire_create("bb", 0, NOOP, false);
    // ...
    assert(list_wires_find(list, "bb") != NULL, "found bb wire in list");
    // ...
}

FAIL. I thought so, but I wanted to check. == checks if the address is the same. For a “logical” comparison, I need strcmp.

// ...
if (strcmp(list->wires[i]->name, name)){
    return list->wires[i];
}
// ...

Now, in the solver, I need access to the list alongside the wire to solve. Then we need to find all the wires from the names in the dependencies, and pass them along to the operation functions:

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

    wire_t** dependencies = malloc(sizeof(wire_t*)*wire->n_dependencies);
    for (int i=0; i < wire->n_dependencies; i++){
        dependencies[i] = list_wires_find(list, wire->dependencies[i]);
    }

    for (int i = 0; i < wire->n_dependencies; i++)
        if (!dependencies[i]->is_set)
            wire_solve(list, dependencies[i]);
    
    if (wire->operation == NOOP)
        dependencies_noop(wire, dependencies);
    // ...

    return;
}

And of course the operations need to be updated as well. For instance:

void dependencies_and(wire_t* wire, wire_t** dependencies){
    uint16_t value = dependencies[0]->value;
    for (int i = 1; i < wire->n_dependencies; i++){
        value = value & dependencies[i]->value;
    }
    wire->value = value;
    wire->is_set = true;
}

Adding back the solve in the test code:

// ...
wire_solve(list, dd);
// ...

I get the results:

w123: [], value=123 : operation=0
w4: [], value=4 : operation=0
c: [a,bb,], value=? : operation=1
dd: [c,w123,], value=127 : operation=2
bb: [w4,], value=? : operation=0
a: [bb,w3,], value=? : operation=3
w3: [], value=3 : operation=0

This didn’t work. The value of dd should be 123, and c, a and bb should be set. Some printf later, it seems that it’s finding w123 and w4 as dependencies when trying to solve, instead of w123 and c. The strings in dependencies are correct, so list_wire_find doesn’t return the right one.

And that is, of course, because I once again failed to RTFM. The return value of strcmp is 0 if the two strings are equal, negative if the first appears before the second in lexicographical order, and positive if it appears after.

So I need:

// ...
if (strcmp(list->wires[i]->name, name) == 0)
// ...

And now it works:

w123: [], value=123 : operation=0
w4: [], value=4 : operation=0
c: [a,bb,], value=0 : operation=1
dd: [c,w123,], value=123 : operation=2
bb: [w4,], value=4 : operation=0
a: [bb,w3,], value=32 : operation=3
w3: [], value=3 : operation=0

On to the test input?

Updating the parser

parse_instructions will need access to the list now.

wire_t* parse_instruction(list_wires_t* list, char* instruction){
    // ...
}

List which I haven’t even created yet in find_value, so let’s add that:

uint16_t find_value(char* input, char* wire){
    str_list_t* instructions = parse_strings(input, '\n');
    list_wires_t* list = list_wires_create(instructions->n);
    for (int i=0; i < instructions->n; i++){
        // ...
        wire_t* wire = parse_instruction(list, instructions->str_list[i]);
        // ...
    }
    // ...
}

I already split the “operation” from the “wire name”. Let’s now make sure that we parse the operation properly, starting with “NOT”:

wire_t* parse_instruction(list_wires_t* list, char* instruction){
    str_list_t* instr_list = parse_strings_with_string(instruction, " -> ");

    char* ops = instr_list->str_list[0];
    char* wire_name = instr_list->str_list[1];

    if (strstr(ops, "NOT") != NULL){
        char* operand_start = ops+strlen("NOT ");
        char* operand_end = ops+strlen(ops);
        char* dependency = strcpy_between(operand_start, operand_end);
        wire_t* wire = wire_create(wire_name, 0, LOGICAL_NOT, false);
        wire_add_dependency(wire, dependency);
        return wire;
    }

    return NULL;
}

Using my strcpy_between code from the parser. This seems to work, in find_value:

wire_t* wire = parse_instruction(list, instructions->str_list[i]);
if (wire != NULL){
    wire_print(wire);
}

I now get the right output for the NOT wires. On to the next operations.

AND:

char* and = strstr(ops, "AND");
if (and != NULL){
    char* firstop_start = ops;        
    char* firstop_end = and-1;
    char *firstop = strcpy_between(firstop_start, firstop_end);
    char *secondop_start = and + strlen("AND ");
    char *secondop_end = ops + strlen(ops);
    char *secondop = strcpy_between(secondop_start, secondop_end);
    wire_t* wire = wire_create(wire_name, 0, LOGICAL_AND, false);
    wire_add_dependency(wire, firstop);
    wire_add_dependency(wire, secondop);
    return wire;
}

OR has the same logic.

LSHIFT and RSHIFT have the added complexity of having to add the “value” wires.

char* lshift = strstr(ops, "LSHIFT");
if (lshift != NULL){
    char* firstop_start = ops;        
    char* firstop_end = lshift-1;
    char *firstop = strcpy_between(firstop_start, firstop_end);
    char *secondop_start = lshift + strlen("LSHIFT ");
    char *secondop_end = ops + strlen(ops);
    char *secondop = strcpy_between(secondop_start, secondop_end);
    wire_t* val_wire = wire_create(secondop, atoi(secondop), NOOP, true);
    list_wires_add(list, val_wire);

    wire_t* wire = wire_create(wire_name, 0, LSHIFT, false);
    wire_add_dependency(wire, firstop);
    wire_add_dependency(wire, secondop);
    return wire;
}

Finally, if we haven’t found any of the keywords, we are just looking at an input wire.

wire_t* wire = wire_create(wire_name, atoi(ops), NOOP, true);
return wire;

Testing on the test input:

assert(find_value(instructions, "i")==(uint16_t) 65079, "test input works");

Works. Another wire:

assert(find_value(instructions, "d")==(uint16_t) 72, "test input works");

Also works. Time to try it out for real.

Attempt at solution

Modify the main:

int main(){
    char *instructions = freadall(INPUT_FILE);
    uint16_t val = find_value(instructions, "a");
    printf("Solution for wire a: %d", val);
}

I get… 0? Checking the input:

lx -> a

Which is a case I didn’t know was possible: we assign directly the value of another wire. When I don’t see an operation, I assume that we are setting a value, but that’s not the case here.

atoi returns 0 if the string cannot be converted to int. Unfortunately, I do have a 0 -> c in the definitions, so I can’t just assume that “if I get a 0, it’s a name”. Sigh.

All the wire names are lower case letters. Let’s check the first character: if it’s higher than 57, which encodes 9, then it’s not a number:

if (ops[0] > 57){
    wire_t* wire = wire_create(wire_name, 0, NOOP, false);
    wire_add_dependency(wire, ops);
    return wire;
}
wire_t* wire = wire_create(wire_name, atoi(ops), NOOP, true);
return wire;

I get an answer! And it’s the right one. Finally.

I guess I should update my status to: still learning…

Part two

Part two has a very short description:

Now, take the signal you got on wire a, override wire b to that signal, and reset the other wires (including wire a). What new signal is ultimately provided to wire a?

Can I do that easily with my setup?

Let’s start by detaching the “build wire setup” from the solver.

list_wires_t* list_wire_create_from_instr(char *input){
    str_list_t* instructions = parse_strings(input, '\n');

    list_wires_t* list = list_wires_create(instructions->n);
    for (int i=0; i < instructions->n; i++){
        if (strlen(instructions->str_list[i]) == 0)
            continue;

        wire_t* wire = parse_instruction(list, instructions->str_list[i]);
        if (wire != NULL){
            wire_print(wire);
            list_wires_add(list, wire);
        }
    }

    str_list_destroy(instructions);
    return list;
}

Change find_value to take the list as input:

uint16_t find_value(list_wires_t* list, char* solve){
    // ...
}

And change the main to set and destroy the list there:

list_wires_t* list = list_wire_create_from_instr(instructions);     
uint16_t val = find_value(list, "a");
printf("Solution for wire a: %d", val);
list_wires_destroy(list);

Now we need to:

for (int i = 0; i < list->n; i++){
    if (list->wires[i]->n_dependencies != 0)
        list->wires[i]->is_set = false;
    if (strcmp(list->wires[i]->name, "b") == 0){
        list->wires[i]->value = val;
        list->wires[i]->is_set = true;
    }
}

uint16_t val2 = find_value(list, "a");
printf("Solution for wire a: %d\n", val2);

And this, amazingly, also works.