Instantly share code, notes, and snippets.

# anonymous/gist:4695794 Created Feb 2, 2013

What would you like to do?
Find the Min
 /* CC0 1.0 Universal (CC0 1.0) Public Domain https://creativecommons.org/publicdomain/zero/1.0/ */ #include #include #include #include #include #include #include #include #include #include #include #include #include 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 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(dest), [&line_iss](T& val) { line_iss >> val; }); } std::vector get_array_problem_vec ( std::istream& is, ap_int_t const n_array_problems ) { std::vector 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 (is, param_tuple); snort_line_of (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>, boost::multi_index::ordered_non_unique, boost::multi_index::identity> > // Yeah, yeah... > num_array; std::generate_n (std::back_inserter(num_array), this->params.k, prng); auto const& in_order_index = num_array.get(); 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_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; }