Day 13, part 2 - Taking a seat

We can fix the first node: since this time we are looping around, where we start doesn’t matter. ABCD and BCDA are the same.

Then we need to test everything. For that, the logic is essentially the same as in day 9: a recursive slog through all possible solutions, keeping track of those where the distance is minimal—or in this case the happiness is maximal—and returning the best one at the end.

There is a bit of renaming, and the little twist that we need to remember to add the first node back at the end of the line so that we complete the circle, but otherwise it’s a big copy-and-paste.

typedef struct {
    list_node_t* list;
    int total_score;
} ordering_t;

ordering_t* ordering_create(node_t* start){
    ordering_t* ordering = malloc(sizeof(ordering_t));
    ordering->total_score = 0;
    ordering->list = list_node_create(8);
    list_node_add(ordering->list, start);
    return ordering;
}

void ordering_destroy(ordering_t* ordering){
    list_node_destroy(ordering->list);
    free(ordering);
}

void ordering_add(ordering_t* ordering, node_t* node, int score){
    list_node_add(ordering->list, node);
    ordering->total_score += score;
}

void ordering_print(ordering_t* ordering){
    printf("Ordering with total score = %d:\n", ordering->total_score);
    printf("\t");
    for (int i=0; i < ordering->list->n_nodes; i++){
        printf("%c", ordering->list->nodes[i]->name);
    }
    printf("\n");
}

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

ordering_t* ordering_clone(ordering_t* ordering){
    ordering_t* clone = malloc(sizeof(ordering_t));
    clone->total_score = ordering->total_score;
    clone->list = list_node_create(ordering->list->capacity);
    for (int i = 0; i < ordering->list->n_nodes; i++){
        list_node_add(clone->list, ordering->list->nodes[i]);
    }
    return clone;
}

ordering_t* find_maximum_happiness_from_node(ordering_t* ordering, node_t* node){
    int max_score = -1;
    ordering_t* max_ordering = NULL;
    for (int i=0; i < node->n_connections; i++){
        if (ordering_contains(ordering, node->connections[i]->dest)){
            continue;
        }
        // clone path
        ordering_t* newordering = ordering_clone(ordering);
        ordering_add(newordering, node->connections[i]->dest, node->connections[i]->score);
        ordering_t* further = find_maximum_happiness_from_node(newordering, node->connections[i]->dest);
        if (max_score < 0 || further->total_score > max_score){
            max_score = further->total_score;
            if (max_ordering != NULL)
                ordering_destroy(max_ordering);
            max_ordering = further;
        }
        else {
            ordering_destroy(newordering);
        }
    }
    if (max_score < 0){
        // add first node at the end for circularization
        node_t* first = ordering->list->nodes[0];
        node_t* last = ordering->list->nodes[ordering->list->n_nodes-1];
        for (int iconn = 0; iconn < last->n_connections; iconn++){
            if (last->connections[iconn]->dest == first){
                ordering_add(ordering, first, last->connections[iconn]->score);
                break;
            }
        }
        return ordering;
    }

    return max_ordering;
}

int find_maximum_happiness(list_node_t* nodes){

    int max_score = 1000000;
    node_t* start = nodes->nodes[0];

    ordering_t* ordering = ordering_create(start);
    ordering_t* max_from_node = find_maximum_happiness_from_node(ordering, start);

    ordering_print(max_from_node);

    return max_from_node->total_score;
}

And it gets us to the correct result for part 1 of the puzzle. I don’t really like that code though. It is very obviously a mash-up of ideas without a clear design for the whole thing. It works, but in the spirit of learning that I try to keep for this run I think I want to spend a bit more time tidying things up.

Some tidying up

To start, I’ll be going through the code looking for some obvious points where I can make the code clearer.

An obvious example is ordering_add, which was copied from path_add in day 9. Right now, we have to pass a node and a score to it, but those always come from the same connection. The code gets cleaner, I think, if I replace:

void ordering_add(ordering_t* ordering, node_t* node, int score){
    list_node_add(ordering->list, node);
    ordering->total_score += score;
}

// ...
ordering_add(newordering, node->connections[i]->dest, node->connections[i]->score);

// ...
ordering_add(ordering, first, last->connections[iconn]->score);

void ordering_add(ordering_t* ordering, connection_t* conn){
    list_node_add(ordering->list, conn->dest);
    ordering->total_score += conn->score;
}

// ...
ordering_add(newordering, node->connections[i]);

// ...
ordering_add(ordering, last->connections[iconn]);

Another one: ordering_clone has to know too much about lists. It would be better to have the list cloning part in the list methods. So from:

ordering_t* ordering_clone(ordering_t* ordering){
    ordering_t* clone = malloc(sizeof(ordering_t));
    clone->total_score = ordering->total_score;
    clone->list = list_node_create(ordering->list->capacity);
    for (int i = 0; i < ordering->list->n_nodes; i++){
        list_node_add(clone->list, ordering->list->nodes[i]);
    }
    return clone;
}

list_node_t* list_node_clone(list_node_t* from){
    list_node_t* to = list_node_create(from->capacity);
    for (int i = 0; i < from->n_nodes; i++){
        list_node_add(to, from->nodes[i]);
    }

    return to;
}

ordering_t* ordering_clone(ordering_t* from){
    ordering_t* to = malloc(sizeof(ordering_t));
    to->total_score = from->total_score;
    to->list = list_node_clone(from->list);
    return to;
}

We can also extract the “find the right connection” part of the circularization code, which would be better with the node stuff:

connection_t* node_find_connection_to(node_t* node, node_t* to){
    for (int i = 0; i < node->n_connections; i++){
        if (node->connections[i]->dest == to){
            return node->connections[i];
        }
    }

    return NULL;
}

And, with some more renaming in find_maximum_happiness_from_node, we get something which I think is at least a little bit better:

ordering_t* find_maximum_happiness_from_node(ordering_t* ordering, node_t* node){
    int max_score = -1;
    bool has_unvisited_connections = FALSE;
    ordering_t* max_ordering = NULL;

    for (int i=0; i < node->n_connections; i++){
        if (ordering_contains(ordering, node->connections[i]->dest)){
            continue;
        }
        has_unvisited_connections = TRUE;

        // clone ordering
        ordering_t* next = ordering_clone(ordering);
        ordering_add(next, node->connections[i]);
        next = find_maximum_happiness_from_node(next, node->connections[i]->dest);
        if (max_score < 0 || next->total_score > max_score){
            max_score = next->total_score;
            if (max_ordering != NULL)
                ordering_destroy(max_ordering);
            max_ordering = next;
        }
        else {
            ordering_destroy(next);
        }
    }

    if (!has_unvisited_connections){
        // add first node at the end for circularization
        node_t* first = ordering->list->nodes[0];
        node_t* last = ordering->list->nodes[ordering->list->n_nodes-1];
        connection_t* conn = node_find_connection_to(last, first);
        if (conn != NULL)
            ordering_add(ordering, conn);

        return ordering;
    }

    return max_ordering;
}

I realize that I can also use this new function in node_add_connection, which checks if there’s already a connection to that node with a very similar code. Changing to:

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 = node_find_connection_to(node, dest);
    if (existing != NULL){
        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++;
}

With that, I think I’m already more satisfied with my code. I thought about moving the nodes and connection stuff to a graph.c file, but I’d have to generalize it a bit further I think for it to be useful, and I don’t want to do that just yet. In this puzzle setting, I’m fine with a bit of copy-pasting around, as long as I take a bit of time to adapt it properly afterwards as I’ve just done now.

A new thing to do

We have to find the total change in happiness if we include “ourselves” into the mix, given that all our connections have a score of 0 with all other guests. I thought that it meant “inserting ourselves in the ordering that we have found”, and wrote this:

int find_optimal_happiness_change(ordering_t* ordering){
    int min_change = 1000000;
    for (int i=0; i < ordering->list->n_nodes-1; i++){
        // inserting between i and i+1 means:
        // removing score of connection i<->i+1
        node_t* left = ordering->list->nodes[i];
        node_t* right = ordering->list->nodes[i+1];
        connection_t* conn = node_find_connection_to(left, right);
        if (conn->score < min_change){
            min_change = conn->score;
        }
    }
    return -min_change;
}

But re-reading the puzzle carefully, we have to recompute a new ordering, including ourselves in the graph itself. And what we need to compute is not the difference with part 1, but just the new happiness score.

So this is actually very easy thanks to the “object-like” code that we’ve made. We create a new node and connect it to the network, then re-run the code from part 1:

int main(){
    printf("==Day 13==\n\n");

    list_node_t* nodes = parse_input(INPUT_FILE);
    list_node_print(nodes);

    ordering_t* max = find_maximum_happiness_ordering(nodes);
    printf("Part 1: %d\n", max->total_score);

    node_t* us = node_create('Z');
    for (int i=0; i < nodes->n_nodes; i++){
        node_add_connection(us, nodes->nodes[i], 0);
        node_add_connection(nodes->nodes[i], us, 0);
    }
    list_node_add(nodes, us);
    ordering_t* max_with_us = find_maximum_happiness_ordering(nodes);
    printf("Part 2: %d\n", max_with_us->total_score);

    ordering_destroy(max);
    ordering_destroy(max_with_us);
    exit(0);
}

An exercise in copy-pasting

Some tidying up

A new thing to do