La Grande sfida MasterMind 2000

"la grande sfida software MASTERMIND 2000", indetta, da un gruppo di lettori del newgroup it.fan.dewdney - purtroppo defunto - Daniele, Emanuele, Luigi, Michele, Roberto e Tommaso, si è conclusa sabato 8 luglio 2000.

  • I concorrenti
  • La prova
  • I risultati
  • I premi
  • Il commento
  • Il regolamento

    • Hanno inviato in tempo utile il loro programma:

    1. Andrea Rimicci, arimicci@aritaly.com
      Programma: MMRimic.c - inviato il 13/6

    2. Stefano Crimì, stefano.CRIMI@imec.be
      Programma: MMCrimi.c - inviato il 21/6

    3. Tantris, di Catania tantris@tin.it
      Programma: MMTantr.c - inviato il 26/6

    4. Rste - Stefano Rocca, di Legnano, rste@nemo.it
      Programma: MMRSte.c - inviato il 29/6

    5. Roberto Corda, di Milano, roberto.corda@inferentia.it
      Programma: MMCorda.c - inviato il 29/6

    6. Luigi Giavazzi, gigi@cyberg.it
      Programma: MMGigi.c - inviato il 29/6

    7. Emanuele Cesena, di Piacenza, ecesena@penguinpowered.com
      Programma: MMCesena.c - inviato il 29/6

    8. Domenico \"Tdx\" Troiano, di Torino, tdx.vic@libero.it
      Programma: MMTdx.c - inviato il 30/6

    Nota: i programmi 5 e 6 si somigliano molto... ma non sono per niente uguali!

    La Repubblica, prima riga del primo articolo di prima pagina di sabato 8 luglio:

    ROMA - Fumo fuorilegge nei ristoranti

    da ci si deduce che le lettere 9, 19 e 29 sono, rispettivamente, "u", "e", "i" (tutte vocali) da cui - secondo il regolamento - si ottiene il seguente file dei numeri da trovare: 
    
59369
44779
82868
67216
22678
... (mind.txt)

    I risultati!

    1. Roberto Corda - MMCorda.out
      Risolti: 100; Mosse: 6; In totale: 625

Tempo impiegato: 177.517 sec 

Risolti in 4 mosse: 2
Risolti in 5 mosse: 12
Risolti in 6 mosse: 49
Risolti in 7 mosse: 34
Risolti in 8 mosse: 2
Risolti in 9 mosse: 1
    2. Stefano Crimì - MMCrimi.out
      Risolti: 100; Mosse: 7; In totale: 630

Tempo impiegato: 128.3 sec 

Risolti in 4 mosse: 2
Risolti in 5 mosse: 12
Risolti in 6 mosse: 48
Risolti in 7 mosse: 31
Risolti in 8 mosse: 6
Risolti in 9 mosse: 1
    3. Luigi Giavazzi - MMGigi.out
      Risolti: 100; Mosse: 7; In totale: 631

Tempo impiegato: 172.767 sec 

Risolti in 5 mosse: 18
Risolti in 6 mosse: 42
Risolti in 7 mosse: 31
Risolti in 8 mosse: 9
    4. Tantris - MMTantr.out
      Risolti: 100; Mosse: 6; In totale: 639

Tempo impiegato: 71.4333 sec

Risolti in 5 mosse: 10
Risolti in 6 mosse: 45
Risolti in 7 mosse: 41
Risolti in 8 mosse: 4
    5. Stefano Rocca - MMRSte.out
      Risolti: 100; Mosse: 7; In totale: 655

Tempo impiegato: 10.55 sec 

Risolti in 3 mosse: 1
Risolti in 4 mosse: 2
Risolti in 5 mosse: 10
Risolti in 6 mosse: 34
Risolti in 7 mosse: 37
Risolti in 8 mosse: 14
Risolti in 9 mosse: 1
Risolti in 10 mosse: 1
    6. Emanuele Cesena - MMCesena.out
      Risolti: 100; Mosse:  9; In totale: 660

