C++17 solution for /r/dailyprogrammer challenge #317 [easy]

challenge_317_easy.cpp

#include <cstdint>
#include <type_traits>
#include <string_view>
#include <string>
#include <range/v3/core.hpp>
#include <boost/hana/core/is_a.hpp>
#include <boost/hana/functional/compose.hpp>
#include <boost/hana/functional/partial.hpp>
#include <boost/hana/at.hpp>
#include <boost/hana/at_key.hpp>
#include <boost/hana/basic_tuple.hpp>
#include <boost/hana/first.hpp>
#include <boost/hana/fold_right.hpp>
#include <boost/hana/front.hpp>
#include <boost/hana/fuse.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/length.hpp>
#include <boost/hana/less.hpp>
#include <boost/hana/map.hpp>
#include <boost/hana/mult.hpp>
#include <boost/hana/not_equal.hpp>
#include <boost/hana/pair.hpp>
#include <boost/hana/plus.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/second.hpp>
#include <boost/hana/string.hpp>
#include <boost/hana/transform.hpp>
#include <boost/hana/unpack.hpp>
#include <boost/hana/zip.hpp>

namespace detail {
    namespace hana = boost::hana;

    auto constexpr index_range_for = [](auto const& xs) noexcept {
        return hana::unpack(
            hana::make_range(hana::size_c<0>, hana::length(xs)),
            hana::make_basic_tuple
        );
    };

    auto constexpr generate_encodings = [](auto const prod_rules) noexcept {
        auto constexpr idx_rng = detail::index_range_for(prod_rules);
        return hana::to_map(hana::transform(
            hana::zip(idx_rng, hana::transform(prod_rules, hana::first)),
            hana::fuse([idx_rng](auto const i, auto const letter) noexcept {
                auto constexpr code = hana::unpack(idx_rng, [i](auto const... js) noexcept {
                    return hana::make_string(hana::char_c<js != i ? '0' : '1'>...);
                });
                return hana::make_pair(letter, code);
            })
        ));
    };

    template<typename DerivedT>
    struct computation_base : ranges::view_facade<DerivedT> {
        computation_base() = default;
        explicit computation_base(std::string_view const initial_word) : buf_(initial_word) { }

        bool equal(ranges::default_sentinel) const noexcept { return buf_.empty(); }
        bool equal(computation_base const& other) const noexcept { return buf_ == other.buf_; }

        decltype(auto) read() const noexcept { return (buf_); }

    protected:
        template<typename StrT, typename = std::enable_if_t<hana::is_a<hana::string_tag, StrT>()>>
        void append(StrT const str) {
            if constexpr (auto constexpr str_len = hana::length(str); str_len != hana::size_c<1>) {
                buf_ += std::string_view{str.c_str(), str_len};
            } else {
                buf_ += hana::front(str);
            }
        }

        std::string buf_;
    };

    template<typename ProductionRulesetT>
    struct computation : computation_base<computation<ProductionRulesetT>> {
        using base_type = computation_base<computation<ProductionRulesetT>>;
        using base_type::base_type;

        void next() {
            static ProductionRulesetT constexpr prod_rules{};

            switch (auto& buf = this->buf_; buf.size()) {
            case 1:
                buf.clear();
            case 0:
                return;
            default:
                auto match_letter = [this, letter = buf.front()](auto const i) {
                    if (auto constexpr p = hana::at(prod_rules, i); hana::first(p) == letter) {
                        this->append(hana::second(p));
                        return true;
                    }
                    return false;
                };
                buf.erase(0, 2);
                hana::unpack(
                    detail::index_range_for(prod_rules),
                    [=](auto const... is) { return (... || match_letter(is)); }
                );
            }
        }
    };

    template<typename ProductionRulesetT>
    struct coded_computation : computation_base<coded_computation<ProductionRulesetT>> {
        using base_type = computation_base<coded_computation<ProductionRulesetT>>;
        using base_type::base_type;
        using base_type::equal;

        bool equal(coded_computation const& other) const noexcept {
            return idx_ == other.idx_ && base_type::equal(other);
        }

