Day 3, part 2 - Extracting the set

Advent of Code 2015

Adrien Foucart

2026-03-02

[Back to index]

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

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

Puzzle, part two

The second part doesn’t seem to be a big change from the first. Now instead of one Santa delivering gifts, the instructions are for two Santas working in parallel, from the same string of characters as instructions. The first santa takes the odd characters, the second one takes the even characters. So if we have:

^^>v>^^<

That would mean that one Santa does:

^>>^

And the second one:

^v^<

And the set of visited locations will be the union of the sets visited by both Santas. Which means that we should just be able to use the same code as before, first splitting the instructions into the two parts, and using the same set to store the locations.

The only thing to change is therefore in the main. To keep things clean, I moved all the previous content in a part1 function, and now create a part2 function for the revised code:

void part2(){
    char* fcontent = freadall(FILE_INPUT);
    int half_size = strlen(fcontent)/2;
    char* moves_one = malloc(sizeof(char)*half_size+1);
    char* moves_two = malloc(sizeof(char)*half_size+1);
    for (int i=0; i < half_size; i++){
        moves_one[i] = fcontent[2*i];
        moves_two[i] = fcontent[2*i+1];
    }
    moves_one[half_size] = '\0';
    moves_two[half_size] = '\0';
    
    table_coords_t* visited_coords = make_table_coords(strlen(fcontent));

    insert_moves(visited_coords, make_coord(0, 0), moves_one);
    insert_moves(visited_coords, make_coord(0, 0), moves_two);

    printf("Total number of visited houses: %d\n", visited_coords->n);

    free(fcontent);
    free_table_coords(visited_coords);
}

And… it works, immediately. That’s nice, and I’m going to take it as a sign that I’m starting to understand what I’m doing.

It also means that I can take a little bit of time to think about what I can extract from this puzzle that may be useful later. Mostly: the set of coordinates.

Moving coordinates to coords.c

It would be nice to have a generic “set of things”, but from a quick search and a look at Ian Fisher’s article, I think it would be a bit overkill to implement something like that at this stage. Also I really don’t like the look of the code-generating macros, I think it would make my code unreadable to me, which is bad. So let’s settle for a “set of coordinates” for now.

Actually, thinking about it, there will probably be many things involving coordinates in general in the future, so let’s make a coords.c and a coords.h file and extract everything we may need later.

As a first pass, I just move things around: in day3.c, I keep everything specific to this puzzle, i.e. the move operations and the puzzle-solving logic, and associated tests:

// day3.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "futils.h"
#include "coords.h"

#define FILE_INPUT "../data/day3.txt"

void move_coordinate(coord_t* coord, char move){
    if (move == '^')
        coord->y--;
    else if (move == 'v')
        coord->y++;
    else if (move == '<')
        coord->x--;
    else if (move == '>')
        coord->x++;
}

void process_moves(coord_t* start, char* moves){
    for (int i=0; i < strlen(moves); i++){
        move_coordinate(start, moves[i]);
    }
}

void insert_moves(table_coords_t* table, coord_t* coords, char* moves){
    add_if_not_exists(table, coords);
    
    for (int i=0; i < strlen(moves); i++){
        move_coordinate(coords, moves[i]);
        add_if_not_exists(table, coords);
    }
}

bool test_move(){
    char* content = "^^^<<";

    coord_t* start = make_coord(0, 0);
    process_moves(start, content);

    return (start->x == -2 && start->y == -3);
}

bool test_table_coords(){
    char* content = "^^^<<";
    table_coords_t* table_coords = make_table_coords(strlen(content)+1);
    coord_t* start = make_coord(0, 0);
    insert_in_table(table_coords, start, 0);

    for (int i=0; i < strlen(content); i++){
        move_coordinate(start, content[i]);
        insert_in_table(table_coords, start, i+1);
    }

    bool success = (table_coords->n == 6) &&
                   (table_coords->coords[0]->x == 0 && table_coords->coords[0]->y == 0) &&
                   (table_coords->coords[5]->x == -2 && table_coords->coords[5]->y == -3); 

    free_table_coords(table_coords);

    return success;
}

