Les 8 reines : galop d’essai en D

27 01 2012

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.

 

 

 

 





Le Blues de Windows 2000

11 09 2011

J’ai retrouvé ça sur mon disque dur. Je l’ai écrit il y a dix ans, depuis j’ai quitté Windows et je suis passé à Linux. Tout n’y est pas rose, juste un peu moins bleu. Il y a dix ans c’était mon quotidien…

Lire la suite »





Kata NombreEnLettres en Perl

9 06 2011

Une fois n’est pas coutume, ce Kata a un nom français. Disons que vous travaillez pour une banque, sur une machine a rédiger les chèques. Dans le cadre de la défense de la langue Française le ministère de la culture demande que désormais les machines indiquent le montant en toute lettres, comme les êtres humains, en suivant les recommandations orthographiques de 1990. En gros, les séparateurs entre composants des chiffres sont des tirets au lieu de parfois des espaces e.g. on écrit vingt-et-un et dix-sept au lieu de vingt et un et dix-sept.

Pour ceux que cela intéresse on peut trouver les règles d’écriture détaillées des nombres en français ici.

Lire la suite »





Présentation du KataCRUD

27 03 2011

CRUD ce sont les initiales des quatres verbes Create Read Update and Delete.  Autrement dit le strict minimum nécessaire pour gérer un fichier structuré du point de vue de l’administrateur du dit fichier. Un kata intéressant parceque c’est un archetype d’un problème courant et pour la multiplicité des environnements techniques dans lesquel on peut le mettre en oeuvre.

Lire la suite »





KataPrimeFactos en Groovy

18 03 2011

Il faut, pour ce Kata, décomposer un nombre supérieur à 1 en produit de facteurs premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 3x3x5.
Lire la suite »





KataBankOCR / Implémentation en Python

14 03 2011

Voici une implémentation possible du KataBankOCR. Ce Kata est un classique dont l’énoncé peut être trouvé sur CodingDojo.org.

Lire la suite »





Kata Chop en C++

11 03 2011

Le Kata Chop est le problème classique de la recherche d’un élément dans un tableau trié. Dans ce Kata j’ai décidé d’utiliser l’environnement de compilation bjam et boost unit test, qui sont particulièrement simples à mettre en oeuvre.

Lire la suite »








Suivre

Recevez les nouvelles publications par mail.