6
\$\begingroup\$

This is a follow-up to the question asked here: Advent of Code 2023 day 1: Trebuchet (Part 1 and 2)

Changes made:

  1. The code no longer assumes that all lines will fit into a fixed-size buffer. Although a fixed-size buffer is used, the code now checks whether a partial line was read. It continues processing and updating the first and last digits until the End of Line (EOL) is encountered. In case a partial line was read, the last 5 characters of the buffer are copied to the front (5 because the length of the longest digit name, such as eight or seven, is 5). The next read then starts 5 characters past the beginning of the buffer.

  2. Error handling has been added.

  3. Proper sizes have been utilized (attempted).

  4. There was a memory leak in the code because the FILE * was not passed to fclose(). This issue has been fixed.

  5. Another member has been added to the digit_map structure that keeps track of the number of bytes that can be skipped after a digit name has been matched in part 2 of the problem. This improvement saves us multiple unnecessary iterations.

  6. For every non-numeric character, around 9 calls to strncmp() were being made. Whilst a prefix tree or similar structure hasn't been implemented or used, a check has been added to verify if the non-numeric character begins any digit before making all the comparisons.

Review request:

Are there any flaws or bugs in what I have implemented so far? Have I missed any cases? Do you see any off-by-one errors? Any general suggestions, style improvements, or potential undefined behavior et cetera.

Part 1:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <errno.h>
#include <stdint.h>

#define BUFSIZE 256

struct digit_pair {
    unsigned int first;
    unsigned int last;
};

static struct digit_pair first_last_digits(const char *buf)
{
    unsigned int first = 0;
    unsigned int last = 0;

    /* Note: This would return true for 0, but 0 is not part of the 
     * problem specification, or the input, so we don't need to check
     * for it.
     */
    for (size_t i = 0; buf[i]; ++i) {
        if (isdigit((unsigned char) buf[i])) {
            first = !first ? buf[i] - '0' : first;
            last = buf[i] - '0';
        }
    }

    return (struct digit_pair) { first, last };
}

static uintmax_t calibration_total(FILE *stream)
{
    char buf[BUFSIZE];
    uintmax_t total = 0;
    unsigned int first = 0;
    unsigned int last = 0;

    while (fgets(buf, sizeof buf, stream)) {
        /* If EOL was seen, parse it normally.
         * Else keep the intermediate first value, and continue updating last
         * until the EOL is actually seen.
         */
        struct digit_pair new = first_last_digits(buf);

        if (!first) {
            first = new.first;
        }

        if (new.last) {
            last = new.last;
        }

        const size_t len = strlen(buf);

        if (len > 0 && buf[len - 1] != '\n') {
            continue;
        }

        total += first * 10 + last;
        first = last = 0;
    }
    return total;
}

int main(int argc, char **argv)
{
    if (!argv[0]) {
        fputs("Fatal - A null argv[0] was passed in.", stderr);
        return EXIT_FAILURE;
    }

    if (argc != 2) {
        fprintf(stderr, "Error - No file provided.\n"
                "Usage: %s <FILE>\n", argv[0]);
        return EXIT_FAILURE;
    }

    errno = 0;
    FILE *const file = fopen(argv[1], "r");

    if (!file) {
        if (errno) {
            perror(argv[1]);
        } else {
            fputs("Error - Failed to open file.fputs\n", stderr);
        }
        return EXIT_FAILURE;
    }

    const uintmax_t total = calibration_total(file);

    if (ferror(file) || !feof(file)) {
        fclose(file);
        fputs("Error - Failed to read file.\n", stderr);
        return EXIT_FAILURE;
    }

    printf("%ju\n", total);
    fclose(file);
    return EXIT_SUCCESS;
}

Part 2:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <errno.h>
#include <stdint.h>

#define BUFSIZE 256

struct digit_pair {
    unsigned int first;
    unsigned int last;
};

struct digit_map {
    const char *const dname;
    const unsigned int val;
    const unsigned int bytes_skippable; /* On a match, we can skip this amount. */
} digits[] = {
    { "one", 1, 1 },
    { "two", 2, 1 },
    { "three", 3, 3 },
    { "four", 4, 3 },
    { "five", 5, 2 },
    { "six", 6, 2 },
    { "seven", 7, 3 },
    { "eight", 8, 4 },
    { "nine", 9, 2 }
};

