[Algoritmi & C++] Algoritmo Mastermind

[Albi89]

Ciao a tutti!
Sto creando un semplice gioco del mastermind per tenermi in esercizio in vista dell'apertura della finestra d'esami.

Per i pochi che non conoscono questo gioco, consiste nell'indovinare un codice segreto: ad ogni turno, il giocatore compone un tentativo e l'altro (nel mio caso il computer) lo confronta con il codice segreto e compone un "feedback" composto dal numero di "cifre" (o pioli) corrette in posizione corretta e di cifre corrette ma in posizione errata.

Mentre la maggior parte degli algoritmi di cui ho avuto bisogno sono molto banali, quello per determinare le cifre corrette in posizione errata mi sta dando dei grattacapi.

Per iniziare, avevo adottato un algoritmo di questo tipo (sia N il numero richiesto):

1. Crea un array delle singole occorrenze numeriche nel codice segreto
2. Scorri gli elementi di questo array
'-> Confronta ogni elemento con tutti gli elementi del codice segreto
     '-> se gli elementi sono uguali e la posizione diversa, incrementa N

Questo algoritmo ha un chiaro problema: mettiamo il caso che il nostro codice segreto sia 2 4 5 2 e il tentativo del giocatore 2 2 2 2.
L'algoritmo dirà che sono presenti 2 pioli corretti in posizione errata (i due 2 "centrali").
Ma questo non è corretto! Infatti i 2 che servono a comporre il codice sono soltanto... due! E sono quelli già correttamente posizionati ai bordi.
Dunque l'algoritmo dovrebbe restituire un N uguale a 0.

Ho allora perfezionato l'algoritmo calcolando, anzitutto, per ogni singola occorrenza numerica il numero di volte che appare nel codice segreto (sia OCC_NUM), e dunque calcolando il numero di volte in cui il piolo appare, nel codice, in posizione corretta (sia NUM_FOUND).

Il valore massimo che potrà assumere il nostro caro N è dunque (OCC_NUM - NUM_FOUND), che chiameremo MAX.

Il mio nuovo algoritmo funziona dunque così:

1. Crea un array delle singole occorrenze numeriche nel codice segreto
2. Scorri gli elementi di questo array
|-> Calcola MAX per il valore corrente come spiegato sopra
'-> Confronta ogni elemento con tutti gli elementi del codice segreto
     '-> se gli elementi sono uguali e la posizione diversa, e inoltre
          N non è stato incrementato più di MAX volte per l'elemento 
          corrente, incrementa N

Purtroppo anche questo algoritmo, sebbene più affidabile, non funziona perfettamente in tutte le occasioni, e non riesco a capire se l'errore è concettuale o di implementazione.

Spero che qualcuno di voi mi sappia dare qualche dritta, in particolare sarei contento se qualcuno mi rassicurasse sulla correttezza dell'algoritmo per permettermi di concentrarmi solo sui dettagli dell'implementazione che potrebbe contenere degli errori: così lavoro "su due fronti" e mi trovo un po' in difficoltà.

Grazie a tutti per l'aiuto! =)

[DanieleC88]

Secondo me hai bisogno di ricordare anche le posizioni, metti il caso che la combinazione sia 2 4 5 2 e il tentativo sia 2 2 7 8, darebbe come risultato un piolo giusto e due mal posizionati, il che è evidentemente non corretto (ma il valore delle posizioni errate sarebbe ammissibile secondo il tuo algoritmo, perché non superiore a MAX).

Puoi quindi quindi usare magari un vettore che ricordi più di un dato (ad esempio due interi, il primo dei quali rappresenta il codice e il secondo la flag riconosciuto/non riconosciuto) e incrementare solo a seconda delle corrispondenze, o altrimenti inserire la combinazione in un dato come una lista e rimuovere prima gli elementi trovati nelle posizioni corrette, e contare tra gli elementi rimasti quelli contenuti nel tentativo (che, se presenti, avranno valori corretti con posizioni errate).

ciao

[gugoXX]

Io propongo il seguente:
- Un primo ciclo per cercare le corrispondenze esatte, marcando con un valore impossibile ogni volta che trovo qualcosa.
- Un secondo ciclo per cercare le corripondenze nel posto sbagliato, marcando di nuovo ogni volta che trovo qualcosa.

ES:
2278 valore da indovinare
5286 valore proposto



Primo ciclo O(N), passo, trovo solo il 2 in seconda posizione come esatto.
Ogni volta che trovo qualcosa devo marcare. Ne risultera' quindi alla fine la seguente.

2X78
5Y86

Secondo ciclo O(N logN), passo, trovo solo un 8 in posizione ovviamente sbagliata. Ogni volta che trovo qualcosa devo marcare subito. Ne risultera' quindi alla fine la seguente

2X7X
5YY6

