samedi 29 mai 2010

Visual Studio: Blocage de fichier durant la compilation de solution

Tavailler avec plusieurs sessions de Visual Studio peut quelques fois se montrer pénible.
Il arrive, de temps à autre, qu'il devienne impossible de compiler une solution parce que un fichier est bloqué par un autre processus.

J'ai déjà eu souvent l'occasion de voir ce message d'erreur durant mes phases de compilation:
Unable to copy de file XXX. The process cannot access the file xxx because it is being used by another process.

Difficile de trouver de la documentation sur ce point, mais Keyvan Nayyeri apporte une réponse satisfaisante dans son article "File Lock Issue in Visual Studio When Building a Project".

Cette erreur se produit lorsque Visual Studio rencontre un fichier ".locked" qu'il ne peut pas effacer car il est détenu par une autre instance de Visual Studio.
Dans ce cas, il ne peut produire un nouvel assembly (d'ou l'erreur).
Cela peut arriver assez facilement si l'on travaille sur de très gros projet... dans mon cas, je soupçonne la compilation de la documentation du code (dans des fichier XML) d'être à l'origine de mon problème.

SqlServer - Cross Apply

A quoi sert Cross Apply
Cross Apply est une nouvelle fonctionnalité T-SQL apparue avec SQL 205 (si je ne me trompe pas).
Cross Apply est une alternative permettant de contourner les limitations du cross join.

En effet, il n'est pas possible d'écrire la requête suivante car A.Val est hors du scope de la requête principale.
select A.*, b.X
from A
cross join (select B.X from B where B.Val=A.Val) b -- Invalid!

La seule façon d'arriver au résultat attendu est de rejeter le test "B.Val=A.Val" hors du scope du cross join.
Mais cela à une lourde conséquence car le travail de jointure est très couteux en ressource.
select A.*, b.X
from A
cross join (select * from B) b
where A.Val = b.Val -- Correct!

 C'est là qu'intervient le Cross Apply car l'instruction permet de faire le test de jointure dans le scope du Cross Apply.
select A.*, b.X
from A
cross apply (select B.X from B where B.Val=A.Val) b



Exemples
-- Cross Apply avec une sous requête
select o.*, rs.RunningSum, rs.SameCode
from Order o
cross apply
 (
   select
     sum(Amount) as RunningSum,
     sum(case when p.OrderCode = o.OrderCode then Amount else 0 end) as SameCode
   from Order P
   where P.OrderDate <= O.OrderDate
 ) rs

-- Cross Apply pour retrouver l'élément précédent
select o.*, prev.*
from Order o
cross apply
 (
   select top 1 *
   from Order P where P.OrderDate < O.OrderDate
   order by OrderDate DESC
 ) prev

Lectures
  •  "Taking a look at CROSS APPLY" est un excellent article avec plein de cas pratiques du Cross Apply. Les exemples sont d'ailleurs issus de cet article.
  • "Using CROSS APPLY" est un article de SqlTeam.
    Visiblement intéressant mais je n'ai pas poussé la lecture sur ce dernier. A noter qu'il utilise l'instruction ROW_NUMBER() sur les partitions SQL.

mercredi 26 mai 2010

LINQ: Placer 8 reines sur un échiquier (solution)

Faisant suite au précédent article concernant la résolution de puzzle et problèmes combinatoires, je me suis demandé comment résoudre le problème des 8 reines à l'aide de LinQ.

Le puzzle consiste à placer 8 reines sur un échiquier de telle façon qu'aucune d'entre-elles ne puisse être en position d'en capturer une autre.
Pour rappel, une reine peut se déplacer d'autant de case qu'elle le désire dans l'une des directions suivantes:

    * Horizontale
    * Verticale
    * Diagonales (les deux sens)


Pour résoudre le problème, il faut qu'une nouvelle reine à placer sur l'échiquier n'occupe pas une case sur la même ligne, même colonne, même diagonale qu'une des autres reines placées sur l'échiquier.

Principe de résolution
Pour résourdre ce problème il faut:
  1. Identifier, de façon simple, la position d'une reine à l'aide sur l'échiquier.
  2. Trouver un processus mathématique qui vérifie si deux reines sont sur une même ligne (ou colonne).
    Problème trivial.
  3. Trouve un processus mathématique qui vérifie si deux reines partages une des diagonales.
