Day 1 - Parentheses

Day 1 is always about setting up the pipeline. Every puzzle has a text input, which I typically store in a text file. I’ll need to retrieve the input and, typically, parse it in some way. Since this is C, I also need to think about how I will organize my sources and binaries and such. For now at least, I’ll go for a fairly simple structure:

In the makefile, I’ll just put a bunch of gcc commands to use as needed, such as:

day1:
    gcc ./src/day1.c -o ./bin/day1.exe

This way I can put whichever files I need for a particular day’s puzzle, as I intend to set aside some utility functions along the way. For instance, assuming that I have a futils.c file for my file-handling functions:

day1:
    gcc ./src/day1.c ./src/futils.c -o ./bin/day1.exe

Okay, I still haven’t looked at the puzzle or written any code, let’s get started.

The puzzle

The puzzle itself is very easy. It’s the first ever Advent of Code puzzle, after all. We have a bunch of opening and closing parentheses to operate an elevator:

Every ( means “going up one floor” (i.e. +1), every ) means “going down” (-1). We need to know which floor we end up on, starting from 0. In other words: we just need to count the ( and ), and compute the difference.

Loading the input

#include <stdio.h>
#include <stdlib.h>

int main(){
    FILE *fp;

    fp = fopen("../data/day1.txt", "r");
    if (fp == NULL)
        exit(1);

    printf("File opened!");

    fclose(fp);
    
    return 0;
}

The main “read-things-from-a-file” function appears to be fread. I need to create a “buffer” (char*) to store the content, the size of each object I want to get (in my case, I want chars, so sizeof(char)), the number of objects to read (some constant for now), and the file pointer.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000

int main(){
    FILE *fp;
    char buffer[MAX_SIZE];

    fp = fopen("../data/day1.txt", "r");
    if (fp == NULL)
        exit(1);

    fread(buffer, sizeof(char), MAX_SIZE, fp);

    printf("%s", buffer);
    fclose(fp);
    
    return 0;
}

I get a nice stream of parentheses. Everything’s fine so far. Let’s try to extract this to a function.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10000

char* freadall(char* path){
    FILE *fp;
    char buffer[MAX_SIZE];

    fp = fopen(path, "r");
    if (fp == NULL)
        exit(1);

    fread(buffer, sizeof(char), MAX_SIZE, fp);
    fclose(fp);

    return buffer;
}

int main(){
    char* buffer = freadall("../data/day1.txt");
    printf("%s", buffer);
    return 0;
}

…and this doesn’t work. The result is (null), and I get this compilation warning: warning: function returns address of local variable. This is pretty clear, and the kind of things I need to get used to coming from Python. If I declare buffer in freadall like that, it gets destroyed when we exit the function, and the pointer now points to nothing. It’s time to get the malloc party going. malloc allocates memory in “heap memory”, where it will remain available until we decide otherwise or the program ends, whereas with char buffer[MAX_SIZE], we were allocating space in “stack memory”, where it only lives within the current scope.

char* buffer = malloc(sizeof(char)*MAX_SIZE);

int main(){
    char* buffer = freadall("../data/day1.txt");
    printf("%s", buffer);
    free(buffer);
    return 0;
}

I don’t think it really matters here, but it’s probably a good idea to get used to think about when to free the space. Anyway, this now works as intended, but I would like to avoid this hardcoded size. Searching around a little bit, it’s not difficult to find the size of a file, with a combination of fseek and ftell:

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

    fp = fopen(path, "r");
    if( fp == NULL )
        exit(1);
    // find beginning of file to allocate size
    fseek(fp, 0L, SEEK_END);
    fsize = ftell(fp);
    printf("File size: %d\n", fsize);
    // return to beginning of file
    rewind(fp);

    buffer = malloc(sizeof(char)*fsize);
    fread(buffer, sizeof(char), MAX_SIZE, fp);
    fclose(fp);

    return buffer;

I get everything, but also some random characters at the end. Why? The file size I get is 7000, which correspond to the number of characters in the file, so that’s correct.

I had to think a bit on this one. When I looked at buffer[6999], it gave me the correct character, so all the parentheses are there. Why do I get the rest? Because a string, as defined by the %s in printf, requires a \0 as the last character, which I didn’t get from fread. Let’s add it:

    // ...
    buffer = malloc(sizeof(char)*fsize+1);
    fread(buffer, sizeof(char), fsize, fp);
    fclose(fp);
    buffer[fsize] = '\0';
    return buffer;

Counting

The hardest part should be done now. We can start working on the actual puzzle: counting ‘(’ and ‘)’. Since our char* is a \0-terminated string, we can use strlen to get its size, and iterate over all the elements, incrementing and decrementing a counter as we go.

int count_floors(char* fcontent){
    // count the '(' and ')', return the difference.
    int counter = 0;
    for( int i = 0; i < strlen(fcontent); i++ ){
        if( fcontent[i] == '(' )
            counter++;
        else if( fcontent[i] == ')' )
            counter--;
    }
    return counter;
}

int main(){
    printf("Starting day1 puzzle\n");
    char* fcontent = freadall("../data/day1.txt");
    printf("File loaded (size=%d)\n", strlen(fcontent));
    int floor = count_floors(fcontent);
    printf("Floor: %d\n", floor);
    return 0;
}

First occurrence

Every Advent of Code puzzle has two parts, and two stars to unlock. For the second one here we need to find out the position of the first character such that our floor is -1, counting from 1.

int count_first_pass(char* fcontent, int floor){
    int counter = 0;
    for( int i = 0; i < strlen(fcontent); i++ ){
        if( fcontent[i] == '(' )
            counter++;
        else if( fcontent[i] == ')' )
            counter--;
        if( counter == floor )
            return i+1;
    }
    return -1;
}

    // ...
    int pos = count_first_pass(fcontent, -1);
    printf("Position: %d\n", pos);
    // ...

As I hoped, the puzzle itself was easy. This will certainly not be the case for every puzzle going forward, but hopefully I get more comfortable with the language as we go, and the total difficulty remains manageable. Clearly here I still struggled with memory management. It’s scary how easy it is in C to just access parts of memory that you shouldn’t be accessing. Moving slowly and cautiously seems to be the way to go here, which is perfectly fine. I find it to be, in general, a good way to approach programming!

Setting things up

The puzzle

Loading the input

Counting

First occurrence