Day 9, part 2 - A detour

We left part 1 with a parser which creates a graph of all our nodes, but we cannot print it yet to check that it is correct. We should probably do that, before we try to solve the puzzle.

Printing the graph

To get started, we can print the starting node and the number of nodes. Our test input is:

And we set the first node in the list as the starting node, so we expect to get London. And we should have three nodes.

void graph_print(graph_t* graph){
    printf("Starting node: %s\n", graph->start->name);
    printf("Number of nodes: %d\n", graph->n);
}

void test_input(){
    char* content = freadall(TEST_INPUT_FILE);
    graph_t* graph = parse_input(content);
    graph_print(graph);
}

int main(){
    test_input();
    exit(0);
}

So far so good. Now if I want to print the rest of the graph, I have to traverse it. I think I will want to do that with some recursion, keeping track of visited nodes to avoid looping into infinity.

void traverse(node_t* node, list_node_t* visited){
    printf("Visiting %s:\n", node->name);
    list_node_add(visited, node);
    for (int i=0; i < node->n_connections; i++){
        node_t* dest = node->connections[i]->dest;
        printf("\t%s -> %s: %d\n", node->name, dest->name, node->connections[i]->dist);
        node_t* in_list = list_node_find(visited, dest->name);
        if (in_list == NULL){
            traverse(dest, visited);
        }
    }
}

void graph_print(graph_t* graph){
    printf("Starting node: %s\n", graph->start->name);
    printf("Number of nodes: %d\n", graph->n);
    list_node_t* visited = list_node_create(graph->n);
    traverse(graph->start, visited);
}

Shortest path

Now we need to think about solving the puzzle. We need to find the shortest path that goes through all nodes. I don’t think the starting point matters. Or does it? I’m suddenly unsure. My original thinking was: since the shortest path goes through all nodes, it will pass through whichever node I’m looking at, and I just “pick up” the path at that point. But that only works if I’m doing a loop and have to come back to that starting point, which I don’t have to. So it’s a bit more complicated than my original idea. That means that my earlier computation that I’d need to test 7! paths is wrong. I need 8! to account for the choice of starting point. That’s still manageable, at 40.320, but I’m a bit more uneasy.

Also, my graph structure is now a bit clunky, and I don’t really need it. I can just have parse_input return the list of nodes. Removing the graph from parse_input, let’s (sigh) create a list_node_print method to go through the list and print all connections. I’m keeping traverse for now, it’ll probably be useful in the pathfinding.

void list_node_print(list_node_t* list){
    for (int i=0; i < list->n_nodes; i++){
        printf("%s:\n", list->nodes[i]->name);
        for (int j=0; j < list->nodes[i]->n_connections; j++){
            printf("\t-> %s (%d)\n", 
                list->nodes[i]->connections[j]->dest, 
                list->nodes[i]->connections[j]->dist);
        }
    }
}

Which is not exactly what I hoped… What is happening? I was able to follow the connections before, so they should point to valid nodes, which means those nodes should have a name, since I’m printing the names in the first place!

Wait. list->nodes[i]->connections[j]->dest is not correct. I’m missing a ->name there. Let’s make the code a bit clearer on the way:

void list_node_print(list_node_t* list){
    for (int i=0; i < list->n_nodes; i++){
        node_t* node = list->nodes[i];
        printf("%s:\n", node->name);
        for (int j=0; j < node->n_connections; j++){
            printf("\t-> %s (%d)\n", 
                node->connections[j]->dest->name, 
                node->connections[j]->dist);
        }
    }
}

I think I need to look at the behaviour I want in the test sample to make things a bit more clear.

A few things I notice. First, I do have lots of repetitions. Was I wrong again in thinking I do have to try every starting point. I’m getting confused.

Imagine that the shortest path from A is ACBD. Is it possible to have something shorter starting from C? If ABCD is the shortest from A, then CBD has to be shorter than CDB. So that leaves us with CBDA or CABD.

I don’t think I can dismiss either as a possibility? Unsure. Since I can’t prove that I don’t need to check them, I’ll go through the list.

Second thing: I don’t actually need to return a path. Once it’s complete, I can return an int with its length.

First attempt

typedef struct {
    list_node_t* list;
    int total_dist;
} path_t;

path_t* path_create(node_t* start){
    path_t* path = malloc(sizeof(path_t));
    path->total_dist = 0;
    path->list = list_node_create(16);
    list_node_add(path->list, start);
}

void path_destroy(path_t* path){
    list_node_destroy(path->list);
    free(path);
}

void path_add(path_t* path, node_t* node, int dist){
    list_node_add(path->list, node);
    path->total_dist += dist;
}

We’ll have one function to go through all possible starting points, and then a recursive function to traverse the possible paths:

