Day 7, part 1

Instructions put values into “wires”. The values are either integers, or the result of a logical operation on one or two other wires. All values are encoded in 16-bit. In the above example:

We have of course in the real input many more instructions, and need to find the value on one particular wire at the end.

Checking binary operations

First, we quickly make the test for the example input, just to have something to look at. We’ll certainly need futils and parser, so we include them. If I understand the Wiki on integer types in C correctly, I also need <stdint.h> to be able to use int16_t and have 16 bits integer, which is exactly what we need.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include "futils.h"
#include "parser.h"
#include "testutils.h"

#define TEST_INPUT "123 -> x\n456 -> y\nx AND y -> d\nx OR y -> e\nx LSHIFT 2 -> f\ny RSHIFT 2 -> g\nNOT x -> h\nNOT y -> i\n"

int16_t find_value(char* input, char* wire){
    return 0;
}

void run_test(){
    char instructions[] = TEST_INPUT;
    assert(find_value(instructions, "d")==(int16_t) 65079, "test input works");
}

int main(){
    run_test();
}

We’ll sort out the representation later. First, I want to test the operations:

void test_binary_ops(){
    int16_t x = 123;
    int16_t y = 456;

    int16_t d = x & y;
    assert(d == (int16_t) 72, "bitwise AND");

    int16_t e = x | y;
    assert(e == (int16_t) 507, "bitwise AND");

    int16_t f = x << 2; 
    assert(f == (int16_t) 492, "x << 2");

    int16_t g = y >> 2; 
    assert(g == (int16_t) 114, "x >> 2");

    int16_t h = !x;
    assert(h == (int16_t) 65412, "NOT x");

    int16_t i = !y;
    assert(i == (int16_t) 65079, "NOT y");
}

The NOT are not working. That’s because I didn’t use the correct operator. It’s ~, not ! in C. My bad. Fixed.

Dependency map

So the operations won’t be a problem. The real input, however, is not as simple as the test one, and it cannot be solved in the order of the instructions. We first need to determine the dependency graph: which wires depend on which wire, so that we can find which one are “solvable” and then propagate their value. Also, the wires can have multiple characters in their name, let’s not forget about that.

I think I’d like to build a small example to test these things, just to be sure. Something like:

I’d like to keep track, for each wire, of its dependencies. In my example, something like:

I could also track if they “have a value”, and put the initial values in their own wires for convenience. Let’s imagine something like:

Then we can go through the list and check if all their dependencies have values. If so, we solve. So we’d have a first round:

To be a little bit efficient, this should be in a dictionary-type structure for easy access per-wire name. Which means that I should implement a hash table, maybe?

Let’s first define a wire, according to our little “design” above. I attempt this:

struct wire_t {
    char* name;
    uint16_t value;
    struct wire_t* dependencies;
    int n_dependencies;
};
typedef struct wire_t wire_t;

I noticed along the way that I had used the wrong type for my integers. I need uint16_t for values between 0 and 65535.

Because of the self-reference to wire_t*, it seems that I need to do this “two-step” declaration with first the struct, then the typedef, otherwise the compiler doesn’t like it. Having direct reference to the dependencies mean that I don’t need another data structure for easy access when checking if their values are set, so maybe the hash table won’t be needed. I don’t know yet.

Now I want to try to build the dependency map based on my example and see if it looks reasonable, and which methods will be necessary.

wire_t* wire_create(char* name, uint16_t value){
    wire_t* wire = malloc(sizeof(wire_t));
    wire->name = malloc(strlen(name)+1);
    strcpy(wire->name, name);
    wire->n_dependencies = 0;
    wire->value = value;
    return wire;
}

void wire_destroy(wire_t* wire){
    free(wire->name);
    free(wire->dependencies);
    free(wire);
}

void test_dependency_map(){
    wire_t* w123 = wire_create("w123", (uint16_t) 123);
    wire_t* w4 = wire_create("w4", (uint16_t) 4);
    wire_t* c = wire_create("c", NULL);
    wire_t* dd = wire_create("dd", NULL);
    wire_t* bb = wire_create("bb", NULL);
    wire_t* a = wire_create("a", NULL);

    wire_destroy(w123);
    wire_destroy(w4);
    wire_destroy(c);
    wire_destroy(dd);
    wire_destroy(bb);
    wire_destroy(a);
}

I have a problem: I can’t set uint16_t to NULL. A perfectly reasonable point from my compiler, even though it annoys me. I think I need a boolean to track if the wire is set, then I can put the value to 0 if not.

// ...
wire_t* w4 = wire_create("w4", (uint16_t) 4, true);
wire_t* c = wire_create("c", 0, false);
// ...

It compiles. I don’t know if it works yet, but it compiles! Now we have to be able to add a dependency.

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

Here I am reallocating memory each time I add a dependency, which is probably not ideal. I should just do the “start with a little bit of space, double when needed” strategy. Add to create:

wire->dependencies = malloc(sizeof(wire_t*)*8);

And change add_dependency. Wait no, I also need a capacity now, otherwise I don’t know how much memory is currently allocated – and thus if I need to grow. Back to create:

wire->capacity = 8;
wire->dependencies = malloc(sizeof(wire_t*)*wire->capacity);

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

Compiling breaks, because dependencies should actually be wire_t**, not wire_t*: I need an array of pointers. Fixed, so I can now try to set those dependencies.

void test_dependency_map(){
    // ...
    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);
    // ...
}

void wire_print(wire_t* wire){
    printf("%s: [", wire->name);
    for (int i=0; i < wire->n_dependencies; i++){
        printf("%s,", wire->dependencies[i]->name);
    }
    printf("], value=");
    if (wire->is_set)
        printf("%d", wire->value);
    else
        printf("?");
    printf("\n");
}

This, however, will need to wait. I think that’s already a good start, and enough for today. I’ll put a break here, and continue later!