C++17 constexpr generation of a FizzBuzz solution
Posted on September 24, 2018 by Paul
The famous FizzBuzz interview question asks to print all numbers from 1 to 100. If a number is divisible with 3 print fizz, if the number is divisible with 5 print buzz and if the number is divisible with both 3 and 5 print fizzbuzz. Writing a program for the above problem is trivial. A more interesting problem is to generate the solution for the FizzBuzz problem at compile time.
In C++ we use the constexpr specifier for a variable or a function that needs to be evaluated at compile time.
A possible approach for the FizzBuzz problem is to use a two dimensional array of characters that is filled with data during the compilation. The array will have 100 rows, one for each number from 1 to 100 and 9 columns. Here is an example of how the solution could be stored in the above array:
1 '1','\n', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
2
3 ...
4
5 '1', '4', '\n', '\0', '\0', '\0', '\0', '\0', '\0'
6 'F', 'i', 'z', 'z', 'B', 'u', 'z', 'z', '\n'
7 '1', '6', '\n', '\0', '\0', '\0', '\0', '\0', '\0'
8
9 ...
10
11 'B', 'u', 'z', 'z', '\n', '\0', '\0', '\0', '\0'Let’s start by defining the dimensions of the solution array:
1 #include <iostream>
2 #include <array>
3
4 constexpr int nr_cols = 9;
5 constexpr int nr_rows = 100;
6
7 // ...Next, we need a function that will convert an integer to a constexpr one-dimensional array of characters:
1 // ...
2
3 constexpr std::array<char, nr_cols> int_to_array_of_chars(int num) {
4 std::array<char, 10> numbers{'0','1','2','3','4','5','6','7','8','9'};
5
6 std::array<char, nr_cols> m{'\0'};
7
8 int num_elem = 0;
9 for(int i = 0; i < nr_cols; i++) {
10 int r = num % 10;
11 m[i] = numbers[r];
12 num = num / 10;
13 num_elem++;
14 if(num == 0) break;
15 }
16
17 std::array<char, nr_cols> res{'\0'};
18 for(int i = num_elem - 1, j = 0; i >= 0; --i, ++j) {
19 res[j] = m[i];
20 }
21 res[num_elem] = '\n';
22 return res;
23 }
24
25 // ...Please note, that the above code does not check if the provided number can fit in the available space, for our particular problem a 9 columns array is more than enough.
Now, we can store the solution in a two-dimensional constexpr array:
1 // ...
2
3 constexpr std::array<std::array<char, nr_cols>, nr_rows> make_fizzbuzz() {
4 std::array<char, nr_cols> buzz{'b','u','z','z','\n'};
5 std::array<char, nr_cols> fizz{'f','i','z','z','\n'};
6 std::array<char, nr_cols> fizzbuzz{'f','i','z','z','b','u','z','z','\n'};
7
8 std::array<std::array<char, nr_cols>, nr_rows> fb{};
9 for(int i = 1; i <= nr_rows; ++i) {
10 if(i % 3 == 0 && i % 5 == 0) {
11 fb[i-1] = fizzbuzz;
12 } else if(i % 3 == 0) {
13 fb[i-1] = fizz;
14 } else if(i % 5 == 0) {
15 fb[i-1] = buzz;
16 } else {
17 fb[i-1] = int_to_array_of_chars(i);
18 }
19 }
20 return fb;
21 }
22
23 // ...We can check that the solution is actually generated at compile time by using static_assert, e.g.:
1 // ...
2
3 int main() {
4 constexpr std::array<std::array<char, nr_cols>, nr_rows> fb = make_fizzbuzz();
5
6 // Check if the solution is actually generated at compile time
7 static_assert(fb[2][0] == 'f', "Fizz Buzz error");
8 static_assert(fb[3][0] == '4', "Fizz Buzz error");
9 static_assert(fb[4][0] == 'b', "Fizz Buzz error");
10 static_assert(fb[14][0] == 'f' && fb[14][4] == 'b', "Fizz Buzz error");
11
12 }If you want to print the solution, you can do it at run time, e.g.:
1 // ...
2
3 int main() {
4 constexpr std::array<std::array<char, nr_cols>, nr_rows> fb = make_fizzbuzz();
5
6 // Check if the solution is actually generated at compile time
7 // ...
8
9 // Print the solution (at run time)
10 for(auto &r : fb) {
11 for(auto &c : r) {
12 std::cout << c;
13 }
14 }
15 }The above code was checked with GCC 8.2, Clang 7 and a preview of the next MSVC compiler. You can see the compilation options and the generated assembly for the 3 test compilers at https://godbolt.org/z/hTmXFS.
Here is an example of running the above code on a macOS machine:
1 $ clang++ -std=c++17 -Wall -pedantic FizzBuzz.cpp -o FizzBuzz
2 $ ./FizzBuzz
3 1
4 2
5 fizz
6 4
7 buzz
8 fizz
9 7
10 8
11 fizz
12 buzz
13 11
14 fizz
15 13
16 14
17 fizzbuzz
18 16
19 17
20 fizz
21 19
22 buzz
23 fizz
24 22
25 23
26 fizz
27 buzz
28 26
29 fizz
30 28
31 29
32 fizzbuzz
33
34 ...If you are interested to learn more about modern C++ I would recommend reading A tour of C++ by Bjarne Stroustrup.
or Effective Modern C++ by Scott Meyers.