Pourquoi des processus mathématique?
Ayant la volonté de résoudre ce problème avec LinQ, l'utilisation de fonction mathématique correspond mieux à la philosophie de résolution (évitant ainsi l'utilisation de boucles/itérations ou tests en cascade).

Identification de la position d'une reine
Bien qu'il soit possible d'identifier la position d'une reine à l'aide d'une structure, cette option n'est pas très efficace car elle nécessite la manipulation d'une structure et la mise en place de double boucles, de vérifications plus poussées, etc.
Le code repris ci-dessous repris à titre de support ne sera donc pas utilisé.
struct QueenPos
{
    public int row; // 1 à 8
    public int column; // de 1 à 8
  
    public QueenPos( int iRow, int iCol ){
        row = iRow; column = iCol;
    }
};

public static void RunSnippet()
{
     QueenPos Queen1 = new QueenPos( 1, 5 );
}

Une alternative plus intéressante sur le plan mathématique étant la numérotation des cases (de 1 à 64) de l'échiquier. La position d'une reine est alors identifié à l'aide d'une valeur numérique UNIQUE de 1 à 64.
Puisqu'un échiquier est un carré de 8 par 8, il est possible de déduire la ligne et la colonne d'une reine à partir de sa position. Il est même possible de déduire la diagonale sur laquelle elle se trouve (mais on reparlera de cela plus loin).
Echiquer où chacune des cases est numérotée

Une reine placée en 3ième lignes, 4ième colonne portera la position 20.


Les positions possibles d'une reine (iQueenPos) peut donc être pris en charge par une simple boucle "For" ou une énumération de 1 à 64. Une approche idéale pour un traitement LinQ.

Position de la reine (ligne et colonne)
Puisque la position d'une reine(iQueenPos) varie de 1 à 64, il faut être capable de transformer cette valeur numérique en ligne et colonne.
Puisque l'échiquier est un carré parfait, la ligne et la colonne peuvent être retrouvé à l'aide de fonctions mathématiques.
/// <summary>
/// Return the Column where the Queen is placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The column number. Value between 1 and 8.</returns>private int QueenCol(int QueenPos) {           
     return ((QueenPos - 1) % 8) + 1;
}

/// <summary>
/// Return the Row where the Queen is placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The Row number. Value between 1 and 8.</returns>
private int QueenRow(int QueenPos)
{
    return ((QueenPos - 1) / 8) + 1;
}

Le test de ces fonctions produit le résultat suivant (avec le code de test repris ci-après).


// Code affichant le résultat des colonnes et lignes
// calculées pour chacune des positions possibles 
// d'une reine
//
//lst is a ListBoxControl
lst.Items.Add("--- Rows ------------------------");
for (int i = 1; i <= 64; i++)
{
    int iRow = QueenRow(i);
    s = s + iRow.ToString().PadLeft(2) + ",";
    if ((i % 8) == 0)
    {
        lst.Items.Add(s);
        s = "";
    }
}
lst.Items.Add(s);

lst.Items.Add("--- Columns --------------------");
for (int i = 1; i <= 64; i++)
{
    int iCol = QueenCol(i);

    s = s + iCol.ToString().PadLeft(2) + ",";
    if ((i % 8) == 0)
    {
        lst.Items.Add(s);
        s = "";
    }
}
lst.Items.Add(s);


Position de la reine (les diagonales)
Il est possible d'identifier la diagonale sur laquelle se trouve une reine à l'aide d'une simple opération mathématique.
/// <summary>
/// Identify the Diagonal (/) on which the Queen is Placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The diagonal number on which the queen is placed. Each diagonal has a unique number.</returns></returns>private int QueenDiag(int QueenPos) {
    return QueenRow(QueenPos) + QueenCol(QueenPos);
}

/// <summary>
/// Identify the Anti-Diagonal (\) on which the Queen is Placed
/// </summary>
/// <param name="QueenPos">The current position of the queen in the GameBoard (Cell 1 to 64)</param>
/// <returns>The anti-diagonal number on which the queen is placed. Each anti-diagonal has a unique number.</returns></returns>
private int QueenAntiDiag(int QueenPos)
{
    return QueenRow(QueenPos) - QueenCol(QueenPos);       
}

En utilisant une code similaire à "position Lignes/Colonnes de la reine" il est possible d'évaluer la valeur des diagonales (et anti-diagonales) pour chacune des positions possible d'une reine.

Ainsi donc, les reines en positions 15 et 57 se gênent l'une l'autre puisqu'elles partagent la même diagonal (la diagonale n° 9).

