Jumping On The Clouds - Revisited¶
Title: Jumping On The Clouds - Revisited
Link: https://www.hackerrank.com/challenges/jumping-on-the-clouds-revisited/
Skipping The Obvious¶
Given that we have already gone for the obvious solution in all previous challenges, we are going to go directly for an iterator-based solution to spare us some lines of text and code.
The challenge demands that we read a number of int values, to be stored in an std::vector<int>, and a constant k that will determine the next jump inside the array of int values.
For each jump the initial e (energy value) of 100 will be decremented by 1, with an extra decrement of 2 if the position we landed on contains a true, non zero, value. The jump trip is over when the new position is the initial position.
#include <algorithm> // std::copy_n
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <vector> // std::vector
template <typename I, typename O>
auto
final_energy(I first, O out, int n, int k, int e) {
auto cloud = first;
do {
auto i = std::distance(first, cloud); // >= 0
cloud = std::next(first, (i + k) % n); // next is at (i + k) % n
e -= 1 + (*cloud * 2); // jump - 1, on non-zero cloud == 1 .. +2
} while(cloud != first);
*out++ = e;
}
///////////////////////////////////////////////////////////////////////////////
// Main
///////////////////////////////////////////////////////////////////////////////
int
main(int, char *[]) {
constexpr auto e = 100; // starting energy level
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<int>{std::cout, "\n"}; // output iterator
for(; in != in_last; in++) { // resync "in" after copy_n operation
auto n = *in++, k = *in++; // input parameters
auto c = std::vector<bool>{}; // storage
std::copy_n(in, n, std::back_inserter(c)); // copy input
final_energy(c.begin(), out, n, k, e);
}
}
As we did previously, we prepare our solution to solve any number of inputs by checking for end-if-input with std::istream_iterator<int>{}.
Once the input is gathered the problem is easily solved with a do-while loop, instead of the usual while and that is because there is always a first jump. Action that could actually take us to the beginning. Notice that we only need the first iterator, because the jump calculation formula, (i + k) % n ensures that we never get a new position greater than n.
Mimicking std::istream_iterator<T¶
The happy hour idea to improve the solution of this problem comes from looking at the STL. In the problem we use
auto in = std::istream_iterator<int>{std::cin}; // input iterator
auto in_last = std::istream_iterator<int>{}; // input iterator end
We can quickly make an analogy: we traverse the array (std::vector<int>) until we hit the end of the trip. The fact that the end is the initial position shall not distract us. We can create an iterator that executes the jumps for us until it comes back to the original position. Our iterator will simply take the iterator from the std::vector<int> that determines the initial position and jump to the next.
Rather than hardcoding the jump in our iterator, it will accept a function to calculate the position. The only parameter the function has to take is the actual position.
template <typename It, typename T = int>
struct JumpingIterator {
// Iterator tags
using iterator_category = std::random_access_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = value_type &;
using pointer = value_type *;
const It m_itfirst;
It m_itcur;
using FunctionMove = std::function<int(int)>;
FunctionMove m_fmove;
bool m_end = false;
JumpingIterator(It first, const FunctionMove &fmove)
: m_itfirst{first}, m_itcur{first}, m_fmove(fmove) {}
JumpingIterator() : m_end{true} {}
That is our iterator basic definition with member attributes and constructors. The wrapped-iterator itself is a template parameter, since we do not know in advance what will come to us.
auto operator *() { return *m_itcur; }
auto &operator ++() { // Prefix increment
if (not m_end) {
auto d = std::distance(m_itfirst, m_itcur); // >= 0
m_itcur = std::next(m_itfirst, m_fmove(d));
m_end = m_itfirst == m_itcur;
}
return *this;
}
The * dereferencing operator will simply return the value of the current position. The actual job is done in the prefix increment ++ operator, where the current distance to the start is calculated and the jump is executed using the function m_fmove that was given during construction. To ensure no extra jumps happen, the m_end flag is checked and calculated also here.
template <typename I, typename FMove, typename FEnergy>
auto
minus_energy(I first, FMove fmove, FEnergy fenergy) {
return std::accumulate(
JumpingIterator<I>(first, fmove), // first
JumpingIterator<I>{}, // last
0, // init
fenergy // binary op
);
}
With such a powerful iterator in the hand we can resort to using std::accumulate to calculate how much energy will be deducted after all jumps have been performed. And once again the formula is a function parameter, fenergy. We do not want to write code in the solution that can come as a parameter.
We have taken the typename O template parameter out of the equation. And this is because it feels redundant to also pass the e, initial energy level, as a parameter. Our solution function gives us the energy that will be deducted and we can directly deduct it from the initial energy and output the result, all in the main loop.
auto n = *in++, k = *in++; // input parameters
auto fenergy = [](auto acc, auto x) { return acc - (1 + (x * 2)); };
auto fmove = [&n, &k](auto x) { return (x + k) % n; };
auto c = std::vector<bool>{}; // storage
std::copy_n(in, n, std::back_inserter(c)); // copy input
*out++ = e + minus_energy(c.begin(), fmove, fenergy); // solve
Our JumpingIterator is ready and passes all tests. We have marked it as an
std::random_access_iterator_tag because it jumps randomly inside the array range. Granted, it is not a random jump, it is a jump determined by the constant k and the range length n, but it fits the description of a RandomAccessIterator.
Here is the complete code.
#include <algorithm> // std::copy_n
#include <functional> // std::function
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <numeric> // std::accumulate
#include <vector> // std::vector
template <typename It, typename T = int>
struct JumpingIterator {
// Iterator tags
using iterator_category = std::random_access_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = value_type &;
using pointer = value_type *;
const It m_itfirst;
It m_itcur;
using FunctionMove = std::function<int(int)>;
FunctionMove m_fmove;
bool m_end = false;
JumpingIterator(It first, const FunctionMove &fmove)
: m_itfirst{first}, m_itcur{first}, m_fmove(fmove) {}
JumpingIterator() : m_end{true} {}
auto operator ->() { return &(*m_itcur); }
auto operator *() { return *m_itcur; }
auto &operator ++() { // Prefix increment
if (not m_end) {
auto d = std::distance(m_itfirst, m_itcur); // >= 0
m_itcur = std::next(m_itfirst, m_fmove(d));
m_end = m_itfirst == m_itcur;
}
return *this;
}
// Postfix increment
auto operator ++(int) { JumpingIterator tmp = *this; ++(*this); return tmp; }
auto operator ==(const JumpingIterator& o) const {
return m_end ? o.m_end : (not o.m_end and (m_itcur == o.m_itcur));
}
auto operator !=(const JumpingIterator& o) const { return not (*this == o); }
};
template <typename I, typename FMove, typename FEnergy>
auto
minus_energy(I first, FMove fmove, FEnergy fenergy) {
return std::accumulate(
JumpingIterator<I>(first, fmove), // first
JumpingIterator<I>{}, // last
0, // init
fenergy // binary op
);
}
///////////////////////////////////////////////////////////////////////////////
// Main
///////////////////////////////////////////////////////////////////////////////
int
main(int, char *[]) {
constexpr auto e = 100; // starting energy level
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<int>{std::cout, "\n"}; // output iterator
for(; in != in_last; in++) { // resync "in" after copy_n operation
auto n = *in++, k = *in++; // input parameters
auto fenergy = [](auto acc, auto x) { return acc - (1 + (x * 2)); };
auto fmove = [&n, &k](auto x) { return (x + k) % n; };
auto c = std::vector<bool>{}; // storage
std::copy_n(in, n, std::back_inserter(c)); // copy input
*out++ = e + minus_energy(c.begin(), fmove, fenergy); // solve
}
}
Adding SFINAE¶
Yes, once again we are going to do some dirty work. Someone has to do it! And we do it because we have, for example, define as parameters the functions that move the iterator and calculate energy deduction. Hence the need to ensure that they take the right number and type of arguments and deliver the expected result.
In the case of the iterator the check does not happen in the struct definition itself, but in the constructor. This is the earliest moment at which we can pass the fmove function, and the check has to therefore take place there.
template <typename F, typename = enable_if_fmove<F>>
JumpingIterator(It first, const F &fmove)
: m_itfirst{first}, m_itcur{first}, m_fmove(fmove) {}
The other checks are all made when the templates parameters are defined. We have had to resort to long strings of beloved decltype / std::declval<T> married couple checks. Applying, for example std::is_integral to the result of std::invoke_result_t to check if the output type of the fmove and fenergy parameters is a match would not work even if it seems optimal.
The full code is presented here.
#include <algorithm> // std::copy_n
#include <functional> // std::function
#include <iostream> // std::cout/cin
#include <iterator> // std::istream/ostream_iterator
#include <numeric> // std::accumulate
#include <vector> // std::vector
#include <type_traits> // std::enable_if, std::is_integral, std::void_t
// SFINAE to check for It being an Input iterator and T and integer-like
template <typename T, typename Tag>
constexpr bool is_it_tag_v =
std::is_base_of_v<Tag, typename std::iterator_traits<T>::iterator_category>;
template <typename I>
constexpr bool is_input_v = is_it_tag_v<I, std::input_iterator_tag>;
template <typename It, typename T>
using enable_if_iter_int =
std::enable_if_t<is_input_v<It> and std::is_integral_v<T>>;
using FunctionMove = std::function<int(int)>;
template<typename, typename = void>
constexpr bool is_fmove_v = false;
template<typename F>
constexpr bool is_fmove_v<F,
std::void_t<
decltype(
std::declval<FunctionMove>()(0) ==
std::declval<std::invoke_result_t<F, int>>()
)>> = true;
template<typename F>
using enable_if_fmove = std::enable_if_t<is_fmove_v<F>>;
template <
typename It, typename T = int, typename = enable_if_iter_int<It, T>>
struct JumpingIterator {
// Iterator tags
using iterator_category = std::random_access_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = value_type &;
using pointer = value_type *;
const It m_itfirst;
It m_itcur;
FunctionMove m_fmove;
bool m_end = false;
template <typename F, typename = enable_if_fmove<F>>
JumpingIterator(It first, const F &fmove)
: m_itfirst{first}, m_itcur{first}, m_fmove(fmove) {}
JumpingIterator() : m_end{true} {}
auto operator ->() { return &(*m_itcur); }
auto operator *() { return *m_itcur; }
auto &operator ++() { // Prefix increment
if (not m_end) {
m_itcur = std::next(
m_itfirst,
m_fmove(std::distance(m_itfirst, m_itcur))
);
m_end = m_itfirst == m_itcur;
}
return *this;
}
// Postfix increment
auto operator ++(int) { JumpingIterator tmp = *this; ++(*this); return tmp; }
auto operator ==(const JumpingIterator& o) const {
return m_end ? o.m_end : (not o.m_end and (m_itcur == o.m_itcur));
}
auto operator !=(const JumpingIterator& o) const { return not (*this == o); }
};
// SFINAE for the solution function
using FunctionEnergy = std::function<int(int, int)>;
template<typename, typename = void>
constexpr bool is_fenergy_v = false;
template<typename F>
constexpr bool is_fenergy_v<F,
std::void_t<
decltype(
std::declval<FunctionEnergy>()(0, 0) ==
std::declval<std::invoke_result_t<F, int, int>>()
)>> = true;
template <typename I, typename FMove, typename FEnergy>
using enable_if_iter_fmove_fenergy = std::enable_if_t<
is_input_v<I> and is_fmove_v<FMove> and is_fenergy_v<FEnergy>>;
template <typename I, typename FMove, typename FEnergy,
typename = enable_if_iter_fmove_fenergy<I, FMove, FEnergy>>
auto
minus_energy(I first, FMove fmove, FEnergy fenergy) {
return std::accumulate(
JumpingIterator<I>(first, fmove), // first
JumpingIterator<I>{}, // last
0, // init
fenergy // binary op
);
}
///////////////////////////////////////////////////////////////////////////////
// Main
///////////////////////////////////////////////////////////////////////////////
int
main(int, char *[]) {
constexpr auto e = 100; // starting energy level
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<int>{std::cout, "\n"}; // output iterator
for(; in != in_last; in++) { // resync "in" after copy_n operation
auto n = *in++, k = *in++; // input parameters
auto fenergy = [](auto acc, auto x) { return acc - (1 + (x * 2)); };
auto fmove = [&n, &k](auto x) { return (x + k) % n; };
auto c = std::vector<bool>{}; // storage
std::copy_n(in, n, std::back_inserter(c)); // copy input
*out++ = e + minus_energy(c.begin(), fmove, fenergy); // solve
}
}