Skip to content

anonymous /gist:4695794
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Find the Min
/*
CC0 1.0 Universal (CC0 1.0)
Public Domain
https://creativecommons.org/publicdomain/zero/1.0/
*/
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <stdexcept>
#include <sstream>
#include <cstdint>
#include <boost/fusion/tuple.hpp>
#include <boost/fusion/algorithm.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>
namespace
{
/* m[] is in the field of r and 1 <= r <= 10^9
* max(m[]) = max(r) - 1 = 2^x where x = ln (10^9 - 1) / ln (2) = <30
* therefore 32bit signed ints are fine for m[i], and still allow us to use < 0 for junk.
*
* The prng [b * m[i-1] + c] cannot exceed ~2^60 so we'll use a 64bit signed int in the generator
* without putting too much thought in to the mathematics.
*
* a, b, c, r, n, k will all be ap_int_t
*/
typedef int32_t ap_int_t;
struct array_prng_t
{
array_prng_t (ap_int_t const a_, ap_int_t const b_, ap_int_t const c_, ap_int_t const r_)
: a(a_), b(b_), c(c_), r(r_), value(a_) {}
ap_int_t operator()()
{
ap_int_t const old_val = value;
value = ((b * int64_t(value)) + c) % r;
return old_val;
}
void reset()
{
value = a;
}
ap_int_t a, b, c, r;
ap_int_t value;
};
struct array_problem_param_t
{
array_problem_param_t (ap_int_t n_, ap_int_t k_): n(n_), k(k_) {}
ap_int_t n, k;
};
struct array_problem_t
{
array_problem_t (array_prng_t&& prng_, array_problem_param_t&& params_)
: prng(prng_), params(params_) {}
ap_int_t nth_element() const;
array_prng_t prng;
array_problem_param_t params;
};
// Not strictly required, but op>> int will jump over new lines, whereas this'll blow up.
template <typename T, typename Tuple>
void
snort_line_of (std::istream& src_stream, Tuple&& dest)
{
std::string line;
std::getline (src_stream, line);
std::istringstream line_iss (line);
line_iss.exceptions (std::ios::failbit | std::ios::badbit);
boost::fusion::for_each (std::forward<Tuple>(dest), [&line_iss](T& val) { line_iss >> val; });
}
std::vector<array_problem_t>
get_array_problem_vec
(
std::istream& is,
ap_int_t const n_array_problems
)
{
std::vector<array_problem_t> array_problem_vec;
if ((n_array_problems < 1) || (n_array_problems > 20))
throw std::range_error ("Number of array problems out of range 5 <= m <= 20");
array_problem_vec.reserve (n_array_problems);
auto array_problem_inserter = std::back_inserter (array_problem_vec);
std::generate_n (array_problem_inserter, n_array_problems,
[&is]() {
ap_int_t n, k;
ap_int_t a, b, c, r;
auto param_tuple = boost::fusion::tie(n, k);
auto prng_tuple = boost::fusion::tie(a, b, c, r);
param_tuple = boost::fusion::make_tuple(-1, -1);
prng_tuple = boost::fusion::make_tuple(-1, -1,-1, -1);
snort_line_of<ap_int_t> (is, param_tuple);
snort_line_of<ap_int_t> (is, prng_tuple);
return array_problem_t (array_prng_t (a, b, c, r), array_problem_param_t (n, k));
}
);
return array_problem_vec;
}
ap_int_t
array_problem_t::nth_element
() const
{
struct in_gen_order {};
struct in_order {};
array_prng_t prng (this->prng);
prng.reset();
boost::multi_index_container<ap_int_t,
boost::multi_index::indexed_by<
boost::multi_index::sequenced<boost::multi_index::tag<in_gen_order>>,
boost::multi_index::ordered_non_unique<boost::multi_index::tag<in_order>,
boost::multi_index::identity<ap_int_t>>
> // Yeah, yeah...
> num_array;
std::generate_n (std::back_inserter(num_array), this->params.k, prng);
auto const& in_order_index = num_array.get<in_order>();
for (ap_int_t i = this->params.k; i < this->params.n; ++i)
{
ap_int_t min_missing = 0;
auto gap_front = *in_order_index.begin();
auto gap_end = in_order_index.upper_bound (gap_front);
if (0 == gap_front) {
while ((gap_end != in_order_index.end()) && (*gap_end <= (gap_front + 1))) {
gap_front = *gap_end;
gap_end = in_order_index.upper_bound (gap_front);
}
min_missing = gap_front + 1;
}
// Simulate a circular buffer
num_array.pop_front ();
num_array.push_back (min_missing);
}
return num_array.back();
}
} // anonymous namespace
int main
(int const argc, char* argv[])
{
std::ifstream src_file;
unsigned n_array_problems = 0;
if (argc < 2)
return EXIT_FAILURE;
src_file.exceptions (std::ios::failbit | std::ios::badbit);
try {
std::string n_array_problems_str;
src_file.open (argv[1]);
std::getline (src_file, n_array_problems_str);
n_array_problems = std::stoul (n_array_problems_str);
std::vector<array_problem_t>
array_problem_vec = get_array_problem_vec (src_file, n_array_problems);
uint32_t i = 1;
std::for_each (array_problem_vec.begin(), array_problem_vec.end(),
[&i](array_problem_t const& array_problem)
{ std::cout << "Case #" << i++ << ": " << array_problem.nth_element() << std::endl; });
return EXIT_SUCCESS;
}
catch (std::exception& e) {
std::cerr << "6 minutes should be enough for anyone." << std::endl;
throw;
}
return EXIT_FAILURE;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.