Use C++ template metaprogramming to prepare the solutions at compile-time.


  • 0
    J

    Just for fun... actually the code would not get accepted as LeetCode puts some compile-time restrictions, e.g. "template instantiation depth exceeds maximum of 128". It should work on a local machine (with flag "-std=c++11" or above, and "-ftemplate-depth=1000" if compiled with clang).

    #include <cstddef>
    #include <string>
    #include <tuple>
    #include <type_traits>
    #include <utility>
    #include <vector>
    
    template <std::size_t value>
    using Value = std::integral_constant<std::size_t, value>;
    
    // Compile-time integer sequence.
    template <std::size_t ...s>
    struct Sequence {
      template <template <typename ...> class Host>
      using bind_to = Host<Value<s>...>;
    };
    
    // Generate a compile-time integer sequence.
    template <std::size_t n, std::size_t ...s>
    struct MakeSequence : MakeSequence<n-1, n-1, s...> {};
    
    template <std::size_t ...s>
    struct MakeSequence<0, s...> {
      using type = Sequence<s...>;
    };
    
    // Forward declaration of TypeList.
    template <typename ...Ts> class TypeList;
    using EmptyList = TypeList<>;
    
    // Meta functions for TypeList.
    // -----------------------------------------------------------------------------
    template <typename TL, typename PosTL, typename Enable = void>
    struct ElementAtImpl;
    
    template <typename TL, typename PosTL>
    struct ElementAtImpl<TL, PosTL, typename std::enable_if<PosTL::length == 0>::type> {
      using type = TL;
    };
    
    template <typename TL, typename PosTL>
    struct ElementAtImpl<TL, PosTL, typename std::enable_if<PosTL::length != 0>::type>
        : ElementAtImpl<typename std::tuple_element<
                            PosTL::head::value,
                            typename TL::template bind_to<std::tuple>>::type,
                        typename PosTL::tail> {};
    
    template <typename Out, typename Rest, template <typename ...> class Op,
              typename Enable = void>
    struct FilterImpl;
    
    template <typename Out, typename Rest, template <typename ...> class Op>
    struct FilterImpl<Out, Rest, Op, typename std::enable_if<Rest::length == 0>::type> {
      using type = Out;
    };
    
    template <typename Out, typename Rest, template <typename ...> class Op>
    struct FilterImpl<Out, Rest, Op,
                      typename std::enable_if<Op<typename Rest::head>::value>::type>
        : FilterImpl<typename Out::template push_back<typename Rest::head>,
                     typename Rest::tail, Op> {};
    
    template <typename Out, typename Rest, template <typename ...> class Op>
    struct FilterImpl<Out, Rest, Op,
                      typename std::enable_if<!Op<typename Rest::head>::value>::type>
        : FilterImpl<Out, typename Rest::tail, Op> {};
    
    template <typename Out, typename Rest, template <typename ...> class Op,
              typename Enable = void>
    struct FlatmapImpl;
    
    template <typename Out, typename Rest, template <typename ...> class Op>
    struct FlatmapImpl<Out, Rest, Op, typename std::enable_if<Rest::length == 0>::type> {
      using type = Out;
    };
    
    template <typename Out, typename Rest, template <typename ...> class Op>
    struct FlatmapImpl<Out, Rest, Op, typename std::enable_if<Rest::length != 0>::type>
        : FlatmapImpl<typename Out::template append<typename Op<typename Rest::head>::type>,
                      typename Rest::tail, Op> {};
    
    template <typename LeftTL, typename RightTL>
    struct CartesianProductImpl {
      template <typename LeftT>
      struct LeftHelper {
        template <typename RightT>
        struct RightHelper {
          using type = TypeList<LeftT, RightT>;
        };
        using type = typename RightTL::template map<RightHelper>;
      };
      using type = typename LeftTL::template flatmap<LeftHelper>;
    };
    // -----------------------------------------------------------------------------
    // End of meta functions.
    
    // A minimal TypeList to support all the compile-time operations.
    template <typename ...Ts>
    class TypeListBase {
     private:
      template <typename ...Tail> struct AppendHelper {
        using type = TypeList<Ts..., Tail...>;
      };
    
     public:
      static constexpr std::size_t length = sizeof...(Ts);
    
      using type = TypeList<Ts...>;
      using self = type;
    
      template <template <typename ...> class Host>
      using bind_to = Host<Ts...>;
    
      template <std::size_t ...pos>
      using at = typename ElementAtImpl<self, TypeList<Value<pos>...>>::type;
    
      template <typename T>
      using push_front = TypeList<T, Ts...>;
    
      template <typename T>
      using push_back = TypeList<Ts..., T>;
    
      template <typename TL>
      using append = typename TL::template bind_to<AppendHelper>::type;
    
      template <typename TL>
      using cartesian_product = typename CartesianProductImpl<self, TL>::type;
    
      template <template <typename ...> class Op>
      using map = TypeList<typename Op<Ts>::type...>;
    
      template <template <typename ...> class Op>
      using flatmap = typename FlatmapImpl<EmptyList, self, Op>::type;
    
      template <template <typename ...> class Op>
      using filter = typename FilterImpl<EmptyList, self, Op>::type;
    
     public:
      template <typename Container, template <typename ...> class Op>
      static inline Container Instantiate() {
        return { Op<Ts>()()... };
      }
    };
    
    template <typename T, typename ...Ts>
    class TypeList<T, Ts...> : public TypeListBase<T, Ts...> {
     public:
      using head = T;
      using tail = TypeList<Ts...>;
    };
    
    template <>
    class TypeList<> : public TypeListBase<> {};
    
    // List of hours and minutes.
    using Hours = MakeSequence<12>::type::bind_to<TypeList>;
    using Minutes = MakeSequence<60>::type::bind_to<TypeList>;
    
    // Count the number of 1-bits in an integer at compile-time.
    template <typename V>
    struct BitCounter {
      static constexpr std::size_t Count(const std::size_t n) {
        return n ? 1 + Count(n & (n-1)) : 0;
      }
      using type = TypeList<V, Value<Count(V::value)>>;
    };
    
    // Combine one hour slot with one minute slot, calculate the # of LEDs that are on.
    template <typename HMPair>
    struct HourMinuteCombiner {
      using H = typename HMPair::template at<0>;
      using M = typename HMPair::template at<1>;
      using type = TypeList<
          Value<H::template at<1>::value + M::template at<1>::value>,
          typename H::head, typename M::head>;
    };
    
    // Get all combinations of hour slot + minute slot.
    using HourMinuteCombinations =
        Hours::map<BitCounter>::cartesian_product<Minutes::map<BitCounter>>
                              ::map<HourMinuteCombiner>;
    
    // Select all the combinations where Count of LEDs are on.
    template <typename Count>
    struct HourMinuteSelector {
      template <typename E>
      struct Filter {
        static constexpr std::size_t value = (E::head::value == Count::value);
      };
      using type = HourMinuteCombinations::filter<Filter>;
    };
    
    // Convert compile-time hour:minute results into string representation.
    // These conversions are done at runtime, though.
    template <typename HMTuple>
    struct HourMinuteToString {
      static inline std::string ToMinuteString(const int value) {
        return value < 10 ? "0" + std::to_string(value) : std::to_string(value);
      }
      inline std::string operator()() const {
        return std::to_string(HMTuple::template at<1>::value) + ':' +
               ToMinuteString(HMTuple::template at<2>::value);
      }
    };
    
    template <typename HMList>
    struct HourMinuteListToStringVector {
      inline std::vector<std::string> operator()() const {
        return HMList::template Instantiate<std::vector<std::string>,
                                            HourMinuteToString>();
      }
    };
    
    // The solution class.
    class Solution {
     public:
      std::vector<std::string> readBinaryWatch(int num) {
        return num >= kTable.size() ? std::vector<std::string>() : kTable[num];
      }
    
     private:
      static const std::vector<std::vector<std::string>> kTable;
    };
    
    // Instantiate the table.
    const std::vector<std::vector<std::string>> Solution::kTable =
        MakeSequence<9>::type
            ::bind_to<TypeList>
            ::map<HourMinuteSelector>
            ::Instantiate<std::vector<std::vector<std::string>>,
                          HourMinuteListToStringVector>();
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.