type Alignment a b = [(a, b)]

trans_align :: (Ord x, Ord y) => Alignment x y -> Alignment y z -> Alignment x z
trans_align ((p1, p2):ps) ((q1, q2) : qs)
    | p2 == q1 = (p1, q2) : trans_align ps qs   -- return match and continue
    | p2 < q1 = trans_align ps ((q1, q2) : qs)  -- skip first 'p'
    | q1 < p2 = trans_align ((p1, p2) : ps) qs  -- skip first 'q'
trans_align _ _ = []                            -- one input is empty

main = do
    let s1 = [(1, 2), (2, 3), (4, 5)] :: Alignment Int Int
    let s2 = [(1, 2), (3, 4), (5, 6)] :: Alignment Int Int
    print $ trans_align s1 s2 -- Output: [(2,4),(4,6)]

See what have we done? In the end we’ll probably just use Int for all the type variables (x, y, and z), but the implementation of trans_align doesn’t know this. Thus the type ensures that indices in the different sequences are kept separately, and things like comparing indices from different sequences, or returning indices from the wrong sequence are no longer not just bad ideas, they’re illegal, and enforced by the compiler. How cool is that?

type Alignment a b = [(a, b)]

trans_align :: (Ord x, Ord y) => Alignment x y -> Alignment y z -> Alignment x z
trans_align ((p1, p2):ps) ((q1, q2) : qs)
    | p2 == q1 = (p1, q2) : trans_align ps qs   -- return match and continue
    | p2 < q1 = trans_align ps ((q1, q2) : qs)  -- skip first 'p'
    | q1 < p2 = trans_align ((p2, p1) : ps) qs  -- try this!
trans_align _ _ = []                            -- one input is empty

main = do
    let s1 = [(1, 2), (2, 3), (4, 5)] :: Alignment Int Int
    let s2 = [(1, 2), (3, 4), (5, 6)] :: Alignment Int Int
    print $ trans_align s1 s2 -- Output: [(2,4),(4,6)]

import std.stdio, std.array, std.typecons;

template Alignment(a, b) {
    alias Tuple!(a,b)[] Alignment;
}

alias tuple T;

Tuple!(x,z)[] trans_align(x, y, z)(Tuple!(x,y)[] p, Tuple!(y,z)[] q) {
    if (p.empty || q.empty) return [];

    auto p1 = p[0][0];
    auto p2 = p[0][1];
    auto ps = p[1 .. $];
    auto q1 = q[0][0];
    auto q2 = q[0][1];
    auto qs = q[1 .. $];

    if (p2 == q1) return T(p1, q2) ~ trans_align(ps, qs); // return match and continue
    if (p2 < q1) return trans_align(ps, T(q1, q2) ~ qs);  // skip first 'p'
    if (q1 < p2) return trans_align(T(p1, p2) ~ ps, qs);  // skip first 'q'
    //if (q1 < p2) return trans_align(T(p2, p1) ~ ps, qs);  // skip first 'q'

    assert(0);
}

void main() {
    Alignment!(int,int) s1 = [T(1, 2), T(2, 3), T(4, 5)];
    Alignment!(int,int) s2 = [T(1, 2), T(3, 4), T(5, 6)];
    writeln(trans_align(s1, s2)); // Output: [Tuple!(int,int)(2, 4), Tuple!(int,int)(4, 6)]
}

f :: Num a => a -> a -> a
f x y = x*x + y*y

main = print (f 3 2.4)

`3` is a valid representation both for Fractional numbers like Float and for Integer. As `2.4` is a Fractional number, `3` is then interpreted as being also a Fractional number.

import std.traits;

T f(T)(in T x, in T y) pure nothrow @safe if (isNumeric!T) {
    return x ^^ 2 + y ^^ 2;
}

void main() {
    import std.stdio;
    writeln(f(2.1, 4.2));
}

import std.traits;

T f(T)(in T x, in T y) pure nothrow @safe if (isNumeric!T) {
    return x ^^ 2 + y ^^ 2;
}

void main() {
    import std.stdio;
    writeln(f(2, 4.2)); // does not match any function template
}

import std.traits, std.bigint;

T f(T)(T x, T y) if (isNumeric!T || is(T == BigInt)) {
    return x ^^ 2 + y ^^ 2;
}

void main() {
    import std.stdio;
    writeln(f(BigInt(2), BigInt(4)));
}

