Day 14 - Velocity

Advent of Code 2015

Adrien Foucart

2026-04-23

[Back to index]

Puzzle: https://adventofcode.com/2015/day/14

My solution: https://codeberg.org/adfoucart/aocode15/src/branch/main/src/day14.c

The input has a list of reindeers with a description of their movement pattern, such as:

Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.

The goal is to determine, after a given amount of seconds, the maximum distance travelled by one of the competitors.

A tiny bit of maths

Let’s math it out first. We have three pieces of information per reindeer: their speed s, their flight period f and their rest period r. A full period p for a given reindeer will therefore be f+r, after which point they will have travelled f*s kilometers. So for Comet above, a full period will be p=137, and every period they will have travelled 10*14=140km.

To compute how far they have travelled after 1000 seconds, we first need to find how many whole periods we get in that time. Here: 1000/137 = 7, so we start from 7*140 = 980km. We still have 1000 - (7*137) = 41 seconds. For the first ten seconds, they will travel another further 140km, so we get a total of 1120km.

A tiny bit of code

This is the second time in a row that we need to extract some substring between two occurrences of a character (a space ' '), so I should probably extract that to a function in parser.c:

// parser.c
/**
 * Find null-terminated substring between the n-th and n+1-th occurrences of a character
 */
char* find_substring_between(char* s, char c, int n){
    // find n-th and n+1-th occurrence
    char *nth = s;
    char *next;
    for (int i=0; i < n; i++){
        nth = strchr(nth, c)+1;
    }
    next = strchr(nth, ' ');
    // copy what's in between, with added null character
    char *sub = malloc(next-nth+1);
    memcpy(sub, nth, next-nth);
    sub[next-nth] = '\0';
    
    return sub;
}

Normally here I’d start making a data structure with a list of reindeers, etc., but here I can actually compute everything I need in one go. We’ll just make one function compute_max_distance to go through the content of the input file line-by-line:

int compute_max_distance(char* content, int t){
    str_list_t* lines = parse_strings(content, '\n');
    int max_distance = 0;
    for (int i = 0; i < lines->n; i++){
        char *line = lines->str_list[i];
        if (strlen(line) == 0) continue;
        // ...
    }

    str_list_destroy(lines);
    return max_distance;
}

Inside, we’ll use our new parsing function to find f, r and s, and convert them to integers with atoi:

// ...
        char* s_string = find_substring_between(line, ' ', 3);
        char* f_string = find_substring_between(line, ' ', 6);
        char* r_string = find_substring_between(line, ' ', 13);

        int s = atoi(s_string);
        int f = atoi(f_string);
        int r = atoi(r_string);

        // ...

        free(s_string);
        free(f_string);
        free(r_string);
// ...

Then we compute the distance travelled and update max_distance if necessary:

// ...
        int full_periods = t/(f+r);
        int dist = full_periods*(s*f);
        int remaining_time = (t-full_periods*(f+r));
        if (remaining_time > f) 
            remaining_time = f;
        dist += remaining_time*s;

        if (dist > max_distance)
            max_distance = dist;
// ...

And that works nicely and, I think, efficiently.

Part 2: a stepwise approach

I was very happy that I avoided having to compute things second-by-second. Part 2 appears to throw a wrench in that plan. The new rules are that, at each second, we need to compute who is in the lead, and to give them one point. At the end, we need the number of points of the winner. So this time I need a two-pass approach.

I’ll start by extracting the “compute distance at time t” code into a small function:

int distance_at_time(int s, int f, int r, int t){
    int full_periods = t/(f+r);
    int dist = full_periods*(s*f);
    int remaining_time = (t-full_periods*(f+r));
    if (remaining_time > f) 
        remaining_time = f;
    dist += remaining_time*s;

    return dist;
}

We’ll need a list of reindeers, and to store reindeer information, including their points.

typedef struct {
    int s;
    int f;
    int r;
    int p;
} reindeer_t;

