Day 3, part 1 - Visiting pointers

Today’s puzzle starts off with a very similar kind of input as day 1: a simple list of symbols, each corresponding to a one-step move in a direction. Except that now we are two-dimensional: starting from some unspecified house, we can go in any of the four cardinal directions ^v<>. The goal is to find out how many unique locations we visit following the instructions in the input.

I can immediately think of several approaches here. The unique condition screams set to me, and certainly in a language where sets are standard I would start from there: keep track of the current coordinates in a 2D grid, adding the coordinates to the set, and at the end counting the number of elements in the set.

But that would mean here implementing a set from scratch, as I don’t want to copy-paste one of the many C implementations of sets that certainly exist all over the internet. It could be interesting, and I’m not rejecting the idea out of hand: sets will certainly be useful later as well. But let’s think a bit more first.

The second option is, well, a 2D grid: I can use a table of boolean values to keep track of which coordinates were visited. The main difficulty is that I don’t know, initially, the size of the grid. Still, it’s doable, either with a first pass to compute the desired size, then a second pass to set the boolean values.

Third option: just compute a list of all coordinates first, then collapse it into unique values. I like this third option, but I think to work well the list should be ordered in some way. It will add a bit of complexity to adding the coordinates, but it will make the “remove duplicates” code a lot easier. Let’s try that first, and if it seems too weird we’ll adjust as we go.

Reading the instructions

We need to start somewhere: let’s make sure that we can read the input with our previously made freadall function:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "futils.h"

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

int main(){
    char* fcontent = freadall(FILE_INPUT);

    printf("%s", fcontent);
}

Everything looks fine. I think I want to start with defining a coordinates, and making sure that I can move from one coordinate to the next.

typedef struct {
    int x;
    int y;
} coord_t;

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

int main(){
    char* fcontent = freadall(FILE_INPUT);

    coord_t* current_coordinate = malloc(sizeof(coord_t));
    current_coordinate->x = 0;
    current_coordinate->y = 0;

    for (int i=0; i < strlen(fcontent); i++){
        char move = fcontent[i];
        if (move == '^')
            current_coordinate->y--;
        else if (move == 'v')
            current_coordinate->y++;
        else if (move == '<')
            current_coordinate->x--;
        else if (move == '>')
            current_coordinate->x++;
        print_coord(current_coordinate);
    }
}

I get a nice stream of coordinates, so it seems like a good start. Let’s put that into a method and make a test. While we are at it, we can make our live a little bit easier by giving each step its own function:

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

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]);
    }
}

int main(){
    char* fcontent = freadall(FILE_INPUT);

    coord_t* current_coordinate = make_coord(0, 0);

    process_moves(current_coordinate, fcontent);
    print_coord(current_coordinate);
}

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

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

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

int main(){
    if (test_move())
        printf("Test move OK\n");
    else {
        printf("Test move FAIL\n");
        exit(1);
    }
    // ...
}

Ordered list

I suddenly feel a little bit dumb, but in the spirit of these notes I’ll not go back to edit the first part to pretend that I’m smart. With the ordered list, I am, in fact, constructing a set. When inserting a new element into the list, if I need to find where to put it, I’ll necessarily find the element if it’s already there, and I can skip the “add” part in that case.

It’s not the most efficient way of doing a set for sure, but it’s certainly simpler to implement than a hash map, so let’s start there and, if I need something more efficient in the future, I’ll look into better ways of doing it.

First, I realize that I haven’t freed my coordinate nor my file contents, so let’s add a:

free(fcontent);
free(current_coordinate);

I can think of two reasonably easy ways of doing the ordered list. First: with a linked list. Very easy to set up, but I’ll need to go through possibly the entire list each time I want to insert something.

Other possibility, which I prefer for now: since I know the maximum number of coordinates I’ll have in my ordered list (set, I guess), I can pre-allocate that memory, and put everything in a table. That way I can use a bisection method to find the best place to add a given coordinate. I’ll still need to copy everything after in the table to offset it by one, but I still think overall it’s going to be a little bit easier.

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

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

I’m not entirely sure it’s right. I think I need the double pointer here for coords in the struct, as each coords[i] will have to be malloced and so will return a pointer. Let’s add a small test, which will also help us better see how to add things in this structure.

bool test_table_coords(){
    char* content = "^^^<<";
    table_coords_t* table_coords = make_table_coords(strlen(content)+1);
    coord_t* start = make_coord(0, 0);
    table_coords->n = 1;
    table_coords->coords[0] = malloc(sizeof(coord_t));
    table_coords->coords[0]->x = start->x;
    table_coords->coords[0]->y = start->y;

    for (int i=0; i < strlen(content); i++){
        move_coordinate(start, content[i]);
        
        table_coords->coords[i+1] = malloc(sizeof(coord_t));
        table_coords->coords[i+1]->x = start->x;
        table_coords->coords[i+1]->y = start->y;
        table_coords->n++;
    }

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

This passes. It also tells me that I probably need a “copy this coordinates at that index” function. Let’s create it:

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

And changing the tests to use it, it all still works. Except that it doesn’t do what I need yet. Small steps, though. Now I can modify this insert code so that it:

Since I need a sense of order in my table, I also need a function to compare two coordinates. How we determine the order doesn’t matter much. Here I’ll go with a simple “order by y, then by x” method. The function will return -1 if a < b, +1 if a > b, and 0 if a==b:

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

First pass at trying to find the right spot, in a very inefficient but simple way: we go through the whole list, if we’re smaller than the current element we insert before, if we’re the same we return -1 to mark a duplicate, if we’re larger than everything in the table so far we return the last position.

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

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

void offset_after(table_coords_t* table_coords, int idx){
    for (int i=table_coords->n; i > idx; i--){
        table_coords[i] = table_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);
}

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

Some print debugging tells me that it happens during the find_index_in_table of the duplicate (1, 3). This succeeded in the previous test, though, so why not now? Printing the content of the table after each add shows me that the culprit is probably in the offset, as I can’t show table_coords->coords[2] after inserting (-1, 2), which should offset (1, 3). Everything seems to be doing what I’m asking, so it must mean that I’m asking the wrong thing.

After way too much testing and questioning my understanding of how pointers work, I found the culprit in offset_after: table_coords[i] = table_coords[i-1] should instead be:

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

And now the test passes. Which means we should have everything now to actually solve the first part of the puzzle.

The puzzle, part 1

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

int main(){
    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);
}

And this gives us the right answer. We’ll stop there for now, and move to part 2 another time. And see along the way if we can maybe set aside some of the functions we used in their own utility file for later use. This probably won’t be the last puzzle with coordinates in it!