## Range comprehensions with range-v3

#### All-digit magic

This article demonstrates the use of range comprehensions in the form

views::for_each / yield_ifin functional programming. In this case, we are going to use a range comprehension to generate all the solutions that satisfy a certain condition.The task is to find all three-digit numbers which together with their square contain all the digits from 1 to 9.

One number that satisfies the condition is

567which gives us321489when squared. The concatenated sequence 5,6,7,3,2,1,4,8,9 contains all the digits from 1 to 9.On the other hand, the number

521doesn't work as it gives us271441when squared. The concatenated sequence 5,2,1,2,7,1,4,4,1 doesn't contain all the digits from 1 to 9.Let's first present the basic skeleton of a comprehension. We are investigating only three-digit numbers, therefore we use

views::iota(100,1000), which gives us the numbers from 100 to 999. For each number we check whether it satisfies the above-mentioned condition, which will be passed as the first argument ofyield_if. If the condition is satisfied, we yield the original number and its square to the output.int main(){ auto rng = views::iota(100,1000) | views::for_each ([](auto x) { //... return yield_if(..., std::make_pair(x,x*x)); }); // (567:321489)... }The easiest way to check whether a candidate number contains all the digits 1 - 9 is to convert it to a sequence (in our case std::string) and check whether that sequence contains only unique elements. To this end, we introduce a function

contains_all_digits(). The function uses a classical trick to determine uniqueness of elements:

- sort the copy of the sequence using
actions::sort- chain it with
actions::uniqueto keep only unique elements- determine whether the number of unique elements equals to 9
auto contains_all_digits(std::string const& s){ auto r = s; // 521271441 r |= actions::sort | actions::unique; // 12457 return distance(r) == 9; // 5 != 9...false }Additionally, we wish to exclude candidates that contain the digit 0. Therefore, we introduce another helper function

contains_char()which checks for the presence of a specific character:auto contains_char(std::string const& s, char c){ return s.find(c) != std::string::npos; }The function above is likely faster as it is designed specifically for strings. Nevertheless, you can also use the lambda expression below designed to work with general ranges.

auto contains_element = [](auto && r, auto e){ return find(r,e) != end(r); };Now that we have our helper functions, we can proceed with the solution.

For each candidate we calculate its square, convert the candidate number and its square to a string and concatenate the strings. What we really need is a conversion of number to an equivalent integer sequence. Nevertheless, using std::string for conversion of a number to a sequence, is a frequently used, albeit sometimes frowned-upon, hack.

The next step is to make sure that the combined candidate string

s_numdoesn't contain '0' and that it contains all the digits between '1' and '9'. Whenever this is satisfied, we yield the candidate together with its square to the output.int main(){ auto rng = views::iota(100,1000) | views::for_each ([](auto x) { // e.g.521 auto x_sq = x*x; // 271441 auto s_x = std::to_string(x); // 521 auto s_sq = std::to_string(x_sq); // 271441 auto s_num = s_x + s_sq; // 521271441 return yield_if(!contains_char(s_num,'0') && // ok contains_all_digits(s_num), // not ok std::make_pair(x,x_sq)); // don't yield 521 }); // (567:321489)(854:729316) }That's it! Notice that there are only two numbers that satisfy the condition above, namely

567and854.The entire code is below. You can copy it and paste it into Wandbox.

#include <iostream> #include <range/v3/all.hpp> using namespace ranges; auto contains_char(std::string const& s, char c){ return s.find(c) != std::string::npos; } auto contains_all_digits(std::string const& s){ auto r = s; // 521271441 r |= actions::sort | actions::unique; //12457 return distance(r) == 9; // 5 != 9...false } int main(){ auto rng = views::iota(100,1000) | views::for_each ([](auto x) { // e.g.521 auto x_sq = x*x; auto s_x = std::to_string(x); // 521 auto s_sq = std::to_string(x_sq); // 271441 auto s_num = s_x + s_sq; // 521271441 return yield_if(!contains_char(s_num,'0') && // ok contains_all_digits(s_num), // not ok std::make_pair(x,x_sq)); // we don't yield 521 }); // (567:321489)(854:729316) for(auto const& [e1,e2] : rng) std::cout << '(' << e1 << ':' << e2 << ')'; }

This exercise is part of a

Range-v3 online exercise seriesthat will become available inMarch 2021. Enter your email here if you wish to get a notification:

Tagged: Range-v3