The Angry Professor - Again¶
Title: Angry Professor
Link: https://www.hackerrank.com/challenges/angry-professor
Adding to the “x_of” Standard Family¶
Let us remain with the “Angry Professor” and on a new second thought moment let us consider if we do not need our custom iterator at all. We have counted, partitioned and iterated, but we have missed the entire point. Our goal is to count we have “at least k students of n”, with n being the entire range, of course.
And the standard library has three algorithms with the _of_, namely: std::all_of, std::any_of and std::none_of. It is obvious that as we needed, these algorithms can break out early if the condition that is being tested fails. Unfortunately they do not test for n elements or “at least” n.
Let us roll our own n_of. Here is the main code skipping all SFINAE definitions we already know so well.
template<typename I, typename F, typename = enable_if_n_of<I, F>>
auto
n_of(I first, I last, ssize_t n, const F &f, bool at_least = false) {
it_difftype<I> dist;
if constexpr (is_random_it_v<I>)
dist = std::abs(std::distance(first, last));
for(; n >= at_least and first != last; ++first) {
if constexpr (is_random_it_v<I>)
if ((unsigned) dist-- < n)
break;
n -= static_cast<bool>(f(*first));
}
return not n;
}
Because calculating the std::distance between first and last can be expensive for non RandomAccessIterator instances, we add an if constexpr guard, to only add the calculation, and later the optimization, for that type of iterators.
The idea is that if the distance to the end is less than the amount of needed items to find n items, we can already break early out.
The algorithm is of course simple: see if we have exactly n elements as determined by function f, a unary predicate returning something convertible to bool. Notice that we have a parameter bool at_least = false. If we set it to true, the algorithm will return true as soon as the nth element has been found. We do not care if more true matches could uncover more items, because we are only asking for “at least” n matches.
Our problem can be solved as soon as we have enough, i.e., “at least”, students arriving early, If more arrive, the more the merrier, but it does not have any implication in deciding whether the class is canceled or held.
If at_least == false, the algorithm will check more elements to see if more than “exactly” n elements are found and return false in that case.
And this is how we use it in our solution. Nice and easy, exactly as a standard library algorithm. The complete code is here.
#include <array> // std::array
#include <algorithm> // std::copy_n, std::partition
#include <cmath> // std::abs
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator, std::back_inserter
#include <vector> // std::vector
#include <type_traits> // std::void_t, std::enable_if ...
// get iterator value_type
template <typename T>
using it_type = typename std::iterator_traits<T>::value_type;
// get iterator difference type
template <typename T>
using it_category = typename std::iterator_traits<T>::iterator_category;
template <typename T>
using it_difftype = typename std::iterator_traits<T>::difference_type;
// Check if an iterator is a class/subclass of a given tag
template <typename T, typename Tag>
constexpr bool is_it_tag_v = std::is_base_of_v<Tag, it_category<T>>;
template <typename I>
constexpr bool is_input_it_v = is_it_tag_v<I, std::input_iterator_tag>;
template <typename I>
constexpr bool is_random_it_v = is_it_tag_v<I, std::random_access_iterator_tag>;
// check function invocation and return type convertibility to bool
template<typename I, typename F>
constexpr bool is_f_v =
std::is_convertible_v<std::invoke_result_t<F, it_type<I>>, bool>;
// check if input iterator and function can be called and delivers as expected
template<typename I, typename F>
using enable_if_n_of =
std::enable_if_t<(is_input_it_v<I> or is_random_it_v<I>) and is_f_v<I, F>>;
// n_of implementation
template<typename I, typename F, typename = enable_if_n_of<I, F>>
auto
n_of(I first, I last, ssize_t n, const F &f, bool at_least = false) {
it_difftype<I> dist;
if constexpr (is_random_it_v<I>)
dist = std::abs(std::distance(first, last));
for(; n >= at_least and first != last; ++first) {
if constexpr (is_random_it_v<I>)
if ((unsigned) dist-- < n)
break;
n -= static_cast<bool>(f(*first));
}
return not n;
}
// Main
int
main(int, char *[]) {
auto in = std::istream_iterator<int>{std::cin}; // input iterator
auto in_last = std::istream_iterator<int>{}; // input iterator end
auto out = std::ostream_iterator<std::string>{std::cout, "\n"}; // out iter
constexpr auto canceled = std::array{"NO", "YES"};
const auto fearly = [](const auto &x) { return x <= 0; };
[[maybe_unused]] auto t = *in++; // number of testcases (unused)
for(; in != in_last; ++in) { // resync "in" after copy_n operation
const auto n = *in++, k = *in++; // students and threshold
auto c = std::vector<int>{}; // storage
std::copy_n(in, n, std::back_inserter(c)); // copy input
const auto early_students = n_of(c.begin(), c.end(), k, fearly, true);
*out++ = canceled[not early_students];
}
return 0;
}
Following The STL Path¶
https://cppreference.com gives us a nice indication as to how std::all_of, and family members, may be implemented and that is by using the std::find_if family. The _of algorithms will test if first algorithm made it to the last, or if it did not to return the bool value that it is expected. For example.
template<class InputIt, class UnaryPred>
constexpr bool any_of(InputIt first, InputIt last, UnaryPred p)
{
return std::find_if(first, last, p) != last;
}
Let us go that route too by creating an find_n_if algorithm. This will be the engine then of our n_of algorithm.
// find_n_if implementation
template<typename I, typename F, typename = enable_if_n_of<I, F>>
auto
find_n_if(I first, I last, ssize_t n, const F &f, bool at_least = false) {
it_difftype<I> dist;
if constexpr (is_random_it_v<I>)
dist = std::abs(std::distance(first, last));
for(; n >= at_least and first != last; ++first) {
if constexpr (is_random_it_v<I>)
if ((unsigned) dist-- < n)
break;
n -= static_cast<bool>(f(*first));
}
// The loop may have been interrupted early. If n is not 0, either not
// enough items were found or too many (at least if fase) => return last
return n ? last : first;
}
// n_of implementation
template<typename I, typename F, typename = enable_if_n_of<I, F>>
auto
n_of(I first, I last, ssize_t n, const F &f, bool at_least = false) {
return find_n_if(first, last, n, f, at_least) != last;
}
It would seem as if we only had to rename n_of to find_n_if and then get a new n_of written that simply checks if the end of the range has been reached. But how the return value in find_n_if is calculated has changed.
// The loop may have been interrupted early. If n is not 0, either not
// enough items were found or too many (at least if fase) => return last
return n ? last : first;
Had we added no optimization checking for the remaining distance to the end for RandomAccessIterator types, we could simply return the last position reached by first. The same happens when it comes to finding exactly n elements, because the loop can be interrupted early. In both cases first is never incremented to make it to the end of the range.
But the return value of find_n_if has to be last if not enough (or exactly) elements have been found. Hence the extra check to return the current position of first on success, delivering the position to the caller or actually last if some elements could have still been found but the loop was interrupted early.
Obviously and because the parameters for both functions are the same, the same set of SFINAE constraints apply to both.
Let us get it over with this challenge with a last “complete source code” entry.
#include <array> // std::array
#include <algorithm> // std::copy_n, std::partition
#include <cmath> // std::abs
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator, std::back_inserter
#include <vector> // std::vector
#include <type_traits> // std::void_t, std::enable_if ...
// get iterator value_type
template <typename T>
using it_type = typename std::iterator_traits<T>::value_type;
// get iterator difference type
template <typename T>
using it_category = typename std::iterator_traits<T>::iterator_category;
template <typename T>
using it_difftype = typename std::iterator_traits<T>::difference_type;
// Check if an iterator is a class/subclass of a given tag
template <typename T, typename Tag>
constexpr bool is_it_tag_v = std::is_base_of_v<Tag, it_category<T>>;
template <typename I>
constexpr bool is_input_it_v = is_it_tag_v<I, std::input_iterator_tag>;
template <typename I>
constexpr bool is_random_it_v = is_it_tag_v<I, std::random_access_iterator_tag>;
// check function invocation and return type convertibility to bool
template<typename I, typename F>
constexpr bool is_f_v =
std::is_convertible_v<std::invoke_result_t<F, it_type<I>>, bool>;
// check if input iterator and function can be called and delivers as expected
template<typename I, typename F>
using enable_if_n_of =
std::enable_if_t<(is_input_it_v<I> or is_random_it_v<I>) and is_f_v<I, F>>;
// find_n_if implementation
template<typename I, typename F, typename = enable_if_n_of<I, F>>
auto
find_n_if(I first, I last, ssize_t n, const F &f, bool at_least = false) {
it_difftype<I> dist;
if constexpr (is_random_it_v<I>)
dist = std::abs(std::distance(first, last));
for(; n >= at_least and first != last; ++first) {
if constexpr (is_random_it_v<I>)
if ((unsigned) dist-- < n)
break;
n -= static_cast<bool>(f(*first));
}
// The loop may have been interrupted early. If n is not 0, either not
// enough items were found or too many (at least if fase) => return last
return n ? last : first;
}
// n_of implementation
template<typename I, typename F, typename = enable_if_n_of<I, F>>
auto
n_of(I first, I last, ssize_t n, const F &f, bool at_least = false) {
return find_n_if(first, last, n, f, at_least) != last;
}
// Main
int
main(int, char *[]) {
auto in = std::istream_iterator<int>{std::cin}; // input iterator
auto in_last = std::istream_iterator<int>{}; // input iterator end
auto out = std::ostream_iterator<std::string>{std::cout, "\n"}; // out iter
constexpr auto canceled = std::array{"NO", "YES"};
const auto fearly = [](const auto &x) { return x <= 0; };
[[maybe_unused]] auto t = *in++; // number of testcases (unused)
for(; in != in_last; ++in) { // resync "in" after copy_n operation
const auto n = *in++, k = *in++; // students and threshold
auto c = std::vector<int>{}; // storage
std::copy_n(in, n, std::back_inserter(c)); // copy input
const auto early_students = n_of(c.begin(), c.end(), k, fearly, true);
*out++ = canceled[not early_students];
}
return 0;
}