-= report de la fastcode LTPIII =-

Soyez indulgents, j'ecris ce texte en meme temps que je 
decouvre et teste les prods, alors si tout se passe bien, 
le resultat final se trouve a la fin du texte :)
Pour l'instant, je vais a l'essentiel, mais une version
plus complete suivra (result2.txt). De toute facon,
rien n'est encore definitif et vous pouvez m'envoyer
vos remarques a skal@planet-d.

---------------
--= Entries =--
---------------

|3223: S!lver & Intense    -> 23 bytes (wow:)
|simple: cyg+mez           -> 144 bytes
|hulud:  hulud/DM          -> 342 bytes        +sources
|339v10: Skytech pool      -> 339 bytes 
|339v10_v2:                -> 339 bytes aussi.
|sh: sed+hulud             -> 407 bytes        +sources
|sed:        (replay2.com) -> 415 bytes        +sources
|arfff:                    -> 5307 bytes       +sources
|arf2:                     -> 12971 bytes      +sources
|arf: soda+gizmo, en C.    -> 28672 bytes      +sources

------------------------------------------
--= Chaines de test: 1010110110111011  =--
------------------------------------------

Choisie au par Monsieur SRandom() himself...

---------------------------------------------
--= Remarques particulieres a chaque prog =--
---------------------------------------------

3223: finement joue' :). 
-------------------------------
339v10.com: 
339v12.com:   meme output pour les deux versions. [precalc]
              Apparement, le bug annonce' n'intervient pas avec ce
              choix d'input. veinard, va :)
-------------------------------
arf: bug? -> "This program cannot be run in DOS mode" ne peut
             decemment *pas* etre considere' comme un output valide :))
arf2:
arfff: meme ouput que arf2. Dans le doute je me base sur cette version-la.
              Ces trois entries ont le meme code source (en c) et
              sont apparament le fruit d'optims en seconde passe
              a partir de la compil. Le prog cherche a placer
              (recursivement) les pieces au fur et a mesure.
              La taille finale est somme toute assez penalisante...
-------------------------------
hulud: Il faut arreter le prog au bout d'un temps raisonnable (5mins)
       et il donne alors son meilleur resultat courant.

	Probleme!!!! le type des pieces est inverse' !!!!!
        Je met ca sur le compte de la fatigue, et de toute facon,
        meme fixe' (ligne13), ca ne change ni la taille du code,
        ni le resultat, ni le classement :)

-------------------------------
sed:   Met longtemps a calculer la solution par inspection,
       mais je decide que ca reste (encore) raisonnable.
-------------------------------        
sh:    precalc 
-------------------------------
simple: a default de source, et au vue du nom et de la taille de l'exe,
        je suppose qu'il doit juste placer les pieces au fur et a
        mesure



-----------------------
--=   Results/score =--
-----------------------

3223:  64 voids -> 3200 + code 23         -> 3223
arfff: 16 voids -> 800 + code 5307        -> 6107

339v10: 8 voids -> 400 + code 339         -> 739

simple: 16 voids -> 800 + code 144        -> 944
sh:        8 voids -> 400 + code 407      -> 807

sed:        8 voids -> 400 + code 415     -> 815

[hulud: 8 voids -> 400 + code 342         -> 742 ]

Il semble donc que l'optimal etait donc de 8 trous, mais meme
avec 16 trous, <simple> s'en sort pas mal, a cause de la taille
du code


------------------
--= Classement =--
------------------

339v10:        739
[hulud]:       742
sed+hulud:     807
sed:           815
simple:        944
3223:          3223
arfff:         6107


--------------------
--= Commentaires =--
--------------------

Rappel des faits:

	Voici quand meme un resume' rapide du probleme:

	- il fallait placer dans une grille 8x8, sans deborder, un
	maximum de pieces de Tetris de 2 types:

                        *                        *
		type 0: **              type 1: **
                         *                      *

        choisies parmi un nombre fixe' en entree. Les rotations etaient
        valables aussi. Le score final tenait compte de la taille de
        l'exe (1 pt de penalite' par byte) et des trous laisse' dans
        la solution presentee (1 trou = 50 pts de penalite). Etait
        gagnant celui qui avait le plus petit score.