int find_shortest_distance(list_node_t* nodes){
    int min_dist = 1000000;
    for (int i = 0; i < nodes->n_nodes; i++){
        node_t* node = nodes->nodes[i];
        path_t* path = path_create(node);
        int min_from_node = find_shortest_distance_from_node(path, node);
        if (min_from_node < min_dist){
            min_dist = min_from_node;
        }
    }

    return min_dist;
}

And let’s start with a dummy function just to check that the first one doesn’t crash:

int find_shortest_distance_from_node(path_t* path, node_t* node){
    return 0;
}

void test_input(){
    // ...
    int min_dist = find_shortest_distance(nodes);
    printf("Shortest distance: %d\n", min_dist);
}

Break

I had to take a bit of a break. I got stuck with a weird bug, then I had other stuff to do, and now we’re one month later and I don’t remember what I was trying to do or how, so let’s regroup and try to go again from here. I’m trying to find the shortest distance to traverse all nodes. The algorithm, which I think should work, is:

I have clearly not tested enough my existing functions, so we need to make sure that everything is working as expected before we move on. Adding a path_print method to debug the paths:

void path_print(path_t* path){
    printf("Path with total distance = %d:\n", path->total_dist);
    for (int i=0; i < path->list->n_nodes; i++){
        printf("\t* %s\n", path->list->nodes[i]->name);
    }
}

And in find_shortest_distance, we start by just creating the path from a starting node and printing it.

int find_shortest_distance(list_node_t* nodes){
    int min_dist = 1000000;
    for (int i = 0; i < nodes->n_nodes; i++){
        node_t* node = nodes->nodes[i];
        path_t* path = path_create(node);
        path_print(path);
    }

    return min_dist;
}

We should get, for each node in the graph, paths with total distance 0 and one starting node. Instead, we get:

And then it crashes on trying to print the nodes. Checking path_create… and I forgot to return the path. Fixing it, it works. I’m amazed that it crashed only on trying to go through the list of nodes and not on path->total_dist. C really lets you screw up a lot. Anyway.

I can now get onto the recursive function to get the shortest path from a node through all unexplored nodes. I need a method to check if a path already contains a node:

bool path_contains(path_t* path, node_t* node){
    for (int i=0; i < path->list->n_nodes; i++)
        if (path->list->nodes[i] == node)
            return true;
    return false;
}

path_t* path_clone(path_t* path){
    path_t* clone = malloc(sizeof(path_t));
    clone->total_dist = path->total_dist;
    clone->list = list_node_create(path->list->capacity);
    for (int i = 0; i < path->list->n_nodes; i++){
        list_node_add(clone->list, path->list->nodes[i]);
    }
    return clone;
}

Now the recursive function. We go through all the connections from a node. If the connection doesn’t lead to a node that is already in the path, we clone the path, add the destination and add to the total distance, then call the function recursively from the destination and return the minimum distance we find between those connections. If no node is unvisited, we return the current total_dist of the path.

int find_shortest_distance_from_node(path_t* path, node_t* node){
    printf("From: %s (current dist: %d)\n", node->name, path->total_dist);
    printf("Path contains %d nodes", path->list->n_nodes);
    printf("\n");
    int min_dist = -1;
    for (int i=0; i < node->n_connections; i++){
        printf("\tlooking towards %s\n", node->connections[i]->dest->name);
        if (path_contains(path, node->connections[i]->dest)){
            printf("\t\talready in. skipping.\n");
            continue;
        }
        // clone path
        path_t* newpath = path_clone(path);
        path_add(newpath, node->connections[i]->dest, node->connections[i]->dist);
        int further = find_shortest_distance_from_node(newpath, node->connections[i]->dest);
        if (min_dist < 0 || further < min_dist){
            min_dist = further;
        }
        path_destroy(newpath);
    }
    if (min_dist < 0)
        return path->total_dist;

    return min_dist;
}

This gives me 605 on the test data, which is correct. Trying on the real input… and it crashes. When parsing it? That’s unexpected. Somehow the empty line at the end of the file has a strlen of 16 instead of 0? Removing the blank line, it works, and very quickly gives me the right answer, so that’s nice, but I’d still like to understand why it failed.

Adding some debugging code to my parse_strings method to look at the part where we iterate through the occurrences of the separating character (\n in our case). It’s the last line, line 28, which causes a problem, so let’s see what’s in the buffer there:

char *buffer = strtok(tok_start, sep_s);
int i = 0;
while(buffer){
    str_list->str_list[i] = malloc(sizeof(char)*(strlen(buffer)+1));
    printf("-- debug line=%d strlen(buffer)=%d\n", i, strlen(buffer));
    if (i==28){
        printf("buffer=%s\n", buffer);
    }
    strcpy(str_list->str_list[i], buffer);
    buffer = strtok(NULL, sep_s);
    i++;
}

I get buffer=E=SURFACE-ADRIEN. I am running this on my Surface right now, so… I’m probably doing some very unsafe memory handling somewhere. I need to investigate before moving on. So let’s put a break here and come back to that in part 3…