Day 13 - Taking a seat

For most of the puzzles so far, I’ve focused more on the “learning how to C” side of things and less on the puzzle-solving part, but this may need to change here. This looks very similar to day 9: we have a bunch of nodes (this time, people sitting at a table), and connections between those node have a certain cost (the “happiness gains” or “losses”). We have to find the best seating arrangement, a.k.a. the circular graph with the most total happiness. The input looks like this:

Thinking time

My first thought is that the “two-ways” definition of the gains and losses doesn’t really matter here. We can reduce those statements to net gains or losses per pair, as if Alice sits next to Bob, Bob necessarily sits next to Alice. So the first step would be to go from the above to:

Since the graph is circular, we can place any person as the “first” seat. Let’s put Alice there. Now how do we choose where to put the others?

If I put Bob and Carol, I have so far a net happiness of -4. If I put Bob and David, +181. Carol and David, -97. So Bob and David seem better:

That leaves us with Carol at the end, meaning that we add a Bob-Carol and a David-Carol connection, worth +53 and +96.

That’s the optimal seating for this example, but I don’t think the reasoning I used here is good enough to guarantee the result when we have more guests. In the real puzzle input, I have eight guests.

There are 8! permutations, but many of those are equals: all “rotations” (ABCDEFGH is the same as BCDEFGHA, etc.) and all “inversions” (ABCDEFGH is the same as HGFEDCBA). So if I’m not mistaken, I should have 7!/2 real permutations: all permutations with A as an arbitrary start, divided by 2 to remove the reverse (even when we start with A: ABCDEFGH is the same as AHGFEDCB). 7! is just 5040, so that would mean 2520 things to test. That’s not bad, as long as we can properly generate those distinct solutions to test.

Coding time: parsing

I’ll first need to parse the input. From previous puzzles, I have a function freadall to read the whole file, and a function parse_strings to split a string into a str_list_t, which is a simple table of strings, using a separating character. Usually \n, which it will be here. Then I need to find the pairs, the happiness gain/loss, and to put both directions of the pairings together (Alice-Bob with Bob-Alice). I don’t really need the full names, I can use the first letter (that holds in the true input), so I actually need the first character of each line and the first character after the last space. As for the number, it’s the integer value of what’s between the third and fourth spaces, with a minus sign if the letter before the third space is e. That should do it, the rest of the string may be ignored.

How to best store those values? I think a graph-like structure, similar to day 9, would be suitable. From each node, we can store the “bidirectional” happiness factor with all potential neighbours. Finding the best arrangement would then become almost identical, I think, to finding the best way through all the nodes. The only difference is that we also have to take into account the last node wrapping into the first. And that we are searching for maximum happiness instead of minimum distance, of course.

Let’s start with the parsing. I think we can use strchr and strrchr to find the spaces that we need. I’m not sure yet exactly what the parsing function will return, so we’ll first just print things out to check that we retrieve the right info, starting with the “node names”.

void parse_input(char* fname){
    char* content = freadall(fname);
    str_list_t* list = parse_strings(content, '\n');

    for (int i = 0; i < list->n; i++){
        char* s = list->str_list[i];
        if (strlen(s) == 0) continue;
        char from = s[0];
        char* last_space = strrchr(s, ' ');
        char to = *(last_space+1);
        printf("%c -> %c\n", from, to);
    }
}

Good. Now the happiness gain/lost. I want to find the third and fourth space, copy what’s in between to a new null-terminated string, and use atoi to convert it to an integer, checking if the word before ends with an e while we’re there to flip the sign if necessary:

int find_happiness_score(char* s){
    // find third and fourth space
    char *third = s;
    char *fourth;
    for (int i=0; i < 3; i++){
        third = strchr(third, ' ')+1;
    }
    fourth = strchr(third, ' ');

    // copy what's in between, with added null character
    char i_string[fourth-third+1];
    memcpy(i_string, third, fourth-third);
    i_string[fourth-third] = '\0';
    
    // convert to int
    int i = atoi(i_string);

    // check sign
    if (*(third-2) == 'e') i *= -1;
    
    return i;
}

