Une sorte de Tetris
Comment remplir une zone de formes basiques au hasard en optimisant le placement ?
En partant d’une grille de 10 sur 10, si la case est vide j’écris un 0 sinon un 1.
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
On peut utiliser un tableau de tableaux, mais je vais utiliser une astuce de 0 et 1.
Première expérimentation simple avec des pièces d’une ligne
Je veux remplir celle-ci avec des barres horizontales de longueurs variables entre 3 et 5 cases en interdisant les superpositions, voici mes barres :
111
1111
11111
Des 0 et des 1
Un peu de culture 🙂
Les ordinateurs utilisent des 0 et des 1 pour faire des opérations, on parle de langage binaire. Si vous avez déjà manipulé un cadenas à chiffres de 0 à 9, en base 10 on compte comme ceci :
000 -> 0
001 -> 1
002 -> 2
…
999 -> 999
C’est simple pour nous, il s’agit de notre système décimal. Avec un cadenas à trois molettes, on a 1000 combinaisons (10 puissance 3).
En binaire, on compte ainsi :
000 -> 0
001 -> 1
010 -> 2
011 -> 3
100 -> 4
101 -> 5
110 -> 6
111 -> 7
Ce qui donne 8 combinaisons (2 puissance 3).
Les zéros « devant » sont facultatifs.
Avec un peu de JavaScript, on peut écrire un binaire en décimal et un décimal en binaire, une gymnastique entre des chiffres et des lettres chaînes de caractères 0 et 1.
(7).toString(2) // 111
parseInt('111',2) // 7
OR | et XOR ^
Supposons que les cases d’une ligne soient occupées ainsi.
0111000111
Je veux placer une pièce de trois cases pour obtenir
0111111111
0111000111 // ma ligne
// en prenant une pièce de trois cases
00000000111 // ma pièce superposée, x = 0
00000001110 // ma pièce superposée, x = 1
00000011100 // ma pièce superposée, x = 2
00000111000 // ma pièce OK
00001110000 // ma pièce superposée
00011100000 // ma pièce superposée
00111000000 // ma pièce superposée
01110000000 // ma pièce superposée
11100000000 // ma pièce superposée
Décalage
Pour décaler d’un zéro vers la gauche, on utilise cet opérateur :
(1 << 3).toString(2) // 1 -> 1000
En boucle
Si je fais un OR et un XOR entre la ligne et la pièce et que le résultat est identique, la place est libre !
var ligneInt = parseInt("0111000111",2);
var piece = "111";
var pieceInt = parseInt(piece,2);
for(var i = 0;i<(10-piece.length);i++){
var pieceInti = pieceInt << i;
console.log(i,"la pièce",(pieceInti).toString(2));
console.log(i,"le |",(pieceInti | ligneInt).toString(2));
console.log(i,"le ^",(pieceInti ^ ligneInt).toString(2));
if((pieceInti | ligneInt) === (pieceInti ^ ligneInt)){
console.log('place disponible en',i);
}
}
Ouvrir le codepen et appuyer sur le bouton console en bas à gauche :
See the Pen or & xor by Benoît Wimart (@benoitwimart) on CodePen.
Avec du HTML et CSS
J’ai commenté le code sur codepen.
J’ai aussi inversé le x par rapport à l’exemple précédent.
See the Pen or & xor + html / css / grid by Benoît Wimart (@benoitwimart) on CodePen.
Avec des pièces plus complexes que des lignes
Ça se complique dans la logique et l’algorithme, mais que le code change peu.
Les pièces sont désormais des tableaux de « lignes ».
['10',
'10',
'11'] // dessine un L
On fera une boucle sur chaque ligne de la pièce pour tester si la place est disponible.
Si les places sont disponibles, on mettra à jour le tableau « ligne » et on dessinera nos pièces avec un peu de CSS (nb : la méthode de dessin ne permet pas de faire des motifs avec des trous comme « 1001 »).
See the Pen or & xor + html / css / grid (e02) by Benoît Wimart (@benoitwimart) on CodePen.
La méthode de dessin via CSS étant rapide, mais avec ses limites, on pourrait poursuivre l’exercice avec des formes SVG plus complexes.