Advent of Code Tips

The most important thing about Advent of Code is: read the puzzle description and test input several times. There is often an edge case mentioned which isn’t obvious from a brief skim of the text.

Don’t get too disheartened if you get stuck, it’s unlikely that you are the only one. One year there was a puzzle with an ambiguous definition, and depending on how you interpreted it (there were two possibilities) the puzzle would either be trivial or impossible.

Remember that usually the most important part of determining how long your solution takes to run is the efficiency of your algorithms. Don’t worry about the most efficient way to read the input, whether to process data as it is read or afterwards etc.

Reading input

Every puzzle has input that you need to read. There are usually two ways of doing this:

Line by line: If each line of the file is independent and either the order doesn’t matter or the lines are in the right order, e.g. if each line contains a number and the puzzle is to find the sum of those numbers.

Whole file at once: If the lines are interdependent or the order is important, e.g. a grid.

I generally prefer to read the whole file in one Go, as I can always process the result line by line if needed.

Since C doesn’t provide a portable, standard library function for reading an entire file into a string (unlike Go, PHP etc.), you will probably need to read each line of the input and build up a single string for later processing. Or you can write your own function to read a given amount of data into a buffer, on the assumption that Advent of Code puzzle inputs will never be larger than 50KB:

int aoc_read_file(const char *filename, char *buffer, size_t buffer_size) {
    size_t read_length = 0;
    FILE *fp = fopen(filename, "r");

    if (fp == NULL) {
        return AOC_READ_FILE_FAILURE_OPEN;
    }

    read_length = fread(buffer, sizeof(char), buffer_size - 1, fp);

    if (read_length < buffer_size) {
        buffer[read_length] = '\0';
    } else {
        return AOC_READ_FILE_FAILURE_BUFFER_SIZE;
    }

    if (ferror(fp)) {
        return AOC_READ_FILE_FAILURE_READ;
    }

    fclose(fp);

    return 0;
}

Designing data structures

Although some puzzles can be solved by reading the input and processing it immediately - especially if you are using a functional language like Haskell - it’s usually best to design and populate a data structure. There are a few reasons for this.

• By splitting the reading of the input, population of the data structure, and solving the puzzle, you can test each step separately. This is usually much easier to debug than if you try and move straight to solving the puzzle.
• Part 2 of the puzzle involves using the same input to solve a slightly different problem. If you already have a data structure, in most cases you can move straight to solving part 2, instead of having to rethink your input processing (this isn’t always possible, as sometimes part 2 means tweaking your data structure).
• If you can’t see why something isn’t working, printing the data structure will often give you a clue.

The most common data structures are arrays (or linked lists in C, since arrays can’t be resized), grids (two dimensional arrays) and trees.

Testing

A test suite might seem overkill for these puzzles, but one thing that catches many people out is the edge cases, e.g. where a marker appears at the beginning or end of a line instead of in the middle. Testing every single function with expected outputs means you can find the source of a problem much quicker, even though there is an initial overhead in writing the tests. I’ve generally found that the time spent writing the tests is outweighed by the time saved on debugging, especially on later puzzles. Break down steps into functions

Break each part of the problem into its smallest possible step, and write a function to perform that step and nothing else. For example, if you have a grid of characters, each of which represents a numeric value, write:

• A function to convert a character to its numeric value.
• A function to convert one line into a single dimension array.
• A function to convert a series of lines into a multi-dimension array (calling the previous function).

Having each step in a sepatate function makes it easier to test and debug. Once you know one function is working, you can build the next one, and if anything goes wrong you know the problem is likely to be with the latest function.

Don’t worry about the overhead of function calls, as they’re unlikely to be significant for the size of input involved in the puzzles.