This article demonstrates the use of range comprehensions in the form views::for_each / yield_if in 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 567 which gives us 321489 when 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 521 doesn't work as it gives us 271441 when 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 of yield_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:

1. sort the copy of the sequence using actions::sort
2. chain it with actions::unique to keep only unique elements
3. 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_num doesn'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 567 and 854.

The entire code is below. You can copy it and paste it into Compiler explorer.

#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 << ')';     
}   

Tagged: Range-v3