void run_tests(){
    if (test_move())
        printf("Test move OK\n");
    else {
        printf("Test move FAIL\n");
        exit(1);
    }
    if (test_table_coords())
        printf("Test table coords OK\n");
    else {
        printf("Test table coords FAIL\n");
        exit(1);
    }
}

void part1(){
    char* fcontent = freadall(FILE_INPUT);

    table_coords_t* visited_coords = make_table_coords(strlen(fcontent));

    insert_moves(visited_coords, make_coord(0, 0), fcontent);

    printf("Total number of visited houses: %d\n", visited_coords->n);

    free(fcontent);
    free_table_coords(visited_coords);
}

void part2(){
    char* fcontent = freadall(FILE_INPUT);
    int half_size = strlen(fcontent)/2;
    char* moves_one = malloc(sizeof(char)*half_size+1);
    char* moves_two = malloc(sizeof(char)*half_size+1);
    for (int i=0; i < half_size; i++){
        moves_one[i] = fcontent[2*i];
        moves_two[i] = fcontent[2*i+1];
    }
    moves_one[half_size] = '\0';
    moves_two[half_size] = '\0';
    
    table_coords_t* visited_coords = make_table_coords(strlen(fcontent));

    insert_moves(visited_coords, make_coord(0, 0), moves_one);
    insert_moves(visited_coords, make_coord(0, 0), moves_two);

    printf("Total number of visited houses: %d\n", visited_coords->n);

    free(fcontent);
    free_table_coords(visited_coords);
}

int main(){
    run_tests();
    part1();
    part2();
}

Then coords.c gets the things related to the coord_t and table_coords_t:

// coords.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "coords.h"

coord_t* make_coord(int x, int y){
    coord_t* coord = malloc(sizeof(coord_t));
    coord->x = x;
    coord->y = y;
    return coord;
}

void print_coord(coord_t* coord){
    printf("(%d, %d),", coord->x, coord->y);
}

table_coords_t* make_table_coords(int max_size){
    table_coords_t* table_coords = malloc(sizeof(table_coords_t));
    table_coords->n = 0;
    table_coords->coords = malloc(sizeof(coord_t*)*max_size);
}

void print_table(table_coords_t* table_coords){
    printf("Table of size %d:", table_coords->n);
    for (int i=0; i < table_coords->n; i++){
        print_coord(table_coords->coords[i]);
    }
    printf("\n");
}

void free_table_coords(table_coords_t* table_coords){
    for (int i=0; i < table_coords->n; i++){
        free(table_coords->coords[i]);
    }
    free(table_coords->coords);
    free(table_coords);
}

int compare(coord_t* a, coord_t* b){
    if (a->y < b->y)
        return -1;
    if (a->y > b->y)
        return 1;
    // a->y == b->y
    if (a->x < b->x)
        return -1;
    if (a->x > b->x)
        return 1;
    return 0;
}

int find_index_in_table(table_coords_t* table_coords, coord_t* coords){
    if (table_coords->n == 0)
        return 0;

    for (int i = 0; i < table_coords->n; i++){
        int c = compare(coords, table_coords->coords[i]);
        if (c < 0)
            return i;
        if (c == 0)
            return -1; // equal -> already exists
    }

    // if we're here, we are larger than everything in the table
    return table_coords->n;
}

void insert_in_table(table_coords_t* table_coords, coord_t* coords, int idx){
    table_coords->coords[idx] = malloc(sizeof(coord_t));
    table_coords->coords[idx]->x = coords->x;
    table_coords->coords[idx]->y = coords->y;
    table_coords->n++;
}

void offset_after(table_coords_t* table_coords, int idx){
    for (int i=table_coords->n; i > idx; i--){
        table_coords->coords[i] = table_coords->coords[i-1];
    }
}

void add_if_not_exists(table_coords_t* table_coords, coord_t* coords){
    int idx = find_index_in_table(table_coords, coords);
    if (idx < 0)
        return;

    offset_after(table_coords, idx);
    insert_in_table(table_coords, coords, idx);
}

With the corresponding coords.h:

// coords.h
typedef struct {
    int x;
    int y;
} coord_t;

