Hidden unique integers

Solutions

A solution consists in finding all the contiguous digits in the string, converting them to integers and putting them in a set for removing duplicates. Finally, outputting the size of the set:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int n; cin >> n;
string input;
while (n--)
{
    cin >> input;
    set<int> integers;
    auto cur = begin(input);
    while (cur != end(input))
    {
        if (cur = std::find_if(cur, end(input), ::isdigit); cur != input.end())
        {
            const auto digitEnd = std::find_if_not(cur, end(input), ::isdigit);
            integers.insert(std::stoi(std::string(cur, digitEnd)));
            cur = digitEnd;    
        }
    }
    cout << integers.size() << "\n";
}

This solution can be redesigned by using C++ ranges. We note that “contiguous digits” are actually “chunks” of characters that are all digits. This means, we can apply views::chunk_by to obtain contiguous sequences of characters that are all of the same “alphabeticalness”. Then we just filter out those which are not digits, convert all the remaining ranges to integers, and finally construct a set from of the resulting range of numbers:

1
2
3
4
5


std::cout << size(input 
    | views::chunk_by([](auto a, auto b) { return isalpha(a) == isalpha(b); })
    | views::filter([](auto rng) { return isdigit(rng[0]); })
    | views::transform([](auto rng) { return std::stoi(to<std::string>(rng)); })
    | to<std::set>());

Strictly speaking, isalpha(a) == isalpha(b) might be false even though both characters are alphabetical because isalpha() returns any positive number if the input is a letter. However, most implementations just return the very same value for every letter and 0 otherwise. Thus, we should raplace that check with something like (bool)isalpha(a) == (bool)isalpha(b).

Paolo Di Giglio noticed that filter is not necessary if we just iterate 2 “chunks” at a time by introducing stride:

1
2
3
4
5
6


std::cout << size(input
	| views::chunk_by([](auto a, auto b) { return static_cast<bool>(isalpha(a)) == static_cast<bool>(isalpha(b)); })
	| views::drop(static_cast<bool>(isalpha(input.front())))
	| views::stride(2)
	| views::transform([](auto rng) { return std::stoi(to<std::string>(rng)); })
	| to<std::set>());

If the input starts with a letter, we also drop the very first chunk.

This solution avoids checking every chunk explicitly. The only caveat is that if we introduce other “chunk types” (e.g. we need to distinguish uppercase and lowercase letters for some reason), the positional approach might not work anymore. On the other hand, the filter approach ensures we only consider the chunk containing digits.

An extension of this solution consists in handling numbers that are out of built-in integral bounds (e.g. int and size_t). This is possible by removing leading zeros from extracted numbers and store them in a set of strings. In the solution snippet below, we actually used string_view to avoid copying data every time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


int n; cin >> n;
string input;
while (n--)
{
    cin >> input;
    std::set<std::string_view> numbers;
    auto cur = begin(input);
    while (cur != end(input))
    {
        if (cur = std::find_if(cur, end(input), ::isdigit); cur != input.end())
        {
            const auto digitEnd = std::find_if_not(cur, input.end(), ::isdigit);
            std::string_view digit(cur, digitEnd); // this is just referencing data
            digit.remove_prefix(std::min(digit.find_first_not_of('0'), digit.size())); // this is a "logical" removal of leading zeros
            numbers.insert(digit);
            cur = digitEnd;
        }
    }
    std::cout << numbers.size() << "\n";
}

Here is the same idea with ranges:

1
2
3
4
5
6
7


std::cout << size(input
	| views::chunk_by([](auto a, auto b) { return static_cast<bool>(isalpha(a)) == static_cast<bool>(isalpha(b)); })
	| views::drop(static_cast<bool>(isalpha(input.front())))
	| views::stride(2)
	| views::transform([](auto rng) { return std::string_view(begin(rng), end(rng)); })
	| views::transform([](std::string_view sv) { return sv.substr(0, sv.find_first_not_of('0')); })
	| to<std::set>());

A extension of this exercise consists in handling negative numbers.

strings patterns