Day 2 - The gift that keeps on giving (errors)

This took me a while. Once again not because the puzzle itself was difficult, but because I keep trying to go too fast, not checking that I don’t make silly mistakes with my pointers and then taking way too long to find where the bug is.

Gift wrapping

We need to compute the amount of wrapping paper necessary to wrap the gifts with those dimensions. This amount is computed as: 2*w*l + 2*w*h + 2*l*h, to which we have to add the area of the smallest side (w*l, w*h or l*h).

This would be very easy to do in Python, but I don’t have access here to list comprehensions, map, etc. I could try to implement those generic tools, but that would just mean re-inventing Python, which isn’t really the point.

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

    printf("%s", fcontent);
}

Line splits

This is where I should have stopped to look carefully at what’s available in <string.h>, instead of stopping when I saw strchr, which made me do a lot more work than necessary. Let me start with that, however, and refactor after.

With strchr, we can find the next occurrence of a character. So to split by new line, we can look for the next \n and cut our string accordingly. Let’s make sure that it works:

char* ptr = fcontent;
char* nextLine = strchr(fcontent, '\n');
while (nextLine != NULL){
    printf("Gift:");
    for (char* p = ptr; p <= nextLine; p++)
        printf("%c", *p);
    ptr = nextLine+1;
    nextLine = strchr(ptr, '\n');
}

I see that everything is cut as it should be. Also, the newline character is written as well, since I used p <= nextLine. If I don’t want it, I can just do < instead. Now what? I don’t like the idea of doing everything in one go. I would like to build an array of “gift dimensions” so that I can keep my “computing area” logic separated. Let’s try something.

// initialize with max number of gifts
char* gifts[2000];
char* ptr = fcontent;
char* nextLine = strchr(fcontent, '\n');
int i = 0;
while (nextLine != NULL){
    // allocate memory for the number of characters in the gift
    gifts[i] = malloc(sizeof(char)*(nextLine-ptr));
    // copy characters from fcontent
    for (char* p = ptr; p <= nextLine; p++)
        gifts[i][p-ptr] = *p;

    ptr = nextLine+1;
    nextLine = strchr(ptr, '\n');
    i++;
}
int nGifts = i;
printf("Found %d gifts.\n", nGifts);

printf("%s\n", gifts[0]);
printf("%s\n", gifts[999]);

I get the right amount of gifts, but I have the same problem as day 1 with the strings: I didn’t put a \0 at the end, so it fails. Adding a +1 to the malloc and :

gifts[i][nextLine-ptr] = '\0';

We get the right thing. I don’t like that we have to allocate a fixed amount of gifts, however. Since I know how to count the number of occurrences of a character in a string, I can count the \n first to determine how many gifts I need. Let’s put that in a function:

int strcount(char* str, char c){
    int n = 0;
    for (int i=0; i < strlen(str); i++)
        if (str[i] == c)
            n++;
    return n;
}

int nGifts = strcount(fcontent, '\n')+1;
char* gifts[nGifts];

I get Found 1001 gifts. I hadn’t noticed it first but my previous code was wrong: since I start counting at 0, I should have added a 1 to my nGifts count. However, I only have 1000 gifts, because there is an extra blank line in my input file. I’ll just remove it.

That’s not good. I was actually ignoring the last line in my code and didn’t even notice it… I should probably do something a little bit more robust, but let’s juste restore the blank line and remove the +1 in the nGifts computation. Everything’s fine again. Let’s try to extract a function now.

And don’t forget to use malloc. gifts will be a char**, as it will point to a list of strings.

char** parse_lines(char* str){
    int nGifts = strcount(str, '\n');
    char** gifts = malloc(sizeof(char*)*nGifts);
    
    char* ptr = str;
    char* nextLine = strchr(ptr, '\n');
    int i = 0;
    while (nextLine != NULL){
        gifts[i] = malloc(sizeof(char)*(nextLine-ptr)+1);
        for (char* p = ptr; p <= nextLine; p++)
            gifts[i][p-ptr] = *p;
        gifts[i][nextLine-ptr] = '\0';
        ptr = nextLine+1;
        nextLine = strchr(ptr, '\n');
        i++;
    }

    return gifts;
}

int main(){
    char* fcontent = freadall(FILE_INPUT);
    char** gifts = parse_lines(fcontent);
    printf("%s\n", gifts[0]);
    printf("%s\n", gifts[999]);
}

This works, but we have an issue: we no longer know how many gifts we are getting. We could pass a pointer to parse_lines to an int that we update in the function, but I think this is a good opportunity to introduce structs.

typedef struct {
    size_t n;
    char** str_list;
} str_list_t;

str_list_t* parse_lines(char* str){
    str_list_t *gifts = malloc(sizeof(str_list_t));
    gifts->n = strcount(str, '\n');
    gifts->str_list = malloc(sizeof(char*)*gifts->n);

    char* ptr = str;
    char* nextLine = strchr(ptr, '\n');
    int i = 0;
    while (nextLine != NULL){
        gifts->str_list[i] = malloc(sizeof(char)*(nextLine-ptr)+1);
        for (char* p = ptr; p <= nextLine; p++)
            gifts->str_list[i][p-ptr] = *p;
        gifts->str_list[i][nextLine-ptr] = '\0';
        ptr = nextLine+1;
        nextLine = strchr(ptr, '\n');
        i++;
    }

    return gifts;
}

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

    str_list_t* gifts = parse_lines(fcontent);
    printf("Found %d gifts.\n", gifts->n);

    printf("%s\n", gifts->str_list[0]);
    printf("%s\n", gifts->str_list[gifts->n-1]);

    return 0;
}

