1
\$\begingroup\$

Task:

The task involves analyzing a calibration document containing lines of text. Each line represents a calibration value that needs to be recovered by extracting the first and last digits (which may also be spelled out as words) and combining them into a two-digit number. The goal is to find the sum of all these calibration values.

For example:

two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen

In this example, the calibration values are 29, 83, 13, 24, 42, 14, and 76. Adding these together produces 281.

Code:

#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <iterator>
#include <regex>

static int get_digit(const std::string &line, const std::regex &accept) 
{
    static const auto digit_names{std::to_array(
            {"zero", "one", "two",   "three", "four",
             "five", "six", "seven", "eight", "nine"})};
    ptrdiff_t digit = -1;
    std::smatch match;

    if (std::regex_search(line, match, accept)) {
        const auto it = std::find(std::begin(digit_names),
                                  std::end(digit_names), match.str(1));

        if (it != std::end(digit_names)) {
            digit = std::distance(std::begin(digit_names), it);
        } else {
            digit = std::stoi(match.str(1));
        }
    }

    return digit;
}

static int get_first_digit(const std::string &line) 
{
    const std::regex accept(
        R"((\d|zero|one|two|three|four|five|six|seven|eight|nine))");
    return get_digit(line, accept);
}

static int get_last_digit(const std::string &line)
{
    const std::regex accept(
        R"(.*(\d|zero|one|two|three|four|five|six|seven|eight|nine))");
    return get_digit(line, accept);
}

static int calc_calibration_total(std::istream &in_file)
{
    std::string line{};
    int sum{};

    while (std::getline(in_file, line)) {
        const int first_digit = get_first_digit(line);

        if (first_digit != -1) {
            sum += first_digit * 10 + get_last_digit(line);
        }
    }
    return sum;
}

int main(int argc, char *argv[]) 
{
    if (argc != 2) {
        std::cerr << "Usage: " << (argv[0] ? argv[0] : "aoc_1b") << " <filename>\n";
        return EXIT_FAILURE;
    }

    std::ifstream in_file(argv[1]);
    const int sum{calc_calibration_total(in_file)};

    if (!in_file.eof()) {
        std::cerr << "Error: failed to read input file " << argv[1] << " - "
                  << std::error_code{errno, std::generic_category()}.message()
                  << ".\n";
        return EXIT_FAILURE;
    }

    std::cout << sum << "\n";
}

Review Request:

General coding comments, style, bad/outdated practices et cetera.

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

I don’t see that regular expressions are really necessary here. This does not seem like a situation that requires their complexity or cost. On top of that, by doing two separate regexes, you have shot yourself in the foot, and introduced a bug.

You don’t need regular expressions

Let’s consider the basics of the first part of what you are trying to do. You have an input string, and you have a list of strings, and you want to find the first of that list of strings in the input string.

So:

constexpr auto needles = std::to_array<std::string_view>({
    "0", "1", "2", ..., "9",
    "zero", "one", "two", ..., "nine"
});

auto found = std::ranges::subrange{std::ranges::end(input), std::ranges::end(input)};

for (auto&& needle : needles)
{
    auto const result = std::ranges::search(input, needle);
    if (std::ranges::begin(result) < std::ranges::begin(found))
        found = result;
}

if (std::ranges::begin(found) == std::ranges::end(input))
    throw std::runtime_error{"no numbers in input"};

Other than a few fairly minor details, that’s basically the first half of the problem solved. The second half—finding the last occurrence—isn’t much different.

Here are some tips to improve the above:

  • Instead of an array of just the needle strings, make an array of tuples combining each needle string with the number it maps to. It makes no sense to compute the number with std::distance() or, worse, std::stoi() when you can just encode that data at compile time. Plus, keeping the string and number together means you don’t need to care about the order of needles in the needle array anymore, which means you can sort it (at compile-time), which will help if you have needles that are substrings of other needles.

  • If the input strings are very long, you could use searchers instead of the vanilla search algorithm.

  • You don’t need to search the whole input string for each needle. Once you’ve found a needle at position \$x\$, you only need to search for another needle of length n from the beginning to position \$(x - 1) + n\$. If the needle is found after that, then it is after the previously found needle (or concurrent with it, in the case that some needles are substrings of other needles).

Regular expressions are overkill.

You can’t break this into two independent sub-problems

Your code basically looks like this:

auto get_first_digit(std::string const& line)
{
    // ...
}

auto get_last_digit(std::string const& line)
{
    // ...
}

auto calc_calibration_total(std::istream& in_file)
{
    // for each line in in_file
    {
        auto digit_1 = get_first_digit(line);
        auto digit_2 = get_last_digit(line);

        // ... etc.
    }

    // ... etc.
}

This structure cannot work, no matter what is in the commented bits.

Easier than trying to explain why, I can demonstrate. Try running your algorithm with the line “sevenine”.

Want an even more damning example? Try the line “3”. Or “three”.

Do you understand the problem now? Unless it is intended that the first and last digit strings overlap… and even to wholly overlap… then you cannot isolate the search for the last digit from the search for the first digit. Once you find the first digit, you need that information for the search for the last digit. Specifically, you need to know where the first digit ends, so that you can start the search for the last digit after that.

If you wanted to solve this with regexes alone, then you would need to do both searches at once. Either that, or once the first digit string is found, you need to create a whole new string with everything up to the end of that first digit string removed. Either way is expensive.

With simple searches, you don’t need to create whole new strings for the second part of the search. You can just use the iterators from the first search to mark where to begin the second.

Whatever method you use, the point is that the second search cannot be fully independent of the first. Somehow, you need to carry information from the first search over to the second, to let it know where to start the search from. Or, put another way, the search for the second digit has to know where not to look (that is, it is not to look in the place where the first digit was found).

Code review

#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <iterator>
#include <regex>

There are quite a few includes here that are not necessary, and a few necessary includes that are missing. I don’t see any reason for <cstdint> or <cstring>. On the other hand, I see std::error_code but no <system_error>.

static int get_digit(const std::string &line, const std::regex &accept)

I notice you’ve made all your functions static. There is no real need for this. I suppose it’s one of those “tricks” that are popular in “coding challenge”-style C++. But it strikes me as having dubious benefit.

Now, as for the const std::string &line style, that is C-style layout, not C++-style. In C++, we keep the type modifiers with the type.

  • C-style: const std::string &line
  • C++-style: const std::string& line
  • C++-style (east const): std::string const& line
    static const auto digit_names{std::to_array(
            {"zero", "one", "two",   "three", "four",
             "five", "six", "seven", "eight", "nine"})};

I’m a little baffled by the use of std::to_array() here.

The purpose of std::to_array() is to handle situations where you only want partial deduction of std::array’s template parameters. Specifically, it is for when you want to force the type, but still deduce the count. That means you almost never want to write just std::to_array({...}); you almost always want std::to_array<type>({...}). Without the <type>, you might as well just write std::array{...}.

Which means, in this case:

static const auto digit_names{
    std::array{
        "zero", "one", "two",   "three", "four",
        "five", "six", "seven", "eight", "nine"
    }
};

// or:

static const std::array digit_names{
    "zero", "one", "two",   "three", "four",
    "five", "six", "seven", "eight", "nine"
};

But do bear in mind that this is creating an array of char const*… which is not great. Better would be to create an array of string views, because when comparing strings to string views, the comparison can be short-circuited if the size is not the same (whereas, for a char const*, it would effectively have to do std::strcmp() every time).

    ptrdiff_t digit = -1;

This should be std::ptrdiff_t to begin with (and you should include the right header)… except… why is it not int? That is what you want it to be in the end in any case. What is the point of making it std::ptrdiff_t?

    if (std::regex_search(line, match, accept)) {
        const auto it = std::find(std::begin(digit_names),
                                  std::end(digit_names), match.str(1));

        if (it != std::end(digit_names)) {
            digit = std::distance(std::begin(digit_names), it);
        } else {
            digit = std::stoi(match.str(1));
        }
    }

Oof, it makes my skin crawl how inefficient this is. It’s not even your fault. I’ll let you in on a dirty little secret. The standard C++ regex library is TERRIBLE. It’s design is terrible, and most implementations are terrible. I never use it. I rarely use regex in C++ at all, but when I do, I use Boost.Regex. (I’ve also been very interested in trying out Hana Dusíková’s CTRE, but haven’t had a chance yet.) But std::regex? 💩.

