Day 9, part 1 - A short trip

The traveling salesman problem is known to be a little bit computationally expensive to solve. Since we can start from any node, and then we can visit the nodes in any order, the amount of combinations to test very quickly skyrocket.

So before we go any further, I’ll take a closer look at my real puzzle input, to get a sense of the complexity.

Let’s start from a simpler example with four nodes to get a better sense of the problem.

Starting from A, I have three choices. From each destination, I get two remaining choices, etc. SO I have (N − 1)! possible paths. Here:

Since in my input I have 8 nodes, that means 7! paths to check, or 5040. That… doesn’t seems too bad. No trick needed so far, so let’s go for the brute force.

Weighted graph

We start by defining a data structure. I think I want to have a graph which has a pointer to an arbitrary starting node, and which knows how many nodes there are. Each node should hold a list of (pointers to) connections, which have a pointer to another node and a weight. Something like:

typedef struct connection_t connection_t;
typedef struct node_t node_t;
typedef struct graph_t graph_t;

struct connection_t {
    node_t* dest;
    int dist;
};

struct node_t {
    char* name;
    connection_t** connections;
    int n_connections;
    int capacity;
};

struct graph_t {
    node_t* start;
    int n;
};

With connection_create, node_create, graph_create, and the corresponding destroy. We’ve gone through this before, and I’m sure I’ll still screw it up somehow, so we’ll quickly have to move on to some sort of test. Do I want to directly parse the test input? I think so. Day 7 showed me how some design choices become a lot easier to make once we are actively trying to make the input fit into the data structure.

Parsing time

So let’s go back to the test input and think about the order that we get the information, and what we can do with it.

Splitting by “=” and by “to”, we can easily get two node names, knowing that they are connected, and with the weight of the connection. The nodes could be new nodes, in which case we want to create them, or exist, in which case we want to add the connection to them. Which means that we need a set of nodes in addition to our graph. Ideally with direct access to a node by its name. Should I take the opportunity to implement a hash map? I don’t think I want to go there yet, maybe as a refactoring step. Let’s start by a simple list, even if we need to go through all of it to know if it contains a node.

typedef struct {
    node_t** nodes;
    int n_nodes;
    int capacity;
} list_node_t;

Almost forgot to put the two * there but caught myself: we want a list of pointers, not a list of nodes. In addition to the create, destroy and add, we need a way to find a node by name:

node_t* list_node_find(list_node_t* list, char* name){
    for (int i = 0; i < list->n_nodes; i++){
        if (strcmp(list->nodes[i]->name, name) == 0)
            return list->nodes[i];
    }
    return NULL;
}

I have now developed a lot of stuff without tests, which means that I’m probably going to run into some problems soon. But everything compiles, so it should be fine, right? Let’s start working on the parse_input and see where it will all break.

graph_t* parse_input(char* input){
    graph_t* graph = graph_create();
    list_node_t* list = list_node_create(16);

    return graph;
}

graph_t* parse_input(char* input){
    // ...
    str_list_t* instructions = parse_strings(input, '\n');
    for (int i=0; i < instructions->n; i++){
        char* instr = instructions->str_list[i];
        if (strlen(instr) == 0)
            continue;
        str_list_t* parsed_line = parse_strings_with_string(instr, " = ");
        if (parsed_line->n != 2){
            printf("error: invalid line: %s", instr);
            exit(1);
        }
        int w = atoi(parsed_line->str_list[1]);
        char *nodes = parsed_line->str_list[0];
        str_list_t* nodes_str = parse_strings_with_string(nodes, " to ");
        if (nodes_str->n != 2){
            printf("error: invalid nodes: %s", nodes);
            exit(1);
        }
        char* nodeA_str = nodes_str->str_list[0];
        char* nodeB_str = nodes_str->str_list[1];
        printf("%s -> %s (%d)\n", nodeA_str, nodeB_str, w);

        str_list_destroy(nodes_str);
        str_list_destroy(parsed_line);
    }

    str_list_destroy(instructions);
    // ...
}

The output is correct, I can parse everything. I haven’t touched my nodes yet though, so I don’t know if anything I’ve done before works. How do I do this?

// ...
node_t* nodeA = list_node_find(list, nodeA_str);
node_t* nodeB = list_node_find(list, nodeB_str);
if (nodeA == NULL){
    nodeA = node_create(nodeA_str);
    list_node_add(list, nodeA);
}
if (nodeB == NULL){
    nodeB = node_create(nodeB_str);
    list_node_add(list, nodeB);
}
connection_t* AtoB = connection_create(nodeB, w);
connection_t* BtoA = connection_create(nodeA, w);
// ...

void node_add_connection(node_t* node, connection_t* conn){
    if (node->n_connections == node->capacity){
        node->capacity *= 2;
        node->connections = realloc(node->connections, sizeof(connection_t*)*node->capacity);
    }

    node->connections[node->n_connections] = conn;
    node->n_connections++;
}

//...
node_add_connection(nodeA, AtoB);        
node_add_connection(nodeB, BtoA);
// ...

// ...
graph->start = list->nodes[0];
graph->n = list->n_nodes;

return graph;

Everything runs, but I don’t have a way of checking what’s in my graph yet. That will be for tomorrow: let’s put a break here.

Thinking time

Weighted graph

Parsing time