Uncategorized

Les 8 reines : galop d’essai en D

Premier essai en langage D. Même ceux qui ne connaissent pas D auront deviné que c’est un language de la famille du C. Disons que D pourrait prendre la suite du C, en considérant que C++ est un échec technique même si c’est une réussite en termes de parts de marché.

Mais ce sujet mérite d’être développé dans un autre billet. Pour le moment il s’agit juste de présenter le résultat de mon premier kata en D. La résolution du classique problème des 8 huits reines : placer 8 reines sur un échiquier sans qu’aucune d’entre elles ne se menace, selon la règle de déplacement des reines aux échecs, c’est à dire lignes droites et diagonales.

Un aspect agréable du D dans l’optique d’un kata, c’est que les tests unitaires sont intégrés au langage.

Bon, voici directement le résultat final.

 

import std.stdio;

struct Pos { uint x, y; };

pure bool menace(immutable Pos q1, immutable Pos q2)
{
    return (q1.x == q2.x)
    || (q1.y == q2.y)
    || (q1.x - q2.x == q1.y - q2.y)
    || (q2.x - q1.x == q1.y - q2.y);
}

bool queen(uint szx, uint szy, Pos [] result, uint remaining)
{
    if (remaining == 0){
        return true;
    }
    uint curx = cast(uint)result.length - remaining;
    uint y = 0;
    nexty: while (y < szy){
        foreach (Pos item ; result[0..$-remaining]){
            if (menace(item, Pos(curx, y))){
                y++;
                continue nexty;
            }
        }
        result[curx] = Pos(curx, y);
        if (queen(szx, szy, result, remaining - 1)){
            return true;
        }
        y++;
    }
    return false;
}

unittest
{
    enum nbqueens = 1;
    Pos [nbqueens] result;
    bool exist = queen(1, 1, result, 1);
    assert(exist == true);
    assert(result[0] == Pos(0, 0));
}

unittest
{
    enum nbqueens = 2;
    Pos [nbqueens] result;
    bool exist = queen(2, 3, result, 2);
    assert(exist == true);
    assert(!menace(result[0], result[1]));
}


void main()
{
    enum nbqueens = 8;
    Pos result[nbqueens];

    bool res = queen(8, 8, result, nbqueens);
    if (!res){
        writeln("No result found");
    }
    for (uint q = 0 ; q < nbqueens ; q++){
        writeln("Q", q, "[", result[q].x, ",", result[q].y, "]");
    }
}

 

L’écriture du kata a probablement été un peu trop directe (je suis passé au résultat final en seulement 2 tests). C’est peut-être aussi lié au fait que les problèmes de nature algorithmique se prêtent souvent mal à la forme kata, car il y a souvent un saut conceptuel entre les première étapes et la solution générale choisie.

 

 

 

 

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

w

Connexion à %s