(There is a particularly hilarious example that I vaguely recall from Dusíková’s CTRE proposal paper, where she was benchmarking different regex libraries, and in one case, a match that took around 20 seconds with Boost.Regex took 20 MINUTES with std::regex.)

One problem with std::regex is that is entirely based on strings. It predates string views. So, for example, when you do match.str(1), instead of just getting a view of the matched needle in line, a whole new string has to be constructed. Just to do the lookup in your digit names table. (To be fair, your needles are very short, so the small string optimization almost certainly applies. Still.)

And then there’s std::stoi(). As with std::regex, std::stoi() is a raging dumpster fire, and a performance-sucking black hole in your program. The problem with std::stoi() is not just that it requires strings (doesn’t really matter here, because you are forced to construct a string anyway thanks to std::regex). The thing that people don’t realize about std::stoi() until the day it bites them in the ass is that std::stoi() is locale-dependent. You are assuming that “0123456789” are digits… but you may find that the current locale thinks otherwise.

There’s no easy fix for std::regex (though Boost.Regex is mostly a far superior drop-in replacement). But at least for std::stoi() we now have a much better alternative: std::from_chars().

HOWEVER

You’re already doing a lookup (in the digit_names array). Why not just go all-in and fully use the lookup?

static auto get_digit(std::string const& line, std::regex const& accept)
{
    constexpr auto digits = std::to_array<std::tuple<std::string_view, int>>({
        { "0", 0 },
        { "1", 1 },
        { "2", 2 },
        // ...
        { "9", 9 },
        { "zero", 0 },
        { "one", 1 },
        { "two", 2 },
        // ...
        { "nine", 9 }
    });

    constexpr auto project_string_view =
        [] (auto&& digit) { return std::get<std::string_view>(d); };

    std::smatch match;
    if (std::regex_search(line, match, accept))
    {
        auto const it = std::ranges::find(digits, match.str(1), project_string_view);
        return std::get<int>(*it);
    }
    else
    {
        throw std::invalid_argument{"no digit in line"};
    }
}

As you can see, it simplifies the function considerably. You could use the same digits data for the search. The regex is basically just:

auto const regex = std::regex{
    '('
    + (digits
        | std::views::elements<0>
        | std::views::join_with('|')
        | std::ranges::to<std::string>
    )
    + ')'
};

Or, if you want to avoid the bug I mentioned and search for both digits at once:

auto const regex_disjunction = '('
    + (digits
        | std::views::elements<0>
        | std::views::join_with('|')
        | std::ranges::to<std::string>
    )
    + ')'
;
auto const regex = std::regex{
    ".*?"
    + regex_disjunction
    ".*"
    + regex_disjunction
    ".*"
};

I’m not suggesting you do this, of course. But you could.

static int calc_calibration_total(std::istream &in_file)
{
    std::string line{};
    int sum{};

    while (std::getline(in_file, line)) {
        const int first_digit = get_first_digit(line);

        if (first_digit != -1) {
            sum += first_digit * 10 + get_last_digit(line);
        }
    }
    return sum;
}

This works, I guess, but it’s not very flexible. What if the data is already loaded in a vector of strings?

The modern way to handle something like this would be to use composable range operations. So, for example:

template <std::input_range R>
requires std::convertible_to<std::ranges::range_value_t<R>, std::string_view>
constexpr auto calculate_trebuchet_calibration(R&& lines)
{
    return std::ranges::fold_left(
        lines
            | std::views::transform(parse_digits)
            | std::views::transform(generate_calibration_value)
        ,
        0,
        std::plus<>{}
    );
}

Note that there is not a single branch or loop in view. The logic is clean and simple; a straight line. You literally cannot screw it up.

(It is unfortunate that the ranges library doesn’t allow a terminating reduction function. It would have been nice to be able to write:

template <std::input_range R>
requires std::convertible_to<std::ranges::range_value_t<R>, std::string_view>
constexpr auto calculate_trebuchet_calibration(R&& lines)
{
    return lines
        | std::views::transform(parse_digits)
        | std::views::transform(generate_calibration_value)
        | xxx::reduce(std::plus<>{})
    ;

    // ... or:
    return lines
        | std::views::transform(parse_digits)
        | std::views::transform(generate_calibration_value)
        | xxx::sum
    ;
}

But, alas, we have to work with the tools we have.)