I/O:
           Le format de la chaine d'entree pouvait paraitre bizarre,
        alors que j'aurais pu simplement me contenter de donner
        (en hexa sur 1 char), le nombre maximal de pieces de type 0 
        a utiliser, par exemple...
           En fait, c'etait simplement pour faciliter le parsing
        au cas ou certains voulaient utiliser l'algo (simpliste?)
        qui consiste a placer les pieces au mieux au fur et a
        mesure qu'elles sont lues ("a la tetris", donc. C'est ce
        que font Soda&gizmo). Pour les autres, ca ne changait pas
        grand chose, il suffisait de compter les '0'...
           Pour le format de sortie, il y avait eventuellement
        un probleme de conversion vers un affichage en hexa,
        mais rien de bien mechant. En tout cas, rien qu'une
        chtite table de conversion finale ou de choix sioux
        du format interne ne puisse venir a bout :)


Choix de la chaine d'input: 

            Aucune des prods n'est random, i.e. elles
        donnent toutes le meme resultat pour une chaine donnee (sauf
        celle de Hulud qui donne un premier choix et essaie ensuite
        de l'ameliorer, mais en un temps redibitoire...). Un seul run
        des programme suffit donc.
            Il peut paraitre dommage de ne les faire tourner qu'avec
        *une* seule chaine alors que vous vous etiez casse' a envisager
        *toutes* les 16 (/8?) combinaisons possible. Mais ca fait partie 
        du jeu :) De plus, j'aurai bien voulu faire une sorte de moyenne
        ponderee des resultats des 16 cas possibles (car certains etaient
        plus dur a optimiser que d'autres), mais ca compliquait
        l'evaluation, alors mieux valait en rester a la regle initiale 
        qui precisait qu'une seule et unique chaine serait utilisee
        (apres tirage au hasard, donc). Le sort a decide' que ce
        serait le cas 5/11 pour les types de piece 0/1. Ainsi soit-il :)


Methodes:

           Alors bien sur, tout le piment residait dans l'occurence
        de deux methodes pour arriver au resultat: soit inspecter
        toutes les configs possibles en un temps raisonnable;
        soit precalculer les solutions optimales et se decarcasser
        pour les packer ensuite (cependant, cette solution ne
        faisait pas l'economie de la methode #1 quant au precalc, hehe:)
           C'est assez heureux qu'en fin de compte la ponderation
        du score n'ait pas privilegie' honteusement l'une ou l'autre
        des methodes, car comme on peut le voir, la difference s'est 
        joue' a 3 points de difference au score final. Lucky strike :)

	[ ... a finir et completer...]

Speciales dedicaces:

        - a ce filou de X-man qui voulait concourir avec 16 executables
        differents. On se demande bien pourquoi :))

        - a Skytech qui m'a pondu l'editeur-de-config-qui-le-fait-mortel(tm)

        - et evidemment a tout ceux qui ont participe' :)


                                                Skal



===========================================================================
== "making of"
===========================================================================

 --= Output des differents progs =--

-=[3323]=-

--------
--------
--------
--------
--------
--------
--------
--------

-=[339v10]=-

CCEE-FF-
6CCEEBFF
66-8BBA-
-688BAA7
44855A77
14405572
11003322
-1033-2-

-=[arfff]=-

-034455-
00334455
0113BB--
11AA-BB-
-66AA---
66----9-
22778899
-2277889

-=[hulud]=-

03366-C-
003366CC
-0599DDC
-15599DD
11-577AA
12277AA-
224488BB
-4488BB-

-=[sed]=-

-DD9966-
DD996633
00-22334
10052244
1155774-
-158877A
BBCC88AA
-BBCC-A-

-=[sh]=-

D002244-
DD002244
9D-1133B
991133BB
-95577B-
-885577C
AA8866CC
-AA66-C-

-=[simple]=-

-113366-
113366--
-99BBAA-
99--BBAA
-887755-
--887755
-442200-
--442200


 --= Analyse des resultats =--

Voici le petit prog en C avec lequel j'ai verifie' que
les resultats etaient conformes:

//
//  proggy de check de la fastcode ltp3
//

