Fast Compo Code LTP3 By Ze Killer,HouHouHouTiGrouTiGrou and ChoJin

Bon, je vais tenter d'expliquer notre methode.
Soyez indulgent car je n'ai pas encore recuper� le source car nous
avons cod� sur la machine de tigrou, et je n'ai pas pens� � prendre
le source.Donc je fais ca de memoire et plusieurs semaine apres
� la demande de skal.

Notre approche a �t� une approche de precalcule (precalcul fait
en fait � la main avec un editeur cod� en delphi par ZeKiller,
en plus de nous 3 qui avons chercher les meilleurs coup, on a eu
l'aide de Luna et Demnia que nous remercions d'ailleur , qui se
sont amus�es sur cette editeur pendant un certain temps, ou
plutot un temps certain je devrais dire :o)) )

Donc en fait, toute la subtilit� de l'algo consistait � trouver
un moyen de compresser les tables de solutions.

Bon tout d'abord y'avait un truc tres simple � voir: il n'y avait
en fait que 9 cas possibles (16 pieces 0 et 0 piece 1, 15 pieces 0 et
1 piece 1 ... etc .. jusqu'a 8 pieces 0 et 8 pieces 1); les autres
combinaisons pouvant se deduire de celles la en realisant tout
simplement une symetrie selon l'axe des Y ou des X au choix.

Mais ceci ne suffisait pas,malheureusement il ne suffisait pas
de faire un tableau de bits du style : bit=0 => trou, bit=1=>piece
car il fallait aussi leur donner un numero selon la chaine pass�.
Donc apres reflexion nous avons trouver cela:
nous avons 2 types de pieces qui peuvent tourner sur eux meme donc
cela nous donne 4 cas:
$        $*
**      **
*

$      $*
**       **
*

Pour placer une piece sur le tableau il nous suffit donc de savoir
quelle cas de piece nous devons placer et la position d'une des cases
occup�es par cette piece(les autres se deduisant grace � la forme
de la piece), nous avons donc choisi pour chaque cas un point de
controle de cette piece
exemple: $*
         **
'$' represente le point de controle, c'est donc la position de ce
point de controle que l'on enregistrera dans nos tables de precalculs

Donc voici comment on lit nos tables:
le premier bit de la table represente la case de la grille en haut �
gauche.

On lit bit par bit:
       - Si le bit=0 alors cela veut dire qu'il y a un trou donc
         on passe � la case suivante dans la grille
       - si bit=1 alors il y a une place, dans ce cas la on lit les
         deux bits suivant pr connaitre le cas de la piece � placer
         (souvenez vous qu'il y a 4 cas possible donc)
        00b=piece type 0 / pas de rotation
        01b=piece type 0 / rotation
        10b=piece de type 1 / pas de rotation
        11b=piece de type 1 / rotation

       Selon le type de piece On cherche dans la chaine d'init une
       piece de se type pour en deduire le numero de piece puis
       on 'raye' cette piece de la liste afin de ne pas la reutiliser
       apres.

       Donc maintenant on affiche � la case courante de la grille
       ce numero, mais la il faut se rappeler que quand le bit de la
       table dit qu'il y a une piece cela veut dire que c'est notre
       point de controle qui se trouve � cette endroit et donc il faut
       placer les autres cases occup�es par cette piece.

       Puis une fois la piece placer on incremente la case courante
       de la grille jusqu'a la prochaine case libre ( qui n'a donc
       pas deja ete prise par une piece placer precedement).
       Puis on continue � lire la table de precalcule

Voila en gros l'id�e donc on va resumer la situation:
On a une table de precalcule ou si le bit est a zero alors il y a un
trou, et si le bit est � 1 alors on lit les deux bits suivants
qui donne le type et la rotation de la piece.

Donc au debut du programme on compte le nombre de piece de type 0
et de type 1. ce qui nous donne la table de precalc � utiser
et si il y a plus de piece de type 1 alors il ne faudra pas oublier
de faire une symetrie de la table apres affichage afin d'inverser les
pieces.

En Conclusion:
Sur les 16pieces donn�es on ne peut en placer que 14 dans le meilleur
des cas et donc la table aura pour taille au maximum:
14*3bits+8*1bit (8*1 car il y aura 8 trous et 1trou = 1bits dans la
table, et 14*3 car 1piece prend 3bits dans la table)
donc taille_max=14*3+8*1=50bits=6 octets et 2 bits.
En imaginant (evidement ce n'est pas possible) que on arrive � placer
dans tous les cas 14 pieces (et donc d'avoir toujours une table de
precalcul de la taille maximum) cela nous donne:
50*9cas=450bits=56 octets et 2 bits.
Evidement ceci est une grosse majoration, mais donne une bonne idee
du niveau de compression de la table.

Bon voila, je crois que y'a pas grand chose � dire de plus.A part
que le probleme de cette methode est que la lecture de la table
en plutot gourmande en taille de code, mais notre derniere version
du programme (non distribu� � cause d'un bug tout mystiq,et on etait
trop fatigu� pour debuger) on est arriv�e � un programme d'une
taille inferieur � 300octets.
Lavantage de l'approche par table, est qu'une fois les bonnes tables
trouv�es la solution est instann�e et surtout elle donne aussi la
meilleur.
Mais je suis certain (j'attend impatiement que skal se prenche sur le
probleme) qu'il est possible de trouver une approche heuristique tres
performante et tres petite.Faudrait y reflechir, mais bon, faut
vraiment aimer ce prendre la tete :o)


Bon Il est clair que notre algo est un peu complexe et tres chiant �
expliquer dans un file.
Donc pour toute question vous pouvez me joindre sur #demofr en ircnet
ou me mailler : [email protected]

Voila Merci d'avoir eu la patience de lire :o)
ChoJin