Splitting dimensions

I know need to split each of these lines by the x character, and convert the strings to integers. I could reuse the same method with strchr, but it’s starting to get a bit ugly. This is where I finally looked at the documentation again and found strtok, which seems very well suited to the task.

typedef struct {
    int l;
    int w;
    int h;
} gift_t;

Then, using the example from the strtok documentation as a starting point, I get:

gift_t* parse_dimensions(char* str){
    char *tok_start = str;
    char *buffer = strtok(tok_start, "x");
    int ndim = 0;
    int dims[3];
    while (buffer){
        dims[ndim++] = atoi(buffer);
        buffer = strtok(NULL, "x");
    }

    gift_t* gift = malloc(sizeof(gift_t));
    gift->l = dims[0];
    gift->w = dims[1];
    gift->h = dims[2];

    return gift;
}

gift_t* gift = parse_dimensions(gifts->str_list[0]);
printf("l=%d, w=%d, h=%d\n", gift->l, gift->w, gift->h);

For the sake of honesty, I need to confess here that I didn’t get to this solution immediately. At first, I tried something a bit dumb, where parse_dimensions took two pointers as arguments – ptr and nextLine – which didn’t work well with strtok, so I had to make a copy, where of course I forgot to add the \0… This took a while. This version is much better.

Computing the area

Now that we have the dimensions, we can compute the wrapping surface, following the puzzle’s specifications. We can compute the three side’s areas, find the minimum value, and then sum everything up:

int surface_area(gift_t* gift){
    int side_a = gift->l*gift->w;
    int side_b = gift->l*gift->h;
    int side_c = gift->w*gift->h;

    int min = side_a;
    if (side_b < min)
        min = side_b;
    if (side_c < min)
        min = side_c;

    return 2*side_a + 2*side_b + 2*side_c + min;
}

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

    str_list_t* gifts = parse_lines(fcontent);
    printf("Found %d gifts.\n", gifts->n);

    int total_surface = 0;
    for (int i=0; i < gifts->n; i++){
        gift_t* gift = parse_dimensions(gifts->str_list[i]);
        total_surface += surface_area(gift);
    }

    printf("Total surface = %d", total_surface);
}

I realized, however, that I forgot to free any of the mallocs. That’s not great. I can actually do that as soon as I compute the surface area for a particular gift:

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

    str_list_t* gifts = parse_lines(fcontent);
    printf("Found %d gifts.\n", gifts->n);

    int total_surface = 0;
    for (int i=0; i < gifts->n; i++){
        gift_t* gift = parse_dimensions(gifts->str_list[i]);
        total_surface += surface_area(gift);
        free(gifts->str_list[i]);
        free(gift);
    }
    free(gifts);
    printf("Total surface = %d", total_surface);
}

Long ribbon

Part two doesn’t really add much difficulty, as we just have to compute another measure, this time for the “ribbon length”. It has to be the smallest side perimeter of the gift, plus its volume, for some reason.

Let’s compute both measure at once and use a struct to put everything together, as I’m starting to like this pattern:

typedef struct {
    int wrapping_area;
    int ribbon_length;
} measures_t;

measures_t* get_measures(gift_t* gift){
    int side_a = gift->l*gift->w;
    int side_b = gift->l*gift->h;
    int side_c = gift->w*gift->h;

    int periph_a = gift->l*2 + gift->w*2;
    int periph_b = gift->l*2 + gift->h*2;
    int periph_c = gift->w*2 + gift->h*2;

    int min = side_a;
    if (side_b < min)
        min = side_b;
    if (side_c < min)
        min = side_c;

    int minp = periph_a;
    if (periph_b < minp)
        minp = periph_b;
    if (periph_c < minp)
        minp = periph_c;

    measures_t* measures = malloc(sizeof(measures_t));
    measures->wrapping_area = 2*side_a + 2*side_b + 2*side_c + min;
    measures->ribbon_length = minp + gift->w*gift->l*gift->h;
    return measures;
}

// ...
int total_surface = 0;
int total_length = 0;
for (int i=0; i < gifts->n; i++){
    gift_t* gift = parse_dimensions(gifts->str_list[i]);
    measures_t* measures = get_measures(gift);
    total_surface += measures->wrapping_area;
    total_length += measures->ribbon_length;
    free(measures);
    free(gifts->str_list[i]);
    free(gift);
}
free(gifts);
printf("Total surface = %d\n", total_surface);
printf("Total length = %d\n", total_length);

Small improvements

It feels like I could use strtok also in the parse_lines function to parse by \n, rather than the strchr mess that we have. The function is not super complex, however. But we could change it to:

str_list_t* parse_lines(char* str){
    str_list_t *gifts = malloc(sizeof(str_list_t));
    gifts->n = strcount(str, '\n');
    gifts->str_list = malloc(sizeof(char*)*gifts->n);

    char *buffer = strtok(str, "\n");
    int i = 0;
    while(buffer){
        gifts->str_list[i] = malloc(sizeof(char)*strlen(buffer)+1);
        strcpy(gifts->str_list[i], buffer);
        buffer = strtok(NULL, "\n");
        i++;
    }

    return gifts;
}

We still have to be careful to add the +1 to our malloc here, which doesn’t see right to me, as I’d expect the buffer to have it added automatically, but it doesn’t seem to be the case. I’ll need to run some tests to better understand that later, but now I’m feeling tired, so let’s call it a success.