Tempo impiegato: 210.767 sec 

Risolti in  4 mosse: 1
Risolti in  5 mosse: 10
Risolti in  6 mosse: 33
Risolti in  7 mosse: 41
Risolti in  8 mosse: 14
Risolti in  9 mosse: 1
    7. Andrea Rimicci - MMRimic.out
      Risolti: 100; Mosse: 6; In totale: 664

Tempo impiegato: 1.46667 sec 

Risolti in 4 mosse: 1
Risolti in 5 mosse: 11
Risolti in 6 mosse: 37
Risolti in 7 mosse: 30
Risolti in 8 mosse: 17
Risolti in 9 mosse: 3
Risolti in 10 mosse: 1
    8. Domenico \"Tdx\" Troiano - MMTdx.out
      Risolti: 100; Mosse: 33; In totale: 3034

Tempo impiegato: 1.23333 sec
    Nota tecnica: i risultati sopra esposti, si riferiscono ai programmi compilati con l'Apple MPW, ed eseguiti su un G4 Macintosh. Su altre piattaforme possono differire i tempi di esecuzione e - in particolare per i programmi 1, 3 e 6 - gli stessi risultati, dal momento che le serie casuali utilizzate possono cambiare (vedi anche la nota al regolamento). In ogni caso, come già appurato, con sequenze di soluzioni diverse, la stessa classifica potrebbe differire. I concorrenti concordano tutti comunque sulla pur non assoluta validità di quella qui esposta, e sul fatto che comunque il programma vincitore abbia meritato il titolo anche per costanza di risultati.

    I premi

  • Il prestigioso pollo di gomma in palio viene pertanto assegnato a Roberto Corda, da Milano, al quale viene anche riconosciuto il titolo di Maestro del MasterMind.

  • Polletto di gomma e titolo di Maestrino del MasterMind al secondo classificato, Stefano Crimì dalla Sicilia (?? - a meno di smentita dall'interessato...)

  • Premio speciale dell'amicizia a Luigi Giavazzi (pure lui di Milano?), senza la collaborazione del quale Roberto, come da sua ammissione, non avrebbe vinto il Pollo di gomma...

  • Premio per l'impegno a Tommaso aka Tantris da Catania, la cui buona volontà è stata determinante per la riuscita (che dite, lo si considera riuscito?) del concorso.

  • Gran premio anche a Stefano Rocca, da Legnano, per essere stato l'unico della categoria "veloci" (vedi commento) a inserirsi nel gruppo dei "lenti".

  • Premio per il superimpegno a Emanuele Cesena, da Piacenza, per aver scritto il programma di base, per aver concorso alla Grande Sfida, per essersi prestato a far da giudice e contemporanemante essersi anche "maturato".

  • Premio per l'efficienza ad Andrea Rimicci da non-so-dove, il cui programma, senza bisogno di formule particolari, è quello che evidentemente accoppia la capacità di risolvere i numeri MasterMind alla maggiore velocità.

  • Un premio anche a Domenico Troiano, da Torino, per aver scritto il programma, oltre che più veloce, sorprendentemente più breve. Peccato solamente che, non potendo considerare i risultati ottenuti nella loro pienezza, fosse di gran lunga meno efficiente degli altri.

    • Abbiamo finito con i premi? No, un momento... se mi permettete vorrei ricordare qualcun altro:

  • Un premio per chi, pur impegnandosi, ha finito col non consegnare il frutto della sua fatica. Almeno mezza dozzina quelli di cui sappiamo per certo; probabilmente molti altri. Il premio, per tutti loro, viene simbolicamente consegnato a chi si è esposto di più in questo ruolo, Sergio aka Roscio.

    •

    Un breve commento

    Per prima cosa vorrei notare come la combinazione estratta non sia stata molto favorevole. Quasi tutti i programi avevano dato risultati migliori con i files su cui erano stati testati. In particolare, il vincitore, Roberto Corda, era andato spesso attorno ai 610; per non parlare dei programmi della coppia di giudici (Tantris e Emanuele) che non erano mai scesi così in basso... quale miglior riprova della loro imparzialità! :-)
    Esaminando i sorgenti degli otto concorrenti, emerge che i programmi si possono dividere in due gruppi: i "veloci" (da 1 a 10 secondi), che sono 3, e i "lenti", da 1 minuto in su, i rimanenti. I "lenti" macinano una gran quantita' di dati per calcolare il loro tentativo; i veloci si basano (o dovrebbero basarsi) sull'ottimizzazione dell'algoritmo. La vittoria - seconod le regole così come sono state stilate, non poteva che andare a un programma "lento". Pur non disconoscendo il forse maggior valore di un algoritmo "ottimizzato" (come quello di Andrea Rimicci) , è anche vero, come faceva notare Luigi, che non è particolarmente diffiicile scrivere un algoritmo in grado di ottenere risultati nell'intervallo 650-675, ma per scendere al di sotto di questa media, ogni punto va "faticato".
    Gli autori dei programmi "lenti" scrivevano tutti su it.fan.dewdney: un'autentica fucina di talenti, visto che hanno monopolizzato la prima mezza classifica ;-) (bisogna dirlo a .mau. che ha avuto una gran fretta di sopprimere il newgroup); i "veloci" invece provengono da altri ng. Forse i dewdneysti sono stati favoriti dall'aver discusso tra loro.
    Ringrazio ancora una volta i partecipanti e a tutti (e anche ad altri, spero) do appuntamento per

    la grande sfida software 2001, prima del nuovo millennio

    Quale sarà? Staremo a vedere..

    Regolamento


  • In cosa consiste la sfida.
    Dato un programma, scritto in Ansi C, che legge sequenzialmente da un file di testo 100 numeri di cinque cifre ciascuno, bisogna completarlo scrivendo la funzione che , facendo uso delle regole del MasterMind, riesca a indovinare esattamente tali cifre nel minor numero di tentativi possibile.

  • Quali sono le regole del MasterMind?
    A ogni tentativo viene proposto un numero composto da altrettante cifre di quello da indovinare, fino a ché non coincida con quest'ultimo. I dati di cui il programma dovrà essere a conoscenza, per calcolare tale numero, sono due:
    a) il numero di cifre "giuste" al posto "giusto",
    b) il numero di cifre "giuste" al posto sbagliato.
    Esempio:
    se il numero da indovinare fosse 84542 e il numero di prova 47236, il risultato sarebbe 0-2, cioè nessuna cifra al posto giusto, ma due cifre (il 4 e il 2) nel posto sbagliato; se il tentativo fosse stato 71443, il risultato sarebbe invece 1-1, cioè una cifra giusta al posto giusto (il 4 in quarta posizione) e una giusta al posto sbagliato (il 4 in terza posizione).

  • Dove si trova il programma da completare?
     Cliccando su questo link troverai lo schema da completare.
    Ogni concorrente potrà aggiungere allo schema proposto tutte le variabili (globali o locali) e le funzioni che gli saranno utili; per trovare la soluzione - pena immediata squalifica - deve fare uso eclusivamente dei dati che vengono passati alla funzione Punta , e cioè:
    - il puntatore ai numeri da usare per il confronto con la stringa da indovinare;
    - il numero delle cifre esatte nell'ultimo confronto;
    - il numero delle cifre indovinate, ma nel posto sbagliato, nell'ultimo confronto;
    - il numero di tentativi finora effettuati (se è uguale a 1, si tratta del primo tentativo per quella singola cifra).

  • A chi bisogna inviare i programmi concorrenti?
    I programmi, esclusivamente sotto forma di sorgente C, vanno inviati, entro la mezzanotte del 30 giugno 2000 al seguente doppio indirizzo:
    tantris@tin.it, ecesena@penguinpowered.com
    Perché un indirizzo doppio?
    Probabilmente i due "giudici ", i quali s'impegnano solennemente a non leggere i sorgenti ricevuti prima del termine di scadenza, vorranno anche concorrere. In questo modo ognuno dei due è tenuto a rispettare i termini previsti, al pari di ogni altro concorrente.

  • Che ne sarà dei programmi?
    I programmi pervenuti, pur restando proprietà intellettuale dell'autore, verranno tutti pubblicati - subito dopo la data di scadenza del concorso - su questa pagina web, corredato ognuno di nome, indirizzo e-mail (tranne indicazione contraria) del concorrente e, a prova effettuata, del risultato conseguito, a disposizione di chi volesse studiare le linee guida di programmazione da cui sono stati ispirati.

  • Come verranno scelti i numeri da indovinare?
     Il file con i cento numeri da indovinare, mind.txt verrà scritto da questo semplice programmino. Nella 15ma riga,

    srand('X'*'X'*'X');

    si sostituiranno le 'X' con i caratteri 9, 19 e 29 del testo (titolo escluso) del primo articolo di prima pagina del quotidiano "La Repubblica" di sabato 8 luglio (in genere, l'editoriale).
    Esempio:
    sulla Repubblica di lunedì 15 maggio questo testo è il seguente:

    BRUXELLES - La corsa europea all'Umts - la nuova tecnologia...

    da cui si ottiene questa riga:

    srand('S'*'s'*' ');

    (Il 29simo carattere è uno spazio).

    Come si può constatare, con tali dati il programma dà questa seguenza:

    94391
    50688
    35581
    40583
    58031
    21325
    95902
    00818
    88987 ... (et cetera) (vedi però le annotazioni)

    Perché un sistema così "barocco"?
    Affinché ognuno possa autonominarsi giudice e ripetere la prova e, soprattutto, non sia possibile conoscere in anticipo i numeri su cui verrà effettuata la prova.
    Per un eventuale spareggio, si farà ricorso ai caratteri immediatamente successivi; se per un qualsiasi motivo il giornale quel giorno non dovesse essere pubblicato, si utilizzerà il primo numero utile immediatamente successivo.

  • Cosa tocca al vincitore?
     A colui il cui programma, nel tempo massimo di 15 minuti, risolverà i 100 problemi nel minor numero di tentativi - in caso di parità spareggio, secondo le regole su illustrate - andrà fama imperitura, il titolo di Maestro del MasterMind e, forse, anche - non appena qualcuno lo mette a disposizione - un bel pollo di gomma, con o senza carrucola incorporata.


    • Annotazioni del 24/6

    1. Come ci ha fatto notare Roscio, in alcune implementazioni non si ottengono gli stessi risultati dalla funzione rand(). Se non ci fosse perciò coincidenza fra l'esempio sopradescritto e i risultati ottenuti, bisogna fare riferimento alle funzioni ansi rand() e srand(), così come ci sono state "illustrate" da Roberto: 
       int rand( )
{
next = next * 1103515245 + 12345;
return ((next >>16) & 32767);
}
void srand (Seed)


unsigned 
int Seed;
{
next = Seed;
}

      ed implementate dallo stesso Roscio in una versione alternativa del programmino generatore di problemi (vedi qui), che consigliamo di usare, previa verifica della sequenza d'esempio, a chi volesse ripetere la disfida sul proprio computer.

    2. Poiché, per motivi di "trasparenza", è preferibile che le prove siano ripetibili, si richiede che i programmi che dovessero fare uso di numeri casuali abbiano un'inizializzazione fissa, possibilmente scelta dall'autore oppure assegnata d'ufficio, entro e non dopo la mezzanotte del 7 luglio. Per le sequenze casuali il riferimento è sempre alla funzione rand() come sopra descritta.

    Torna alla Home page