Esercitazione del 17-10-03

Il gioco del "Master Mind"

Nel gioco del "Master Mind" l'obiettivo è scoprire un codice segreto.

• Il codice è formato da NCIFRE numero di cifre (ad esempio 5)
• Le cifre possono essere ripetute
• Bisogna trovare il codice segreto nel minor numero di tentativi
• Un tentativo è un codice dello stesso numero di cifre
• Il direttore di gioco (o il computer) che sa il codice segreto risponde indicando:
  • quanti "strike" (cifre giuste al posto giusto) sono presenti nel tentativo
  • e quanro "ball" (cifre giuste al posto sbagliato) sono presenti nel tentativo
• si vince quando il numero di strike è NCIFRE

Come implementare il "direttore di gioco" (che sa il codice segreto)

Strutture dati necessarie

• il codice segreto è memorizzato come un array di interi, una cifra per posizione
• il tentativo viene letto come un intero decimale e poi spacchettato in un array di cifre
• per evitare di contare una cifra più di una volta usiamo un array per ricordare se una cifra del codice è stata già trovata nel tentativo
• leggiamo il tentativo da input come un numero decimale
• ci servono alcune variabili di appoggio: tentativo, strike, ball, qualche contatore

Pseudocodice

1. definire e inizializzare le variabili
2. definire il codice segreto
3. ripetere:
   1. inizializzare le risposte strike e ball e il vettore trovata
   2. leggere un tentativo
   3. spacchettare il numero nel vettore cifra
   4. contare il numero di strike
   5. contare il numero di ball
   6. rispondere stampando numero di strike e ball
   7. continuare il ciclo se il numero di strike è diverso da NCIFRE

Per contare il numero di strike:

1. per ogni cifra del codice
   1. se la cifra corrispondente del tentativo è uguale
      1. incremento il numero di strike
      2. marco la cifra come usata

Per contare il numero di ball:

1. per ogni cifra del tentativo non usata in uno strike
   1. per ogni cifra del codice
      1. se le due cifre corrispondono e la cifra del codice non è usata
         1. incremento il numero di ball
         2. marco la cifra del codice come usata
         3. esco dal ciclo interno e passo alla prossima cifra del tentativo

Codice

#include <stdio.h>

#define NCIFRE 5
#define TRUE 1
#define FALSE 0

int main() {
   int strike,ball,i,j,tentativo;
   int codice[NCIFRE] = {1, 3, 7, 3, 2}; // codice da indovinare
   int cifra[NCIFRE] = { 0 };    // cifre del tentativo corrente
   int usata[NCIFRE] = { 0 };    // serve a ricordare se una cifra del codice è stata già usata (in genere)
   int usata_s[NCIFRE] = { 0 };    // serve a ricordare se una cifra del tentativo è stata già usata per uno strike

   do {
      // re-inizializzazione di strike, ball e usata
      strike=0;
      ball=0;
      for (i=0 ; i<NCIFRE ; i++) {
         usata[i] = FALSE;
         usata_s[i] = FALSE;
      }

      // leggo il tentativo
      scanf("%d",&tentativo);

      // estraggo le cifre dal tentativo a partire dalle unità
      for (i=NCIFRE-1 ; i>=0 ; i--) {
         cifra[i] = tentativo % 10;   // la cifra è resto della divisione per 10
         tentativo /= 10;      // divisione intera di tentativo per 10
      }

      // conto gli strike
      for (i=0 ; i<NCIFRE ; i++) 
         if (cifra[i] == codice[i]) {
            strike++;
            usata[i] = TRUE;   // marco la cifra del codice come usata
            usata_s[i] = TRUE;   // marco la cifra del tentativo come usata per uno strike
         }

      // conto i balls   
      for (i=0 ; i<NCIFRE ; i++)    // ciclo sulle cifre del tentativo non usate
         if (!usata_s[i])
            for (j=0 ; j<NCIFRE ; j++) // ciclo sulle cifre del codice non usate
               if (cifra[i] == codice[j] && !usata[j]) {
                  ball++;
                  usata[j] = TRUE;  // marco la cifra del codice come usata
                  // esco dal ciclo che conta i ball
                  // e passo alla prossima cifra del tentativo
                  break;       
               }

      // stampo il risultato
      printf("%d %d\n",strike,ball);
   } while (strike != NCIFRE);

   return 0;
}

-- AndreaSterbini - 17 Oct 2003

Mi segnala DaniloRossi che anche la versione 2 del programma soffre di un leggero bug.

Se una delle cifre del codice appare nel tentativo sia come strike che come ball questa versione la conta due volte.

Dobbiamo:

• ricordare se una cifra del codice è stata già usata
• ma anche ricordare se una cifra del tentativo è stata già usata come strike

Ho corretto il codice.

-- AndreaSterbini - 27 Oct 2003