Since you intend to read from a stream, you could write a helper function:

auto calculate_trebuchet_calibration(std::istream& in)
{
    auto const result = calculate_trebuchet_calibration(std::views::istream<std::string>(in));

    if (not in)
        throw std::runtime_error{"failed to read trebuchet calibration data from file"};

    return result;
}

Then it’s just a matter of writing the transform functions:

auto parse_digits(std::string_view) -> std::tuple<digit, digit>;
auto generate_calibration_value(std::tuple<digit, digit>) -> int;

Put a pin in all that, because this is not the only way to do this, and may not be the best way for this particular problem. Let’s look at main():

    std::ifstream in_file(argv[1]);
    const int sum{calc_calibration_total(in_file)};

    if (!in_file.eof()) {
        std::cerr << "Error: failed to read input file " << argv[1] << " - "
                  << std::error_code{errno, std::generic_category()}.message()
                  << ".\n";
        return EXIT_FAILURE;
    }

This is a bad pattern. If there was an error reading the input file, that should have been determined in the function reading the input file. Trying to do it here, after the fact, is a hack.

Furthermore, .eof() is not an error status, nor should it be interpreted as one. If you want to determine whether an error occurred, you either need to check .fail() and .bad(), or, more simply, just use the stream’s bool conversion. In other words, if (!in_file.eof()) is the wrong way to check for an error; it should be if (!in_file).

If you want to properly handle IOstream errors, I would suggest the first step is always enabling exceptions on the stream. That will save you a lot of headaches, to begin with. If you don’t want to do that, then you should at least do a check for .is_open() before starting anything else.

Next, you need a proper type to parse. Something like:

class trebuchet_calibration_data
{
public:
    friend auto operator>>(std::istream& in, trebuchet_calibration_data& data)
        -> std::istream&
    {
        auto s = std::string{};
        if (in >> s)
        {
            // Extract the two digits here.
            //
            // If the extraction is successful, then:
            //      data.digit_1 = digit_1;
            //      data.digit_2 = digit_2;
            //
            // If the extraction was *not* successful, then:
            //      in.setstate(std::ios_base::failbit);
        }

        return in;
    }

    int digit_1 = 0;
    int digit_2 = 0;
};

With that, error handling is mostly automatic. while (std::getline(in_file, line)) will stop on the first error, as will std::views::istream. This is the proper way to work with IOstreams.

So, perhaps the best idea is to make a custom type like the above, and a program structure like:

namespace trebuchet_calibration {

enum class calibration_error
{
    // list of potential errors
};

// <system_error> stuff...
template <>
struct std::is_error_code_enum<calibration_error> : true_type
{};

class error_category_t : public std::error_category
{
public:
    auto name() const noexcept -> char const* override
    {
        return "trebuchet_calibration";
    }

    auto message(int value) const -> std::string override
    {
        switch (static_cast<calibration_error>(value))
        {
        // ...
        default:
            return "{unrecognized error}";
        }
    }
};

auto error_category() -> std::error_category const&
{
    static auto const cat = error_category_t{};
    return cat;
}

auto make_error_code(calibration_error value) -> std::error_code
{
  return std::error_code{static_cast<int>(value), error_category()};
}

class calibration_data
{
public:
    static auto parse(std::string_view s)
        -> std::expected<calibration_data, calibration_error>
    {
        // Try to extract the two digits from the string view.
    };

    friend auto operator>>(std::istream& in, calibration_data& data)
        -> std::istream&
    {
        auto s = std::string{};
        if (in >> s)
        {
            if (auto const result = parse(s); result)
                data = *result;
            else
                in.setstate(std::ios_base::failbit);
        }

        return in;
    }

    constexpr auto calculate_value() const noexcept
    {
        return (digit_1 * 10) + digit_2;
    }

