• bearophile (228/228) Mar 19 2011 These are mostly weekend musings.

bearophile <bearophileHUGS lycos.com> writes:

These are mostly weekend musings.
I've found another possible usage for the 'where' statement. But first let me
introduce the topic better.

This page contains a little problem:
http://csokavar.hu/blog/2010/04/20/problem-of-the-week-9-digit-problem/

The problem:
Find a number consisting of 9 digits in which each of the digits from 1 to 9
appears only once. This number must also satisfy these divisibility
requirements:
1. The number should be divisible by 9.
2. If the rightmost digit is removed, the remaining number should be divisible
by 8.
3. If the rightmost digit of the new number is removed, the remaining number
should be divisible by 7.
4. And so on, until there’s only one digit (which will necessarily be divisible
by 1).


A solution using just C++0x templates (not found by me, modified):

-------------

// g++ -ftemplate-depth-2000 -std=c++0x nine_digits.cpp
#include "stdio.h"

template<int... digits>
struct Value;

template<>
struct Value<> {
    static const int v = 0;
};

template<int first, int... rest>
struct Value<first, rest...> {
    static int const v = 10 * Value<rest...>::v + first;
};

template<int elem, int... set>
struct Contains;

template<int elem>
struct Contains<elem> {
    static const bool v = false;
};

template<int elem, int first, int... rest>
struct Contains<elem, first, rest...> {
    static const bool v = elem == first || Contains<elem, rest...>::v;
};

template<int... digits>
struct DivisorTest;

template<>
struct DivisorTest<> {
    static const bool v = true;
};

template<int first, int... rest>
struct DivisorTest<first, rest...> {
    static const int num = Value<first, rest...>::v;
    static const int div = sizeof...(rest) + 1;
    static const int mod = num % div;
    static const bool v = mod == 0;
};

template<int first, int... rest>
struct TestCandidate {
    static const bool v = (DivisorTest<first, rest...>::v && !Contains<first,
rest...>::v);
};

template<int length, int... digits>
struct Search;

template<int length, bool good, bool final, int digit, int... rest>
struct SearchI {
    static const int v = Search<length, digit + 1, rest...>::v;
};

template<int length, int digit, int... rest>
struct SearchI<length, true, true, digit, rest...> {
    static const int v = Value<digit, rest...>::v;
};

template<int length, int digit, int... rest>
struct SearchI<length, true, false, digit, rest...> {
    static const int v = Search<length, 1, digit, rest...>::v;
};

template<int length, int digit, int... rest>
struct Search<length, digit, rest...> {
    static const bool good = TestCandidate<digit, rest...>::v;
    static const bool final = good && 1 + sizeof...(rest) == length;
    static const int v = SearchI<length, good, final, digit, rest...>::v;
};

template<int length>
struct Search<length, 10> {
    static const int v = -1;
};

template<int length, int next, int... rest>
struct Search<length, 10, next, rest...> {
    static const int v = Search<length, next + 1, rest...>::v;
};

template<int length>
struct Search<length> {
    static const int v = Search<length, 1>::v;
};

int main() {
    printf("%d\n", Search<7>::v);
    return 0;
}

-------------

A translation of the C++0x to Haskell, from here, modified:
http://gergo.erdi.hu/cs/ninedigits/lorentey-c%2B%2B-tmp/lorentey-c%2B%2B-tmp.hs


value :: [Int] -> Int
value [] = 0
value (first:rest) = 10 * (value rest) + first

contains :: Int -> [Int] -> Bool
contains elem [] = False
contains elem (first:rest) = elem == first || (contains elem rest)

divisor_test :: [Int] -> Bool
divisor_test (first:rest) = mod' == 0
    where num = value (first:rest)
          div = (length rest) + 1
          mod' = num `mod` div

test_candidate :: [Int] -> Bool
test_candidate (first:rest) = divisor_test (first:rest) && (not (contains first
rest))

search_i :: Int -> Bool -> Bool -> [Int] -> Int
search_i len True True  (digit:rest) = value (digit:rest)
search_i len True False (digit:rest) = search len (1:digit:rest)
search_i len good final (digit:rest) = search len (digit+1:rest)

search :: Int -> [Int] -> Int
search len []             = search len [1]
search len [10]           = -1
search len (10:next:rest) = search len ((next+1):rest)
search len (digit:rest)   = search_i len good final (digit:rest)
    where good = test_candidate (digit:rest)
          final = good && 1 + (length rest) == len

main = print $ search 9 []

-------------

A translation of the Haskell code to D2 templates:


import core.stdc.stdio: printf;
import std.typetuple: allSatisfy;

template IsInteger(alias x) {
    enum bool IsInteger = is(typeof(x) == int);
}

template AreAllIntegers(args...) {
    enum bool AreAllIntegers = allSatisfy!(IsInteger, args);
}