typedef struct {
    coord_t** coords;
    int n;
} table_coords_t;

coord_t* make_coord(int x, int y);
void print_coord(coord_t* coord);

table_coords_t* make_table_coords(int max_size);
void print_table(table_coords_t* table_coords);
void free_table_coords(table_coords_t* table_coords);
void insert_in_table(table_coords_t* table_coords, coord_t* coords, int idx);
int find_index_in_table(table_coords_t* table_coords, coord_t* coords);
void add_if_not_exists(table_coords_t* table_coords, coord_t* coords);

And the related tests get their own file:

// test_coords.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "coords.h"

bool test_find_index(){
    table_coords_t* table_coords = make_table_coords(5);
    insert_in_table(table_coords, make_coord(0, -1), 0);
    insert_in_table(table_coords, make_coord(2, -1), 1);
    insert_in_table(table_coords, make_coord(-1, 1), 2);
    insert_in_table(table_coords, make_coord(2, 1), 3);
    insert_in_table(table_coords, make_coord(0, 3), 4);

    int should_be_0 = find_index_in_table(table_coords, make_coord(0, -2));
    int should_be_1 = find_index_in_table(table_coords, make_coord(1, -1));
    int should_be_2 = find_index_in_table(table_coords, make_coord(0, 0));
    int should_be_5 = find_index_in_table(table_coords, make_coord(1, 3));
    int should_be_minus_1 = find_index_in_table(table_coords, make_coord(-1, 1));

    bool success = (should_be_0 == 0) &&
                   (should_be_1 == 1) && 
                   (should_be_2 == 2) && 
                   (should_be_5 == 5) && 
                   (should_be_minus_1 == -1);

    free_table_coords(table_coords);

    return success;
}

bool test_insert_as_set(){
    table_coords_t* table_coords = make_table_coords(5);
    add_if_not_exists(table_coords, make_coord(0, 0));
    add_if_not_exists(table_coords, make_coord(1, 3));
    add_if_not_exists(table_coords, make_coord(-1, 2));
    add_if_not_exists(table_coords, make_coord(1, 3));
    add_if_not_exists(table_coords, make_coord(3, -1));

    bool success = (table_coords->n == 4) &&
                   (table_coords->coords[0]->x == 3 && table_coords->coords[0]->y == -1) &&
                   (table_coords->coords[3]->x == 1 && table_coords->coords[3]->y == 3);

    free_table_coords(table_coords);

    return success;
}

int main(){
    if (test_find_index())
        printf("Test find index OK\n");
    else {
        printf("Test find index FAIL\n");
        exit(1);
    }
       
    if (test_insert_as_set())
        printf("Test insert as set OK\n");
    else {
        printf("Test insert as set FAIL\n");
        exit(1);
    }
}

Something that I immediately notice is that the interface of my “table of coordinates” doesn’t seem to know if it’s a table or a set, which is normal given how I developed it. But now it’s a bit confusing. This is probably a good place to refactor.

Table and sets of coordinates

Idea: separate the table_coords_t and a set_coords_t, so that we can manipulate either a table that can have duplicates, or a set, which will use a table but add the order and no-duplicate part.

Let’s think about the interfaces to both:

In a table, I want to:

In a set, I want to:

And in both cases get the current size. With some renaming to a more class-like interface, we could get something like:

// coords.h
typedef struct {
    int x;
    int y;
} coord_t;

typedef struct {
    coord_t** coords;
    int n;
} table_coords_t;

typedef struct {
    table_coords_t* table;
} set_coords_t;

coord_t* coord_create(int x, int y);
void coord_print(coord_t* coord);

table_coords_t* table_coords_create(int max_size);
void table_coords_print(table_coords_t* table_coords);
void table_coords_destroy(table_coords_t* table_coords);
void table_coords_insert(table_coords_t* table_coords, coord_t* coords, int idx);
int table_coords_find_first(table_coords_t* table_coords, coord_t* coords);
void table_coords_remove(table_coords_t* table_coords, int idx);
void table_coords_get(table_coords_t* table_coords, int idx);
void table_coords_size(table_coords_t* table_coords);