typedef struct {
    reindeer_t** reindeers;
    int size;
    int capacity;
} reindeers_list_t;

Instead of just parsing, we will now get a list of reindeers:

reindeers_list_t* get_reindeers(char* content){
    str_list_t* lines = parse_strings(content, '\n');
    reindeers_list_t* reindeers = malloc(sizeof(reindeers_list_t));
    reindeers->capacity = lines->n;
    reindeers->size = 0;
    reindeers->reindeers = malloc(sizeof(reindeer_t*)*lines->n);

    for (int i = 0; i < lines->n; i++){
        char *line = lines->str_list[i];
        if (strlen(line) == 0) continue;
        char* s_string = find_substring_between(line, ' ', 3);
        char* f_string = find_substring_between(line, ' ', 6);
        char* r_string = find_substring_between(line, ' ', 13);

        reindeer_t* reindeer = malloc(sizeof(reindeer_t));
        reindeer->s = atoi(s_string);
        reindeer->f = atoi(f_string);
        reindeer->r = atoi(r_string);
        reindeer->p = 0;
        
        reindeers->reindeers[reindeers->size++] = reindeer;

        free(s_string);
        free(f_string);
        free(r_string);
    }

    str_list_destroy(lines);
    return reindeers;
}

Now we need to go time step by time step, compute the distance of each reindeer, and give a point to the one ahead.

Then we return the maximum points.

int get_maximum_points(reindeers_list_t* reindeers, int time){
    for (int t=1; t <= time; t++){
        int best_idx = -1;
        int best_dist = 0;
        for (int i=0; i < reindeers->size; i++){
            reindeer_t* r = reindeers->reindeers[i];
            int d = distance_at_time(r->s, r->f, r->r, t);
            if (d > best_dist){
                best_dist = d;
                best_idx = i;
            }
        }

        reindeers->reindeers[best_idx]->p++;
    }
    
    int max_points = 0;
    for (int i=0; i < reindeers->size; i++){
        reindeer_t* r = reindeers->reindeers[i];
        printf("%d: %d points\n", i, r->p);
        if (r->p > max_points){
            max_points = r->p;
        }
    }
    
    return max_points;
}

And the main:

// ...
    reindeers_list_t* reindeers = get_reindeers(content);
    int max_points = get_maximum_points(reindeers, time);

    printf("Part 2: %d\n", max_points);
// ...

This… doesn’t work? On the example, I have an off-by-one error, and I don’t understand it. The puzzle description says:

After the 1000th second, Dancer has accumulated 689 points, while poor Comet, our old champion, only has 312. So, with the new scoring system, Dancer would win (if the race ended at 1000 seconds).

That means a total of 1001 points attributed, which shouldn’t be possible in 1000 seconds.

Except, as I’m writing this, that I didn’t consider ex-aequos. Re-reading the puzzle more carefully, it says:

(If there are multiple reindeer tied for the lead, they each get one point.)

I skipped over that.

That means I have to do another pass on the reindeers table to add points to all those that have a distance equal to the best distance:

int get_maximum_points(reindeers_list_t* reindeers, int time){
    for (int t=1; t <= time; t++){
        int best_dist = 0;
        int distances[reindeers->size];

        for (int i=0; i < reindeers->size; i++){
            reindeer_t* r = reindeers->reindeers[i];
            int d = distance_at_time(r->s, r->f, r->r, t);
            distances[i] = d;
            if (d > best_dist){
                best_dist = d;
            }
        }

        for (int i=0; i < reindeers->size; i++){
            if (distances[i] == best_dist)
                reindeers->reindeers[i]->p++;
        }
    }
    
    int max_points = 0;
    for (int i=0; i < reindeers->size; i++){
        reindeer_t* r = reindeers->reindeers[i];
        printf("%d: %d points\n", i, r->p);
        if (r->p > max_points){
            max_points = r->p;
        }
    }
    
    return max_points;
}

This gives me the correct result. Easy puzzle, if you can read.