The Tortoise And The Hare¶
Title: Bit Array
Link: https://www.hackerrank.com/challenges/bitset-1/problem
The problem description would seem to indicate that one will have to scan an array of N elements and length 108. But considering that the operation that fills the array restricts the integers to be modulo 231, there will be a sequence repeating itself. But if the length of the array is restricted, one may hit the end before the sequence starts repeating.
Therefore, finding the number of different integers boils down to detecting a cycle. The “Floyd's Tortoise and Hare” algorithm is certainly a good choice.
#include <iostream> // std::cin, std::cout
int
main(int, char *[]) {
// problem parameters (const and from input)
constexpr int mod = 1 << 31;
int N, S, P, Q; // variables for input
std::cin >> N >> S >> P >> Q;
// lambda to calculate next position
auto fmove = [P, Q](const auto &x) { return (x * P + Q) % mod; };
auto tort = S % mod, hare = tort; // initial positions
// solve problem
auto n = 0;
while(++n < N and ((tort = fmove(tort)) != (hare = fmove(fmove(hare)))));
std::cout << n; // output result and go
return 0;
}
A single movement for the Tortoise is calculated with the lambda assigned to fmove. The Hare uses fmove twice in each round.
Notice that we have to check if the array has been traversed before moving our heroes. Consider the simple case where N = 1. The solution will obviously be 1, and there is no cycle to detect, although philosophically, one could say we are facing an eternal cycle.
Iterating the Range¶
Looking at the problem we can identify two sets of movements running in parallel, and each of those sets can lead to the solution.
-
Moving along the range
1 => N, the maximum array length, and checking ifNis reached -
Moving the Tortoise and the Hare and checking if they occupy the same array position before
Nis reached. In this case the distance traveled between1andNis the solution.
To address the first set of movements we will be using our Range virtual container, the one emulating Python's range that we developed for the “For Loop” problem.
The second one has been addressed with our lambda. However, the check in the if expression to see if the cycle has been detected will look smarter and more elegant by abusing the lambda expressions and packing the check in a single function.
Given that we have find a cycle, or the lack of it, the standard std::find_if seems perfectly suited for the task. If the cycle is found, with the unary predicate we feed it with, we will know at which position. Else it will run until the length of the array is reached. This will also come as a natural result of using std::find_if, because the returned iterator will be at position N, right after the end of the array, that is a half-open interval [1, N). Here are the lambda expressions.
// Initialize the tortoise & hare positions, and prepare calculating lambdas
auto tort = S % mod, hare = tort;
auto fmove = [P, Q](const auto &x) { return (x * P + Q) % mod; };
auto ftort = [&fmove, &tort]() { return tort = fmove(tort); };
auto fhare = [&fmove, &hare]() { return hare = fmove(fmove(hare)); };
auto ftoha = [&ftort, &fhare](const auto &) { return ftort() == fhare(); };
auto range = Range{1, N}; // Prepare a lazy evaluation Range from 1 to N
tortoise_and_hare(range.begin(), range.end(), out, ftoha); // solve
Notice how our ftoha cycle-detecting lambda defines a const auto & argument for which we provide no name, as we simply ignore it. It is the position in the array. Position that is only relevant for the answer and not for the cycle detection.
We have, of course, also resorted to input/output iterators to fetch the input parameters and to create a custom STL-like solution function. This can already take a function returning bool and taking a parameter matching the type of what dereferencing the iterator would give us.
template <typename T>
using it_type = typename std::iterator_traits<T>::value_type;
template <typename T>
using Predicate = std::function<bool(const it_type<T> &)>;
template <typename I, typename O>
auto
tortoise_and_hare(I first, I last, O out, const Predicate<I> &pred) {
// Find cycle (hare meets tortoise) along the range 1=>N or end of range
*out++ = *std::find_if(first, last, pred);
}
SFINAE here would help us with a check using std::enable_if that returns Predicate<I>, to give us the same type that we have manually defined, but after having checked the iterators. We will tackle that on our next iteration to solve the problem.
Here is this entire solution.
#include <algorithm> // std::find_if
#include <functional> // std::function
#include <iostream> // std::cin, std::cout
#include <iterator> // std::istream_iterator/ostream_iterator
#include <limits> // std::numeric_limits
#include <type_traits> // std::enable_if, std::is_integral, std::void_t
template <typename T>
using enable_if_integral = std::enable_if_t<std::is_integral_v<T>>;
template <typename T = int, typename = enable_if_integral<T>>
class Range {
struct StartStopStep {
const T start = 0;
const T stop = std::numeric_limits<T>::max();
const T step = 1;
} m_sss;
public:
Range(const StartStopStep& sss) : m_sss{sss} {};
Range(const T stop) : m_sss{.stop=stop} {};
Range(const T start, const T stop, const T step = 1)
: m_sss{.start=start, .stop=stop, .step=step} {};
private:
struct Iter {
private:
StartStopStep m_sss;
T m_pos;
public:
// Iterator tags
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = value_type; // usually value_type &
using pointer = value_type; // usually value_type *
Iter(const StartStopStep &sss) : m_sss{sss}, m_pos{m_sss.start} {};
Iter(const T &pos) : m_sss{.stop=pos}, m_pos{pos} {}; // end-of-range
auto operator *() const { return m_pos; }
auto operator ->() const { return &m_pos; }
auto& operator ++() { // Prefix increment - increase until stop
m_pos = std::min(m_pos + m_sss.step, m_sss.stop);
return *this;
}
// Postfix increment
auto operator ++(int) { Iter tmp = *this; ++(*this); return tmp; }
auto operator ==(const Iter& o) const { return m_pos == o.m_pos; }
auto operator !=(const Iter& o) const { return m_pos != o.m_pos; }
};
public:
auto begin() const { return Iter{m_sss}; } // copy range, pos at start
auto end() const { return Iter{m_sss.stop}; } // place directly at end
};
template <typename T>
using it_type = typename std::iterator_traits<T>::value_type;
template <typename T>
using Predicate = std::function<bool(const it_type<T> &)>;
template <typename I, typename O>
auto
tortoise_and_hare(I first, I last, O out, const Predicate<I> &pred) {
// Find cycle (hare meets tortoise) along the range 1=>N or end of range
*out++ = *std::find_if(first, last, pred);
}
int
main(int, char *[]) {
// Prepare iterators for input and output
auto in = std::istream_iterator<int>{std::cin};
auto out = std::ostream_iterator<int>{std::cout};
// problem parameters (const and from input)
constexpr int mod = 1 << 31;
auto N = *in++, S = *in++, P = *in++, Q = *in++;
// Initialize the tortoise & hare positions, and prepare calculating lambdas
auto tort = S % mod, hare = tort;
auto fmove = [P, Q](const auto &x) { return (x * P + Q) % mod; };
auto ftort = [&fmove, &tort]() { return tort = fmove(tort); };
auto fhare = [&fmove, &hare]() { return hare = fmove(fmove(hare)); };
auto ftoha = [&ftort, &fhare](const auto &) { return ftort() == fhare(); };
auto range = Range{1, N}; // Prepare a lazy evaluation Range from 1 to N
tortoise_and_hare(range.begin(), range.end(), out, ftoha); // solve
return 0;
}
Real Iterators¶
We have not really used proper iterators in the previous solution and this is something we can address by defining our custom iterators.
Recall that std::istream_iterator<T>(std::istream &) has a counterpart to mark the end of the iteration. This can be invoked as: std::istream_iterator<T>(). We are going to implement that concept with an iterator named: CycleIterator. As the name seems to indicate it will be in charge of finding if there is a cycle or get to the end of the defined range.
Since we want to “find” a cycle, using std::find_if seems semantically the best STL verb to use from the available algorithms. Recall that std::find_if needs a [bool-returning][2-star-bool]{target=_blank} predicate to indicate, in our case, that the cycle has been found and we get the dereferenced value of the current iterator position. The cycle detection cannot be done merely by looking at the current position, but that is, for example, what we have to obtain by dereferencing the iterator if the end of the range is hit.
Houston, we need a dereferenced value that holds two values simultaneously. Nothing that cannot be solved with an std::pair<T, T2>. But let us be brave and use instead the more general std::tuple with just two types. We already used std::pair when using an std::map and now we will be able to use std::get<N>(x) to get the needed values.
template <typename T = int>
struct CycleIterator {
using CycleVal = std::tuple<bool, T>;
// Iterator tags
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = CycleVal;
using reference = value_type &;
using pointer = value_type *;
There is the definition of our tuple and how this is the value used in the iterator.
We will also need to hold the current position in the range, the positions of the tortoise and the hare, and the current combo “cycle detection + position” inside the std::tuple<bool, int>.
T m_pos; // array position
using FuncMove = std::function<int(const int &)>;
const FuncMove m_fmove;
T m_tort, m_hare; // Positions of tortoise/hare
const T m_tsteps = T{1}, m_hsteps = T{2}; // Mover per cycle
CycleVal m_val; // cycle detected / array pos
Calculations are done in our operator ++(). Notice that we have commented out the -> operator and the postfix increment. They are not really needed.
// auto operator ->() { return &m_val; } // deref to calc
auto &operator *() { return m_val; }
auto &operator ++() { // Prefix increment
for (T i{m_tsteps}; i--; m_tort = m_fmove(m_tort));
for (T i{m_hsteps}; i--; m_hare = m_fmove(m_hare));
m_val = {m_tort == m_hare, ++m_pos};
return *this;
}
// Postfix increment
// auto operator ++(int) { CycleIterator tmp = *this; ++(*this); return tmp; }
Notice how we have customized how many times the tortoise and the hare can move. The default values in the constructor are 1 and 2, but nothing prevents us from using other speeds.
The constructor is something we need to look into.
CycleIterator(
const T &start, // start position of array length
const FuncMove &fmove, // function that will move tortoise and hare
const T &htstart = T{1}, // starting pos for tort/hare
const T &tsteps = T{1},
const T &hsteps = T{2} // steps for tort/hare
) : m_pos{start - 1}, m_fmove{fmove},m_tort{htstart}, m_hare{htstart},
m_tsteps{tsteps}, m_hsteps{hsteps} { ++(*this); }
CycleIterator(const T &stop) : m_pos{stop} {}
First, our “end-of-range” constructor at the end of the snippet. It takes the end position of the range, N, and is a no-op for all things.
Then our regular constructor that takes the function that moves the tortoise and the hare and allows customizing where to start and how to move. Something important to notice:
-
The
startposition is taken with a-1 -
The prefix increment
++is called during initialization. This will effectively restorestart(adding1) and will calculate the initial first-jump positions of our competitors. If the first comparison happens to detect the cycle, the result will bestartthat we have restored to its original value.
Our solution function needs some explaining for sure.
template <typename I, typename O>
auto
tortoise_and_hare(I first, I last, O out) {
// Find if there is cycle (hare meets tortoise) along the range 1=>N
// and output that point or the length of the range is the result
auto pred = [](const auto &x) { return std::get<0>(x); };
*out++ = std::get<1>(*std::find_if(first, last, pred));
}
We define a predicate pred that will get and return the first value of whatever has been dereferenced. We know it is a bool in the std::tuple<bool, int>.
The final output over out is the second value, the int, be it because a cycle has been detected or because the end of the range has been reached.
Unfortunately, we cannot let pred be a parameter, because it needs internal knowledge of the structure holding the cycle detection and the range position.
The main function has now been cleaned of all lambda expressions but fmove, that goes into the CycleIterator to push the range of the tortoise and the hare.
See the entire code, including the main function below.
#include <algorithm> // std::find_if
#include <functional> // std::function
#include <iostream> // std::cin, std::cout
#include <iterator> // std::istream_iterator/ostream_iterator
#include <tuple> // std::get, std::tuple
#include <type_traits> // std::iterator_traits
template <typename T = int>
struct CycleIterator {
using CycleVal = std::tuple<bool, T>;
// Iterator tags
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = CycleVal;
using reference = value_type &;
using pointer = value_type *;
T m_pos; // array position
using FuncMove = std::function<int(const int &)>;
const FuncMove m_fmove;
T m_tort, m_hare; // Positions of tortoise/hare
const T m_tsteps = T{1}, m_hsteps = T{2}; // Mover per cycle
CycleVal m_val; // cycle detected / array pos
CycleIterator(
const T &start, // start position of array length
const FuncMove &fmove, // function that will move tortoise and hare
const T &htstart = T{1}, // starting pos for tort/hare
const T &tsteps = T{1},
const T &hsteps = T{2} // steps for tort/hare
) : m_pos{start - 1}, m_fmove{fmove},m_tort{htstart}, m_hare{htstart},
m_tsteps{tsteps}, m_hsteps{hsteps} { ++(*this); }
CycleIterator(const T &stop) : m_pos{stop} {}
// auto operator ->() { return &m_val; } // deref to calc
auto &operator *() { return m_val; }
auto &operator ++() { // Prefix increment
for (T i{m_tsteps}; i--; m_tort = m_fmove(m_tort));
for (T i{m_hsteps}; i--; m_hare = m_fmove(m_hare));
m_val = {m_tort == m_hare, ++m_pos};
return *this;
}
// Postfix increment
// auto operator ++(int) { CycleIterator tmp = *this; ++(*this); return tmp; }
auto operator ==(const CycleIterator& o) const { return m_pos == o.m_pos; }
auto operator !=(const CycleIterator& o) const { return not (*this == o); }
};
template <typename I, typename O>
auto
tortoise_and_hare(I first, I last, O out) {
// Find if there is cycle (hare meets tortoise) along the range 1=>N
// and output that point or the length of the range is the result
auto pred = [](const auto &x) { return std::get<0>(x); };
*out++ = std::get<1>(*std::find_if(first, last, pred));
}
int
main(int, char *[]) {
// Prepare iterators for input and output
auto in = std::istream_iterator<int>{std::cin};
constexpr auto mod = 1 << 31; // fixed constant
// problem parameters (const and from input)
auto N = *in++, S = *in++, P = *in++, Q = *in++;
// Prepare "move" lambda and solve
auto fmove = [P, Q](const auto &x) { return (x * P + Q) % mod; };
tortoise_and_hare(
CycleIterator{1, fmove, S % mod},
CycleIterator{N},
std::ostream_iterator<int>{std::cout}
);
return 0;
}
Real-Real Iterators¶
There is a fundamental problem in the design shown above because we place N, the end of the range, in the end-of-range iterator. That means that we departed from the std::istream_iterator<T>() design to mark the end of the range. It seemed natural to put that N there as a kind of EOF marker. We will work on changing that.
However, the most fundamental flaw is the use of std::tuple<bool, int> as the magical tool to sometimes deliver the indication that the cycle has been detected and where (or if the end of the range has been reached). Although it seems ideal, we were actually forced to use such a construction because we let ourselves be misled by the semantics. In order to “find” the cycle we deemed std::find_if as the right tool.
Breaking out of the search for the cycle can only be done if the iterator itself signals the cycle has been found. It seems therefore redundant that we need a lambda accessing the first value inside our std::tuple<bool, int> and blindly returning it. The cycle has already been detected and the iteration could stop “on its own”, i.e., by meeting the requirement of being equal to the last iterator.
Going a couple of steps backwards and looking at the original problem definition, what we want is to “count” the number of different integers before those integers start repeating. Let us therefore switch to using std::count.
template <typename I, typename O>
auto
tortoise_and_hare(I first, I last, O out) {
#ifdef CASE1
*out++ = std::accumulate(first, last, 0); // +1 til cycle/end
#else // default solution
*out++ = std::count(first, last, true); // count trues til cycle/end
#endif
}
We will be counting as long as the iterator returns true. As a bonus we also have another implementation using std::accumulate, that will start with an init value of 0 and add all the true instances, a value that obviously is converted to 1.
Correspondingly, our iterator will simply return true every time it is dereferenced. As simple as this.
To do so we remove the std::tuple<bool, int> value holder and add a boolean marker for the end.
T m_pos, m_posmax; // start/current pos / end of range
using FuncMove = std::function<int(const int &)>;
const FuncMove m_fmove;
T m_tort, m_hare; // Positions of tortoise/hare
const T m_tsteps = T{1}, m_hsteps = T{2}; // Mover per cycle
bool m_end;
CycleIterator(
const T &start, // steps for hare
const T &stop, // steps for hare
const FuncMove &fmove, // function that will move tortoise and hare
const T &htstart = T{1}, // starting pos for tort/hare
const T &tsteps = T{1}, // steps for tort
const T &hsteps = T{2} // steps for hare
) : m_pos{start}, m_posmax{stop}, m_fmove{fmove},
m_tort{htstart}, m_hare{htstart}, m_tsteps{tsteps}, m_hsteps{hsteps},
m_end(m_pos == m_posmax) {}
CycleIterator() : m_pos{std::numeric_limits<T>::max()}, m_end{true} {}
We have also changed the constructors, with the regular one taking the beginning and end of range and the “end-of-range” taking no parameters. The construction in main therefore changes. To be noted: the regular constructor no longer increments the iterator during initialization. But it is able to detect if the range is of zero length because N is 1, i.e., the iteration has to immediately stop.
tortoise_and_hare(
CycleIterator{1, N, fmove, S % mod},
CycleIterator{},
std::ostream_iterator<int>{std::cout}
);
Once the iterator detects the cycle it will mark itself as ended, making it “equal” to the “end-of-range” iterator. The detection and marking do happen inside the prefix increment operator.
auto &operator ++() { // Prefix increment
if (not m_end) {
for (T i{m_tsteps}; i--; m_tort = m_fmove(m_tort));
for (T i{m_hsteps}; i--; m_hare = m_fmove(m_hare));
m_end = (m_tort == m_hare) or (m_pos++ == m_posmax);
}
return *this;
}
To make sure that the iteration is stopped by the internal loops inside std::count, std::accumulate or a manual loop we could code ourselves, the operator == has to be also tweaked to use the m_end marker and compare itself to the “end-of-range” iterator.
auto operator ==(const CycleIterator& o) const {
return m_end ? o.m_end : (not o.m_end and (m_pos == o.m_pos));
}
With all the pieces in place, our approach solves the problem neatly with either std::count or std::accumulate (compile and test with make 04 case1 to use the latter).
Should you implement your own solution, there are two test cases available. This is so because the sample test provided in the problem description is an end-of-range test case. We also need to verify we do not make it to the end if a cycle is found.
Testing with the standard test case requires a simple make.
To test with the cycle-exists test case add a test1 to the make clause.
Summary¶
We finally have an iterator-based solution that is also customizable with custom ranges to traverse, start position for the tortoise and hare markers and additionally accepting a custom function to move the markers. Mission accomplished.
Note
SFINAE has been left out in this occasion to keep things shorter and because we have already done all the tests in previous solutions.
The reader may have also noticed that main can now take several problems by reading
problem inputs until the end-of-input is reached. This is not part of the problem
description but it seemed like a nice final touch.
Here is the code for the last, final, and great solution.
#include <algorithm> // std::count
#include <functional> // std::function
#include <iostream> // std::cin, std::cout
#include <iterator> // std::istream_iterator/ostream_iterator
#include <limits> // std::numeric_limits
#include <numeric> // std::accumulate
#include <type_traits> // std::enable_if, std::is_integral, std::void_t
template <typename T = int>
struct CycleIterator {
// Iterator tags
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = value_type &;
using pointer = value_type *;
T m_pos, m_posmax; // start/current pos / end of range
using FuncMove = std::function<int(const int &)>;
const FuncMove m_fmove;
T m_tort, m_hare; // Positions of tortoise/hare
const T m_tsteps = T{1}, m_hsteps = T{2}; // Mover per cycle
bool m_end;
CycleIterator(
const T &start, // steps for hare
const T &stop, // steps for hare
const FuncMove &fmove, // function that will move tortoise and hare
const T &htstart = T{1}, // starting pos for tort/hare
const T &tsteps = T{1}, // steps for tort
const T &hsteps = T{2} // steps for hare
) : m_pos{start}, m_posmax{stop}, m_fmove{fmove},
m_tort{htstart}, m_hare{htstart}, m_tsteps{tsteps}, m_hsteps{hsteps},
m_end(m_pos == m_posmax) {}
CycleIterator() : m_pos{std::numeric_limits<T>::max()}, m_end{true} {}
auto operator *() { return true; }
// auto operator ->() { return &m_val; } // deref to calc
auto &operator ++() { // Prefix increment
if (not m_end) {
for (T i{m_tsteps}; i--; m_tort = m_fmove(m_tort));
for (T i{m_hsteps}; i--; m_hare = m_fmove(m_hare));
m_end = (m_tort == m_hare) or (m_pos++ == m_posmax);
}
return *this;
}
// Postfix increment
// auto operator ++(int) { CycleIterator tmp = *this; ++(*this); return tmp; }
auto operator ==(const CycleIterator& o) const {
return m_end ? o.m_end : (not o.m_end and (m_pos == o.m_pos));
}
auto operator !=(const CycleIterator& o) const { return not (*this == o); }
};
template <typename I, typename O>
auto
tortoise_and_hare(I first, I last, O out) {
#ifdef CASE1
*out++ = std::accumulate(first, last, 0); // +1 til cycle/end
#else // default solution
*out++ = std::count(first, last, true); // count trues til cycle/end
#endif
}
int
main(int, char *[]) {
// Prepare iterators for input and output
auto in = std::istream_iterator<int>{std::cin};
auto in_last = std::istream_iterator<int>{};
constexpr auto mod = 1 << 31; // fixed constant
while(in != in_last) {
// problem parameters (const and from input)
auto N = *in++, S = *in++, P = *in++, Q = *in++;
// Prepare "move" lambda and solve
auto fmove = [P, Q](const auto &x) { return (x * P + Q) % mod; };
tortoise_and_hare(
CycleIterator{1, N, fmove, S % mod},
CycleIterator{},
std::ostream_iterator<int>{std::cout}
);
}
return 0;
}