set_coords_t* set_coords_create(int max_size);
void set_coords_add(set_coords_t* table_coords, coord_t* coords);
void set_coords_remove(set_coords_t* table_coords, coord_t* coords);
void set_coords_size(set_coords_t* table_coords);

But changing all of that at once will break everything. We would have to change the names everywhere, and implement the missing functionalities. We need to take it step by step if we want it to work well, and add relevant tests along the way.

Making coord_t more object-like

First, we rename the two existing “coords” functions:

// coords.h
// ...
coord_t* coord_create(int x, int y);
void coord_print(coord_t* coord);

And changing also wherever it’s used. Nothing breaks. Adding a test, which unsurprisingly passes:

// test_coords.c
bool test_coord_create(){
    coord_t* coord = coord_create(1, 3);

    bool success = (coord->x == 1 && coord->y == 3);
    coord_destroy(coord);
    return success;
}
}

While we’re here, add a destroy function, even if it just wraps free. This way I don’t have to remember if a particular structure can be freed directly or not.

Making table_coords_t more object-like

Now give table_coords_t the same treatment. First the renaming:

table_coords_t* table_coords_create(int max_size);
void table_coords_print(table_coords_t* table_coords);
void table_coords_destroy(table_coords_t* table_coords);
void table_coords_insert(table_coords_t* table_coords, coord_t* coords, int idx);
int table_coords_find(table_coords_t* table_coords, coord_t* coords);
void table_coords_add_if_not_exists(table_coords_t* table_coords, coord_t* coords);

Then the tests. We already have one for find and for add, which should just get renamed. We need to add one for create and insert.

// test_coords.c
bool test_table_coords_create(){
    table_coords_t* table = table_coords_create(5);

    bool success = (table->n == 0);
    table_coords_destroy(table);
    return success;
}

bool test_table_coords_insert(){
    table_coords_t* table_coords = table_coords_create(2);
    table_coords_insert(table_coords, coord_create(0, -1), 0);
    table_coords_insert(table_coords, coord_create(2, -1), 1);

    bool success = (table_coords->n == 2) && 
                   (table_coords->coords[0]->x == 0) && 
                   (table_coords->coords[1]->y == -1);

    table_coords_destroy(table_coords);
    return success;
}

Adding get and update

If we’re going object-like, we should avoid making day3.c and other future days know too much about the struct directly. So let’s add coord_update, table_coords_get and table_coords_udpate.

// coords.c
void coord_update(coord_t* coord, int x, int y){
    coord->x = x;
    coord->y = y;
}

And change the usage in day3.c:

// day3.c
void move_coordinate(coord_t* coord, char move){
    if (move == '^')
        coord_update(coord, coord->x, coord->y-1);
    else if (move == 'v')
        coord_update(coord, coord->x, coord->y+1);
    else if (move == '<')
        coord_update(coord, coord->x-1, coord->y);
    else if (move == '>')
        coord_update(coord, coord->x+1, coord->y);
}
// coords.c
coord_t* table_coords_get(table_coords_t* table_coords, int idx){
    if (idx < 0 || idx >= table_coords->n)
        return NULL;
    return table_coords->coords[idx];
}

With a test:

// test_coords.c
bool test_table_coords_get(){
    table_coords_t* table_coords = table_coords_create(4);
    table_coords_insert(table_coords, coord_create(0, -1), 0);
    table_coords_insert(table_coords, coord_create(2, -1), 1);

    bool success = (table_coords_get(table_coords, -1) == NULL) && 
                   (table_coords_get(table_coords, 2) == NULL) && 
                   (table_coords_get(table_coords, 0)->x == 0) && 
                   (table_coords_get(table_coords, 1)->x == 2);
    
    table_coords_destroy(table_coords);
    return success;
}
// coords.c
void table_coords_update(table_coords_t* table_coords, coord_t* coords, int idx){
    if (idx < 0 || idx >= table_coords->n)
        return;
    table_coords->coords[idx]->x = coords->x;
    table_coords->coords[idx]->y = coords->y;
}

With a test as well. This is all looking good so far. I’m not using these functionalities at the moment, but it feels like they should be there, and they’re easy to implement, so why not?

Finally making the set

