Day 9, part 3 - A longer trip

In the previous episode, we got our star for finding the shortest path through all the nodes, but we also ended on a worrying bug: the parse_strings method, when there’s an empty line at the end of the input file, sometimes fills this empty line with data that it’s clearly pulling from elsewhere. Let’s start by trying to isolate the error in a test. I had a test to check that a last empty line was just equals to \0, but evidently it’s not sufficient here:

bool test_parse_strings_empty_line_is_null(){
    char test[] = "last empty line\n";
    str_list_t* str_list = parse_strings(test, '\n');
    return (str_list->str_list[1][0] == '\0');
}

This test runs fine. Writing a new test specifically for the day 9 inputs immediately shows a big difference:

bool test_parse_strings_empty_line_is_null_on_day9(){
    char* test = freadall("./data/day9.txt");
    str_list_t* str_list = parse_strings(test, '\n');
    return (str_list->str_list[28][0] == '\0');
}

This fails. But in the first case, I was defining a string with the char test[] = "..." syntax, which automatically adds a \0 at the end for us. In my day 9 version here, I’m getting a char* from freadall, which is a function I’ve written, and therefore more likely to contain some mistake. Let’s take a look at freadall:

char* freadall(char *path){
    FILE *fp;
    char *buffer;
    int fsize;

    fp = fopen(path, "r");
    if( fp == NULL )
        exit(1);
    // find end of file to allocate size
    fseek(fp, 0L, SEEK_END);
    fsize = ftell(fp);
    // return to beginning of file
    rewind(fp);

    printf("Size of file: %d\n", fsize);

    // allocate file content
    buffer = malloc(sizeof(char)*fsize+1);

    // read file
    fread(buffer, sizeof(char), fsize, fp);
    buffer[fsize] = '\0';

    fclose(fp);
    return buffer;
}

So I’m using fseek and ftell to compute the size of the file, allocating that to a buffer, copying the file content, and then setting the last character to \0. My hypothesis now is that the size I compute is not correct, and I therefore allocate too much space to my buffer. Since I set the last char in the memory region to \0, there could be some stuff between the end of the copied file content and the added \0. I guess.

The goal with fseek and ftell is to first set the pointer to the end of the file with fseek(fp, 0L, SEEK_END), then to get the position with ftell, which should therefore be equal to the size. That’s what I got from this StackOverflow comment, at least ! One little problem looking now at the documentation for ftell:

So let’s make a less efficient but safer freadall, shall we? Here’s the plan:

char* freadall(char *path){
    FILE *fp;
    char *buffer;
    int fsize = 0;
    int capacity = 512;
    int MAX_SIZE = 65532;

    fp = fopen(path, "r");
    if( fp == NULL )
        exit(1);
    
    // preallocate file content
    buffer = malloc(sizeof(char)*capacity);

    // read file
    do {
        int c = fgetc(fp);
        if (c == EOF) break;
        if (fsize == capacity){
            capacity *= 2;
            buffer = realloc(buffer, capacity);
        }
        buffer[fsize++] = c;
    } while (fsize < MAX_SIZE);
    
    fclose(fp);

    buffer[fsize] = '\0';
    buffer = realloc(buffer, fsize);

    return buffer;
}

I’ve added a MAX_SIZE because I’m always uncomfortable to keep a while(true) somewhere. Running my tests again, everything seems fine. Running the day9.c code also works, even with the new line in the file. Great.

Part 2, same as part 1

Part 2 of the puzzle is the same as part 1, except we need to longest path instead of the shortest. Since we did an exhaustive search in part 1, we just have to change some signs and variable names:

int find_longest_distance_from_node(path_t* path, node_t* node){
    int max_dist = -1;
    for (int i=0; i < node->n_connections; i++){
        if (path_contains(path, node->connections[i]->dest)){
            continue;
        }
        // clone path
        path_t* newpath = path_clone(path);
        path_add(newpath, node->connections[i]->dest, node->connections[i]->dist);
        int further = find_longest_distance_from_node(newpath, node->connections[i]->dest);
        if (further > max_dist){
            max_dist = further;
        }
        path_destroy(newpath);
    }
    if (max_dist < 0)
        return path->total_dist;

    return max_dist;
}

int find_longest_distance(list_node_t* nodes){
    int max_dist = 0;
    for (int i = 0; i < nodes->n_nodes; i++){
        node_t* node = nodes->nodes[i];
        path_t* path = path_create(node);
        int max_from_node = find_longest_distance_from_node(path, node);
        if (max_from_node > max_dist){
            max_dist = max_from_node;
        }
    }

    return max_dist;
}

And now that our freadall does what it’s supposed to do, we directly get the right answer. One month for part 1, five minutes for part 2. That’s unusual. I’ll take it. 18 stars down, 32 to go. If I go to the end. We’ll see.