L'algoritmo e' distruttivo, quindi e' necessario fare una copia preventiva dei due vettori, e lavorare su di queste.

[Albi89]

Originariamente inviato da DanieleC88

Secondo me hai bisogno di ricordare anche le posizioni, metti il caso che la combinazione sia 2 4 5 2 e il tentativo sia 2 2 7 8, darebbe come risultato un piolo giusto e due mal posizionati, il che è evidentemente non corretto (ma il valore delle posizioni errate sarebbe ammissibile secondo il tuo algoritmo, perché non superiore a MAX).

Puoi quindi quindi usare magari un vettore che ricordi più di un dato (ad esempio due interi, il primo dei quali rappresenta il codice e il secondo la flag riconosciuto/non riconosciuto) e incrementare solo a seconda delle corrispondenze, o altrimenti inserire la combinazione in un dato come una lista e rimuovere prima gli elementi trovati nelle posizioni corrette, e contare tra gli elementi rimasti quelli contenuti nel tentativo (che, se presenti, avranno valori corretti con posizioni errate).

ciao

Mh non credo perchè io MAX l'ho calcolato come (OCC_NUM - NUM_FOUND) dove OCC_NUM era il numero di occorrenze (nel nostro caso 2) mentre NUM_FOUND il numero di volte che il piolo è già trovato in posizione corretta (quindi nel nostro caso 1).
Dunque MAX sarebbe 1 e, per il caso che porti, l'algoritmo funzionerebbe
Però sono abbastanza sicuro che ci siano casi per cui questo non vale... mi armo di carta e penna e cerco di trovarne qualcuno

Eventualmente opterò per la soluzione di Gugo che mi sembra sicuramente funzionante... anche se mi rimarrà "in canna" il mio algoritmo fallimentare

[wingman87]

1. Crea un array delle singole occorrenze numeriche nel codice segreto
2. Scorri gli elementi di questo array
|-> Calcola MAX per il valore corrente come spiegato sopra
'-> Confronta ogni elemento con tutti gli elementi del codice segreto
     '-> se gli elementi sono uguali e la posizione diversa, e inoltre
          N non è stato incrementato più di MAX volte per l'elemento 
          corrente, incrementa N

Premetto che potrei non aver compreso bene l'algoritmo, o meglio il modo in cui l'hai implementato, detto questo provo a darti una mano.
Secondo me l'algoritmo non funziona bene per quella che è la natura di N e quella che è la natura di MAX, mi spiego: N è condiviso tra tutti i numeri che compongono il codice mentre MAX è calcolato in base al numero su cui sei posizionato, questo comporta degli errori, ti faccio un esempio che mi è venuto in mente
CODICE: 1133
TENTATIVO: 3311
ora i primi due 3 faranno incrementare N a 2, quando andrò a controllare gli ultimi 2 "1" MAX varrà 2 ma essendo N=2 questo non verrà più incrementato...

[DanieleC88]

Originariamente inviato da Albi89

Mh non credo perchè io MAX l'ho calcolato come (OCC_NUM - NUM_FOUND) dove OCC_NUM era il numero di occorrenze (nel nostro caso 2) mentre NUM_FOUND il numero di volte che il piolo è già trovato in posizione corretta (quindi nel nostro caso 1).
Dunque MAX sarebbe 1 e, per il caso che porti, l'algoritmo funzionerebbe

Hai ragione in effetti. Ma guarda che ora era, non avevo certo la lucidità necessaria per fare due sottrazioni.

[Albi89]

Originariamente inviato da wingman87

Premetto che potrei non aver compreso bene l'algoritmo, o meglio il modo in cui l'hai implementato, detto questo provo a darti una mano.
Secondo me l'algoritmo non funziona bene per quella che è la natura di N e quella che è la natura di MAX, mi spiego: N è condiviso tra tutti i numeri che compongono il codice mentre MAX è calcolato in base al numero su cui sei posizionato, questo comporta degli errori, ti faccio un esempio che mi è venuto in mente
CODICE: 1133
TENTATIVO: 3311
ora i primi due 3 faranno incrementare N a 2, quando andrò a controllare gli ultimi 2 "1" MAX varrà 2 ma essendo N=2 questo non verrà più incrementato...

Grazie per avermi illuminato
L'errore non era proprio questo, e in realtà temo che non sapremo mai quale fosse... semplicemente il metodo deputato al calcolo di N era stato scritto in serata "non ispirata"... righe e righe di codice convulso e incomprensibile...
L'ho appena riscritto ed in 3 righe, pratiche pratiche, fa quello che dovrebbe fare: finalmente il gioco fa il suo

Per ora sto usando una classe console_game per testare il gioco, il prossimo obiettivo è realizzare la parte grafica!
Grazie a tutti per i drittoni, è una sera felice