This is the bigger one: add a new structure for the set, and move the table_coords_add_if_not_exists function to this new “class”, and add the destroy and remove functions.

// coords.h
typedef struct {
    table_coords_t* table;
} set_coords_t;

set_coords_t* set_coords_create(int max_size);
void set_coords_destroy(set_coords_t* set);
void set_coords_add(set_coords_t* set, coord_t* coords);
void set_coords_remove(set_coords_t* set, coord_t* coords);

Coding the remove makes me realize that the offset function I had really shouldn’t exist. Now that we have a update in the table, we should let insert and remove from the table handle the offsets. Which means we need a table_coords_remove function.

// coords.c
void table_coords_remove(table_coords_t* table_coords, int idx){
    if (table_coords->n == 0)
        return;
    if (idx < 0 || idx >= table_coords->n)
        return;
    
    for (int i=idx; i < table_coords->n-1; i++){
        table_coords->coords[i] = table_coords->coords[i+1];
    }

    table_coords->n--;
}


set_coords_t* set_coords_create(int max_size){
    set_coords_t* set = malloc(sizeof(set_coords_t));
    set->table = table_coords_create(max_size);
}

void set_coords_destroy(set_coords_t* set){
    table_coords_destroy(set->table);
    free(set);
}

void set_coords_add(set_coords_t* set, coord_t* coords){
    int idx = table_coords_find(set->table, coords);
    if (idx < 0)
        return;

    table_coords_insert(set->table, coords, idx);
}

void set_coords_remove(set_coords_t* set, coord_t* coords){
    int idx = table_coords_find(set->table, coords);
    if (idx < 0)
        return;

    table_coords_remove(set->table, idx);
}

Now we need to change the usage in day3.c, but first in the test file, where we already had a test for the “add if not exists”.

bool test_set_coords_add(){
    set_coords_t* set = set_coords_create(5);
    set_coords_add(set, coord_create(0, 0));
    set_coords_add(set, coord_create(1, 3));
    set_coords_add(set, coord_create(-1, 2));
    set_coords_add(set, coord_create(1, 3));
    set_coords_add(set, coord_create(3, -1));

    bool success = (set->table->n == 4) &&
                   (set->table->coords[0]->x == 3 && set->table->coords[0]->y == -1) &&
                   (set->table->coords[3]->x == 1 && set->table->coords[3]->y == 3);

    set_coords_destroy(set);

    return success;
}

This crashes. Before exploring further why, I think I want to add the test for create:

bool test_set_coords_create(){
    set_coords_t* set = set_coords_create(5);
    
    bool success = (set->table->n == 0);

    set_coords_destroy(set);
    return success;
}

This crashes as well. And… I wasn’t returning the set in create. Fixed, and all tests pass.

Now let’s use the set in day3.c.

The main method to change is insert_moves:

void insert_moves(set_coords_t* set, coord_t* coords, char* moves){
    set_coords_add(set, coords);
    
    for (int i=0; i < strlen(moves); i++){
        move_coordinate(coords, moves[i]);
        set_coords_add(set, coords);
    }
}

Then a couple of changes in part1 and part2:

set_coords_t* visited_coords = set_coords_create(strlen(fcontent));
// ...
printf("Total number of visited houses: %d\n", visited_coords->table->n);
// ...
set_coords_destroy(visited_coords);

I don’t like that we have to go to ->table->n. I had plans for size methods for the table and the set to hide this implementation detail, so let’s quickly put that in.

int table_coords_size(table_coords_t* table_coords){
    return table_coords->n;
}
// ...
int set_coords_size(set_coords_t* set){
    return table_coords_size(set->table);
}

So that we can write in day3.c:

printf("Total number of visited houses: %d\n", set_coords_size(visited_coords));

To do?: add capacity

Improvement to keep in mind but that I don’t want to bother doing until it’s necessary: at the moment, the capacity of the table is fixed, and if we go over it we will get errors or undefined behaviour. In this puzzle, I know the maximum capacity, so it’s not an issue. It will be at some point, presumably. So we should have a capacity stored alongside the n, and increase the size of the table as needed.

But enough for now, I want to check what day 4 has to offer…