Skip to content

Instantly share code, notes, and snippets.

@dodheim

dodheim/challenge_317_easy.cpp

Last active October 5, 2017 20:49
Show Gist options
  • Save dodheim/8c26bc73d616c0f9e8acab34c03f5834 to your computer and use it in GitHub Desktop.
Save dodheim/8c26bc73d616c0f9e8acab34c03f5834 to your computer and use it in GitHub Desktop.
Download ZIP
C++17 solution for /r/dailyprogrammer challenge #317 [easy]
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment