Le but de ce défi est d'écrire un programme capable de deviner un mot dans le plus petit nombre possible de tentatives. Il est basé sur le concept de l'émission Lingo TV ( http://en.wikipedia.org/wiki/Lingo_(US_game_show) ).

Règles

Étant donné une longueur de mot passée comme premier argument sur sa ligne de commande, le programme du joueur dispose de cinq tentatives pour deviner le mot en écrivant une supposition sur sa sortie standard suivie d'un seul \ncaractère.

Après avoir fait une supposition, le programme reçoit une chaîne sur son entrée standard, également suivie d'un seul \ncaractère.

La chaîne a la même longueur que le mot à deviner et se compose d'une séquence des caractères suivants:

• X: ce qui signifie que la lettre donnée n'est pas présente dans le mot à deviner
• ?: ce qui signifie que la lettre donnée est présente dans le mot à deviner, mais à un autre endroit
• O: ce qui signifie que la lettre à cet endroit a été correctement devinée

Par exemple, si le mot à deviner est dents, et le programme envoie le mot dozes, il recevra OXX?Oparce que det ssont corrects, eest mal placé et oet zn'est pas présent.

Attention, si une lettre est présente plus de fois dans la tentative de devinette que dans le mot à deviner, elle ne sera pas marquée comme ?et Oplus de fois que le nombre d'occurrences de la lettre dans le mot à deviner. Par exemple, si le mot à deviner est cozieset que le programme envoie tosses, il recevra XOXXOOcar il n'y en a qu'un sà localiser.

Les mots sont choisis dans une liste de mots anglais. Si le mot envoyé par le programme n'est pas un mot valide de la bonne longueur, la tentative est considérée comme un échec automatique et seuls Xsont renvoyés.
Le programme du lecteur doit supposer qu'un fichier nommé wordlist.txtet contenant un mot par ligne est présent dans le répertoire de travail actuel et peut être lu si nécessaire.
Les suppositions ne doivent être composées que de caractères alphabétiques en minuscules ( [a-z]).
Aucune autre opération réseau ou fichier n'est autorisée pour le programme.

Le jeu se termine lorsqu'une chaîne composée uniquement de Oest retournée ou après que le programme a effectué 5 tentatives et n'a pas pu deviner le mot.

Notation

Le score d'un match est donné par la formule donnée:

score = 100 * (6 - number_of_attempts)

Donc, si le mot est correctement deviné au premier essai, 500 points sont accordés. Le dernier essai vaut 100 points.

Ne pas deviner le mot n'accorde aucun point.

La fosse

Les programmes des joueurs seront évalués en essayant de leur faire deviner 100 mots aléatoires pour chaque longueur de mot comprise entre 4 et 13 caractères inclusivement.
La sélection aléatoire des mots sera effectuée à l'avance de sorte que toutes les entrées devront deviner les mêmes mots.

Le programme gagnant et la réponse acceptée seront ceux qui atteindront le score le plus élevé.

Les programmes seront exécutés sur une machine virtuelle Ubuntu, en utilisant le code à https://github.com/noirotm/lingo . Les implémentations dans n'importe quel langage sont acceptées tant que des instructions raisonnables pour les compiler et / ou les exécuter sont fournies.

Je fournis quelques implémentations de test en ruby ​​dans le référentiel git, n'hésitez pas à vous en inspirer.

Cette question sera périodiquement mise à jour avec des classements pour les réponses publiées afin que les challengers puissent améliorer leurs entrées.

L'évaluation finale officielle aura lieu le 1er juillet .

Mise à jour

Les entrées peuvent désormais supposer la présence de wordlistN.txtfichiers pour accélérer la lecture de la liste de mots pour la longueur de mot actuelle pour N entre 4 et 13 inclusivement.

Par exemple, il existe un wordlist4.txtfichier contenant les quatre mots et wordlist10.txtcontenant les dix mots, etc.

Résultats du premier tour

À la date du 01/07/2014, trois entrées ont été soumises, avec les résultats suivants:

                        4       5       6       7       8       9       10      11      12      13      Total
./chinese-perl-goth.pl  8100    12400   15700   19100   22100   25800   27900   30600   31300   33600   226600
java Lingo              10600   14600   19500   22200   25500   28100   29000   31600   32700   33500   247300
./edc65                 10900   15800   22300   24300   27200   29600   31300   33900   33400   33900   262600

** Rankings **
1: ./edc65 (262600)
2: java Lingo (247300)
3: ./chinese-perl-goth.pl (226600)

Toutes les entrées ont fonctionné de manière cohérente, avec un gagnant clair, étant l'entrée C ++ de @ edc65.

Tous les candidats sont assez impressionnants. Jusqu'à présent, je n'ai même pas pu battre @ chinese-perl-goth.
Si plus d'entrées sont soumises, une autre évaluation aura lieu. Les entrées actuelles peuvent également être améliorées si vous sentez que vous pouvez faire mieux.

C ++ 267700 points

Un portage à partir d'un ancien moteur MasterMind.
Différences avec MasterMind:

• Plus d'emplacements
• Plus de symboles
• Plus grand espace de solution (mais pas tellement, car toutes les combinaisons de symboles ne sont pas autorisées)
• La réponse est très informative, nous avons donc plus d'informations après chaque supposition
• La réponse est plus lente à générer et c'est dommage car mon algorithme doit le faire beaucoup.

L'idée de base est de choisir le mot qui minimise l'espace de la solution. L'algorithme est vraiment lent pour la première supposition (je veux dire «jours»), mais la meilleure première supposition dépend uniquement du mot len, il est donc codé en dur dans la source. Les autres suppositions se font en quelques secondes.

Le code

(Compiler avec g ++ -O3)

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

class LRTimer
{
private:
    time_t start;
public:
    void startTimer(void)
    {
        time(&start);
    }

    double stopTimer(void)
    {
        return difftime(time(NULL),start);
    } 

};

#define MAX_WORD_LEN 15
#define BIT_QM 0x8000

LRTimer timer;
int size, valid, wordLen;

string firstGuess[] = { "", "a", "as", "iao", "ares", 
    "raise", "sailer", "saltier", "costlier", "clarities", 
    "anthelices", "petulancies", "incarcerates", "allergenicity" };

class Pattern
{
public:
    char letters[MAX_WORD_LEN];
    char flag;
    int mask;

    Pattern() 
        : letters(), mask(), flag()
    {
    }

    Pattern(string word) 
        : letters(), mask(), flag()
    {
        init(word);
    }

    void init(string word)
    {
        const char *wdata = word.data();
        for(int i = 0; i < wordLen; i++) {
            letters[i] = wdata[i];
            mask |= 1 << (wdata[i]-'a');
        }
    }

    string dump()
    {
        return string(letters);
    }

    int check(Pattern &secret)
    {
        if ((mask & secret.mask) == 0)
            return 0;

        char g[MAX_WORD_LEN], s[MAX_WORD_LEN];
        int r = 0, q = 0, i, j, k=99;
        for (i = 0; i < wordLen; i++)
        {
            g[i] = (letters[i] ^ secret.letters[i]);
            if (g[i])
            {
                r += r;
                k = 0;
                g[i] ^= s[i] = secret.letters[i];
            }
            else
            {
                r += r + 1;
                s[i] = 0;
            }
        }
        for (; k < wordLen; k++)
        {
            q += q;
            if (g[k]) 
            {
                for (j = 0; j < wordLen; j++)
                    if (g[k] == s[j])
                    {
                        q |= BIT_QM;
                        s[j] = 0;
                        break;
                    }
            }
        }
        return r|q;
    }

    int count(int ck, int limit);

    int propcheck(int limit);

    void filter(int ck);
};

string dumpScore(int ck)
{
    string result(wordLen, 'X');
    for (int i = wordLen; i--;)
    {
        result[i] = ck & 1 ? 'O' : ck & BIT_QM ? '?' : 'X';
        ck >>= 1;
    }
    return result;
}

int parseScore(string ck)
{
    int result = 0;
    for (int i = 0; i < wordLen; i++)
    {
        result += result + (
            ck[i] == 'O' ? 1 : ck[i] == '?' ? BIT_QM: 0
        );
    }
    return result;
}

Pattern space[100000];

void Pattern::filter(int ck)
{
    int limit = valid, i = limit;
//  cerr << "Filter IN Valid " << setbase(10) << valid << " This " << dump() << "\n"; 

    while (i--)
    {
        int cck = check(space[i]);
//      cerr << setbase(10) << setw(8) << i << ' ' << space[i].dump() 
//          << setbase(16) << setw(8) << cck << " (" << Pattern::dumpScore(cck) << ") ";

        if ( ck != cck )
        {
//          cerr << " FAIL\r" ;
            --limit;
            if (i != limit) 
            {
                Pattern t = space[i];
                space[i] = space[limit];
                space[limit] = t;
            }
        }
        else
        {
//          cerr << " PASS\n" ;
        }
    }
    valid = limit;
//  cerr << "\nFilter EX Valid " << setbase(10) << valid << "\n"; 
};

int Pattern::count(int ck, int limit)
{
    int i, num=0;
    for (i = 0; i < valid; ++i)
    {
        if (ck == check(space[i]))
            if (++num >= limit) return num;
    }
    return num;
}

int Pattern::propcheck(int limit)
{
    int k, mv, nv;

    for (k = mv = 0; k < valid; ++k)
    {
        int ck = check(space[k]);
        nv = count(ck, limit);
        if (nv >= limit)
        {
            return 99999;
        }
        if (nv > mv) mv = nv;
    }
    return mv;
}

int proposal(bool last)
{
    int i, minnv = 999999, mv, result;

    for (i = 0; i < valid; i++) 
    {
        Pattern& guess = space[i];
//      cerr << '\r' << setw(6) << i << ' ' << guess.dump();
        if ((mv = guess.propcheck(minnv)) < minnv)
        {
//          cerr << setw(6) << mv << ' ' << setw(7) << setiosflags(ios::fixed) << setprecision(0) << timer.stopTimer() << " s\n";
            minnv = mv;
            result = i;
        }
    }   
    if (last) 
        return result;
    minnv *= 0.75;
    for (; i<size; i++) 
    {
        Pattern& guess = space[i];
//      cerr << '\r' << setw(6) << i << ' ' << guess.dump();
        if ((mv = guess.propcheck(minnv)) < minnv)
        {
//          cerr << setw(6) << mv << ' ' << setw(7) << setiosflags(ios::fixed) << setprecision(0) << timer.stopTimer() << " s\n";
            minnv = mv;
            result = i;
        }
    }   
    return result;
}

void setup(string wordfile)
{
    int i = 0; 
    string word;
    ifstream infile(wordfile.data());
    while(infile >> word)
    {
        if (word.length() == wordLen) {
            space[i++].init(word);
        }
    }
    infile.close(); 
    size = valid = i;
}

int main(int argc, char* argv[])
{
    if (argc < 2) 
    {
        cerr << "Specify word length";
        return 1;
    }

    wordLen = atoi(argv[1]);

    timer.startTimer();
    setup("wordlist.txt");
    //cerr << "Words " << size 
    //  << setiosflags(ios::fixed) << setprecision(2)
    //  << " " << timer.stopTimer() << " s\n";

    valid = size;
    Pattern Guess = firstGuess[wordLen];
    for (int t = 0; t < 5; t++)
    {
        cout << Guess.dump() << '\n' << flush;
        string score;
        cin >> score;
        int ck = parseScore(score);
        //cerr << "\nV" << setw(8) << valid << " #" 
        //  << setw(3) << t << " : " << Guess.dump()
        //  << " : " << score << "\n";
        if (ck == ~(-1 << wordLen))
        {
            break;
        }
        Guess.filter(ck); 
        Guess = space[proposal(t == 3)];
    }
    // cerr << "\n";

    double time = timer.stopTimer();
    //cerr << setiosflags(ios::fixed) << setprecision(2)
    //   << timer.stopTimer() << " s\n";

    return 0;
}

Mes scores

Évaluation avec jargon, 100 tours:

4   9000
5   17700
6   22000
7   25900
8   28600
9   29700
10  31000
11  32800
12  33500
13  34900

Total 265'100

Scores auto-évalués

Voici mes points moyens, marqués sur toute la liste de mots. Pas complètement fiable car certains détails de l'algorithme ont changé pendant les tests.

 4 # words  6728 PT AVG   100.98 87170.41 s
 5 # words 14847 PT AVG   164.44 42295.38 s
 6 # words 28127 PT AVG   212.27 46550.00 s 
 7 # words 39694 PT AVG   246.16 61505.54 s
 8 # words 49004 PT AVG   273.23 63567.45 s
 9 # words 50655 PT AVG   289.00 45438.70 s
10 # words 43420 PT AVG   302.13 2952.23 s
11 # words 35612 PT AVG   323.62 3835.00 s
12 # words 27669 PT AVG   330.19 5882.98 s
13 # words 19971 PT AVG   339.60 2712.98 s

D'après ces chiffres, mon score moyen devrait être proche de 257'800

PIT SCORE

Enfin, j'ai installé Ruby, j'ai maintenant un score «officiel»:

    4       5       6       7       8       9      10      11      12      13   TOTAL
10700   16300   22000   25700   27400   30300   32000   33800   34700   34800   267700

Java, 249700 points (bat Chinese Perl Goth dans mon test)

Liste de classement mise à jour:

                        4 5 6 7 8 9 10 11 12 13 Total
perl chinese_perl_goth.pl 6700 12300 16900 19200 23000 26100 28500 29600 32100 33900 228300
java Lingo 9400 14700 18900 21000 26300 28700 30300 32400 33800 34200 249700

Voici l' ancienne liste de classement utilisant pit.rb:

                        4 5 6 7 8 9 10 11 12 13 Total
ruby player-example.rb 200400400500 1800 1400 1700 1600 3200 4400 15600
ruby player-example2.rb 2700 3200 2500 4300 7300 6300 8200 10400 13300 15000 73200
ruby player-example3.rb 4500 7400 9900 13700 15400 19000 19600 22300 24600 27300 163700
perl chinese_perl_goth.pl 6400 14600 16500 21000 22500 26000 27200 30600 32500 33800 231100
java Lingo 4800 13100 16500 21400 27200 29200 30600 32400 33700 36100 245000

** Classements **
1: java Lingo (245000)
2: perl chinese_perl_goth.pl (231100)
3: ruby ​​player-example3.rb (163700)
4: joueur rubis-example2.rb (73200)
5: rubis player-example.rb (15600)

Par rapport à @chineseperlgoth, je perds en mots plus courts (<6 caractères) mais je gagne en mots plus longs (> = 6 caractères).

L'idée est similaire à @chineseperlgoth, c'est juste que mon idée principale est de trouver la supposition (peut être n'importe quel mot de la même longueur, pas nécessairement l'une des possibilités restantes) qui donne le plus d'informations pour la prochaine supposition.

Actuellement, je joue toujours avec la formule, mais pour le tableau de bord ci-dessus, je choisis le mot qui donnera le minimum pour:

-num_confusion * entropie

La dernière version utilise des scores différents pour trouver la meilleure estimation suivante, qui maximise le nombre de "possibilités uniques" après la supposition actuelle. Pour ce faire, essayez tous les mots de la liste de mots élagués (pour gagner du temps) sur tous les candidats possibles et voyez quelle hypothèse est la plus susceptible de produire une "possibilité unique" (c'est-à-dire qu'après cette supposition, il n'y aura qu'une seule réponse possible) pour le prochaine supposition.

Ainsi, par exemple, cette course:

Commencer un nouveau tour, le mot est bénéfique
Got: seora
Envoyé:? XOXX
Got: topsl
Envoyé: XOX? X
Got: moines
Envoyé: XO? XO
Got: bewig
Envoyé: OXXXX
Got: boons
Envoyé: OOOOO
Tour gagné avec un score de 100

Des trois premières suppositions, nous avons déjà obtenu "* oo * s" avec un "n" quelque part et nous devons encore trouver une autre lettre. Maintenant, la beauté de cet algorithme est qu'au lieu de deviner des mots similaires à cette forme, il devine plutôt le mot qui n'a aucun rapport avec les suppositions précédentes, essayant de donner plus de lettres, révélant, espérons-le, la lettre manquante. Dans ce cas, il arrive également d'obtenir correctement la position du "b" manquant et se termine par la bonne estimation finale "boons".

Voici le code:

import java.util.*;
import java.io.*;

class Lingo{
    public static String[] guessBestList = new String[]{
                                "",
                                "a",
                                "sa",
                                "tea",
                                "orae",
                                "seora", // 5
                                "ariose",
                                "erasion",
                                "serotina",
                                "tensorial",
                                "psalterion", // 10
                                "ulcerations",
                                "culteranismo",
                                "persecutional"};
    public static HashMap<Integer, ArrayList<String>> wordlist = new HashMap<Integer, ArrayList<String>>();

    public static void main(String[] args){
        readWordlist("wordlist.txt");
        Scanner scanner = new Scanner(System.in);
        int wordlen = Integer.parseInt(args[0]);
        int roundNum = 5;
        ArrayList<String> candidates = new ArrayList<String>();
        candidates.addAll(wordlist.get(wordlen));
        String guess = "";
        while(roundNum-- > 0){
            guess = guessBest(candidates, roundNum==4, roundNum==0);
            System.out.println(guess);
            String response = scanner.nextLine();
            if(isAllO(response)){
                break;
            }
            updateCandidates(candidates, guess, response);
            //print(candidates);
        }
    }

    public static void print(ArrayList<String> candidates){
        for(String str: candidates){
            System.err.println(str);
        }
        System.err.println();
    }

    public static void readWordlist(String path){
        try{
            BufferedReader reader = new BufferedReader(new FileReader(path));
            while(reader.ready()){
                String word = reader.readLine();
                if(!wordlist.containsKey(word.length())){
                    wordlist.put(word.length(), new ArrayList<String>());
                }
                wordlist.get(word.length()).add(word);
            }
        } catch (Exception e){
            System.exit(1);
        }
    }

    public static boolean isAllO(String response){
        for(int i=0; i<response.length(); i++){
            if(response.charAt(i) != 'O') return false;
        }
        return true;
    }

    public static String getResponse(String word, String guess){
        char[] wordChar = word.toCharArray();
        char[] result = new char[word.length()];
        Arrays.fill(result, 'X');
        for(int i=0; i<guess.length(); i++){
            if(guess.charAt(i) == wordChar[i]){
                result[i] = 'O';
                wordChar[i] = '_';
            }
        }
        for(int i=0; i<guess.length(); i++){
            if(result[i] == 'O') continue;
            for(int j=0; j<wordChar.length; j++){
                if(result[j] == 'O') continue;
                if(wordChar[j] == guess.charAt(i)){
                    result[i] = '?';
                    wordChar[j] = '_';
                    break;
                }
            }
        }
        return String.valueOf(result);
    }

    public static void updateCandidates(ArrayList<String> candidates, String guess, String response){
        for(int i=candidates.size()-1; i>=0; i--){
            String candidate = candidates.get(i);
            if(!response.equals(getResponse(candidate, guess))){
                candidates.remove(i);
            }
        }
    }

    public static int countMatchingCandidates(ArrayList<String> candidates, String guess, String response){
        int result = 0;
        for(String candidate: candidates){
            if(response.equals(getResponse(candidate, guess))){
                result++;
            }
        }
        return result;
    }

    public static String[] getSample(ArrayList<String> words, int size){
        String[] result = new String[size];
        int[] indices = new int[words.size()];
        for(int i=0; i<words.size(); i++){
            indices[i] = i;
        }
        Random rand = new Random(System.currentTimeMillis());
        for(int i=0; i<size; i++){
            int take = rand.nextInt(indices.length-i);
            result[i] = words.get(indices[take]);
            indices[take] = indices[indices.length-i-1];
        }
        return result;
    }

    public static String guessBest(ArrayList<String> candidates, boolean firstGuess, boolean lastGuess){
        if(candidates.size() == 1){
            return candidates.get(0);
        }
        String minGuess = candidates.get(0);
        int wordlen = minGuess.length();
        if(firstGuess && guessBestList[wordlen].length()==wordlen){
            return guessBestList[wordlen];
        }
        int minMatches = Integer.MAX_VALUE;
        String[] words;
        if(lastGuess){
            words = candidates.toArray(new String[0]);
        } else if (candidates.size()>10){
            words = bestWords(wordlist.get(wordlen), candidates, 25);
        } else {
            words = wordlist.get(wordlen).toArray(new String[0]);
        }
        for(String guess: words){
            double sumMatches = 0;
            for(String word: candidates){
                int matches = countMatchingCandidates(candidates, guess, getResponse(word, guess));
                if(matches == 0) matches = candidates.size();
                sumMatches += (matches-1)*(matches-1);
            }
            if(sumMatches < minMatches){
                minGuess = guess;
                minMatches = sumMatches;
            }
        }
        return minGuess;
    }

    public static String[] bestWords(ArrayList<String> words, ArrayList<String> candidates, int size){
        int[] charCount = new int[123];
        for(String candidate: candidates){
            for(int i=0; i<candidate.length(); i++){
                charCount[(int)candidate.charAt(i)]++;
            }
        }
        String[] tmp = (String[])words.toArray(new String[0]);
        Arrays.sort(tmp, new WordComparator(charCount));
        String[] result = new String[size+Math.min(size, candidates.size())];
        String[] sampled = getSample(candidates, Math.min(size, candidates.size()));
        for(int i=0; i<size; i++){
            result[i] = tmp[tmp.length-i-1];
            if(i < sampled.length){
                result[size+i] = sampled[i];
            }
        }
        return result;
    }

    static class WordComparator implements Comparator<String>{
        int[] charCount = null;

        public WordComparator(int[] charCount){
            this.charCount = charCount;
        }

        public Integer count(String word){
            int result = 0;
            int[] multiplier = new int[charCount.length];
            Arrays.fill(multiplier, 1);
            for(char chr: word.toCharArray()){
                result += multiplier[(int)chr]*this.charCount[(int)chr];
                multiplier[(int)chr] = 0;
            }
            return Integer.valueOf(result);
        }

        public int compare(String s1, String s2){
            return count(s1).compareTo(count(s2));
        }
    }
}

Perl

Il y a encore de la place pour des améliorations mais au moins ça bat les joueurs inclus dans l'exemple :)

Suppose un accès en écriture au répertoire actuel pour la mise en cache des listes de mots (pour le faire fonctionner un peu plus rapidement); va créer des wordlist.lenN.storfichiers en utilisant Storable. S'il s'agit d'un problème, supprimez read_cached_wordlistet modifiez le code à utiliser uniquement read_wordlist.

Explication

Tout d'abord, je construis un histogramme des fréquences des lettres dans tous les mots de la liste de mots actuelle ( build_histogram). Ensuite, je dois choisir ma prochaine supposition - ce qui est fait par find_best_word. L'algorithme de notation ajoute simplement les valeurs de l'histogramme ensemble, en ignorant les lettres déjà vues. Cela me donne un mot contenant les lettres les plus fréquentes dans la liste de mots. S'il y a plus d'un mot avec un score donné, j'en choisis un au hasard. Après avoir trouvé un mot, je l'envoie au moteur de jeu, lis la réponse puis essaie de faire quelque chose d'utile :)