        void next() {
            static ProductionRulesetT constexpr prod_rules{};
            static auto constexpr encodings     = detail::generate_encodings(prod_rules);
            static auto constexpr alphabet_size = hana::integral_c<decltype(idx_), hana::length(prod_rules)>;
            static auto constexpr reset_idx_at  = alphabet_size * hana::integral_c<decltype(idx_), 2>;

            switch (auto& buf = this->buf_; buf.size()) {
            case alphabet_size:
                buf.clear();
            case 0:
                return;
            default:
                bool const bit_set = buf.front() == '1';
                buf.erase(0, 1);
                if (idx_ < alphabet_size && bit_set) {
                    auto match_bit = [this](auto const i) {
                        if (i == idx_) {
                            auto constexpr code = hana::fold_right(
                                hana::second(hana::at(prod_rules, i)), hana::string_c<>,
                                hana::compose(hana::plus, hana::partial(hana::at_key, encodings))
                            );
                            this->append(code);
                            return true;
                        }
                        return false;
                    };
                    hana::unpack(
                        detail::index_range_for(prod_rules),
                        [=](auto const... is) { return (... || match_bit(is)); }
                    );
                }
                if (++idx_ == reset_idx_at) {
                    idx_ = 0;
                }
            }
        }

    private:
        std::uint_fast8_t idx_{};
    };

    template<template<typename> typename Computation>
    struct computer {
        template<typename ProductionRulesetT, typename CompT = Computation<ProductionRulesetT>,
                 typename = std::enable_if_t<std::is_base_of_v<computation_base<CompT>, CompT>>>
        CompT operator ()(std::string_view const initial_word, ProductionRulesetT) const {
            CompT ret{initial_word};
            ret.next();
            return ret;
        }
    };
} // namespace detail

detail::computer<detail::computation>       constexpr compute{};
detail::computer<detail::coded_computation> constexpr compute_coded{};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// demo

#include <cstdlib>
#include <exception>
#include <vector>
#include <iostream>
#include <range/v3/algorithm/copy.hpp>
#include <range/v3/algorithm/for_each.hpp>
#include <range/v3/numeric/accumulate.hpp>
#include <range/v3/view/transform.hpp>

namespace hana = boost::hana;
namespace rngs = ranges;
namespace rngvs = ranges::view;

using namespace std::string_view_literals;
using namespace hana::literals;

using checksum_type = std::int_fast32_t;
struct word_checksum {
    std::string_view word;
    checksum_type checksum;
};

auto constexpr prod_rules = hana::make_basic_tuple(
    hana::make_pair(hana::char_c<'a'>, "bc"_s),
    hana::make_pair(hana::char_c<'b'>, "a"_s),
    hana::make_pair(hana::char_c<'c'>, "aaa"_s)
);

auto const test_print = [](auto const& initial_word_checksums, auto const comp) {
    for (auto const& [initial_word, _] : initial_word_checksums) {
        auto const results = rngs::to_vector(comp(initial_word, prod_rules));
        std::cout << initial_word << " ("sv << results.size() << ")\n"sv;
        rngs::for_each(results, [](auto const& word) {
            std::cout << '\t';
            rngs::copy(word, rngs::ostreambuf_iterator<char>{std::cout});
            std::cout << '\n';
        });
        std::cout << '\n';
    }
};

auto const test_checksum = [](auto const& initial_word_checksums, auto const comp) {
    for (auto const& [initial_word, checksum] : initial_word_checksums) {
        auto const cs = rngs::accumulate(rngvs::transform(
            comp(initial_word, prod_rules),
            [](auto const& buf) {
                return rngs::accumulate(
                    buf, checksum_type{}, rngs::plus{},
                    [](auto const ch) -> checksum_type { return ch; }
                );
            }
        ), checksum_type{});
        std::cout << initial_word << " sums match ("sv << checksum << "): "sv << (cs == checksum) << '\n';
    }
};

static void impl() {
    static std::initializer_list<word_checksum> constexpr initial_words = {{"aaa"sv, 11834}, {"aaaaaaa"sv, 185886}};
    static std::initializer_list<word_checksum> constexpr initial_coded_words = {{"100100100"sv, 117293}};

    test_print(initial_words, compute);
    test_print(initial_coded_words, compute_coded);
    test_checksum(initial_words, compute);
    test_checksum(initial_coded_words, compute_coded);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cerr << std::boolalpha;
    std::cout << std::boolalpha;
    try {
        impl();
        return EXIT_SUCCESS;
    } catch (std::exception const& ex) {
        std::cerr << ex.what() << '\n';
    } catch (...) {
        std::cerr << "unknown exception (...)\n"sv;
    }
    return EXIT_FAILURE;
}