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