// ...
        int h = find_happiness_score(s);
        printf("%c -> %c [%d]\n", from, to, h);
// ...

Which seems correct. Obviously I’m just assuming here that the strings are always well formatted as in the example, but in a puzzle context I think that’s fair.

Copy/pasting time: nodes

Let’s grab all the nodes and connections stuff from day 9. The only thing I’ve changed is that connection_t will have a score instead of a dist, and that the node names will be chars instead of char*s.

typedef struct connection_t connection_t;
typedef struct node_t node_t;

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

connection_t* connection_create(node_t* dest, int score){
    connection_t* connection = malloc(sizeof(connection_t));
    connection->dest = dest;
    connection->score = score;
}

void connection_destroy(connection_t* connection){
    free(connection);
    // don't delete node!
}

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

node_t* node_create(char name){
    node_t* node = malloc(sizeof(node_t));
    node->name = name;
    node->capacity = 8;
    node->n_connections = 0;
    node->connections = malloc(sizeof(connection_t*)*node->capacity);
    return node;
}

void node_destroy(node_t* node){
    for (int i=0; i < node->n_connections; i++)
        connection_destroy(node->connections[i]);
    free(node->connections);
    free(node);
}

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++;
}

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

list_node_t* list_node_create(int initial_capacity){
    list_node_t* list = malloc(sizeof(list_node_t));
    list->capacity = initial_capacity;
    list->n_nodes = 0;
    list->nodes = malloc(sizeof(node_t*)*initial_capacity);
}

void list_node_destroy(list_node_t* list){
    free(list->nodes); // don't free the nodes?
    free(list);
}

void list_node_add(list_node_t* list, node_t* node){
    if (list->n_nodes == list->capacity){
        list->capacity *= 2;
        list->nodes = realloc(list->nodes, sizeof(node_t*)*list->capacity);
    }

    list->nodes[list->n_nodes] = node;
    list->n_nodes++;
}

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

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

Coding time: making the graph

Modifying parse_input to start building the graph as we encounter node. Every time, we check if it was already there, and we create the connections.

void parse_input(char* fname){
    char* content = freadall(fname);
    str_list_t* list = parse_strings(content, '\n');
    list_node_t* nodes = list_node_create(ceil(sqrt(list->n)));

    for (int i = 0; i < list->n; i++){
        char* s = list->str_list[i];
        if (strlen(s) == 0) continue;
        char from = s[0];
        char* last_space = strrchr(s, ' ');
        char to = *(last_space+1);
        int h = find_happiness_score(s);

        node_t* node_from = list_node_find(nodes, from);
        if (node_from == NULL){
            node_from = node_create(from);
            list_node_add(nodes, node_from);
        }
        node_t* node_to = list_node_find(nodes, to);
        if (node_to == NULL){
            node_to = node_create(to);
            list_node_add(nodes, node_to);
        }
        node_add_connection(node_from, connection_create(node_to, h));
        node_add_connection(node_to, connection_create(node_from, h));
        // printf("%c -> %c [%d]\n", from, to, h);
    }
    list_node_print(nodes);
}

I forgot that if a connection to the same node was already there (added from the other direction), we should add the score and not put it again. An alternative would be to discard the “simplification” I had in mind and only keep track of unidirectional scores. Computing the total score of a link would still be reasonably easy, but I think I still prefer the bidirectional idea. I think it will make the hardest part of the code easier. I may, of course, be very wrong about that.

I think the best option is to change the add_connection code to only create a new connection if necessary.

void node_add_connection(node_t* node, node_t* dest, int score){
    // check if there is already a connection to that node
    connection_t* existing = NULL;
    for (int i = 0; i < node->n_connections; i++){
        if (node->connections[i]->dest->name == dest->name){
            existing = node->connections[i];
            // update existing connection
            existing->score += score;
            return;
        }
    }
    // otherwise, create new connection
    if (node->n_connections == node->capacity){
        node->capacity *= 2;
        node->connections = realloc(node->connections, sizeof(connection_t*)*node->capacity);
    }

    node->connections[node->n_connections] = connection_create(dest, score);
    node->n_connections++;
}