Day 7, part 3 - Solutions?

In part 1, I made wires and encoded dependencies between them. In part 2, I added lists of wires, operations, and a solver. What we are still lacking is a parser.

Parsing rules

Let’s take a look back at what our input looks like. The test input, that is, the real one for me has 339 instructions.

Every line corresponds to one wire’s output, at the right side of the ->. So: first parse by new line (we can do that), then parse by -> (we can do that as well). The second term of that last split gives us the wire name. The left is a bit trickier, as there are three possibilities:

In the first case, the tricky part is that 2 will not have a wire definition by itself. Question: are the LSHIFT and RSHIFT operations sometimes between two wires, or always with a value?

Looking at my input: no. And the AND/OR operations are always between two wires. So that makes thing a little bit easier. Let’s set the rules:

Let’s (finally) get to it

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]);
    }

    str_list_destroy(instructions);
    return 0;
}

I realized that I hadn’t actually written a str_list_destroy, which I added to my parser code. I’m probably leaking memory everywhere in the previous days. Oops again.

Now to parse by ->, and I have a problem. My parser parses by a single char, not a string. I thought that would be a problem at some point, but then forgot about it. Now I get a reminder !

Why do I need the separator to be a char? Because I wanted to count the number of separators before starting to call strtok, so that I knew how much memory to allocate. I think I have a better understanding of strtok, memory allocation, and strings in general now than I did when I coded that, so I can probably do better.

str_list_t* parse_strings_with_string(char* str, char* sep){
    return parse_strings(str, sep[0]);
}

bool test_parse_strings_with_string(){
    char test[] = "this text :: should be parse :: into 3 lines";
    str_list_t* list = parse_strings_with_string(test, " :: ");
    return (list->n == 3);
}

Now to make the real code. How about this: we start with an initial capacity of 2, which we double when needed. At the end, we remove the unused bits of memory.

str_list_t* parse_strings_with_string(char* str, char* sep){
    char tok_start[strlen(str)+1];
    strcpy(tok_start, str);

    int capacity = 2;
    str_list_t *str_list = malloc(sizeof(str_list_t));
    str_list->n = 0;
    str_list->str_list = malloc(sizeof(char*)*capacity);

    char *buffer = strtok(tok_start, sep);
    while(buffer){
        if (str_list->n == capacity){
            capacity *= 2;
            str_list->str_list = realloc(str_list->str_list, sizeof(char*)*capacity);
        }
        str_list->str_list[str_list->n] = malloc(sizeof(char)*(strlen(buffer)+1));
        strcpy(str_list->str_list[str_list->n], buffer);
        buffer = strtok(NULL, sep);
        str_list->n++;
    }
    // remove unecessary memory
    str_list->str_list = realloc(str_list->str_list, sizeof(char*)*str_list->n);

    return str_list;
}

Trying… and the test still fails. I get… 8 substrings? Apparently I get a split on every ' ' as well as the ' :: '. Did I misunderstand what strtok does again? Let’s read the docs…

Yes I did. So much for my “better understanding” of strtok. I guess I’ll have to use strstr? After a bit of fussing around, I get to this:

char* strcpy_between(char* start, char* end){
    char *dst = malloc(end-start+1);
    memcpy(dst, start, end-start);
    dst[end-start] = '\0';
    return dst;
}

str_list_t* parse_strings_with_string(char* str, char* sep){
    int capacity = 2;
    str_list_t *str_list = malloc(sizeof(str_list_t));
    str_list->n = 0;
    str_list->str_list = malloc(sizeof(char*)*capacity);

    char *prv = str;
    char *nxt = strstr(str, sep);
    while (nxt != NULL){
        if (str_list->n == capacity){
            capacity *= 2;
            str_list->str_list = realloc(str_list->str_list, sizeof(char*)*capacity);
        }
        str_list->str_list[str_list->n] = strcpy_between(prv, nxt);

        prv = nxt+strlen(sep);
        nxt = strstr(nxt+strlen(sep), sep);
        str_list->n++;
    }
    str_list->str_list[str_list->n] = strcpy_between(prv, str+strlen(str));
    str_list->n++;

    str_list->str_list = realloc(str_list->str_list, sizeof(char*)*str_list->n);

    return str_list;
}

This appears to work. I added a test with a string without a separator, and it passes as well.

Let’s (finally (finally)) get to it

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]);

    return NULL;
}

I get the two sides correctly. The right side is the name of the wire. The left side needs to be further parsed according to our rules.

First, there is still a fair amount of pointer arithmetic to do, and it’s getting a bit late for this for me, so I’m making lots of mistakes. Second… I made a big mistake. When adding dependencies, I add wires. I thought I was clever, making a graph-like structure. But I don’t know the wire that I’m depending on yet when I’m parsing.