Solving an Advent of Code task at compile time in modern C++

Let's solve an Advent of Code task at compile time

In this post, I try to solve one of the Advent of Code tasks at compile time. This is a great chance to explore C++'s compile-time programming capabilities. Along the way, I discuss the challenges I encountered while solving this task. Finally, I conclude with the pros and cons of this approach.

The Advent of Code task

The full description of the task can be found at the link. In short, three operations are available operations: addition, multiplication, and concatenation. We need to read a file, where each line contains a sequence of numbers and a final result. The task is to apply these operations in any combination to the given numbers in order to obtain the final result. To solve the first part, we need to use addition and multiplication. For the second part, we have to use all three operations.

Example input:

190: 10 19
3267: 81 40 27

To get 190 from 10 and 19, we multiply 10 by 19.

To get 3267, there are two ways to do that: 81 + 40 * 27 and 81 * 40 + 27.

I came up with a relatively simple algorithm based on the recursive backtracking approach. The recursive method takes the current result—initially set to 0—and a list of operations. It then invokes itself recursively, applying an operation to the next number. This process continues until the current result is equal to or less than the final result, or until there are no more numbers left. However, the algorithm is not efficient. Its complexity is O(2ⁿ) for the first part and O(3ⁿ) for the second part, respectively.

The pseudo-code algorithm implementation is the following:

bool solution(final_result, arguments[], id, current_result, operations) {
  if(current_result >= final_result) {
    return current_result == final_result
  }

  for(op : operations) {
     new_result = op(current_result, arguments[id])
     if(solution(equations, arguments, id + 1, new_result, operations) {
       return true
     }
  }
  return false
}

Now, let’s dive into implementation. This task can be divided into 3 subtasks: file reading, parsing, and calculation.

File reading

The constexpr feature is responsible for compile time computing in C++. The feature was added in the C++11 standard and has been evolving continuously. For example, the first implementation didn’t allow the creation of local variables. In C++20, even virtual functions can be constexpr.

The input data consists of 850 lines. Embedding such a large string directly in the code is impractical, as it makes code navigation difficult. Therefore, I will store the input data in a separate file. But reading the file with std::ifstream is not possible because it is not constexpr.

In C++23 we could leverage the std::embed feature. In C++20 I have to use the following technique:

constexpr std::string_view gData {
    #include "input.txt"
};

#include "input.txt" is a preprocessor directive that is executed before the compilation step. It instructs the preprocessor to read the content of the "input.txt" and insert them into the source file. Note that the file content must be enclosed in quotation marks. I implemented this workaround using CMake by creating a separate file that contains the quoted content of the original file.

# Read the content of the input file
file(READ ${CMAKE_CURRENT_SOURCE_DIR}/data/2024/day7.txt FILE_CONTENT)

# Quote the content
set(FILE_CONTENT "R\"(${FILE_CONTENT})\"")

file(WRITE ${CMAKE_CURRENT_SOURCE_DIR}/data/2024/day7_constexpr.txt ${FILE_CONTENT})

The file content will be:

R"(190: 10 19
3267: 81 40 27)"

Let me know if there is a better way to read a file at compile time.

Parsing

In this chapter, I provide a brief overview of the parsing implementation without going into details. The process begins by counting the number of equations/lines in the file. Because the creation of the std::array requires to specify the size statically. Next, I invoke the parseEquations method to parse the input data. Finally, the solveFirstPart method calculates the answer. The following code demonstrates these steps:

int main() {
    auto constexpr_context = [] {
        constexpr size_t N{numOfEquastions(gInput)};
        std::array<Equation, N> equations{};
        parseEquations(gInput, equations);
        return equations;
    };   
    constexpr auto equations{constexpr_context()};
    constexpr auto firstPartAns{solveFirstPart(equations)};
    std::cout << firstPartAns;
}

Looking at the code, a reader might wonder what the constexpr_context is for. The compiler gives an error if we place the equations array in the main function. To place it there, this array must be constexpr, but it cannot be constant because it’s modified in the parseEquations function. The parseEquations method is used in both runtime and compile-time contexts. This makes the application flexible, allowing it to run with different file inputs.

Also, we can notice that the lambda is not marked constexpr explicitly. The standard guarantees that a lambda becomes constexpr if it adheres constexpr rules.

Calculation

Above, I provided the implementation in pseudo-code. Now, the following code presents the actual implementation:

template<typename ...Operations>
requires (OperatorInvocable<Operations> && ...)
class Combiner final
{
public:
    constexpr explicit Combiner(Operations&& ...operations) : m_operations{std::forward<Operations>(operations)...} {}

    [[nodiscard]] constexpr bool compute(const Equation& equation, size_t id, int64_t curValue) const {
        if(curValue >= equation.result) {
            return curValue == equation.result;
        }
        if(id >= equation.argumentsCount) {
            return false;
        }

        return std::apply(
            [&, this](const auto& ...op) {
                const auto arg{equation.arguments[id++]};
                return ((compute(equation, id, op(curValue, arg))) || ...);
            },
            m_operations);
    }
private:
    std::tuple<Operations...> m_operations;
};

The class holds a set of operations(e.g. addition, multiplication, concatenation). The compute - the main function - accepts an equation and сalculates a new value using operations. The function recursively invokes itself to process a new calculated value. The calculation finishes when the value becomes equal to or greater than the final result, or when all arguments have been processed.

The operation class is a function object taking two integers and returning the result. For the addition and multiplication operations, I leverage STL’s std::plus and std::multiplies, respectively. As of the concatenation operation, I implemented it myself:

[[nodiscard]] constexpr int64_t cat(int64_t a, int64_t b) noexcept
{
    const int multiplier = std::pow(10, numOfDigits(b));
    return a * multiplier + b;
};

class CatOperation final
{
public:
    constexpr auto operator()(int64_t initValue, int64_t curValue) const noexcept {
        return cat(initValue, curValue);
    }
};

The compute function uses interesting features such as std::apply and fold expression:

std::apply(
    [&, this](const auto& ...op) {
        const auto arg{equation.arguments[id++]};
        return ((compute(equation, id, op(curValue, arg))) || ...);
    },
    m_operations);

std::apply helps iterate over the elements of a tuple. There are other ways to achieve this, but they tend to be more verbose and require additional template code. The const auto& ...op is a pack of operations. The fold expression helps use operations in one line.

The creation of the combiner class is pretty simple:

template<typename ...Operation> requires (OperatorInvocable<Operation> && ...)
[[nodiscard]] constexpr auto makeCombiner(Operation&& ...ops) noexcept {
    return Combiner<Operation...>{std::forward<Operation>(ops)...};
}

The Operation&& ...ops is a packed variadic template argument list, where each ops is an operation object. I use std::forward to keep the original value category. Operation&& is a universal reference that can be either rvalue or lvalue. The creation can be further simplified with template argument deduction guides feature.

---

Ok, let’s assemble these pieces and try to compile them. The attempt to solve the first part of the task fails after 3 seconds with this error:

error: ‘constexpr’ evaluation operation count exceeds limit of 33554432 (use ‘-fconstexpr-ops-limit=’ to increase the limit)

According to the assignment, the file contains 850 lines and requires the use of two operations. After increasing the threshold to 335544320, it works successfully.

Let’s try to solve the second part that requires all 3 operations. This attempt fails with a similar error even though I increase the threshold by 10 times. The compiler eats out memory and dies due to OOM.

The final implementation is available at the following link.

Conclusion

In this post, I showed some C++’s compile-time capabilities by solving the practical task. C++ allows us to read a file(though not an arbitrary one), parse strings, and perform calculations, including recursive operations, at compile time. The constexpr functions are free from undefined behavior(UB). The constexpr speeds up the application. These two things are the main advantages of the constexpr.

However, it has some limitations and drawbacks. It can significantly slow down project compilation, as shown in the benchmarks section below. Additionally, it imposes restrictions on memory allocation and deallocation.

Benchmarks

Compiling the first part takes 10 seconds and requires 2GB of memory. The compilation of the second part takes infinite time and memory. The runtime evaluation takes 4ms for the first part and 71ms for the second part, respectively.

As we can see, compile-time evaluation requires much more resources than runtime. Thus, it makes no sense to solve this task at compile time in production. However, for another task, it’s a perfect tool that C++ engineers should use.