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 : chojin@skytech.org

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