Advent of Code 2015 Day 2: I Was Told There Would Be No Math

Input is a list of present dimensions, in the format 1x2x3. The numbers represent the length, width and height respectively. Each set of dimensions is on its own line.

Part 1

The first thing we need is a data structure to represent a present with its dimensions:

typedef struct present {
    int length;
    int width;
    int height;
} present_t;

We then need a function to parse a string representing a present and return a populated present_t. There are several ways we could do this.

Use a regular expression library. The regular expression would be: ^([0-9]+)x([0-9]+)x([0-9]+)$. However, there is no regular expression parser in the standard library, and our self-imposed restriction is to avoid third party libraries.

Write a regular expression parser. This needs to extract capturing groups as well as checking for matches. There is an example in The Practice of Programming, but it is very basic, does not support ranges (e.g. [0-9]) and only tells you if a match has been found. It does not support capturing groups.

Write a generic equivalent of the PHP explode function. The explode function splits a string into an array of strings based on a delimiter (x in this case).

Use existing standard library functions. The most obvious function is strtok. However, this modifies the string, and as a result does not work with constant strings, which makes testing harder. It is also not thread safe, unless we use strtok_r, but that is part of POSIX rather than the C standard library. size_t strcspn(const char *dest, const char *src) from string.h is another option, as it finds the number of characters in dest before the first instance of src.

Write a parser specifically for this function. This would possibly be the easiest option, but also the least reusable.

In the end I chose to write a generic equivalent of the PHP explode function, because that would be useful for later exercises. I will write this process up as a separate article, however the struct and function signature are:

typedef struct aoc_explode_result {
    size_t size;
    char **data;
} aoc_explode_result_t;

aoc_explode_result_t aoc_explode(const char * const separator, const char * const input);

The parse_present function is then very simple, it calls the aoc_explode function and assigns the relevant parts of the result to the struct:

present_t parse_present(const char * const input)
{
    present_t present = {
        .length = 0,
        .width = 0,
        .height = 0,
    };

    aoc_explode_result_t explode_result = aoc_explode("x", input);

    if (explode_result.size == 3) {
        present.length = atoi(explode_result.data[0]);
        present.width = atoi(explode_result.data[1]);
        present.height = atoi(explode_result.data[2]);
    }

    return present;
}

Next we need to calculate the wrapping paper required for each present, which is defined as the surface area of the present plus the area of the smallest side. These can be calculated as:

Surface area (2 x length x width) + (2 x width x height) + (2 x length x height).

Smallest side: Rather than calculating all the sides and finding the smallest, we can calculate the product of the three dimensions and then divide by the largest dimension to cancel it out. For example, (2 * 3 * 4) / max(2, 3, 4) becomes (2 * 3 * 4) / 4, which is equivalent to 2 * 3.

We also need to consider whether we calculate the size of the wrapping paper in parse_present and store it in present_t, or calculate it separately. Since the wrapping paper size is not part of the input, and therefore is not parsed, we will use a separate function to calculate it as and when required. We can also separate the calculation of the surface area and the smallest side into different functions, so they can be tested independently.

Calculating the surface area as a function:

int surface_area(present_t present) {
    int area = 0;

    if (present.length > 0 && present.width > 0 && present.height > 0) {
        area += (2 * present.length * present.width);
        area += (2 * present.width * present.height);
        area += (2 * present.length * present.height);
    }

    return area;
}

Calculating the smallest side as a function:

int smallest_side(present_t present) {
    int side = 0;

    if (present.length > 0 && present.width > 0 && present.height > 0) {
        side = (present.length * present.width * present.height);
        side /= aoc_max_int(present.length, aoc_max_int(present.width, present.height));
    }

    return side;
}

Combining the two to calculate the wrapping paper:

int wrapping_paper(present_t present) {
    return surface_area(present) + smallest_side(present);
}

Now we need to combine all of the above to calculate the total wrapping paper for all presents. Since we have one present per line in our input, which we have read in one go, we need to:

Split the input into lines
Parse each line as a present
Calculate the wrapping paper for the present
Add the wrapping paper to our total

Final code:

int total_wrapping_paper(const char * const input) {
    int total = 0;
    aoc_explode_result_t present_lines = aoc_explode("\n", input);
    present_t present;

    for (size_t p = 0; p < present_lines.size; p++) {
        present = parse_present(present_lines.data[p]);
        total += wrapping_paper(present);
    }

    return total;
}

Part 2

We can use the same data structure as part 1, however the challenge is now to find the sum of:

Present volume: Length x width x height.

Perimeter of smallest side: Since calculating the perimeter of a side is trivial, find the smallest of (length + width), (length + height), (width + height), then multiply by two.

Volume function:

int volume(present_t present) {
    if (present.length > 0 && present.width > 0 && present.height > 0) {
        return present.length * present.width * present.height;
    }

    return 0;
}

Smallest side perimeter function:

int smallest_side_perimeter(present_t present) {
    if (present.length > 0 && present.width > 0 && present.height > 0) {
        return 2 * aoc_min_int(present.length + present.width, aoc_min_int(present.length + present.height, present.width + present.height));
    }

    return 0;
}

The ribbon function combines the two:

int ribbon(present_t present) {
    return volume(present) + smallest_side_perimeter(present);
}

Finally, we need to calculate the total ribbon:

Split the input into lines
Parse each line as a present
Calculate the ribbon for the present
Add the ribbon to our total

This is fairly short:

int total_ribbon(const char * const input) {
    int total = 0;

    aoc_explode_result_t present_lines = aoc_explode("\n", input);
    present_t present;

    for (size_t p = 0; p < present_lines.size; p++) {
        present = parse_present(present_lines.data[p]);
        total += ribbon(present);
    }

    return total;
}