Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdint>
- #include <cstdlib>
- #include <type_traits>
- #include <utility>
- #include <memory>
- #include <range/v3/core.hpp>
- #include <range/v3/span.hpp>
- #include <range/v3/action/insert.hpp>
- #include <range/v3/numeric/accumulate.hpp>
- #include <range/v3/utility/functional.hpp>
- #include <range/v3/view/indices.hpp>
- #include <range/v3/view/sliding.hpp>
- #include <range/v3/view/transform.hpp>
- #include <boost/container/flat_map.hpp>
- #include <boost/container/static_vector.hpp>
- #include <boost/hof/construct.hpp>
- #include <boost/hof/unpack.hpp>
- // HACK: make flat_map play nice with span until it gains its own proper data() member;
- // unnecessary some point post-Boost 1.67
- namespace boost::container {
- template<typename... Ts>
- typename flat_map<Ts...>::pointer data(flat_map<Ts...>& fm) noexcept {
- return !fm.empty() ? std::addressof(*fm.begin()) : nullptr;
- }
- template<typename... Ts>
- typename flat_map<Ts...>::const_pointer data(flat_map<Ts...> const& fm) noexcept {
- return !fm.empty() ? std::addressof(*fm.begin()) : nullptr;
- }
- }
- namespace hof = boost::hof;
- namespace rngs = ranges;
- namespace rngvs = rngs::view;
- using int_t = std::int_fast8_t;
- using distance_t = std::int_fast16_t;
- namespace detail {
- using indexed_ints_t = boost::container::flat_map<
- distance_t, int_t, // <n: int_t, idx: size_t> -- representational optimization
- rngs::less,
- boost::container::static_vector<std::pair<distance_t, int_t>, 100>
- >;
- auto const index_ints = [](auto const& ints) -> indexed_ints_t {
- indexed_ints_t ret;
- rngs::action::insert(
- ret,
- rngvs::transform(ints, rngvs::indices(static_cast<int_t>(rngs::size(ints))),
- hof::construct<indexed_ints_t::value_type>())
- );
- return ret;
- };
- auto const sum_consecutive_distances = [](rngs::span<indexed_ints_t::value_type const> const indexed_ints) -> distance_t {
- return rngs::accumulate(
- rngvs::sliding(indexed_ints, 2),
- distance_t{}, rngs::plus{},
- [](auto const& iis) {
- auto [a, a_idx] = iis.front();
- auto const& [b, b_idx] = iis.back();
- return ++a == b ? static_cast<int_t>(std::abs(b_idx - a_idx)) : int_t{}; // ++ avoids promotion
- }
- );
- };
- auto const sum_gapped_distances = [](distance_t const gap, indexed_ints_t const& indexed_ints) -> distance_t {
- return rngs::accumulate(
- rngs::span{indexed_ints},
- distance_t{}, rngs::plus{},
- hof::unpack([&indexed_ints, gap](auto n, auto const idx) {
- auto const it = indexed_ints.find(n += gap); // += avoids promotion
- return it != indexed_ints.end() ? static_cast<int_t>(std::abs(it->second - idx)) : int_t{};
- })
- );
- };
- } // namespace detail
- auto const sum_distances = [](int_t const gap, auto const& ints)
- -> std::enable_if_t<std::is_same_v<rngs::range_value_type_t<decltype(ints)>, int_t>, distance_t>
- {
- auto const indexed_ints = detail::index_ints(ints);
- return gap == int_t{1}
- ? detail::sum_consecutive_distances(indexed_ints)
- : detail::sum_gapped_distances(gap, indexed_ints);
- };
- ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- // demo
- #include <cstddef>
- #include <exception>
- #include <bitset>
- #include <optional>
- #include <string_view>
- #include <tuple>
- #include <string>
- #include <iostream>
- #include <range/v3/algorithm/all_of.hpp>
- #include <range/v3/algorithm/copy.hpp>
- #include <range/v3/algorithm/for_each.hpp>
- #include <range/v3/view/generate.hpp>
- #include <range/v3/view/generate_n.hpp>
- #include <range/v3/view/take_while.hpp>
- #include <boost/fusion/include/std_tuple.hpp>
- #include <boost/hof/capture.hpp>
- #include <boost/hof/flow.hpp>
- #include <boost/hof/rotate.hpp>
- #include <boost/spirit/home/x3/core.hpp>
- #include <boost/spirit/home/x3/auxiliary/attr.hpp>
- #include <boost/spirit/home/x3/auxiliary/eoi.hpp>
- #include <boost/spirit/home/x3/char/char_class.hpp>
- #include <boost/spirit/home/x3/directive/repeat.hpp>
- #include <boost/spirit/home/x3/numeric/int.hpp>
- #include <boost/spirit/home/x3/numeric/uint.hpp>
- #include <boost/spirit/home/x3/operator/alternative.hpp>
- #include <boost/spirit/home/x3/operator/sequence.hpp>
- namespace x3 = boost::spirit::x3;
- using header = std::tuple<std::size_t, int_t, int_t>; // <rows, cols, gap>
- namespace {
- template<int_t N>
- std::integral_constant<int_t, N> constexpr int_c{};
- x3::int_parser<int_t> constexpr int_parser{};
- x3::uint_parser<std::size_t> constexpr rows_parser{};
- struct failfast { };
- auto const make_line_parser = [](std::string_view const line, auto&& parser) {
- return [line, parser = decltype(parser)(parser)](auto& attr) -> bool {
- return x3::phrase_parse(line.begin(), line.end(), parser >> x3::eoi, x3::ascii::space, attr);
- };
- };
- auto const parse_header = [](std::string_view const line) -> std::optional<header> {
- auto const parse_into = make_line_parser(line, rows_parser >> int_parser >> (int_parser | x3::attr(int_c<1>)));
- auto constexpr are_in_range = hof::unpack([](auto const rows, auto const cols, auto const gap) noexcept {
- return rows && cols > int_t{} && cols <= int_t{100} && gap > int_t{} && gap < int_t{100};
- });
- std::optional<header> ret;
- if (!line.empty() && (!parse_into(ret.emplace()) || !are_in_range(*ret))) {
- ret = std::nullopt;
- }
- return ret;
- };
- auto const parse_ints = [](int_t const count, std::string_view const line) -> boost::container::static_vector<int_t, 100> {
- auto const parse_into = make_line_parser(line, x3::repeat(count)[int_parser]);
- auto constexpr are_in_range = hof::capture([](auto const n) noexcept { return n > int_t{} && n <= int_t{100}; })
- (hof::rotate(rngs::all_of));
- auto const are_unique = [](auto const& ints) {
- std::bitset<100> ints_set;
- return rngs::all_of(
- ints,
- [&ints_set](auto const i) noexcept -> bool { return ints_set[i].flip(); },
- [](std::make_unsigned_t<int_t> n) noexcept -> std::size_t { return --n; }
- );
- };
- boost::container::static_vector<int_t, 100> ret;
- if (line.empty() || !parse_into(ret)) {
- throw failfast{};
- }
- if (rngs::span const rsp{std::as_const(ret)}; !are_in_range(rsp) || !are_unique(rsp)) {
- throw failfast{};
- }
- return ret;
- };
- void impl()
- try {
- std::string line_buf_;
- line_buf_.reserve(291); // max for trim valid input: characters in stringized [1,100] + delimiting spaces
- auto const read_line = [&line_buf_]() -> std::string_view {
- if (!std::getline(std::cin, line_buf_)) {
- throw failfast{};
- }
- return line_buf_;
- };
- auto read_print_distances = hof::unpack([read_line](auto const rows, auto const cols, auto const gap) {
- rngs::copy(
- rngvs::generate_n(hof::flow(read_line,
- hof::capture(cols)(parse_ints),
- hof::construct<rngs::span<int_t const>>(),
- hof::capture(gap)(sum_distances)),
- rows),
- rngs::ostream_iterator{std::cout, "\n"}
- );
- });
- rngs::for_each(
- rngvs::generate(hof::flow(read_line, parse_header)) | rngvs::take_while(rngs::convert_to<bool>{}),
- rngs::indirect(std::move(read_print_distances))
- );
- } catch (failfast) { }
- } // anon namespace
- int main()
- try {
- std::ios::sync_with_stdio(false);
- impl();
- return EXIT_SUCCESS;
- } catch (std::exception const& ex) {
- std::cerr << ex.what() << '\n';
- return EXIT_FAILURE;
- } catch (...) {
- std::cerr << "unknown exception (...)\n";
- return EXIT_FAILURE;
- }
Add Comment
Please, Sign In to add comment