Puzzle 8-10-08 (answer)

[Koroskin Denis]

On Tue, 12 Aug 2008 04:23:55 +0400, bearophile <bearophileHUGS at lycos.com>  
wrote:

> bearophile:
>> But I don't understand why for example getValue() can be a CT function,  
>> while DoCheckMen() can't.
>

because the following code is wrong due to mixing of compile time and  
run-time constants:

template square(int a)
{
    const int foo = a * a;
}

int getSquare(int a)
{
     return square!(a); // you can't instantiate a template
     // with a variable (unless it is an alias, which is not a case)
}

> Anyway, even using those few small CT functions the compile time  
> decreases from 1.81 s to about 0.91 s on my PC, and the memory used from  
> about 42 MB to 32 MB, I don't know why.
>
> Bye,
> bearophile

That's because compiler doesn't have to instantiate all those hundreds of  
templates (and hold them in memory until exit).

I took a step forward and eliminated all the templates. Note that now the  
result is returned as a string due to a lack of compile time text output  
(it will be output once per template/fuction instance).

int numChildren(int men, int women) {
     return 100 - men - women;
}

bool isEven(int number) {
     return !(number & 1);
}

int getValue(int men, int women, int children) {
     return 3 * men + 2 * women + children / 2;
}

bool isOverflow(int men, int women = 0) {
     return getValue(men, women, 0) > 100;
}

char[] DoCheckMen(int men) {
     return CheckWomen(men, 0, 100 - men);
}

char[] itoa(int i)
{
     if (i < 10) {
         return "0123456789"[i..i+1];
     } else {
         return itoa(i / 10) ~ itoa(i % 10);
     }
}

char[] CheckSolution(int men, int women, int children) {
     if (isEven(children) && getValue(men,women,children) == 100) {
         return  
"Men:\t"~itoa(men)~"\tWomen:\t"~itoa(women)~"\tChildren:\t"~itoa(children)~"\n";
     } else {
         return "";
     }
}

char[] DoCheckWomen(int men, int women) {
     return CheckSolution(men, women, numChildren(men, women));
}

char[] CheckWomen(int men, int first, int last) {
     if (first == last) {
         return DoCheckWomen(men, first);
     }

     if (isOverflow(men, first)) {
         return "";
     }

     return DoCheckWomen(men, first) ~ CheckWomen(men, first+1, last);
}

char[] CheckMen(int first, int last) {
     if (first == last) {
         return DoCheckMen(first);
     }
     if (isOverflow(first)) {
         return "";
     }

     return DoCheckMen(first) ~ CheckMen(first+1, last);
}

const char[] solutios = CheckMen(0, 100);
pragma(msg, solutios);