template value(args...) if (AreAllIntegers!args) {
    static if (args.length == 0)
        enum int value = 0;
    else
        enum int value = 10 * value!(args[1..$]) + args[0];
}

template contains(int elem, args...) if (AreAllIntegers!args) {
    static if (args.length == 0)
        enum bool contains = false;
    else
        enum bool contains = elem == args[0] || contains!(elem, args[1..$]);
}

template divisor_test(args...) if (AreAllIntegers!args) {
    enum bool divisor_test = (value!args % args.length) == 0;
}

template test_candidate(args...) if (AreAllIntegers!args) {
    enum bool test_candidate = divisor_test!args && !(contains!args);
}

template search_i(int length, bool good, bool isFinal, digits...) if
(AreAllIntegers!digits) {
    static if (good && isFinal)
        enum int search_i = value!digits;
    else static if (good && !isFinal)
        enum int search_i = search!(length, 1, digits);
    else
        enum int search_i = search!(length, digits[0]+1, digits[1..$]);
}

template search(int length, digits...) if (AreAllIntegers!digits) {
    static if (digits.length == 0)
        enum int search = search!(length, 1);
    else static if (digits.length == 1 && digits[0] == 10)
        enum int search = -1;
    else static if (digits.length > 1 && digits[0] == 10)
        enum int search = search!(length, digits[1]+1, digits[2..$]);
    else
        enum int search = search_i!(length,
                                    test_candidate!digits,
                                    test_candidate!digits && digits.length ==
length,
                                    digits);
}

pragma(msg, search!9);
void main() {}

-------------

You see very well that C++/C++0x/D templates are functional programming, D
templates are a limited memory-hungry subset of Haskell with a noisy syntax :-)
(This also means that taking a look at Haskell syntax and implementation may
allow to improve D syntax and D implementation of templates, to reduce the
memory they need when they are used to perform computations on true values.
This reminds me the famous quite 'Any sufficiently complicated C or Fortran
program contains an ad hoc, informally-specified, bug-ridden, slow
implementation of half of Common Lisp.').

The D2 code that uses templates doesn't compile because it performs too many
template expansions (the C++0x version needs -ftemplate-depth-2000 to be
compiled).

This is a function of the Haskell version:

search :: Int -> [Int] -> Int
search len []             = search len [1]
search len [10]           = -1
search len (10:next:rest) = search len ((next+1):rest)
search len (digit:rest)   = search_i len good final (digit:rest)
    where good = test_candidate (digit:rest)
          final = good && 1 + (length rest) == len


A translation to D2:

template search(int length, digits...) if (AreAllIntegers!digits) {
    static if (digits.length == 0)
        enum int search = search!(length, 1);
    else static if (digits.length == 1 && digits[0] == 10)
        enum int search = -1;
    else static if (digits.length > 1 && digits[0] == 10)
        enum int search = search!(length, digits[1]+1, digits[2..$]);
    else
        enum int search = search_i!(length,
                                    test_candidate!digits,
                                    test_candidate!digits && digits.length ==
length,
                                    digits);
}


The D2 translation shows two things:
- The variadic template arguments (digits) are typed both in Haskell ([Int])
and C++0x (int digit, int... rest), but not in D2, so I've had to add a
template constraint (AreAllIntegers!digits).
- The Haskell code uses a "where" statement. Several people have asked for
"private" declarations inside D2 templates that don't break the eponymous
template trick. But a different solution is to introduce a "where", this is
hypothetical D2/D3 syntax:


// typesafe variadic template, syntax like Typesafe Variadic Functions
template search(int length, int[] digits...) {
    static if (digits.length == 0)
        enum int search = search!(length, 1);
    else static if (digits.length == 1 && digits[0] == 10)
        enum int search = -1;
    else static if (digits.length > 1 && digits[0] == 10)
        enum int search = search!(length, digits[1]+1, digits[2..$]);
    else
        enum int search = search_i!(length, good, final, digits);
        where {
            enum bool good = test_candidate!digits;
            enum bool isFinal = good && digits.length == length;
        };
}


This syntax is not so good, probably there are better ways to solve the same
problem. But the need exists, I'd like some way to define other constants in a
template that uses the eponymous template trick.

-------------

By the way, it's quite easy to solve the problem with D2 CTFE:

int x(int[] r, int v, int l) {
    int tot = l == 9 ? v : 0;
    foreach (i; r)
        if (((v * 10 + i) % (l + 1)) == 0) {
            int[] sele;
            foreach (j; r)
                if (j != i)
                    sele ~= j;
            tot += x(sele, v*10 + i, l + 1);
        }

    return tot;
}

pragma(msg, x([1,2,3,4,5,6,7,8,9], 0, 0));
void main() {}

Bye,
bearophile