Quand deux reines se gênent t-elles?
Le test devient alors relativement simple.
Deux reines (Reine 1 en position newQueenPos, Reine 2 en position otherQueenPos ) se gênent si elles partagent la même colonne ou la même ligne ou la même diagonale ou la même anti-diagonale.
Ce qui produit le code suivant (ainsi que la routine de test pour N reines):
/// <summary>
/// Test if 2 queens will be killing each oter because of their positions on the Chessgame
/// </summary>
/// <param name="NewQueenPos">Position of the new Queen placed on the game board (Position to be tested against another queen)</param>
/// <param name="OtherQueenPos">Position of an existing queen.</param>
/// <returns>True if the 2 Queens kill each other.</returns>private bool KillingPosition(int newQueenPos, int otherQueenPos)
{
    // 2 Queens cannot be on the same row
    int Q1Row = QueenRow( newQueenPos );
    int Q2Row = QueenRow( otherQueenPos );
    if( Q1Row == Q2Row)
        return true;

    // 2 Queens Cannot be on the same column    
    int Q1Col = QueenCol( newQueenPos );
    int Q2Col = QueenCol( otherQueenPos );
    if( Q1Col == Q2Col )
        return true;

    // 2 Queens Cannot be on the same "/" diagonal 
    //    ((Q1Col + Q1Row) == (Q2Col + Q2Row))
if( QueenDiag( newQueenPos ) == QueenDiag( otherQueenPos ) ) 
return true;

    // 2 Queens Cannot be on the same "\" diagonal
    //   ((Q1Row - Q1Col) == (Q2Row - Q2Col))
if( QueenAntiDiag( newQueenPos ) == QueenAntiDiag( otherQueenPos ) ) 
return true;

    // The 2 queens will not kill each other.
    return false;
}

/// <summary>
/// Test a new queen placed on the board to check if she is about to be killed by any of the other queens already placed on the GameBoard
/// </summary>
/// <param name="newQueenPos">The Position of the New Queen to be placed on GameBoard</param>
/// <param name="otherQueensPos">The position of all the other queens already placed on the GameBoard</param>
/// <returns>True if the new queen placed at newQueenPos is killed by an existing queen placed on the GameBoard</returns>
private bool KillingPosition(int newQueenPos, int[] otherQueensPos) {
    foreach (int queenOnGameBoard in otherQueensPos)
        if( KillingPosition( newQueenPos, queenOnGameBoard ) )
            return true;
    return false;

}

Résolution du poblème?
Armé de tout ces éléments il est maintenant possible de résoudre ce problème à l'aide de LinQ.
var Solutions = 
    from Q1 in Enumerable.Range( 1, 64 )
    from Q2 in Enumerable.Range( 1, 64 ).Where( q2Value => !KillingPosition( q2Value, Q1 ) )
    from Q3 in Enumerable.Range(1, 64).Where(q3Value => !KillingPosition(q3Value, new int[] {Q1, Q2} ))
    from Q4 in Enumerable.Range(1, 64).Where(q4Value => !KillingPosition(q4Value, new int[] { Q1, Q2, Q3 }))
    from Q5 in Enumerable.Range(1, 64).Where(q5Value => !KillingPosition(q5Value, new int[] { Q1, Q2, Q3, Q4 }))
    from Q6 in Enumerable.Range(1, 64).Where(q6Value => !KillingPosition(q6Value, new int[] { Q1, Q2, Q3, Q4, Q5 }))
    from Q7 in Enumerable.Range(1, 64).Where(q7Value => !KillingPosition(q7Value, new int[] { Q1, Q2, Q3, Q4, Q5, Q6 }))
    from Q8 in Enumerable.Range(1, 64)
    where !KillingPosition( Q8, new int[]{Q1, Q2, Q3, Q4, Q5, Q6, Q7})
    select new int[]{ Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8 };

Par contre, contrairement à ce que je pensais, il n'y a pas que quelques solutions mes plusieurs dizaines de milliers (sans distinction des doublons).
J'ai donc interrompu l'exécution après 87.000 solutions et bricolé à la va-vite un petit code d'affichage.
A préciser, quand même, que je ne teste pas les doublons.
// LinQ expression (déjà présenté ci-dessus)
var Solutions = 
    from Q1 in Enumerable.Range( 1, 64 )
 ... ;

