1
\$\begingroup\$

This, but via template metaprogramming:

template <int n> struct insanity { int[][n] permutations; }

Generate all numbers with n digits (0-9) such that each digit is either:

  1. Zero
  2. The first digit
  3. Already present
  4. Greater than the maximum digit to the left

Don't worry about leading zeros either way.

Valid examples:

012333
012391

Invalid examples:

012945

(Is this even possible?)

Winning code will be explainable and concise, but I'll take a clear short answer over the shortest.

Clarification on conditions: Shortest code with a complete explanation for what's going on. "Complete" means: Explain it to someone who knows how templates work, but not how TMP works.

\$\endgroup\$
  • 2
    \$\begingroup\$ What is the objective winning criteria? Do you have a solution? \$\endgroup\$ – Johannes Kuhn Jun 15 '13 at 15:16
  • \$\begingroup\$ I do not have a solution. Let me clarify my criteria. \$\endgroup\$ – Narfanator Jun 15 '13 at 15:21
  • 2
    \$\begingroup\$ There are a number of things which aren't clear to me. What is a digit (i.e. are you assuming base 10)? What is the purpose of case 4? Why does the title talk about permutations? \$\endgroup\$ – Peter Taylor Jun 15 '13 at 16:13
3
\$\begingroup\$

Success!!!! It only took me 3 hours or so. (Note: Requires C++11 support)

4,410 characters (including output functions)

Compiled on GCC 4.7.2 (Ideone)

#include<iostream>
#include<type_traits>

int constexpr powOf10(size_t power)
{
    return power == 0 ? 1 : 10 * powOf10(power - 1);
}

template<int... digits>
struct buildNumber;

template<int first, int... digits>
struct buildNumber<first, digits...> : std::integral_constant<int, first * powOf10(sizeof...(digits)) + buildNumber<digits...>::value>
{
};

template<>
struct buildNumber<> : std::integral_constant<int, 0>
{
};

template<int... digits>
struct areAllDigits;

template<int first, int... digits>
struct areAllDigits<first, digits...>
{
    static bool constexpr value = first > 0 && first < 10 && areAllDigits<digits...>::value;
};

template<int first>
struct areAllDigits<first>
{
    static bool constexpr value = first>0 && first < 10;
};

template<class T>
struct buildNumberT;


template<int... digits>
struct digitContainer
{

};


template<int... digits>
struct buildNumberT<digitContainer<digits...>> : buildNumber<digits...> {};

template<class T1, class T2>
struct concatCtr;

template<int... digits1, int... digits2>
struct concatCtr<digitContainer<digits1...>, digitContainer<digits2...>>
{
    typedef  digitContainer<digits1..., digits2...> type;
};

template<int number, size_t digit>
struct breakIntoDigits
{
    typedef typename concatCtr<digitContainer<number / powOf10(digit)>, typename breakIntoDigits<number % powOf10(digit), digit - 1>::ctr>::type ctr;
};

template<int number>
struct breakIntoDigits<number, 0>
{
    typedef digitContainer<number> ctr;
};

template<int needle, int... haystack>
struct contains;

template<int needle, int first, int... haystack>
struct contains<needle, first, haystack...>
{
    static bool constexpr value = needle == first || contains<needle, haystack...>::value;
};

template<int needle>
struct contains<needle>
{
    static constexpr bool value = false;
};

template<int... values>
struct max;

template<int first, int... rest>
struct max<first, rest...>
{
    static constexpr int value = first > max<rest...>::value ? first : max<rest...>::value;
};

template<>
struct max<>
{
    static int constexpr value = 0;
};

template<class container, int... digits>
struct ruleChecker;

template<int current, int... allPrevious, int... rest>
struct ruleChecker<digitContainer<allPrevious...>, current, rest...>
{
    static bool constexpr value = (current == 0 || sizeof...(allPrevious) == 0 || contains<current, allPrevious...>::value || current > max<allPrevious...>::value) && ruleChecker<digitContainer<allPrevious..., current>, rest...>::value;
};

template<class container>
struct ruleChecker<container>
{
    static bool constexpr value = true;
};

template<class ctr1, class ctr2>
struct ruleCheckerT;

template<class ctr1, int... set2>
struct ruleCheckerT<ctr1, digitContainer<set2...>> : ruleChecker<ctr1, set2...>{};


template<int number, int length>
struct isValidNumber : ruleCheckerT<digitContainer<>, typename breakIntoDigits<number, length>::ctr>
{
};


template<int number, int length>
struct generateList
{
    typedef typename std::conditional<number % powOf10(length) == 0, 
        digitContainer<>,
        typename concatCtr<
            typename generateList<number + 1, length>::container,
            typename std::conditional<isValidNumber<number, length>::value,
                    digitContainer<number>,
                    digitContainer<>
                >::type
            >::type
        >::type container;
};

template<int number>
struct generateList<number, 1>
{
    typedef typename concatCtr<
        typename generateList<number + 1, 1>::container,
        typename std::conditional<isValidNumber<number, 1>::value,
                digitContainer<number>,
                digitContainer<>
            >::type
        >::type container;
};

#define DEFINE_ENDPOINT_FOR_LENGTH(length) template<> struct generateList<powOf10(length), (length)>{typedef digitContainer<> container;}

template<int length>
struct insanity
{
    static_assert(length > 0, "Length must be greater than 0.");
    typedef typename concatCtr<typename generateList<1, length>::container, digitContainer<0>>::type numberList;
};

template<int first, int... rest>
void outputContainer(digitContainer<first, rest...> values)
{
    std::cout<<first<<'\n';
    outputContainer(digitContainer<rest...>{});
}

void outputContainer(digitContainer<> empty)
{
    std::flush(std::cout);
}

Explanation

insanity is the entry point, as used in the OP. buildNumber builds a number from a list of digits; breakIntoDigits does the opposite; it takes a number and breaks it into length digits. areAllDigits is just a helper I used earlier. It isn't used in the final code. It's value property is true if all the numbers passed to it are base-10 digits. It generates a list of valid numbers (validated by isValidNumber) and puts them in a digitContainer (originally I was only going to use this for digits, but I decided to use it for both things).

Limitations

  • It can only calculate up to the point the compiler errors out from template recursion depth.
  • You need to define an ending point for each length because otherwise it keeps instantiating templates up to the limit because of std::conditional. You define an ending point for each length by typing DEFINE_ENDPOINT_FOR_LENGTH(i) where i is the length.
\$\endgroup\$
  • \$\begingroup\$ I'm really impressed. I'm slowly getting the time to understand this, but either way, I'll give you the answer in a day or two since you satisfy the criteria. \$\endgroup\$ – Narfanator Jun 19 '13 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.