template isInputRange(R) {
    enum bool isInputRange = __traits(compiles, {
        R r = void; // can define a range object
        if (r.empty) {} // can test for empty
        r.popFront(); // can invoke popFront()
        auto h = r.front; // can get the front of the range
    });
}

import std.stdio, std.random, std.algorithm;

__gshared uint dieCount;

int throwDie() {
    dieCount++;
    return uniform(0, 6);
}

int random8() {
    return ((throwDie() % 2) << 2) +
           ((throwDie() % 2) << 1) +
           (throwDie() % 2);
}

void main() {
    enum int N = 10_000_000;
    uint[int] freqs;

    foreach (_; 0 .. N)
        freqs[random8()]++;

    foreach (k; freqs.keys.sort())
        writeln(k, " ", freqs[k]);

    writefln("\n%.6f", dieCount / cast(double)N);
}

0 1249566
1 1250357
2 1251060
3 1248940
4 1250848
5 1248829
6 1250353
7 1250047

3.000000

import std.stdio, std.random, std.algorithm;

__gshared uint dieCount;

int throwDie() {
    dieCount++;
    return uniform(0, 6);
}

int random8() {
    while (true) {
        immutable int d1 = throwDie();
        if (d1 < 4)
            return (d1 << 1) + (throwDie() % 2);
    }
}

void main() {
    enum int N = 10_000_000;
    uint[int] freqs;

    foreach (_; 0 .. N)
        freqs[random8()]++;

    foreach (k; freqs.keys.sort())
        writeln(k, " ", freqs[k]);

    writefln("\n%.6f", dieCount / cast(double)N);
}

0 1250850
1 1249593
2 1248823
3 1248606
4 1249314
5 1250182
6 1251221
7 1251411

2.500165

import std.random: uniform;

__gshared uint die5Count;

/// Generates a random number in [1, 5].
int dice5() /*nothrow*/ {
    die5Count++; // update count
    return uniform(1, 6);
}

/// Naive, generates a random number in [1, 7] using dice5.
int fiveToSevenNaive() /*nothrow*/ {
    immutable int r = dice5() + dice5() * 5 - 6;
    return (r < 21) ? (r % 7) + 1 : fiveToSevenNaive();
}

/**
Generates a random number in [1, 7] using dice5,
minimizing calls to dice5.
*/
int fiveToSevenSmart() /*nothrow*/ {
    static int rem = 0, max = 1;

    while (rem / 7 == max / 7) {
        while (max < 7) {
            immutable int rand5 = dice5() - 1;
            max *= 5;
            rem = 5 * rem + rand5;
        }

        immutable int groups = max / 7;
        if (rem >= 7 * groups) {
            rem -= 7 * groups;
            max -= 7 * groups;
        }
    }

    immutable int result = rem % 7;
    rem /= 7;
    max /= 7;
    return result + 1;
}

void main() {
    import std.algorithm; // sort, reduce
    import std.stdio; // writefln
    enum int N = 10_000_000;

    foreach (rnd; [&fiveToSevenNaive, &fiveToSevenSmart]) {
        uint[int] counts;
        .die5Count = 0;

        foreach (_; 0 .. N)
            counts[rnd()]++;

        immutable tot = reduce!q{a + b}(counts.byValue());
        foreach (k; sort(counts.keys))
            writefln("%d %.2f%%", k, (100 * counts[k]) / cast(double)tot);

        writefln("Average dice5 throws: %.4f\n",
                 die5Count / cast(double)N);
    }
}

1 14.29%
2 14.30%
3 14.27%
4 14.29%
5 14.26%
6 14.29%
7 14.29%
Average dice5 throws: 2.3813

1 14.28%
2 14.28%
3 14.29%
4 14.30%
5 14.29%
6 14.29%
7 14.27%
Average dice5 throws: 1.5458

This post is about the D translation of two old little C++ programs, to show some differences in the idioms of the two languages, and to discuss a little about static typing too.

I have found the original C++ code in this page:
See also: http://www.weitz.de/einstein.html

Both C++ programs solve a logic problem named "Einstein's Riddle". Here you find more info about its variants:
http://en.wikipedia.org/wiki/Zebra_Puzzle

The original C++ versions are by Klaus Betzler and by Dr. Gabor Csanyi.

This post is not a discussion of the Einstein's Riddle, or of algorithms that solve it. The C++ code is about ten years old, so it doesn't use some of the handy features of modern C++0x, that are sometimes comparable to D features. So this is not meant to be a fair comparison between modern C++ and modern D V.2 language.