int iSolutionCount = 0;
// lst is a ListBoxControl display control
//   Each Solution is composed of an Array of int
foreach( var Solution in Solutions ){
    iSolutionCount++;
    // Display a solution every 500 solutions
    if (iSolutionCount > 10 )
        break;

    lst.Items.Add( String.Format("--- Solution #{0}", iSolutionCount ) );
    // Display the positsion of Queens
    foreach( int QueenPos in Solution.ToList() ){
        lst.Items.Add( String.Format( "   R: {0}, C: {1}. Cell: {2}", QueenRow( QueenPos ), QueenCol( QueenPos ), QueenPos ) );
    }
    // Display in a ChessBoard
    lst.Items.Add("Queens on GameBoard:");
    for (int row = 1; row <= 8; row++)
    {
        string s = row.ToString().PadLeft(2) + ": ";
        for (int col = 1; col <= 8; col++)
        {
            int iCurrentCell = (row-1)*8+col;
            if (Solution.Contains(iCurrentCell))
                s = s + " Q,";
            else
                s = s + "  ,";
        }
        lst.Items.Add(s);

    }
}

Il est intéressant de noter que le code d'affichage des solutions est plus long que l'expression LinQ permettant de les identifier :-)

mardi 25 mai 2010

Nouveauté du Débugger de Visual Studio 2010

