Extract longest connected subvector fullfilling a condition

user_5578293 0
Viewed 82

We have as input a vector, as an example

std::vector<std::int32_t> allnumbers{1,2,-3,4,5,-6,7,8,9};

We have a boolean condition, as an example output numbers have to be larger 3.

What we want is as output the longest subvector fullfilling the condition. All elements of the output have to have been connected in the input.

std::vector<std::int32_t> allnumbers{4,5,7,8,9};

Is wrong, as 5 and 7 have not been adjacent before (-6 between them).

std::vector<std::int32_t> allnumbers{4,5};

Is wrong, as it is not the longest subvector.

std::vector<std::int32_t> allnumbers{7,8,9};

Is finally correct.

How to write the algorithm elegantly with C++17 standard, possibly without using the Boost library? By elegantly I mean few lines of code with good readability. Utilizing prefarably as much as possible. Performance or memory consumption is here less of an issue. I think the "brute force" solution I post below already has here enough performance. One time iterate through input and only few iterators to keep track during exectuion.

The following is a working "brute force" solution:

#include <functional>
#include <iostream>
#include <stdint.h>
#include <vector>

std::vector<std::int32_t> longestConnectedVectorFullfillingPredicate(
    std::function<bool(const std::int32_t)> predicate,
    std::vector<std::int32_t> &inputVector)
{
    auto currentIt = inputVector.begin();
    auto endIt = inputVector.end();
    auto beginLongestConnectedSubvector = endIt;
    auto endLongestConnectedSubvector = endIt;
    auto longestConnectedSubvectorLength = 0;
    while (currentIt != endIt)
    {
        const auto currentBeginConnectedSubvector = std::find_if(
            currentIt, endIt, [predicate](const std::int32_t &value) {            return predicate(value); });
        const auto currentEndConnectedSubvector = std::find_if(
            currentBeginConnectedSubvector, endIt, [predicate](const std::int32_t &value) {
                return !predicate(value);
            });
        const auto currentConnectedSubvectorLength =
        std::distance(currentBeginConnectedSubvector, currentEndConnectedSubvector);
        if (currentConnectedSubvectorLength > longestConnectedSubvectorLength)
        {
            longestConnectedSubvectorLength = currentConnectedSubvectorLength;
            beginLongestConnectedSubvector = currentBeginConnectedSubvector;
            endLongestConnectedSubvector = currentEndConnectedSubvector;
        }
        currentIt = currentEndConnectedSubvector;
    }
    return std::vector<std::int32_t>(beginLongestConnectedSubvector, endLongestConnectedSubvector);
}

int main()
{
    const auto largerThree = [](std::int32_t value) { return value > 3; };
    std::vector<std::int32_t> allnumbers{1, 2, -3, 4, 5, -6, 7, 8, 9};
    auto result = longestConnectedVectorFullfillingPredicate(largerThree, allnumbers);
    for (auto res : result)
    {
        std::cout << res << std::endl;
    }
    return 0;
}

This is quite a few lines... Would like to shorten it without loosing much readability.

c++17 c++
1 Answers

You might like this, which does the following

  • include needed headers, define useful namespace aliases, and a couple of useful function objects
  • pipes allnumbers into group_by which puts all adjacent numbers greater than 3 in a range/chunk (all other numbers remain in singleton range each)
  • pipes that into filter which says goodby to the singletons with the number not greater than 3
  • then finds the longest range by using max_element to which an appropriate lambda is passed
#include <boost/hana/functional/on.hpp>
#include <boost/hana/functional/partial.hpp>
#include <boost/hana/functional/reverse_partial.hpp>
#include <boost/range/numeric.hpp>
#include <functional>
#include <iostream>
#include <range/v3/algorithm/max_element.hpp>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/filter.hpp>
#include <range/v3/view/group_by.hpp>
#include <range/v3/view/transform.hpp>
#include <vector>

using boost::hana::on;
using boost::hana::reverse_partial;
using namespace ranges::views;
using namespace ranges;

auto both = [](bool x, bool y){ return x && y; };
auto greater_than_3 = reverse_partial(std::greater<>{}, 3);

int main() {

    std::vector<int> allnumbers{1,2,-3,4,5,-6,7,8,9};

    auto chunks
        = allnumbers
        | group_by(both ^on^ greater_than_3)
        | filter([](auto v){ return greater_than_3(v.front()); })
        | transform(to_vector)
        | to_vector;

    auto result = *max_element(
            chunks,
            std::less<>{} ^on^ std::mem_fn(&decltype(allnumbers)::size));

    for (auto i : result) {
        std::cout << i << ',';
    }
}
user_58252940
Related