To compile the D code I am using DMD v.2.056 (or an alpha version of v.2.057 from GitHub).

See here for the complete C++ and D code:
http://www.fantascienza.net/leonardo/js/einstein.zip

Archive contents:
- einstein1.cpp: original first C++ (fast) solution.
- einstein1a.d: D translation of the first C++ solution.
- einstein2.cpp: original second C++ (slow) solution.
- einstein2a.d: first D translation of the second C++ solution. This contains a good amount of strong static typing. This uses more idiomatic D arrays.
- einstein2b.d: second D translation of the second C++ solution. This uses arrays that are more efficient but less idiomatic D.
- einstein2c.py: Python2 translation of the first D translation of the second C++ solution. This program is rather slow, even counting it's in Python, I don't fully know why.

Comments on the first program (einstein1.cpp and einstein1a.d):

C> inline unsigned long BIT(unsigned n) {return 1<<n;}
C> 
C> const unsigned long
C>   yellow = BIT(0),
C>   blue = BIT(1),
C>   red = BIT(2),
C>   green = BIT(3),
C>   white = BIT(4),
C> 
C>   norwegian = BIT(5),
C>   dane = BIT(6),
C>   brit = BIT(7),
C>   german = BIT(8),
C>   swede = BIT(9),
C> 
C>   water = BIT(10),
C>   tea = BIT(11),
C>   milk = BIT(12),
C>   coffee = BIT(13),
C>   beer = BIT(14),
C> 
C>   dunhill = BIT(15),
C>   marlboro = BIT(16),
C>   pallmall = BIT(17),
C>   rothmans = BIT(18),
C>   winfield = BIT(19),
C> 
C>   cat = BIT(20),
C>   horse = BIT(21),
C>   bird = BIT(22),
C>   fish = BIT(23),
C>   dog = BIT(24);
C> 
C> const char * Label[] = {
C>   "Yellow","Blue","Red","Green","White",
C>   "Norwegian","Dane","Brit","German","Swede",
C>   "Water","Tea","Milk","Coffee","Beer",
C>   "Dunhill","Marlboro","Pallmall","Rothmans","Winfield",
C>   "Cat","Horse","Bird","Fish","Dog"
C> };