/* The author was not ready to part with this piece of code, so this has been commented out. */ 
/*static size_t get_next_pos(const char *buf) */
/*{ */
/*    /1* */
/*     *  "one"   --- Skip 1 char, as 'e' might start "eight". */
/*     *  "two"   --- Skip 1 char, as 'o' might start "one". */
/*     *  "three" --- Skip 3 chars, as 'e' might start "eight". */
/*     *  "four"  --- Skip the remaining chars. */
/*     *  "five"  --- Skip 2 chars, as 'e' might start "eight". */
/*     *  "six"   --- Skip the remaining chars. */
/*     *  "seven" --- Skip 3 chars, as 'n' might start "nine". */
/*     *  "eight" --- Skip the remaining chars. */
/*     *  "nine"  --- Skips 2 chars, as 'e' might start "eight". */
/*     *1/ */
/*    switch (buf[0]) { */
/*        case 'o': return 1; */
/*        case 't': return buf[1] == 'w' ? 1 : 3; */
/*        case 'f': return buf[1] == 'o' ? 3 : 2; */
/*        case 's': return buf[1] == 'i' ? 2 : 3; */
/*        case 'e': return 4; */
/*        case 'n': return 2; */
/*    } */

     /* /1* Now that I think of it, none of this was necessary. */
     /*  * Simply add another member to the digit_map struct. */
     /*  *1/ */
     /* return 0; */
 /* } */

static struct digit_pair first_last_digits(const char *buf)
{
    unsigned int first = 0;
    unsigned int last = 0;

    /* Note: This would return true for 0, but 0 is not part of the 
     * problem specification, or the input, so we don't need to check
     * for it.
     */
    for (size_t i = 0; buf[i]; ++i) {
        if (isdigit((unsigned char) buf[i])) {
            first = !first ? buf[i] - '0' : first;
            last = buf[i] - '0';
        } else if (strchr("otfsen", buf[i])) {  /* Check if buf[i] begins any digit. */
            for (size_t j = 0; j < sizeof digits / sizeof *digits; ++j) {
                if (!strncmp(buf + i, digits[j].dname, strlen(digits[j].dname))) {
                    first = !first ? digits[j].val : first;
                    last = digits[j].val;
                    i += digits[j].bytes_skippable - 1;
                    break;
                }
            }
        }
    }

    return (struct digit_pair) { first, last };
}

static uintmax_t calibration_total(FILE *stream)
{
    char buf[BUFSIZE];
    uintmax_t total = 0;
    unsigned int first = 0;
    unsigned int last = 0;
    size_t size = sizeof buf;
    char *tmp = buf;

    while (fgets(tmp, size, stream)) {
        /* If EOL was seen, parse it normally.
         * Else keep the intermediate first value, and continue updating last
         * until the EOL is actually seen.
         */
        struct digit_pair new = first_last_digits(buf);

        if (!first) {
            first = new.first;
        }

        if (new.last) {
            last = new.last;
        }

        const size_t len = strlen(buf);

        if (len > 0 && buf[len - 1] != '\n') {
            /* Move the last 5 characters to the start of the buffer, 
             * as we'd not detect it if a digit is split into two lines, 
             * 5, because the length of the longest digit is 5. 
             */
            memmove(buf, buf + len - 5, 5);
            tmp = buf + 5;

            /* Adjust the buffer size. The check is required because each 
             * subsequent read without an EOL would otherwise decrease size
             * by 5.
             */
            size = sizeof buf - 5 == size ? size : size - 5;
            continue;
        }

        total += first * 10 + last;
        first = last = 0;
        tmp = buf;
        size = sizeof buf;
    }

    return total;
}

int main(int argc, char **argv)
{
    if (!argv[0]) {
        fputs("Fatal - A null argv[0] was passed in.", stderr);
        return EXIT_FAILURE;
    }

    if (argc != 2) {
        fprintf(stderr, "Error - No file provided.\n"
                "Usage: %s <FILE>\n", argv[0]);
        return EXIT_FAILURE;
    }

    errno = 0;
    FILE *const file = fopen(argv[1], "r");

    if (!file) {
        if (errno) {
            perror(argv[1]);
        } else {
            fputs("Error - Failed to open file.\n", stderr);
        }
        return EXIT_FAILURE;
    }

    const uintmax_t total = calibration_total(file);

    if (ferror(file) || !feof(file)) {
        fclose(file);
        fputs("Error - Failed to read file.\n", stderr);
        return EXIT_FAILURE;
    }

    fclose(file);
    printf("%ju\n", total);
    return EXIT_SUCCESS;
}
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Since Part 2 is mostly a superset of Part 1, I'll just review that.

288373.c:28:30: warning: operand of ‘?:’ changes signedness from ‘int’ to ‘unsigned int’ due to unsignedness of other operand [-Wsign-compare]
   28 |             first = !first ? buf[i] - '0' : first;
      |                              ^~~~~~~~~~~~
288373.c:28:43: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
   28 |             first = !first ? buf[i] - '0' : first;
      |                                           ^
288373.c:29:20: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
   29 |             last = buf[i] - '0';
      |                    ^~~

We could eliminate these with a small digit_value() function, or perhaps use unsigned char for our buffer.


struct digit_map {
    const char *const dname;
    const unsigned int val;
    const unsigned int bytes_skippable; /* On a match, we can skip this amount. */
} digits[] = {

Is it really necessary to store val here, given it can be derived from the index into this array?

Even with the comment, it's not clear how bytes_skippable is computed. For example, why can we skip only 3 bytes of "three", when no digit name begins "ee"? It's harmless, of course (unlike over-skipping), but makes me question whether this optimisation is premature. It also creates more work if we were to localise to a different input language (though we could automate that, I guess).


Here's another case where the input language is baked-in:

  } else if (strchr("otfsen", buf[i])) {  /* Check if buf[i] begins any digit. */

We could derive that string automatically from the list of digit names, but again it's not clear that this really is an optimisation. If you have benchmark results justifying it, then it's worth including at least summary evidence in comments.


I wonder whether a series of strstr() might be a more efficient search method? Of course, the most efficient method would be to construct a finite-state automaton from the digit names (and actual digits, of course). That would simplify the line-handling code, as we wouldn't need to read more than one character at a time.


unsigned int first = 0;
unsigned int last = 0;

These variables wouldn't be necessary if we owned a struct digit_pair and passed it by reference to first_last_digits to populate.


char *tmp = buf;

That's a very poor name for the read insert position.


Here's another language dependency, involving a magic number that appears several times:

        /* Move the last 5 characters to the start of the buffer, 
         * as we'd not detect it if a digit is split into two lines, 
         * 5, because the length of the longest digit is 5. 
         */
        memmove(buf, buf + len - 5, 5);
        tmp = buf + 5;

Since the longest digit name is five characters, surely we only need to preserve the last four from the buffer? That's the largest amount that could be an incomplete digit name.

        size = sizeof buf - 5 == size ? size : size - 5;

This is weird. At this point, we're either on the first iteration, and size is sizeof buf, or else we're on a subsequent iteration and it's sizeof buf - 5. In both cases the result is the same: sizeof buf - 5.


if (argc != 2) {
    fprintf(stderr, "Error - No file provided.\n"
            "Usage: %s <FILE>\n", argv[0]);
    return EXIT_FAILURE;
}

The program would be much more ergonomic if it could read from standard input when a file name isn't specified.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ "Re: For example, why can we skip only 3 bytes of "three", when no digit name begins "ee"?" ==> After the first character of the digit that we are currently at (t here), three more characters (hre) can be skipped, as the last e might start eight. I should probably move the comment from get_next_pos() to the struct definition, and clarify this. \$\endgroup\$
    – Harith
    Feb 7 at 7:32
3
\$\begingroup\$

General Observations

While it is interesting to see your thoughts in the code, if you are using a version control system such as Git there is no reason to comment out code, you can go back to an earlier version of the code if you need to. Generally, commented out code means the code is not ready for review.

Since Part 2 is an extension of Part 1 you might only want a review of Part 2 in the future. Since Part 1 and Part 2 provide the same interface calibration_total(FILE* stream) the code could be in a header file for each part instead (part1.h and part2.h).

Type mismatch, as G. Sliepen indicated in the first review - you want to be careful where you use the size_t type. My compiler (Visual Studio 2022 Professional) reports a type mismatch and possible data lose on the following line for the variable size:

    while (fgets(tmp, size, stream)) {

Use Standard Constants Where Possible

The code is already using the standard constants EXIT_SUCCESS and EXIT_FAILURE, so there is no need to define your own BUFSIZE constant. The stdio.h file includes a standard constant called BUFSIZ, which is guaranteed to be at least 256, and may be larger. The value is based on the optimum value for file I/O on the system.

Complexity of the main Function

The main() function is too complex; there should be a function to parse the command line arguments. In this case the function to parse the arguments could just return the file pointer if the file is opened in the function to parse the command line arguments. In most cases a structure with the necessary values might be better.

Parsing the Command Line Arguments

Check the value of argc before checking the value of any of the argv contents. The test for argv[0] being NULL is not necessary, argv[0] should always be the name of the program you are running, as far as I know, no operating system will allow argv[0] to be NULL.

Don't Depend on Users Doing the Correct Thing

This comment could indicate a future bug since what to do for zero is undefined.

    /* Note: This would return true for 0, but 0 is not part of the
     * problem specification, or the input, so we don't need to check
     * for it.
     */

Style Issue

This is an opinion that isn't shared by all C and C++ programmers, but rather than have the opening brace ({) for a section of code at the end of the line, it is easier to read code that has the opening brace on its own line that is properly indented.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.