Do you need help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2021-22 loggatevi e attivatelo nella vostra pagina dei corsi preferiti. A quel punto il corso appare nel menù personale cliccando sul proprio avatar. Per i materiali degli anni precedenti seguite lo stesso metodo.

To join the Programming/Lab 2021-22 course, log-on and select it on the my courses page. It will appear on the personal menu of your avatar. For earlier years use the same method.

VIDEOLEZIONI DEL CORSO DI FONDAMENTI DI PROGRAMMAZIONE AA20-21

PROGRAMMING COURSE VIDEOCONFERENCES AY20-21

Soluzioni Mastermind

m
matteocalvani (820 points)
10 19 26
in Es1 by (820 points)
Ciao a tutti,

dato che gli homework sono finiti e siamo prossimi all'esame, volevo chiedere a tutti voi che ragionamento/algoritmo avete applicato magari dicendo anche quanti codici indovinate con quel ragionamento/algoritmo.
Grazie a chi (spero) voglia condividere la propria idea a scopo migliorativo per tutti.
Un saluto e in bocca al lupo a tutti per recuperi ed esame!

Matteo
816 views

2 Answers

pengfei (1180 points)
3 13 23
by (1.2k points)
edited by
Ciao, io l'ho risolto creando inizialmente un albero con tutti i codici possibili (che rappresenta tutte le possibili soluzioni), poi dopo il primo indizio creo due nuovi alberi, uno supponendo che l'indizio sia del tipo (a,b) non invertito, e l'altro supponendo che l'indizio sia (b,a), in cui scarto tutti i codici non compatibili con l'indizio. Poi negli step successivi riapplico la procedura su ogni albero creato nel passo precedente, il numero di alberi (corrispondenti a tutti i "mondi" possibili) potenzialmente può raddoppiare ad ogni passo, ma alla fine la cosa non è così grave, perchè ad ogni passo il numero di elementi rimasti in ogni lista diminuisce molto più velocemente dell'aumento del numero degli alberi, soprattutto negli alberi in cui le supposizioni sull'inversione risultano sbagliate, l'incoerenza negli indizi porta molto in fretta al loro collasso, restano senza elementi e possono essere scartati.
Ho scelto il codice da usare come scommessa tra uno a caso degli alberi rimasti come soluzioni, però preferendo gli alberi con più elementi, ipotizzando che sia più probabile che corrisponda al mondo "giusto". Una volta scelto l'albero, ho scelto un codice a caso, non è una scelta ottimale, idealmente si dovrebbe scegliere il codice che consente di scartare il maggior numero di codici nel caso peggiore, però ero già troppo tirato coi tempi, non ho neanche provato a implementare la cosa.
Come ottimizzazione ulteriore al primo step ho pensato che fosse più probabile che l'albero corretto sia quello costruito sull'ipotesi in cui il numero di cifre indovinate al posto sbagliato sia molto superiore al numero di cifre al posto giusto (ad esempio di solito la prima risposta è qualcosa come (1,6) o (6,1), ci vorrebbe un sedere come il Colosseo per indovinare 6 cifre al posto giusto al primo tentativo), e quindi davo priorità a questo albero e ai suoi figli nella scelta della seconda puntata, ma sono convinto che questa ottimizzazione sia stata totalmente inutile, per i primi tentativi non penso sia un problema puntare codici sbagliati, e poi la tabella "sbagliata" creata nel primo tentativo si azzera in fretta.
Con questo approccio ho indovinato 16 codici con 135 tentativi, ero molto tirato coi tempi di esecuzione, c'è chi ha avuto approcci più efficaci
P
Pic1 (1030 points)
7 24 31
by (1.0k points)
Io ho creato, in fase di import del programma, una lista di 3 liste, ognuna delle quali ha tutte le possibili permutazioni senza ripetizioni (generate con itertools) per l=6,7,8 (L=lunghezza del codice)

Se len(configurazione)==1, prendo la lista contenuta in lista[n-6] e la metto nella variabile globale ‘possibili’ e provo il primo codice [0]*n, con n=lunghezza del codice da trovare.

Altrimenti se len(configurazione)==2, se la risposta avuta é (0,0) scarto dalla lista tutti i codici contenenti 0, altrimenti scarto tutti quelli senza lo 0

Dagli elementi rimasti in ‘possibili’ ne prendo uno e lo provo

In tutti gli altri casi (ovvero per len(configurazione)>2), prendo la risposta del codice precedente e applico la funzione ‘risposta’ (quella del simulatore del prof) a ogni elemento, usando come codice ‘da trovare’ il codice passato nel tentativo precedente. Se la risposta è diversa da quella data dal simulatore o dalla sua inversa, elimino l’elemento dalla lista ‘possibili’.

In tal modo, in 10-11 tentativi al massimo, riesco a trovare il codice esatto.

Alla valutazione ne ho indovinati 15 con 150 tentativi e 28.24 secondi

Ferdinando

Matr1823149

P.s. Probabilmente il prof metterà, come per gli altri Homework il link al codice di ognuno cliccando sulla rispettiva matricola in classifica.