D> string bitFlags(BaseType=uint)(string enumName, string enumItems) {
D>     string result = text("enum ", enumName, " : ", BaseType.stringof, " {\n");
D>     result ~= text("    None = 0,\n");
D>     foreach (i, flag; enumItems.split())
D>         result ~= text("    ", flag, " = (1 << ", i, "),\n");
D>     return result ~ "}";
D> }
D> 
D> mixin(bitFlags!uint("E", "
D> Yellow    Blue     Red      Green    White
D> Norwegian Dane     Brit     German   Swede
D> Water     Tea      Milk     Coffee   Beer
D> Dunhill   Marlboro Pallmall Rothmans Winfield
D> Cat       Horse    Bird     Fish     Dog"));

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

C> const unsigned long color = yellow+blue+red+green+white;
C> const unsigned long country = norwegian+dane+brit+german+swede;
C> const unsigned long drink = water+tea+milk+coffee+beer;
C> const unsigned long cigar = dunhill+marlboro+pallmall+rothmans+winfield;
C> const unsigned long animal = cat+horse+bird+fish+dog;
C> 
C> unsigned long house[5] = {norwegian,blue,milk,0,0};  // rules 8,9,14
C> unsigned long result[5];
C> 
C> const unsigned long comb[] = { // simple rules
C>   brit+red,                    // 1
C>   swede+dog,                   // 2
C>   dane+tea,                    // 3
C>   green+coffee,                // 5
C>   pallmall+bird,               // 6
C>   yellow+dunhill,              // 7
C>   winfield+beer,               // 12
C>   german+rothmans              // 13
C> };
C> 
C> const unsigned long combmask[] = { // corresponding selection masks
C>   country+color,
C>   country+animal,
C>   country+drink,
C>   color+drink,
C>   cigar+animal,
C>   color+cigar,
C>   cigar+drink,
C>   country+cigar
C> };

D> enum E color =   E.Yellow    | E.Blue     | E.Red      | E.Green    | E.White;
D> enum E country = E.Norwegian | E.Dane     | E.Brit     | E.German   | E.Swede;
D> enum E drink =   E.Water     | E.Tea      | E.Milk     | E.Coffee   | E.Beer;
D> enum E cigar =   E.Dunhill   | E.Marlboro | E.Pallmall | E.Rothmans | E.Winfield;
D> enum E animal =  E.Cat       | E.Horse    | E.Bird     | E.Fish     | E.Dog;
D> 
D> immutable E[] comb = [ // simple rules
D>     E.Brit     | E.Red,     // 1
D>     E.Swede    | E.Dog,     // 2
D>     E.Dane     | E.Tea,     // 3
D>     E.Green    | E.Coffee,  // 5
D>     E.Pallmall | E.Bird,    // 6
D>     E.Yellow   | E.Dunhill, // 7
D>     E.Winfield | E.Beer,    // 12
D>     E.German   | E.Rothmans // 13
D> ];
D> 
D> immutable E[] combMask = [ // corresponding selection masks
D>     country | color,
D>     country | animal,
D>     country | drink,
D>     color   | drink,
D>     cigar   | animal,
D>     color   | cigar,
D>     cigar   | drink,
D>     country | cigar
D> ];

The D version uses | (or) instead of +, for better clarity. comb and combMask are not enums for more efficiency.

D> int main() {
D>     E[5] house = [E.Norwegian, E.Blue, E.Milk, E.None, E.None]; // rules 8, 9, 14
D>     E[5] result;

'house' is an array of E enums, that are strongly typed, so I have had to add E.None, that is represented with 0.

==========================================

Comments on the second program (einstein2.cpp and einstein2a.d):

C> char *NationS[] = {"British", "Swedish", "Danish", "Norvegian", "German"};
C> enum Nation {British, Swedish, Danish, Norvegian, German};
C> char *NumberS[] = {"One", "Two", "Three", "Four", "Five"};
C> enum Number {One, Two, Three, Four, Five};
C> char *ColourS[] = {"Red", "Green", "Blue", "White", "Yellow"};
C> enum Colour {Red, Green, Blue, White, Yellow};
C> char *DrinkS[] = {"Milk", "Coffee", "Water", "Beer", "Tea"};
C> enum Drink {Milk, Coffee, Water, Beer, Tea};
C> char *SmokeS[] = {"PallMall", "Dunhill", "Blend", "BlueMaster", "Prince"};
C> enum Smoke {PallMall, Dunhill, Blend, BlueMaster, Prince};
C> char *PetS[] = {"Dog", "Cat", "Fish", "Horse", "Bird"};
C> enum Pet {Dog, Cat, Fish, Horse, Bird};

D> enum Number : ubyte { One,      Two,     Three,  Four,       Five   };
D> enum Color  : ubyte { Red,      Green,   Blue,   White,      Yellow };
D> enum Drink  : ubyte { Milk,     Coffee,  Water,  Beer,       Tea    };
D> enum Smoke  : ubyte { PallMall, Dunhill, Blend,  BlueMaster, Prince };
D> enum Pet    : ubyte { Dog,      Cat,     Fish,   Horse,      Bird   };
D> enum Nation : ubyte { British,  Swedish, Danish, Norvegian,  German };

http://en.wikipedia.org/wiki/C%2B%2B0x#Strongly_typed_enumerations

In D writeln is able to print the name of named enums, so the arrays like PetS are not necessary. In D unsigned bytes are named "ubyte".

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

C> void
C> myprint(char *ptr, char **s)
C> {
C>   printf("%12s%12s%12s%12s%12s\n", s[ptr[0]], s[ptr[1]], s[ptr[2]], s[ptr[3]], s[ptr[4]]);
C> }
...
C> main()
C> {
...
C> 		      // woo-hoo!
C> 		      printf("Found a solution:\n");
C> 		      printf("Nation: ");
C> 		      myprint(nation, NationS);
C> 		      printf("Number: ");
C> 		      myprint(number, NumberS);
C> 		      printf("Colour: ");
C> 		      myprint(colour, ColourS);
C> 		      printf("Drink : ");
C> 		      myprint(drink, DrinkS);
C> 		      printf("Smoke : ");
C> 		      myprint(smoke, SmokeS);
C> 		      printf("Pet   : ");
C> 		      myprint(pet, PetS);
C> 		      printf("\n");

D> void showRow(E)(in E[] data) {
D>     auto names = [EnumMembers!E];
D>     writefln("%6s: %12s%12s%12s%12s%12s",
D>              (Unqual!E).stringof,
D>              text(names[data[0]]), text(names[data[1]]),
D>              text(names[data[2]]), text(names[data[3]]),
D>              text(names[data[4]]));
D> }
...
D> void main() {
...
D>                                             writeln("Found a solution:");
D>                                             showRow(nation);
D>                                             showRow(number);
D>                                             showRow(color);
D>                                             showRow(drink);
D>                                             showRow(smoke);
D>                                             showRow(pet);
D>                                             writeln();
D>                                         }

D here is doing more at compile-time. The printing template function showRow is able to find the names of the enums and of their elements.

text() is used because formats like "%12s" are not yet supported (DMD 2.056) for enum members.

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

C> char perms[][5] = {
C>   {     4,     3,     2,     1,     0},
C>   {     3,     4,     2,     1,     0},
C>   {     4,     2,     3,     1,     0},
C>   {     2,     4,     3,     1,     0},
C>   {     3,     2,     4,     1,     0},
C>   {     2,     3,     4,     1,     0},
C>   {     4,     3,     1,     2,     0},
C>   {     3,     4,     1,     2,     0},
C>   {     4,     1,     3,     2,     0},
C>   {     1,     4,     3,     2,     0},
C>   {     3,     1,     4,     2,     0},
C>   {     1,     3,     4,     2,     0},
C>   {     4,     2,     1,     3,     0},
C>   {     2,     4,     1,     3,     0},
C>   {     4,     1,     2,     3,     0},
C>   {     1,     4,     2,     3,     0},
C>   {     2,     1,     4,     3,     0},
C>   {     1,     2,     4,     3,     0},
C>   {     3,     2,     1,     4,     0},
C>   {     2,     3,     1,     4,     0},
C>   {     3,     1,     2,     4,     0},
C>   {     1,     3,     2,     4,     0},
C>   {     2,     1,     3,     4,     0},
C>   {     1,     2,     3,     4,     0},
C>   {     4,     3,     2,     0,     1},
C>   {     3,     4,     2,     0,     1},
C>   {     4,     2,     3,     0,     1},
C>   {     2,     4,     3,     0,     1},
C>   {     3,     2,     4,     0,     1},
C>   {     2,     3,     4,     0,     1},
C>   {     4,     3,     0,     2,     1},
C>   {     3,     4,     0,     2,     1},
C>   {     4,     0,     3,     2,     1},
C>   {     0,     4,     3,     2,     1},
C>   {     3,     0,     4,     2,     1},
C>   {     0,     3,     4,     2,     1},
C>   {     4,     2,     0,     3,     1},
C>   {     2,     4,     0,     3,     1},
C>   {     4,     0,     2,     3,     1},
C>   {     0,     4,     2,     3,     1},
C>   {     2,     0,     4,     3,     1},
C>   {     0,     2,     4,     3,     1},
C>   {     3,     2,     0,     4,     1},
C>   {     2,     3,     0,     4,     1},
C>   {     3,     0,     2,     4,     1},
C>   {     0,     3,     2,     4,     1},
C>   {     2,     0,     3,     4,     1},
C>   {     0,     2,     3,     4,     1},
C>   {     4,     3,     1,     0,     2},
C>   {     3,     4,     1,     0,     2},
C>   {     4,     1,     3,     0,     2},
C>   {     1,     4,     3,     0,     2},
C>   {     3,     1,     4,     0,     2},
C>   {     1,     3,     4,     0,     2},
C>   {     4,     3,     0,     1,     2},
C>   {     3,     4,     0,     1,     2},
C>   {     4,     0,     3,     1,     2},
C>   {     0,     4,     3,     1,     2},
C>   {     3,     0,     4,     1,     2},
C>   {     0,     3,     4,     1,     2},
C>   {     4,     1,     0,     3,     2},
C>   {     1,     4,     0,     3,     2},
C>   {     4,     0,     1,     3,     2},
C>   {     0,     4,     1,     3,     2},
C>   {     1,     0,     4,     3,     2},
C>   {     0,     1,     4,     3,     2},
C>   {     3,     1,     0,     4,     2},
C>   {     1,     3,     0,     4,     2},
C>   {     3,     0,     1,     4,     2},
C>   {     0,     3,     1,     4,     2},
C>   {     1,     0,     3,     4,     2},
C>   {     0,     1,     3,     4,     2},
C>   {     4,     2,     1,     0,     3},
C>   {     2,     4,     1,     0,     3},
C>   {     4,     1,     2,     0,     3},
C>   {     1,     4,     2,     0,     3},
C>   {     2,     1,     4,     0,     3},
C>   {     1,     2,     4,     0,     3},
C>   {     4,     2,     0,     1,     3},
C>   {     2,     4,     0,     1,     3},
C>   {     4,     0,     2,     1,     3},
C>   {     0,     4,     2,     1,     3},
C>   {     2,     0,     4,     1,     3},
C>   {     0,     2,     4,     1,     3},
C>   {     4,     1,     0,     2,     3},
C>   {     1,     4,     0,     2,     3},
C>   {     4,     0,     1,     2,     3},
C>   {     0,     4,     1,     2,     3},
C>   {     1,     0,     4,     2,     3},
C>   {     0,     1,     4,     2,     3},
C>   {     2,     1,     0,     4,     3},
C>   {     1,     2,     0,     4,     3},
C>   {     2,     0,     1,     4,     3},
C>   {     0,     2,     1,     4,     3},
C>   {     1,     0,     2,     4,     3},
C>   {     0,     1,     2,     4,     3},
C>   {     3,     2,     1,     0,     4},
C>   {     2,     3,     1,     0,     4},
C>   {     3,     1,     2,     0,     4},
C>   {     1,     3,     2,     0,     4},
C>   {     2,     1,     3,     0,     4},
C>   {     1,     2,     3,     0,     4},
C>   {     3,     2,     0,     1,     4},
C>   {     2,     3,     0,     1,     4},
C>   {     3,     0,     2,     1,     4},
C>   {     0,     3,     2,     1,     4},
C>   {     2,     0,     3,     1,     4},
C>   {     0,     2,     3,     1,     4},
C>   {     3,     1,     0,     2,     4},
C>   {     1,     3,     0,     2,     4},
C>   {     3,     0,     1,     2,     4},
C>   {     0,     3,     1,     2,     4},
C>   {     1,     0,     3,     2,     4},
C>   {     0,     1,     3,     2,     4},
C>   {     2,     1,     0,     3,     4},
C>   {     1,     2,     0,     3,     4},
C>   {     2,     0,     1,     3,     4},
C>   {     0,     2,     1,     3,     4},
C>   {     1,     0,     2,     3,     4},
C>   {     0,     1,     2,     3,     4}
C> };

D> const(T[][]) permutations(T)(in T[] items) pure nothrow {
D>     const(T[])[] result;
D> 
D>     void perms(in T[] s, in T[] prefix=[]) nothrow {
D>         if (s.length)
D>             foreach (i, c; s)
D>                perms(s[0 .. i] ~ s[i+1 .. $], prefix ~ c);
D>         else
D>             result ~= prefix;
D>     }
D> 
D>     perms(items);
D>     return result;
D> }
...
D> void main() {
D>     static immutable permsNumber = permutations([EnumMembers!Number]);
D>     static immutable permsColor = cast(immutable(Color[][]))permsNumber;
D>     static immutable permsDrink = cast(immutable(Drink[][]))permsNumber;
D>     static immutable permsSmoke = cast(immutable(Smoke[][]))permsNumber;
D>     static immutable permsPet = cast(immutable(Pet[][]))permsNumber;

Here I have used one of the peculiar features of D, the compile-time function evaluation. The C++ 'perms' array is just an array of all permutations of the [0, 1, 2, 3, 4] numbers. So I have written a little permutations() function (a function as commonly useful as this one, maybe as a lazy range, needs to be present in Phobos. Python has a similar generator in the itertools standard library module) that returns an array of all the permutations.

In D the enums are strongly typed, and the functions of this program work with strongly typed enums to avoid bugs, so I need different permutations of the enum members. Probably a good compiler is able to see all those immutable arrays contain the same bit patterns (despite being of different types), but this program iterates on them many times, so to be sure there is low pressure on the CPU cache, the other arrays are just aliases of the first one. I don't last casts a lot, because they are quite unsafe in D, but here I think they are acceptable.

The D 2D arrays like permsNumber are dynamic arrays of dynamic arrays of 5 enum members, that are represented with ubytes. In the C++ code perms is an array of fixed-sized arrays, this gives a bit higher performance to the C++ code. I have created another D version that solves this problem, but needs to use the arrays in a not D idiomatic way, see below.

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

C> char
C> possible(char *number, char *colour, char* drink, char *smoke, char *pet)
C> {
C>   // Rules, with the rule number as a comment
C> 
C>   // single property rules
C>   if(number != NULL && number[Norvegian] != One) // 9
C>     return FALSE;
C>   if(colour != NULL && colour[British] != Red) // 1
C>     return FALSE;
C>   if(drink != NULL && drink[Danish] != Tea)  // 3
C>     return FALSE;
C>   if(smoke != NULL && smoke[German] != Prince) // 13
C>     return FALSE;
C>   if(pet != NULL && pet[Swedish] != Dog)    // 2
C>     return FALSE;

D> bool isPossible(in Number[] number, in Color[] color, in Drink[] drink,
D>                 in Smoke[] smoke, in Pet[] pet) pure nothrow {
D>     // Rules, with the rule number as a comment
D> 
D>     // single property rules
D>     if (!number.empty && number[Nation.Norvegian] != Number.One) // 9
D>         return false;
D>     if (!color.empty && color[Nation.British] != Color.Red)      // 1
D>         return false;
D>     if (!drink.empty && drink[Nation.Danish] != Drink.Tea)       // 3
D>         return false;
D>     if (!smoke.empty && smoke[Nation.German] != Smoke.Prince)    // 13
D>         return false;
D>     if (!pet.empty && pet[Nation.Swedish] != Pet.Dog)            // 2
D>         return false;

Here the stronger typing of the D enums allows to write safer code, with less chance for bugs.

Generally the D function uses const/immutable/pure/nothrow everywhere it's possible, this gives performance and safety.

==========================================

Comments on the second program, second version (einstein2b.d):

This is very similar to einstein2a.d, the main difference comes from the desire to increase the performance avoiding one pointer level using fixed-size arrays to represent the is various permutations.

D> import std.stdio, std.math, std.traits, std.array, std.conv;
D> 
D> 
D> const(T[N][]) permutationsFixed(T, size_t N)(in T[N] items) pure nothrow {
D>     const(T[N])[] result;
D>     T[N] row;
D> 
D>     void perms(in T[] s, in T[] prefix=[]) nothrow {
D>         if (s.length)
D>             foreach (i, c; s)
D>                perms(s[0 .. i] ~ s[i+1 .. $], prefix ~ c);
D>         else {
D>             row[] = prefix[];
D>             result ~= row;
D>         }
D>     }
D> 
D>     perms(items);
D>     return result;
D> }

The permutationsFixed() function returns an dynamic array of fixed size arrays.

D> enum Number : uint { One,      Two,     Three,  Four,       Five   };
D> enum Color  : uint { Red,      Green,   Blue,   White,      Yellow };
D> enum Drink  : uint { Milk,     Coffee,  Water,  Beer,       Tea    };
D> enum Smoke  : uint { PallMall, Dunhill, Blend,  BlueMaster, Prince };
D> enum Pet    : uint { Dog,      Cat,     Fish,   Horse,      Bird   };
D> enum Nation : uint { British,  Swedish, Danish, Norvegian,  German };

The enums have uint as base type because it's about or more efficient than ubytes, in this program.

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

D> bool isPossible(immutable(Number[5])* number,
D>                 immutable(Color[5])* color,
D>                 immutable(Drink[5])* drink,
D>                 immutable(Smoke[5])* smoke,
D>                 immutable(Pet[5])* pet
D>                 ) pure nothrow {
D>     // Rules, with the rule number as a comment
D> 
D>     // single property rules
D>     if (number && (*number)[Nation.Norvegian] != Number.One) // 9
D>         return false;
D>     if (color && (*color)[Nation.British] != Color.Red)      // 1
D>         return false;
D>     if (drink && (*drink)[Nation.Danish] != Drink.Tea)       // 3
D>         return false;
D>     if (smoke && (*smoke)[Nation.German] != Smoke.Prince)    // 13
D>         return false;
D>     if (pet && (*pet)[Nation.Swedish] != Pet.Dog)            // 2
D>         return false;
D> 
D>     // only check complicated rules, if everything is defined
D>     if (!number || !color || !drink || !smoke || !pet)
D>         return true;
D> 
D>     // double property rules
D>     foreach (i; 0 .. 5) {
D>         if ((*color)[i] == Color.Green && (*drink)[i] != Drink.Coffee)    // 5
D>             return false;
D>         if ((*smoke)[i] == Smoke.PallMall && (*pet)[i] != Pet.Bird)       // 6
D>             return false;
...
D> void main() {
...
D>     foreach (ref number; permsNumber)
D>         if (isPossible(&number, null, null, null, null))
D>             foreach (ref color; permsColor)
D>                 if (isPossible(&number, &color, null, null, null))

Normally in D you pass static arrays efficiently using "const ref T[N]", but in this program also nulls must be supported. So I have had to perform some experiments to find a flexible enough but efficient way to give them to the isPossible() function.

So I pass them as pointers to immutable fixed size arrays:

D>                 immutable(Color[5])* color,

They are pointers to arrays (so they are like C/C++/D1 fixed size arrays), so they are efficient, despite this is a not idiomatic way to use arrays in D.

To use the array items you need to deference the pointer first:

(*color)[i]

An alternative syntax, but it's less natural because the first isn't really an array of size 1, it's a pointer to an array:

color[0][i]

==========================================

Runtime timings, seconds:
  einstein1.cpp:  0.01
  einstein1a.d:   0.05
  einstein2.cpp:  0.70
  einstein2a.d:   1.09
  einstein2b.d:   0.76
  einstein2c.py: 19.03 (with Psyco)

G++ 4.6.1
Python 2.6.6

Celeron 2.3 GHz, 32 bit OS.

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

So "Make illegal states unrepresentable", as it's said here regarding OCaML code:
http://ocaml.janestreet.com/?q=node/85

So write your code to turn the illegal states into static errors.

There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).

Points where the sum of the digits of the x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant. For example, the point (59,79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25.

How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?

from collections import deque
import psyco; psyco.full()

def sum_digits(n):
    tot = 0
    while n:
        tot += n % 10
        n //= 10
    return tot

def ant():
    seen = set()
    count = 0
    stack = deque([(1000, 1000)])

    while stack:
        p = stack.pop()
        if p not in seen:
            seen.add(p)
            x, y = p
            if sum_digits(x) + sum_digits(y) <= 25:
                count += 1
                stack.append((x+1, y  ))
                stack.append((x-1, y  ))
                stack.append((x,   y+1))
                stack.append((x,   y-1))

    return count

print ant()

import std.stdio;

struct P { int x, y; }

int sumDigits(int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

uint[P] seen;
size_t count;

void walk(P p) {
    if (p !in seen) {
        seen[p] = 0;
        if (sumDigits(p.x) + sumDigits(p.y) <= 25) {
            count++;
            walk(P(p.x+1, p.y));
            walk(P(p.x-1, p.y));
            walk(P(p.x, p.y+1));
            walk(P(p.x, p.y-1));
        }
    }
}

void main() {
    walk(P(1000, 1000));
    writeln(count);
}

dmd -L/STACK:1000000 -O -release -inline ant_puzzle1_d.d

import std.stdio, std.typetuple;

size_t ant() pure nothrow {
    static int sumDigits(int n) pure nothrow {
        int sum = 0;
        while (n) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    static struct P { short x, y; }

    // This speeds up the hashing...
    static uint mapP(in P p) pure nothrow {
        return (p.x << 16) + p.y;
    }

    uint[uint] seen;
    size_t count;

    P[44_000] stack = void;
    size_t stackLen;

    stack[stackLen] = P(1000, 1000);
    stackLen++;

    while (stackLen) {
        immutable P p = stack[stackLen - 1];
        stackLen--;
        if (mapP(p) !in seen) {
            seen[mapP(p)] = 0;
            if (sumDigits(p.x) + sumDigits(p.y) <= 25) {
                count++;
                foreach (s; TypeTuple!(P(1,0), P(-1,0), P(0,1), P(0,-1))) {
                    stack[stackLen] = P(cast(short)(p.x+s.x), cast(short)(p.y+s.y));
                    stackLen++;
                }
            }
        }
    }

    return count;
}

void main() {
    writeln(ant());
}

#include <stdio.h>
#include <stdint.h>
#include <stack>
#include <boost/unordered_set.hpp>

using namespace std;

inline int sum_digits(int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

struct P { int16_t x, y; };

inline uint32_t map_p(const P p) {
    return (p.x << 16) + p.y;
}

size_t ant() {
    size_t count = 0;
    boost::unordered_set<uint32_t> seen;
    stack
 mystack;
    mystack.push({1000, 1000});

    while (!mystack.empty()) {
        const P p = mystack.top();
        mystack.pop();
        if (seen.find(map_p(p)) == seen.end()) {
            seen.insert(map_p(p));
            if (sum_digits(p.x) + sum_digits(p.y) <= 25) {
                count++;
                mystack.push({ (int16_t)(p.x + 1), p.y });
                mystack.push({ (int16_t)(p.x - 1), p.y });
                mystack.push({ p.x, (int16_t)(p.y + 1) });
                mystack.push({ p.x, (int16_t)(p.y - 1) });
            }
        }
    }

    return count;
}

int main() {
    printf("%u\n", ant());

    return 0;
}