Je maintiens un ensemble de conditions, c'est-à-dire des lettres qui peuvent apparaître à une position donnée dans un mot. Au début, cela est simple (['a'..'z'] x $len), mais il est mis à jour en fonction des conseils donnés en réponse (voir update_conds). Je construis ensuite une expression régulière à partir de ces conditions et je filtre la liste de mots à travers elle.

Au cours des tests, j'ai découvert que le filtrage susmentionné ne gère pas ?trop bien, d'où le deuxième filtre ( filter_wordlist_by_reply). Cela profite du fait qu'une lettre marquée comme ?apparaît dans le mot à une position différente et filtre la liste de mots en conséquence.

Ces étapes sont répétées pour chaque itération de la boucle principale, à moins que la solution ne soit trouvée (ou qu'il ne soit plus possible de lire depuis stdin, ce qui signifie un échec).

Code

#!perl
use strict;
use warnings;
use v5.10;
use Storable;

$|=1;

sub read_wordlist ($) {
    my ($len) = @_;
    open my $w, '<', 'wordlist.txt' or die $!;
    my @wordlist = grep { chomp; length $_ == $len } <$w>;
    close $w;
    \@wordlist
}

sub read_cached_wordlist ($) {
    my ($len) = @_;
    my $stor = "./wordlist.len$len.stor";
    if (-e $stor) {
        retrieve $stor
    } else {
        my $wl = read_wordlist $len;
        store $wl, $stor;
        $wl
    }
}

sub build_histogram ($) {
    my ($wl) = @_;
    my %histo = ();
    for my $word (@$wl) {
        $histo{$_}++ for ($word =~ /./g);
    }
    \%histo
}

sub score_word ($$) {
    my ($word, $histo) = @_;
    my $score = 0;
    my %seen = ();
    for my $l ($word =~ /./g) {
        if (not exists $seen{$l}) {
            $score += $histo->{$l};
            $seen{$l} = 1;
        }
    }
    $score
}

sub find_best_word ($$) {
    my ($wl, $histo) = @_;
    my @found = (sort { $b->[0] <=> $a->[0] } 
                 map [ score_word($_, $histo), $_ ], @$wl);
    return undef unless @found;
    my $maxscore = $found[0]->[0];
    my @max;
    for (@found) {
        last if $_->[0] < $maxscore;
        push @max, $_->[1];
    }
    $max[rand @max]
}

sub build_conds ($) {
    my ($len) = @_;
    my @c;
    push @c, ['a'..'z'] for 1..$len;
    \@c
}

sub get_regex ($) {
    my ($cond) = @_;
    local $" = '';
    my $r = join "", map { "[@$_]" } @$cond;
    qr/^$r$/
}

sub remove_cond ($$$) {
    my ($conds, $pos, $ch) = @_;
    return if (scalar @{$conds->[$pos]} == 1);
    return unless grep { $_ eq $ch } @{$conds->[$pos]};
    $conds->[$pos] = [ grep { $_ ne $ch } @{$conds->[$pos]} ]
}

sub add_cond ($$$) {
    my ($conds, $pos, $ch) = @_;
    return if (scalar @{$conds->[$pos]} == 1);
    return if grep { $_ eq $ch } @{$conds->[$pos]};
    push @{$conds->[$pos]}, $ch
}

sub update_conds ($$$$) {
    my ($word, $reply, $conds, $len) = @_;
    my %Xes;
    %Xes = ();
    for my $pos (reverse 0..$len-1) {
        my $r = substr $reply, $pos, 1;
        my $ch = substr $word, $pos, 1;

        if ($r eq 'O') {
            $conds->[$pos] = [$ch]
        }

        elsif ($r eq '?') {
            for my $a (0..$len-1) {
                if ($a == $pos) {
                    remove_cond $conds, $a, $ch
                } else {
                    unless (exists $Xes{$a} and $Xes{$a} eq $ch) {
                        add_cond($conds, $a, $ch);
                    }
                }
            }
        }

        elsif ($r eq 'X') {
            $Xes{$pos} = $ch;
            for my $a (0..$len-1) {
                remove_cond $conds, $a, $ch
            }
        }
    }
}

sub uniq ($) {
    my ($data) = @_;
    my %seen; 
    [ grep { !$seen{$_}++ } @$data ]
}

sub filter_wordlist_by_reply ($$$) {
    my ($wl, $word, $reply) = @_;
    return $wl unless $reply =~ /\?/;
    my $newwl = [];
    my $len = length $reply;
    for my $pos (0..$len-1) {
        my $r = substr $reply, $pos, 1;
        my $ch = substr $word, $pos, 1;
        next unless $r eq '?';
        for my $a (0..$len-1) {
            if ($a != $pos) {
                if ('O' ne substr $reply, $a, 1) {
                    push @$newwl, grep { $ch eq substr $_, $a, 1 } @$wl
                }
            }
        }
    }
    uniq $newwl
}

my $len = $ARGV[0] or die "no length";
my $wl = read_cached_wordlist $len;
my $conds = build_conds $len;

my $c=0;
do {
    my $histo = build_histogram $wl;
    my $word = find_best_word $wl, $histo;
    die "no candidates" unless defined $word;
    say $word;
    my $reply = <STDIN>; 
    chomp $reply;
    exit 1 unless length $reply;
    exit 0 if $reply =~ /^O+$/;
    update_conds $word, $reply, $conds, $len;
    $wl = filter_wordlist_by_reply $wl, $word, $reply;
    $wl = [ grep { $_ =~ get_regex $conds } @$wl ]
} while 1