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.
------------------------------------------
--= 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
- 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)
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 );
}