Très chouette article de ScottGu's a propos des nouveautés apparues dans le Debugger de VS2010.
Hormis le "Pinned Data Tips" qui permet de garder visible les "Data Tips" durant une session de debbuging (Plus sympa que les watchs), je trouve particulièrement intéressant que ces informations soient disponibles après la session de debugging (la dernière valeur connue est consultable depuis l'éditeur après la session de débug :-) ).
Plus intéressant encore cette possibilité de sauvegarder les "Pinned Data Tips" (ex: pour les attacher à un Bug Report ou les passer à un collègue).

A noter également, la possibilité de regrouper des BreakPoints sous un même libellé.
Cela permet le filtrage et l'activation/désactivation rapide d'un groupe entier de BreakPoint.
Tout aussi intéressant que pour les "pinned data tips", il est également possible de sauver une liste de breakpoints dans un fichier xml. Option bien pratique pour documenter un bug report ou passer facilement le relai à un collègue.

lundi 24 mai 2010

Du retard à la lecture

Je crois que j'ai pris un peu de retard dans mes lectures.
Voila ce que j'ai en attente de lecture sur mes étagères.
Comme le dit si bien ma tendre épouse:
Ne t'inquiète pas, tu auras tout le temps pour les lires quand tu seras pensionné et qu'il n'y aura plus de livre papier.

Mes livres en attente de lecture.
Cliquer pour agrandir

dimanche 23 mai 2010

Les villages médiévaux des "prisonniers du temps"

Suite à la lecture (em mars 2010) des "Prisonniers du temps" de Michael Crichton, j'ai fais une petite recherche sur les noms des lieux repris dans le livre. C'est ainsi que j'ai appris que les villages et châteaux mentionnés existent encore aujourd'hui...
Voila de quoi planifier de chouettes vacances.

Ville médiéval de Sarlat
En Dordogne.

Villes de Beynac-et-Cazenac
La Dordogne (fleuve) servait de frontière militaire naturelle entre les français et les anglais.
Beynac, village pittoresque, était une place forte Française.
Au delà, sur la rive opposée, se trouve le chateau rival de Castelnaud (ancienne place forte anglaise).

vendredi 21 mai 2010

InterProcess communication - les messages windows

Parce qu'un petit rappel ne fait jamais de mal.
 
Parmi les procédés d'intercommunication, il y a l'envoi (et la capture) de message Windows.
Les messages Windows étant destiné à une fenêtre particulière (identifié par un handle) et composé d'une structure relativement simple (un WParam et un LParam qui sont des valeurs numériques).
Windows dispose déjà d'un grand nombre de messages, mais pour des besoins logiciels il peut être nécessaire de définir ses propres messages applicatifs.

Envoi de message personnalisés
Un message est identifier à l'aide d'une valeur numérique unique dans l'OS.
Autrement dit, les messages de manipulation des fenêtre est identique (même numéro) quel que soit l'application.

Il est également possible de définir ses propre messages utilisateurs.
Soit en désignant une valeur numérique arbitraire (WM_MON_MESSAGE_A_MOI : integer = WM_USER + 1;),
Soit en demandant au système d'exploitation de générer un numéro de message unique ( RegisterWindowMessage('WM_MESSAGE_ENVOYEUR'); )

Cet article présente un exemple d'implémentation de message personnalisé en Delphi.

WM_CopyData
Parmi tous les messages existant, il y WM_CopyData.
Ce message particulier (accompagné d'une structure  COPYDATASTRUCT) permet de transmettre des blocs de données entre applications (par l'intermédaire d'envoi de pointer/référence vers un buffer).

Plus d'information

jeudi 20 mai 2010

Google Font Directory

Google dispose d'un répertoire de quelques fonts open source (Cantarell, Cardo, Droid, etc).
Ces fonts sont d'ailleurs accessibles via fonts.googleapis.com sous forme de stylesheet.

Pour ceux qu'un peu d'html ne rebute pas, il est ainsi vraiment aisé (et facile) d'agrémenter son site Web ou blog avec ces nouvelles font.
Il suffit, à peu de choses près, d'ajouter une balise link de type stylesheet dans le header de la page.
Aller donc jeter un oeil sur la page "Getting Started" de Google, le résultat est quand même bluffant.

Capture graphique d'une des font disponibles (avec drop shadow)

mardi 18 mai 2010

ComOCom un émulateur NullModem et une solution de redirection de port COM sur Tcp/Ip

Le projet sourceforge Null-modem emulator
Le projet Null-modem emulator (com0com) est un driver windows (en kernel-mode) qui permet de créer et connecter des ports séries virtuels. Il est ainsi possible de créer un nombre illimité de paires de périphériques COM et de les connecter ensemble... permettant ainsi à des applications de communiquer ensembles (ex: un logiciel et un émulateur de robot).



ComOCom et COM port to TCP redirector
Cette page sur SourceForge  offre une description plus générale et référence également un lien vers COM port to TCP redirector, une solution s'appuyant sur ComOCom pour partager des port série à travers une connexion TCP/IP.

samedi 15 mai 2010

LINQ: Résolution de problèmes combinatoires et de puzzles

Résolution de problèmes combinatoires
Dans l'article "Solving Combinatory Problems with LINQ", Octavio Hernandez explique comment résoudre le problème combinatoire suivant:

"""
Trouver un nombre en 9 positions constitué des chiffres de 1 à 9 où chacun des chiffres n'apparait qu'une seule fois.
Le nombre doit également satisfaire au contraintes suivantes:
  • Le nombre doit être divisible par 9.
  • Si le chiffre le plus à droite est enlevé, le restant du nombre doit être divisible par 8.
  • Du nouveau nombre, si le chiffre le plus à droite est enlevé, le restant du nombre doit être divisible par 7
  • Et ainsi de suite en enlevant à chaque fois un chiffre supplémentaire.
    Le dernier chiffre restant étant inévitablement divisible par 1 """
La solution élégante étant la suivante:
int[] oneToNine = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// the query
var query = 
    from i1 in oneToNine
   from i2 in oneToNine
    where i2 != i1
       && (i1 * 10 + i2) % 2 == 0
    from i3 in oneToNine
    where i3 != i2 && i3 != i1
       && (i1 * 100 + i2 * 10 + i3) % 3 == 0
    from i4 in oneToNine
    where i4 != i3 && i4 != i2 && i4 != i1
       && (i1 * 1000 + i2 * 100 + i3 * 10 + i4) % 4 == 0
    from i5 in oneToNine
    where i5 != i4 && i5 != i3 && i5 != i2 && i5 != i1
       && (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) % 5 == 0
    from i6 in oneToNine
    where i6 != i5 && i6 != i4 && i6 != i3 && i6 != i2 && i6 != i1
       && (i1 * 100000 + i2 * 10000 + i3 * 1000 + i4 * 100 + i5 * 10 + i6) % 6 == 0
    from i7 in oneToNine
    where i7 != i6 && i7 != i5 && i7 != i4 && i7 != i3 && i7 != i2 && i7 != i1
       && (i1 * 1000000 + i2 * 100000 + i3 * 10000 + i4 * 1000 + i5 * 100 + i6 * 10 + i7) % 7 == 0
    from i8 in oneToNine
    where i8 != i7 && i8 != i6 && i8 != i5 && i8 != i4 && i8 != i3 && i8 != i2 && i8 != i1
       && (i1 * 10000000 + i2 * 1000000 + i3 * 100000 + i4 * 10000 + 
           i5 * 1000 + i6 * 100 + i7 * 10 + i8) % 8 == 0
    from i9 in oneToNine
    where i9 != i8 && i9 != i7 && i9 != i6 && i9 != i5 && i9 != i4 && i9 != i3 && i9 != i2 && i9 != i1
    let number = i1 * 100000000 +
                 i2 * 10000000 +
                 i3 * 1000000 +
                 i4 * 100000 +
                 i5 * 10000 +
                 i6 * 1000 +
                 i7 * 100 +
                 i8 * 10 +
                 i9 * 1
    where number % 9 == 0
    select number;

// run it!
foreach (int n in query)
    Console.WriteLine(n);

Article sur la résolution de puzzle à l'aide de LINQ
http://blogs.msdn.com/lukeh/archive/2007/03/19/using-linq-to-solve-puzzles.aspx

Un autre puzzle très intéressant est celui des balanciers.
Le but étant de maintenir un balancier complexe en équilibre en assignant correctement les poids de A à M.

Règles du puzzle:
  • Chaque pivot (sous-balance) doit être en équilibre.
  • Chaque lettre/poids doit avoir une valeur comprise entre 1 et 12.
Une petite explication:
  • Le pivot CD est en équilibre si: D = 5*C.
  • Le pivot G(CD) est en équilibre si: 3*G = 2 * (poids de CD) donc si  3*G = 2 * (C+D).
  • La branche de droite du pivot principal (ABCDGJK) est en équilibre si:
    2*J + 3*A+B = 1*K+2*(G+C+D)
  • Toutes les branches droite du pivot principal (ABCDGJK) sont en équilibres si:
    1*B = 4*A et
    1*D = 5*C et
    3*G = 2*(C+D) et
    2*J + 3*(A+B) = 1*K+2*(G+C+D)
La solution LinQ étant:
var solutions =
    // Branche droite
    /*  1*B = 4*A et
        1*D = 5*C et
        3*G = 2*(C+D) et
        2*J + 3*A+B = 1*K+2*(G+C+D) */    from a in Enumerable.Range(1, 13)
    join b in Enumerable.Range(1, 13) on 4 * a equals b
    from c in Enumerable.Range(1, 13)
    join d in Enumerable.Range(1, 13) on 5 * c equals d
    join g in Enumerable.Range(1, 13) on 2 * (c + d) equals 3 * g
    from j in Enumerable.Range(1, 13)
    join k in Enumerable.Range(1, 13) on (2 * j + 3 * (a + b)) - 2 * (g + c + d) equals k
    // Branche Gauche
    from f in Enumerable.Range(1, 13)
    join e in Enumerable.Range(1, 13) on 2 * f equals 3 * e
    from h in Enumerable.Range(1, 13)
    join i in Enumerable.Range(1, 13) on 3 * h - 2 * (e + f) equals 3 * i
    from l in Enumerable.Range(1, 13)
    join m in Enumerable.Range(1, 13) on h + i + e + f - l equals 4 * m
    where
       3 * (j + k + a + b + g + c + d) == 4 * (l + m + h + i + e + f)
    select new { a, b, c, d, e, f, g, h, i, j, k, l, m };

    // solutions.ToList().ForEach(solution => Console.WriteLine(solution));
    solutions.ToList().ForEach(solution => lst.Items.Add(solution));

Comme expliqué par l'auteur, le codage le plus simple est encore d'inclure toutes les conditions dans la clause where. Cependant, cela génère une exécution de la clause where 13^13 fois. Inutile de dire que cette option n'est pas optimale (voir article).
Par contre, il est possible d'éliminer des solutions plus tôt dans le processus en éludant les solutions impossibles à l'aide de jointures.

La résolution du Carré Magique de Dürer à l'aide de LINQ
Carré magique mentionné dans le roman "Le symbole perdu" de Dan Brown, il est visible sur la gravure la Mélancolie de Dürer (Wikipédia).
la Mélancolie de Dürer. Source: Blog de Eric Demey
Le carré magique est visible en haut à droite de la gravure (sous la cloche)

Carré magique. Source: Cours de mathématique de Xavier Hubaut

Les règles du carré magique de Dührer sont:
  1. Carré de 4 * 4 cases.
  2. La somme de chaque ligne, de chaque colonne et des diagonales est a chaque fois identique.
    Le nombre 34.
  3. L'année de conception 1514 est indiquée sur les deux cases centrales de la dernière ligne (A savoir, le chiffre 15 en position 2 et le chiffre 14 en position 3). 
  4. Chaque chiffre étant unique et compris entre 1 et 16 (inclus). 
La solution LinQ:
Variables de l'algorithme
 
private void button3_Click(object sender, EventArgs ea)
        {
            DateTime dtStart = new DateTime();
            dtStart = DateTime.Now;
            // lst is a ListBoxControl displaying the lines contained in Items.
            lst.Items.Add("Time Start: "+dtStart.ToLongTimeString() );
            const int MAX = 16;
            const int  SUM = 34;
            var Solutions =
                // Ligne 1
                from a in Enumerable.Range(1, MAX)
                from b in Enumerable.Range(1, MAX).Where(bValue => a + bValue < SUM) // Eliminate wrong combination as soon as possible
                from c in Enumerable.Range(1, MAX).Where( cValue => a+b+cValue < SUM ) // Eliminate wrong combination as soon as possible
                join d in Enumerable.Range(1, MAX) on a + b + c equals SUM-d
                // En ajoutant des contraintes sur les colonnes 2 & 3 maintenant, 
                //     on reduit déja au minimum les solutions disponibles (on connais déjà les valeurs 15 & 14)
                // Colonne 2
                from f in Enumerable.Range(1, MAX).Where(fValue => b+fValue+15 < SUM ) 
                join j in Enumerable.Range(1,MAX) on b+f+15 equals SUM-j 
                // Colonne 3
                from g in Enumerable.Range(1,MAX).Where( gValue => c+gValue+14 < SUM )
                join k in Enumerable.Range(1,MAX) on c+g+14 equals SUM-k

                // Ligne 4 (+ test 1iere Diagonale)
                from m in Enumerable.Range( 1, MAX ).Where( mValue => (mValue + 14 + 15 < SUM) && (mValue+j+g+d == SUM ) )
                join p in Enumerable.Range( 1, MAX ) on m+15+14 equals SUM-p

                // Colonne 1
                from e in Enumerable.Range( 1, MAX ).Where( eValue => eValue +a+m < SUM )
                join i in Enumerable.Range( 1, MAX ) on a+e+m equals SUM-i

                // Colonne 4
                from h in Enumerable.Range( 1, MAX ).Where( hValue => hValue+d+p < SUM )
                join l in Enumerable.Range( 1, MAX ) on d+h+p equals SUM-l

                where ( e+f+g+h == SUM ) && (i+j+k+l == SUM) && ( a+f+k+p == SUM ) && ( m+j+g+d == SUM ) && 
                      IsEachValueDifferent( a,b,c,d,e,f,g,h,i,j,k,l,m,p)
                select new { a, b, c, d, e, f, g, h, i, j, k, l, m, p };

            int iSolutionCount = 1;
            foreach (var Solution in Solutions) {
                lst.Items.Add("");
                lst.Items.Add( String.Format("A solution #{0}:", iSolutionCount++ ) );
                lst.Items.Add(Solution.a.ToString().PadLeft(2) + "|" + Solution.b.ToString().PadLeft(2) + "|" + Solution.c.ToString().PadLeft(2) + "|" + Solution.d.ToString().PadLeft(2) );
                lst.Items.Add("--+--+--+--");
                lst.Items.Add(Solution.e.ToString().PadLeft(2) + "|" + Solution.f.ToString().PadLeft(2) + "|" + Solution.g.ToString().PadLeft(2) + "|" + Solution.h.ToString().PadLeft(2));
                lst.Items.Add("--+--+--+--");
                lst.Items.Add(Solution.i.ToString().PadLeft(2) + "|" + Solution.j.ToString().PadLeft(2) + "|" + Solution.k.ToString().PadLeft(2) + "|" + Solution.l.ToString().PadLeft(2));
                lst.Items.Add("--+--+--+--");
                lst.Items.Add(Solution.m.ToString().PadLeft(2) + "|15|14|" + Solution.p.ToString().PadLeft(2));


            }

            DateTime dtEnd = new DateTime();
            dtEnd = DateTime.Now;
            TimeSpan dtCompute = dtEnd.Subtract(dtStart);
            lst.Items.Add("Compute Time: " + dtCompute.Seconds.ToString()+" s");
            

           // Solutions.ToList().ForEach(Solution => displaySolution( Solution ) );
        }

        /// <summary>
        /// Check that the value of each parameter is different from the other parameters of the function
        /// </summary>
        /// <returns>True if value of A is unique amoung the serie [b,c,d...m,p] and value of b unique amoung the serie [c,d,...m,p]</returns>
        Boolean IsEachValueDifferent(int a, int b, int c, int d, int e, int f, int g, int h, int i, int j, int k, int l, int m, int p) { 
            HashSet<int> aSet = new HashSet<int>();
            aSet.Add(a);
            if (aSet.Contains(b))
                return false;
            aSet.Add(b);
            if (aSet.Contains(c))
                return false;
            aSet.Add(c);
            if (aSet.Contains(d))
                return false;
            aSet.Add(d);
            if (aSet.Contains(e))
                return false;
            aSet.Add(e);
            if (aSet.Contains(f))
                return false;
            aSet.Add(f);
            if (aSet.Contains(g))
                return false;
            aSet.Add(g);
            if (aSet.Contains(h))
                return false;
            aSet.Add(h);
            if (aSet.Contains(i))
                return false;
            aSet.Add(i);
            if (aSet.Contains(j))
                return false;
            aSet.Add(j);
            if (aSet.Contains(k))
                return false;
            aSet.Add(k);
            if (aSet.Contains(l))
                return false;
            aSet.Add(l);
            if (aSet.Contains(m))
                return false;
            aSet.Add(m);
            if (aSet.Contains(p))
                return false;
            aSet.Add(p);
            return true;
        }
Le carré de Durër ne manque pas de solution, il y en a 40 identifiée en 6 secondes.
La solution au problème est également abordée sur le blog de Octavio Hernández Leal (en espagnol).


Placer 8 reines sur un échiquier
Un autre petit puzzle amusant consiste à placer 8 reines sur un échiquier de telle façon qu'aucune d'entre-elles ne puisse être en position d'en capturer une autre.
Pour rappel, une reine peut se déplacer d'autant de case qu'elle le désire dans l'une des directions suivantes:
  • Horizontale
  • Verticale
  • Diagonales (les deux)
Source: www.ludi.com

Ce puzzle peut également être résolu à l'aide de LinQ et fera l'objet d'un article séparé.

lundi 10 mai 2010

DB4O - Un système de persistance d'objet pour C#

Voici encore un sous projet de "Mono Project". Cette fois, au lieu de s'attaquer à Windows Communication Framework (projet Olive), le projet dbo4 s'attarde sur la persistance des objets.

db4o est un système de persistance (sauvegarde sous dans un fichier ou flux) non intrusif permettant de stocker n'importe quel object complexe en une ligne de commande.
Lorsqu'un objet est stocké, le diagramme des classes de l'application est analysé et ajusté en temps réel.
La fonctionnalité d'interrogation des objets (Object-oriented querying) est assuré via Native Queries (NQ).
Il est possible de faire des requêtes sur la DB en utilisant la syntaxe et la sémantique .Net (concept similaire a LINQ/DLINQ) ou encore le concept Query by Example (QBE) qui utilise des objets prototypes pour les faire requêtes.
db4o assure de hautes performance grâce à l'indexation de champs et en réduisant au minimum l'utilisation des redirection sur le-fichier-de-donnée-interne-de-la-DB.
db4o supporte les transactions ACID (Atomicité, Cohérence, Isolation, Durabilité), un mode "single-user embedded" et des accès Client/Server multi-transactionel.
db4o s'utilise localement ou via TCP, supporte la réplication orienté-objet et ObjectManager pour naviguer dans les fichiers de la DB... et plus encore

Voici un exemple de code issu du site du projet:
using System;
 
using Db4objects.Db4o;
 
public class Test {
 
    static string _file = "store.db4o";
 
    // A very basic db4o example that demonstrates
    // automatic schema generation and Query-By-Example
    public static void Main (string [] args)
    {
        using (IObjectContainer db = Db4oFactory.OpenFile (_file)) {
            db.Set (new Pilot ("Michael Schumacher", 101));
            db.Set (new Pilot ("Rubens Barrichello", 99));
            db.Commit ();
 
            IObjectSet pilots = db.Get (new Pilot(null, 101));
            foreach (Pilot p in pilots) {
                Console.WriteLine (p);
            }
        }
    }
}
 
public class Pilot {
 
    string _name;
    int _points;
 
    public Pilot (string name, int points)
    {
        _name = name;
        _points = points;
    }
 
    public override string ToString ()
    {
        return _name + "/" + _points;
    }
}