#include <stdio.h>
#include <time.h>
#define OUT fprintf( stderr, 

   // stockage des pieces de base sur 24bits (3 lignes)

	// type 0
   // *   
   // **  = b00000010/00000011/00000001 = 0x010302
   //  *

   //  **
   // **  = b00000011 00000110 = 0x000603

	// type 1
   //  *
   // **  = b00000001 00000011 00000010 = 0x020301
   // *

   // **
   //  **  = b00000110 00000011 = 0x000306

unsigned int base[4] = { 0x010302, 0x000603, 0x020301, 0x000306 };
unsigned char tab[8][8], input[16];

int search( int t )
{
   int i,j, type;
   unsigned int cmp[8+1], line;
   OUT "searching for piece #%x, type %d...", t, input[t] );

   for( j=0; j<8; ++j ) 
   {
      cmp[j]=0;
      for( i=0; i<8; ++i ) cmp[j] |= (tab[j][i]==t) ? (0x80>>i) : 0;
   }
   cmp[8] = 0; // pad anti-overflow

   for( j=0; j<=6; ++j )
   {
      line = cmp[j] | (cmp[j+1]<<8) | (cmp[j+2]<<16); // retreives 3 lines
      type =-1;
      for( i=0; i<=6; ++i )
      {
         if ( line==base[0] || line==base[1] ) { type=0; break; }
         if ( line==base[2] || line==base[3] ) { type=1; break; }
         line = (line>>1) & 0x7f7f7f;
      }
      if ( type!=-1 )
      {
         OUT ".. found at position (%d,%d)\n", 6-i, j );
         return( type );
      }
   }
   OUT "...piece #%x unused\n", t );
   return( -1 );
}

main( int argc, char **argv )
{
   int i, j, c, n;
   int empty, unused, typea, typeb, typeA;

//////// tirage au hasard une chaine ////////

   if ( argc>1 && argv[1][0] == '-' )  
   {
      n = argv[1][1] - '0';
      srandom( time(NULL) );
      for( i=0; i<16; ++i )
      {
         if ( n ) { c = random() & 0x01; if ( c ) n--; }
         else c=0;
         OUT "%c", c ? '1' : '0' );
         input[i] = c;
      }
      OUT "\n" );
      exit(0);
   }

///////////////// analyse ///////////////////

   if ( argc>1 )   // chaine de reference
   {
      typeA = 0;
      for( i=0; i<16; ++i )
      {
         input[i] = argv[1][i] - '0';
         if ( !input[i] ) typeA++;
      }
   }

   OUT "Base string:" );
   for( i=0; i<16; ++i ) OUT "%c",input[i] + '0' );
   OUT "\nmax typeA:%d    max typeB:%d\n\n", typeA, 16-typeA );

   empty = 0;
   for( j=0; j<8; ++j )
   {
      for( i=0; i<8; ++i )
      {
         c = fgetc( stdin );
         if ( c>='0'&& c<='9' ) tab[j][i] = c - '0';
         else if ( c>='a' && c<='f' ) tab[j][i] = c - 'a' + 0x0a;
         else if ( c>='A' && c<='F' ) tab[j][i] = c - 'A' + 0x0a;
         else if ( c=='-' ) { tab[j][i] = 0xff; empty++; }
         else { 
Aieee:
            OUT "\n -- char %d/%d ->'%c' not permitted.\n", i,j,c ); 
            exit(1); 
         }
      }
      if ( fgetc( stdin ) != '\n' ) goto Aieee;
   }   

      // check correct use of input

   unused = typea = typeb = 0;
   for( i=0; i<16; ++i )
   {
      n = search( i );
      if ( n!=input[i] )
      {
         if ( n!=-1 )
         {
            OUT "invalid type (%d) for piece #%x\n", n, i );
            exit(1);
         }
         else unused++;
      }
      else if ( !n ) typea++;
      else typeb++;
   }
   OUT "type0:%d  type1:%d   unused:%d\n", typea, typeb, unused );

   if ( typea>typeA || typeb>16-typeA )
   {
      OUT "invalid use of input. limit reached.\n" );
      exit(1);
   }
   OUT "limits ok.\n" );
   OUT "\nempty:%d   -> score:%d\n", empty, empty*50 );
}