    int digit_1 = 0;
    int digit_2 = 0;
};

template <std::input_range R>
requires std::convertible_to<std::ranges::range_value_t<R>, calibration_data>
constexpr auto calculate(R&& data)
{
    return std::ranges::fold_left(
        lines | std::views::transform(&calibration_data::calculate_value),
        0,
        std::plus<>{}
    );
}

template <std::input_range R>
requires std::convertible_to<std::ranges::range_value_t<R>, std::string_view>
constexpr auto calculate(R&& strings)
{
    return calculate(strings
        | std::views::transform([] (auto&& s)
            {
                auto result = calibration_data::parse(s);
                if (not result)
                    throw std::system_error{make_error_code(result.error())};
                return *result;
            }
        )
    );
}

auto calculate(std::istream& in)
{
    auto const result = calculate(std::views::istream<calibration_data>(in));
    if (not in)
        throw std::runtime_error{"failed to parse trebuchet calibration data"};

    return result;
}

} // namespace trebuchet_calibration

auto handle_errors(std::string_view prog) -> int
{
    try
    {
        throw;
    }
    catch (no_filename_given_error const&)
    {
        std::cerr << "Usage: " << prog << " <filename>\n";
    }
    catch (std::exception const& x)
    {
        std::cerr << prog << ": " << x.what() << '\n';
    }
    catch (...)
    {
        std::cerr << prog << ": unknown error\n";
    }

    return EXIT_FAILURE;
}

auto main(int argc, char* argv) -> int
{
    try
    {
        if (argc != 2)
            throw no_filename_given_error{};

        auto in_file = std::ifstream{argv[1]};
        if (not in_file.is_open())
            throw open_file_error{argv[1]};

        auto const result = trebuchet_calibration::calculate(in_file);
        std::cout << result << '\n';
    }
    catch (...)
    {
        return handle_errors(argv[0] ? argv[0] : "aoc_1b");
    }
}

That’s just a very rough approximation of one kind of solution. Most of it is error handling (the <system_error> stuff is very verbose).

It might even be better to have the calculate() functions return a expected<int, calibration_error> instead of just an int, and avoid throwing anything at all. You’d have to write a monadic version of std::plus<> for the fold, but that wouldn’t be hard.

Anywho, that should be enough for a review.

In summary:

  • You don’t need regular expressions for this.
  • Even if you do, you should avoid std::regex.
  • If you’re going to be using a lookup map anyway, you might as well go all-in, and lookup all possible values (rather than splitting the logic into digits and “digit words”), and include other useful information (like the numeric value of the digit).
  • You cannot separate finding the first and last digits into two isolated problems. You need to pass information form one task to the next… specifically, where not to search (because something was found there already).
  • Don’t try to “guess” whether an error occurred on reading input by circumstantial evidence (like whether EOF was hit). Either use the correct error signalling IOStream bit (which would be failbit in this case), or use exceptions or some other legit error-signalling mechanism.
  • Modern C++ avoids explicit loops and branches by chaining operations on ranges, so tasks read like a simple sequence of steps. This is what you should strive for.
  • Making a few custom types can really help with the above.

Happy coding!

\$\endgroup\$
2
\$\begingroup\$
    ptrdiff_t digit = -1;

Assuming that's a typo for std::ptrdiff_t, we need to include <cstddef>.


I don't like the need to write out the digit names three times - that makes it hard to convert to another language, for instance. It would be better to move digit_names to file scope and change it to an array of std::string_view, so that we could use it to derive the regexp (using std::views::join_with()).


The statement of task doesn't mention any limits to the input, so we don't know whether it will exceed the range of int (which must be able to represent up to 32767, though most common platforms today provide a bigger range).


It would be nice if the program would accept its input on standard input stream if we don't specify a file argument. That would make it easier to use in a pipe, for example.

\$\endgroup\$
2
  • \$\begingroup\$ Is there an alternative to using std::views::join_with() prior to C++23? \$\endgroup\$
    – Harith
    Commented Feb 15 at 21:12
  • \$\begingroup\$ The alternative would be to open-code it with a loop, I think. std::string re{"\\d"}; for (std::string s: digit_names) { re += "|" + s; } (re-write more efficiently only if needed). \$\endgroup\$ Commented Feb 16 at 7:59

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.