Closed DenisYaroshevskiy closed 5 years ago
I'll comment upfront that (imo) this sort of question is better directed to stack overflow than the ranges-v3 issue tracker.
#include <functional>
#include <vector>
#include <range/v3/core.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/partial_sum.hpp>
int solution(const std::vector<int>& v, int k) {
auto quotion_plus_remainder = [k](int x) { return x / k + x % k; };
return ranges::back(
v |
ranges::view::transform(quotion_plus_remainder) |
ranges::view::partial_sum(std::greater<>{}));
}
ranges::back
requires a bidirectional range. In general, partial_sum cannot be implemented as anything stronger than a forward range. Note that partial_sum is defined in terms of an arbitrary binary operator. Reverse iteration would require somehow inferring the inverse operation. An inverse may not even exist, and even if it did, C++ (or any other language that I know of) does not provide a mechanism for that sort of inference.
In your example, your interested in only the greatest element, rather than the the partial sum. This sort of fold operation can be implemented with an accumulate in the general case. In this sense, (if I understand the problem at hand) your implementation isn't consistent with your intent. The operation you're interested in the std::max
rather than std::greater
.
#include <functional>
#include <vector>
#include <range/v3/core.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/view/partial_sum.hpp>
int solution(const std::vector<int>& v, int k) {
auto quotion_plus_remainder = [k](int x) { return x / k + x % k; };
auto max = [](auto left, auto right) { return std::max(left, right); };
return ranges::accumulate(
v | ranges::view::transform(quotion_plus_remainder),
std::numeric_limits<int>::min(),
max);
}
This use case is sufficiently common that ranges-v3 provides this functionality out of the box, e.g. ranges::max
. I've provided a simple modifcation to your solution on compiler explorer and wandbox. The solution (with trivial test) and console output is reproduced below should the links go stale.
#include <iostream>
#include <functional>
#include <vector>
#include <range/v3/core.hpp>
#include <range/v3/view/transform.hpp>
#include <range/v3/numeric.hpp>
auto solution(const std::vector<int>& v, int k) {
auto quotion_plus_remainder = [k](int x) { return x / k + x % k; };
return ranges::max(v | ranges::view::transform(quotion_plus_remainder));
}
int main(){
std::vector<int> vi = {22, 34, 12, 95, 81, 34, 65};
std::cout << "class of 1 solution: " << solution(vi, 1) << std::endl;
std::cout << "class of 30 solution: " << solution(vi, 30) << std::endl;
}
class of 1 solution: 95
class of 30 solution: 23
Thx, you right - probably should have asked on Stack Overflow.
Hi!
Saw this video recently: https://youtu.be/y3vnhJ2rrd0
It suggests to do transform + max with a temporary vector. I tried to do this without and failed (https://gcc.godbolt.org/z/y0Y4dr) - because partial sum is not bound.
How can I do this? Is there a good reason why there is no max_element_view or partial_max_view?