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.
