C++17 constexpr generation of a FizzBuzz solution
source link: https://www.tuicool.com/articles/hit/IZfMNnM
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Posted on September 23, 2018 by Sol
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; 5 6 std::array<char, nr_cols> m; 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; 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; 5 std::array<char, nr_cols> fizz; 6 std::array<char, nr_cols> fizzbuzz; 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/eQmFUB .
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK