Итак, недавно захотелось попрактиковаться в извращениях на шаблонах. Недолго думая, я решил сосчитать на них число счастливых билетов от 100 000 до 999 999. Назовем таковыми билеты, у которых сумма первых трех цифр равна сумме последних .
При этом задача должна выполниться в compile-time на шаблонах.
Первое что приходит в голову при решении такой задачи - организация простого цикла на шаблонах вида:
#include <stdio.h>
#define GET1(a) //получение первой цифры числа
#define GET2(a) //получение второй цифры числа
#define GET2(a) //получение второй цифры числа
#define GET3(a) //получение третьей цифры числа
#define GET4(a) //получение четвёртой цифры числа
#define GET5(a) //получение пятой цифры числа
#define GET6(a) //получение шестой цифры числа
#define CHECK(a) ((GET1(a)+GET2(a)+GET3(a)==GET4(a)+GET5(a)+GET6(a))?1:0)
template<int A>
struct get
{
static const int val=CHECK(A)+get<A-1>::val;
};
template<>
struct get<100000>
{
static const int val=0;
};
int main(int argc,char ** argv)
{
printf("%d\n",get<999999>::val);
return 0;
}
Но это решение не будет работать. Не будут работать и решения с разбитием числа сразу на отдельные символы и линейной итерацией по ним. Причина в том, что происходит много инстанцирований "в глубину", т.е. не определив класс get<x> мы определяем классы get<x-1>, get<x-2>. и.т.п. Современные компиляторы дают возможность делать много инстанцирований в глубину, в GCC к примеру был зашит предел в 500 который легко обходился указанием параметра -ftemplate-depth-1000000. Однако, это вызывало вылет компилятора. Очевидно, данное решение крайне неудачно.
Также в голову приходит очевидное решение: итерироваться не по числу, а по цифрам, что даёт более оптимальное решение. В коде оно будет выглядеть как:
#include <stdio.h>
#define GET(A) ((a0+a1+a2 == a3+a4+ A )?1:0)
template<
char a0,
char a1,
char a2,
char a3,
char a4,
>
struct get_lucky6
{
static const int val=GET(9)+GET(8)+GET(7)+GET(6)+GET(5)+GET(4)+GET(3)+GET(2)+GET(1)+GET(0);
};
template<
char a0,
char a1,
char a2,
char a3,
char a4
>
struct get_lucky5
{
static const int val=get_lucky6<a0,a1,a2,a3,a4>::val+get_lucky5<a0,a1,a2,a3,a4-1>::val;
};
template<
char a0,
char a1,
char a2,
char a3
>
struct get_lucky5<a0,a1,a2,a3,0>
{
static const int val=get_lucky6<a0,a1,a2,a3,0,9>::val;
};
template<
char a0,
char a1,
char a2,
char a3
>
struct get_lucky4
{
static const int val=get_lucky5<a0,a1,a2,a3,9>::val+get_lucky4<a0,a1,a2,a3-1>::val;
};
template<
char a0,
char a1,
char a2
>
struct get_lucky4<a0,a1,a2,0>
{
static const int val=get_lucky5<a0,a1,a2,0,9>::val;
};
template<
char a0,
char a1,
char a2
>
struct get_lucky3
{
static const int val=get_lucky4<a0,a1,a2,9>::val+get_lucky3<a0,a1,a2-1>::val;
};
template<
char a0,
char a1
>
struct get_lucky3<a0,a1,0>
{
static const int val=get_lucky4<a0,a1,0,9>::val;
};
template<
char a0,
char a1
>
struct get_lucky2
{
static const int val=get_lucky3<a0,a1,9>::val+get_lucky2<a0,a1-1>::val;
};
template<
char a0
>
struct get_lucky2<a0,0>
{
static const int val=get_lucky3<a0,0,9>::val;
};
template<
char a0
>
struct get_lucky1
{
static const int val=get_lucky2<a0,9>::val+get_lucky1<a0-1>::val;
};
template<>
struct get_lucky1<1>
{
static const int val=get_lucky2<1,9>::val;
};
int main(int argc,char ** argv)
{
printf("%d\n",get_lucky1<9>::val);
return 0;
}
Здесь при помощи препроцессора развернут последний внутренний цикл, дабы чуть сократить время компиляции. Однако, этот код не дает успешного результата. При компиляции данного кода компилятор "съедает" 300+ Мб памяти, и после 4 часов компиляции не завершает свою работу.
Замечу, что выше уже приведено направление оптимизации: нужно делать вычисление не одного билета за инстанцирование, а нескольких. Здесь на помощь приходит препроцессор: с его помощью и жертвой безопасности типов можно рекуррентно развернуть еще один цикл, существенно сократив число инстанцирований:
#include <stdio.h>
#define GET(A1,A) ((a0+a1+a2 == a3+A1+ A )?1:0)
#define GETA1(A1) (GET(A1,9)+GET(A1,8)+GET(A1,7)+GET(A1,6)+GET(A1,5)+GET(A1,4)+GET(A1,3)+GET(A1,2)+GET(A1,1)+GET(A1,0))
#define GETA2 (GETA1(9)+GETA1(8)+GETA1(7)+GETA1(6)+GETA1(5)+GETA1(4)+GETA1(3)+GETA1(2)+GETA1(1)+GETA1(0))
#define GET0(A1,A) ((a0+a1+a2 == A1+ A )?1:0)
#define GET0A1(A1) (GET0(A1,9)+GET0(A1,8)+GET0(A1,7)+GET0(A1,6)+GET0(A1,5)+GET0(A1,4)+GET0(A1,3)+GET0(A1,2)+GET0(A1,1)+GET0(A1,0))
#define GET0A2 (GET0A1(9)+GET0A1(8)+GET0A1(7)+GET0A1(6)+GET0A1(5)+GET0A1(4)+GET0A1(3)+GET0A1(2)+GET0A1(1)+GET0A1(0))
template<
char a0,
char a1,
char a2,
char a3
>
struct get_lucky4
{
static const int val=GETA2+get_lucky4<a0,a1,a2,a3-1>::val;
};
template<
char a0,
char a1,
char a2
>
struct get_lucky4<a0,a1,a2,0>
{
static const int val=GET0A2;
};
template<
char a0,
char a1,
char a2
>
struct get_lucky3
{
static const int val=get_lucky4<a0,a1,a2,9>::val+get_lucky3<a0,a1,a2-1>::val;
};
template<
char a0,
char a1
>
struct get_lucky3<a0,a1,0>
{
static const int val=get_lucky4<a0,a1,0,9>::val;
};
template<
char a0,
char a1
>
struct get_lucky2
{
static const int val=get_lucky3<a0,a1,9>::val+get_lucky2<a0,a1-1>::val;
};
template<
char a0
>
struct get_lucky2<a0,0>
{
static const int val=get_lucky3<a0,0,9>::val;
};
template<
char a0
>
struct get_lucky1
{
static const int val=get_lucky2<a0,9>::val+get_lucky1<a0-1>::val;
};
template<>
struct get_lucky1<1>
{
static const int val=get_lucky2<1,9>::val;
};
int main(int argc,char ** argv)
{
printf("%d\n",get_lucky1<9>::val);
return 0;
}
Данный код "съедает" порядка 450Мб, компилируется около 1,5 мин и дает корректный результат.
Может показаться, что в таком случае задачу на шаблонах не стоит строить и лучше воспользоваться чистым препроцессором. Это не так. Скомпилировав код:
#include <stdio.h>
#define GET(A0,A1,A2,A3,A4,A5) ((A0+A1+A2 == A3+A4+ A5 )?1:0)
#define GET6(A0,A1,A2,A3,A4) (GET(A0,A1,A2,A3,A4,0)+GET(A0,A1,A2,A3,A4,1)+GET(A0,A1,A2,A3,A4,2)+GET(A0,A1,A2,A3,A4,3)+GET(A0,A1,A2,A3,A4,4)+ \ GET(A0,A1,A2,A3,A4,5)+GET(A0,A1,A2,A3,A4,6)+GET(A0,A1,A2,A3,A4,7)+GET(A0,A1,A2,A3,A4,8)+GET(A0,A1,A2,A3,A4,9))
#define GET5(A0,A1,A2,A3) (GET6(A0,A1,A2,A3,0)+GET6(A0,A1,A2,A3,1)+GET6(A0,A1,A2,A3,2)+GET6(A0,A1,A2,A3,3)+GET6(A0,A1,A2,A3,4)+ \ GET6(A0,A1,A2,A3,5)+GET6(A0,A1,A2,A3,6)+GET6(A0,A1,A2,A3,7)+GET6(A0,A1,A2,A3,8)+GET6(A0,A1,A2,A3,9))
#define GET4(A0,A1,A2) (GET5(A0,A1,A2,0)+GET5(A0,A1,A2,1)+GET5(A0,A1,A2,2)+GET5(A0,A1,A2,3)+GET5(A0,A1,A2,4)+GET5(A0,A1,A2,5)+ \ GET5(A0,A1,A2,6)+GET5(A0,A1,A2,7)+GET5(A0,A1,A2,8)+GET5(A0,A1,A2,9))
#define GET3(A0,A1) (GET4(A0,A1,0)+GET4(A0,A1,1)+GET4(A0,A1,2)+GET4(A0,A1,3)+GET4(A0,A1,4)+GET4(A0,A1,5)+GET4(A0,A1,6) \ +GET4(A0,A1,7)+GET4(A0,A1,8)+GET4(A0,A1,9))
#define GET2(A0) (GET3(A0,0)+GET3(A0,1)+GET3(A0,2)+GET3(A0,3)+GET3(A0,4)+GET3(A0,5)+GET3(A0,6)+GET3(A0,7)+GET3(A0,8)+GET3(A0,9))
#define GET1 (GET2(1)+GET2(2)+GET2(3)+GET2(4)+GET2(5)+GET2(6)+GET2(7)+GET2(8)+GET2(9))
const int lucky=GET1;
int main(int argc,char ** argv)
{
printf("%d\n",lucky);
return 0;
}
Мы при компиляции получим порядка минуты, однако компилятор при этом "съедает" около 952Мб памяти.
Вообще вычисление этой задачи в compile-time несёт мало преимуществ. Однако, это возможно.
При тестировании использовался компьютер со следующими параметрами:
Процессор: Core 2 Duo 1.87GHz
RAM: 2Gb
Версия GCC: 4.4.3