Il perverso problema dell'impiccato

Question

L'impiccato di Perverso è un gioco molto simile a un normale impiccato con una differenza importante: la parola vincente è determinata dinamicamente dalla casa a seconda di quali lettere sono state indovinate.

Ad esempio, supponiamo di avere la scheda _ A I L e 12 ipotesi rimanenti. Perché ci sono 13 parole diverse che finiscono in AIL (cauzione, fallimento, grandine, prigione, cauzione, posta, chiodo, secchio, rotaia, vela, coda, vail, lamento) la casa è garantita per vincere perché non importa quali 12 lettere indovinate , la casa rivendicherà che la parola scelta è stata quella che non hai indovinato. Tuttavia, se la scheda è stata _ I L M, hai messo in un angolo la casa come FILM è l'unica parola che termina in ILM.

La sfida è: Dato un dizionario, una lunghezza di parola & il numero di tentativi consentiti, venire con un algoritmo che:

a) dimostra che il giocatore vince sempre emettendo un albero decisionale per il giocatore quello che si abbatte sulla casa non importa cosa

b) dimostra che la casa vince sempre emettendo un albero decisionale per la casa che permette alla casa di scappare a prescindere da cosa.

Come esempio giocattolo, considerano il dizionario:

bat 
bar 
car 

Se ti è consentito 3 tentativi sbagliati, il giocatore vince con il seguente albero:

Guess B 
NO -> Guess C, Guess A, Guess R, WIN 
YES-> Guess T 
     NO -> Guess A, Guess R, WIN 
     YES-> Guess A, WIN 

Answer 1

Questo è quasi identica alla " come trovo la moneta dispari con ripetute pesate? " problema. L'intuizione fondamentale è che stai cercando di massimizzare la quantità di informazioni che ottieni dalla tua ipotesi.

L'algoritmo greedy per costruire l'albero decisionale è il seguente: - per ogni ipotesi, scegliere l'ipotesi per cui la risposta è "vera" e la cui risposta è "falso" è il 50-50 come possibile, in quanto informazioni teoricamente ciò fornisce la maggior parte delle informazioni.

Sia N la dimensione del set, A sia la dimensione dell'alfabeto, e L sia il numero di lettere nella parola.

Quindi metti tutte le tue parole in un set. Per ogni posizione di lettera e per ogni lettera del tuo alfabeto conta quante parole hanno quella lettera in quella posizione (questa può essere ottimizzata con una tabella hash aggiuntiva). Scegli il conteggio più vicino alla metà del set. Questo è O (L * A).

Dividete il set in due prendendo il sottoinsieme che ha questa lettera in questa posizione e fate che i due rami dell'albero. Ripeti per ogni sottoinsieme fino a quando non hai l'intero albero. Nel peggiore dei casi ciò richiederà dei passi O (N), ma se hai un bel dizionario questo porterà a passi O (logN).

Answer 2

Questa non è propriamente una risposta, dal momento che non fornisce un albero decisionale, ma ho fatto qualcosa di molto simile scrivendo il mio hangman solver. Fondamentalmente, guarda l'insieme di parole nel suo dizionario che corrispondono al modello e prelevano la lettera più comune. Se indovina, elimina il maggior numero di candidati. Dal momento che non c'è penalità per indovinare il diritto nel boia, penso che questa sia la strategia ottimale dati i vincoli.

Quindi, con il dizionario che hai dato, sarebbe prima indovinare a correttamente.Quindi indicherebbe r, anche correttamente, quindi b (errato), quindi c.

Il problema con il boia perverso è che si indovina sempre male se si indovina male, ma questo è perfetto per questo algoritmo poiché elimina prima il set più grande. Come esempio leggermente più significativo:

Dizionario:

mar 
bar 
car 
fir 
wit 

In questo caso indovina r correttamente prima ed è lasciato con solo spirito. Se wit sono stati sostituiti nel dizionario con sir, allora si potrebbe indovinare r in modo corretto quindi a in modo errato, eliminando il set più grande, quindi w o f a caso in modo errato, seguito dall'altra per l'ultima parola con solo 1 ipotesi errata.

Quindi, questo algoritmo vincerà se è possibile vincere, anche se è necessario eseguirlo per vedere se ha vinto.