Objetivo

Dada uma lista de senhas de três palavras, decifre todas elas. Cada vez que você adivinhar, você terá uma pista no estilo de Mastermind , representando quantos caracteres correspondem à senha e quantos estão na posição correta. O objetivo é minimizar o número total de suposições em todos os casos de teste.

Senhas

Na lista de palavras padrão do meu sistema, escolhi aleatoriamente 10.000 palavras distintas para formar o dicionário para esse desafio. Todas as palavras consistem a-zapenas. Este dicionário pode ser encontrado aqui (em bruto ).

A partir deste dicionário, eu gerei 1000 frases secretas que consistem em três palavras aleatórias separadas por espaço cada ( apple jacks feverpor exemplo). Palavras individuais podem ser reutilizadas em cada frase secreta ( hungry hungry hippos). Você pode encontrar a lista de senhas aqui (em bruto ), com uma por linha.

Seu programa pode usar / analisar o arquivo de dicionário da maneira que desejar. Você não pode analisar as frases secretas para otimizar esta lista específica. Seu algoritmo ainda deve funcionar, com uma lista diferente de frases

Adivinhação

Para adivinhar, você envia uma string para um verificador. Ele deve retornar apenas :

• O número de caracteres na sua string também na frase secreta ( não na posição correta)
• O número de caracteres na posição correta

Se sua string é uma combinação perfeita, ela pode gerar algo indicando isso (a minha usa -1para o primeiro valor).

Por exemplo, se a senha é the big cate você acha tiger baby mauling, o verificador deve retornar 7,1. 7 caracteres ( ige<space>ba<space>) estão nas duas cadeias, mas em posições diferentes, e 1 ( t) está na mesma posição nas duas. Observe que os espaços contam.

Eu escrevi um exemplo (leia-se: não otimizado) da função em Java, mas sinta-se à vontade para escrever seu próprio, contanto que ele forneça apenas as informações necessárias.

int[] guess(String in){
    int chars=0, positions=0;
    String pw = currentPassword; // set elsewhere, contains current pass
    for(int i=0;i<in.length()&&i<pw.length();i++){
        if(in.charAt(i)==pw.charAt(i))
            positions++;
    }
    if(positions == pw.length() && pw.length()==in.length())
        return new int[]{-1,positions};
    for(int i=0;i<in.length();i++){
        String c = String.valueOf(in.charAt(i));
        if(pw.contains(c)){
            pw = pw.replaceFirst(c, "");
            chars++;
        }
    }
    chars -= positions;
    return new int[]{chars,positions};
}

Pontuação

Sua pontuação é simplesmente o número de suposições que você envia ao verificador (contando a final correta) para todas as frases de teste. A pontuação mais baixa vence.

Você deve decifrar todas as frases da lista. Se o seu programa falhar em algum deles, é inválido.

Seu programa deve ser determinístico. Se executar duas vezes no mesmo conjunto de frases secretas, retornará o mesmo resultado.

No caso de empate pela primeira vez, executarei as entradas empatadas no meu computador quatro vezes cada, e o menor tempo médio para resolver todas as 1000 vitórias. Meu computador está executando o Ubuntu 14.04, com um i7-3770K e 16 GB de algum tipo de RAM, caso isso faça diferença no seu programa. Por esse motivo, e para facilitar o teste, sua resposta deve estar em um idioma que possua um compilador / intérprete que possa ser baixado da Web gratuitamente (sem incluir testes gratuitos) e que não exija inscrição / registro.

_{Título adaptado do XKCD}

Tempo Scala 9146 (mínimo 7, máximo 15, média 9,15): 2000 segundos

Como muitas entradas, começo obtendo o comprimento total, depois encontrando os espaços, obtendo um pouco mais de informação, reduzindo os candidatos restantes e adivinhando frases.

Inspirado na história em quadrinhos original do xkcd, tentei aplicar meu entendimento rudimentar da teoria da informação. Há um trilhão de frases possíveis ou pouco menos de 40 bits de entropia. Defino uma meta de menos de 10 palpites por frase de teste, o que significa que precisamos aprender em média quase 5 bits por consulta (já que o último é inútil). A cada palpite, recuperamos dois números e, grosso modo, quanto maior o potencial desses números, mais esperamos aprender.

Para simplificar a lógica, eu uso cada consulta com eficácia, duas perguntas separadas para que cada sequência de palpites seja composta de duas partes, um lado esquerdo interessado no número de posições corretas (estacas pretas no cérebro) e um lado direito interessado no número de caracteres corretos ( pegs totais). Aqui está um jogo típico:

Phrase:        chasteness legume such
 1: p0 ( 1/21) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -aaaaaaaaaaaabbbbbbbbbcccccccccdddddddddeeeeeeeeeeeeeeefffffffffgggggggggggghhhhhhhhhiiiiiiiiiiiiiiiiiijjjjjjkkkkkkkkkllllllllllllmmmmmmmmmnnnnnnnnnnnnoooooooooooopppppppppqqqrrrrrrrrrrrrssssssssssssssstttttttttuuuuuuuuuuuuvvvvvvwwwwwwxxxyyyyyyyyyzzzzzz
 2: p1 ( 0/ 8)   -  - -  ---    - ---aaaaaaaaaaaadddddddddeeeeeeeeeeeeeeefffffffffjjjjjjkkkkkkkkkllllllllllllooooooooooooqqqwwwwwwxxxyyyyyyyyyzzzzzz
 3: p1 ( 0/11) ----- ------ ---------bbbbbbbbbdddddddddeeeeeeeeeeeeeeefffffffffgggggggggggghhhhhhhhhiiiiiiiiiiiiiiiiiikkkkkkkkkllllllllllllppppppppptttttttttvvvvvv
 4: p1 ( 2/14) ---------- ------ ----ccccccccceeeeeeeeeeeeeeehhhhhhhhhkkkkkkkkkllllllllllllmmmmmmmmmooooooooooooqqqrrrrrrrrrrrrsssssssssssssssvvvvvvwwwwwwzzzzzz
 5: p3 ( 3/ 3) iaaiiaaiai iaaiia iaaiaaaaaaaaaaaabbbbbbbbbdddddddddiiiiiiiiiiiiiiiiiikkkkkkkkkllllllllllllqqquuuuuuuuuuuuvvvvvvyyyyyyyyy
 6: p3 ( 3/11) aaaasassaa aaaasa aaaaaaaaaaaaaaaabbbbbbbbbcccccccccdddddddddfffffffffhhhhhhhhhppppppppprrrrrrrrrrrrssssssssssssssstttttttttuuuuuuuuuuuuwwwwwwxxxyyyyyyyyy
 7: p4 ( 4/10) accretions shrive pews
 8: p4 ( 4/ 6) barometric terror heir
 9: p4 SUCCESS chasteness legume such

Adivinhar espaços

Cada palpite de espaço pode retornar no máximo 2 pinos pretos; Tentei construir suposições para retornar 0,1 e 2 pinos com probabilidades 1 / 4,1 / 2 e 1/4, respectivamente. Acredito que este é o melhor que você pode fazer por 1,5 bits de informações esperados. Eu decidi por uma sequência alternada para o primeiro palpite, seguido pelos gerados aleatoriamente, embora geralmente valha a pena começar a adivinhar na segunda ou terceira tentativa, pois sabemos as frequências de comprimento das palavras.

Contagem de conjuntos de caracteres de aprendizagem

Para as suposições do lado direito, escolho conjuntos de caracteres aleatórios (sempre 2 de e / i / a / s) para que o número esperado retornado seja metade do comprimento da frase. Uma variação mais alta significa mais informações e, na página da Wikipedia na distribuição binomial , estou estimando cerca de 3,5 bits por consulta (pelo menos nos primeiros antes que a informação se torne redundante). Depois que o espaçamento é conhecido, eu uso seqüências aleatórias das letras mais comuns no lado esquerdo, escolhidas para não entrar em conflito com o lado direito.

Agrupando os candidatos restantes

Este jogo é uma troca de eficiência de velocidade / consulta de computação e a enumeração dos candidatos restantes pode levar um tempo muito longo sem informações estruturadas, como caracteres específicos. Otimizei essa parte coletando principalmente informações invariantes à ordem das palavras, o que me permite pré-calcular as contagens do conjunto de caracteres para cada palavra individual e compará-las com as contagens aprendidas nas consultas. Agrupo essas contagens em um inteiro longo, usando o comparador de igualdade de máquina e somador para testar todas as minhas contagens de caracteres em parralel. Foi uma grande vitória. Posso acumular até 9 contagens no Long, mas achei que a coleta de informações adicionais não valia a pena e decidi de 6 a 7.

Depois que os candidatos restantes são conhecidos, se o conjunto for razoavelmente pequeno, eu escolho aquele com o menor log esperado de candidatos restantes. Se o conjunto for grande o suficiente para consumir esse tempo, eu escolho um pequeno conjunto de amostras.

Obrigado a todos. Este foi um jogo divertido e me atraiu a me inscrever no site.

Atualização: código limpo para simplicidade e legibilidade, com pequenos ajustes no algoritmo, resultando em uma pontuação aprimorada.
Pontuação original: 9447 (min 7, 13 máx., Média 9,45): 1876 segundos

O novo código é 278 linhas de Scala, abaixo

object HorseBatteryStapleMastermind {
  def main(args: Array[String]): Unit = run() print ()

  val n = 1000       // # phrases to run
  val verbose = true // whether to print each game

  //tweakable parameters
  val prob = 0.132   // probability threshold to guess spacing 
  val rngSeed = 11   // seed for random number generator
  val minCounts = 6  // minimum char-set counts before guessing

  val startTime = System.currentTimeMillis()
  def time = System.currentTimeMillis() - startTime

  val phraseList = io.Source.fromFile("pass.txt").getLines.toArray
  val wordList = io.Source.fromFile("words.txt").getLines.toArray

  case class Result(num: Int = 0, total: Int = 0, min: Int = Int.MaxValue, max: Int = 0) {
    def update(count: Int) = Result(num + 1, total + count, Math.min(count, min), Math.max(count, max))

    def resultString = f"#$num%4d  Total: $total%5d  Avg: ${total * 1.0 / num}%2.2f  Range: ($min%2d-$max%2d)"
    def timingString = f"Time:  Total: ${time / 1000}%5ds Avg: ${time / (1000.0 * num)}%2.2fs"
    def print() = println(s"$resultString\n$timingString")
  }

  def run(indices: Set[Int] = (0 until n).to[Set], prev: Result = Result()): Result = {
    if (verbose && indices.size < n) prev.print()

    val result = prev.update(Querent play Oracle(indices.head, phraseList(indices.head)))

    if (indices.size == 1) result else run(indices.tail, result)
  }

  case class Oracle(idx: Int, phrase: String) {
    def query(guess: String) = Grade.compute(guess, phrase)
  }

  object Querent {

    def play(oracle: Oracle, n: Int = 0, notes: Notes = Notes0): Int = {
      if (verbose && n == 0) println("=" * 100 + f"\nPhrase ${oracle.idx}%3d:    ${oracle.phrase}")

      val guess = notes.bestGuess
      val grade = oracle.query(guess)

      if (verbose) println(f"${n + 1}%2d: p${notes.phase} $grade $guess")

      if (grade.success) n + 1 else play(oracle, n + 1, notes.update(guess, grade))
    }

    abstract class Notes(val phase: Int) {
      def bestGuess: String
      def update(guess: String, grade: Grade): Notes
    }

    case object Notes0 extends Notes(0) {
      def bestGuess = GuessPack.firstGuess

      def genSpaceCandidates(grade: Grade): List[Spacing] = (for {
        wlen1 <- WordList.lengthRange
        wlen2 <- WordList.lengthRange
        spacing = Spacing(wlen1, wlen2, grade.total)
        if spacing.freq > 0
        if grade.black == spacing.black(bestGuess)
      } yield spacing).sortBy(-_.freq).toList

      def update(guess: String, grade: Grade) =
        Notes1(grade.total, genSpaceCandidates(grade), Limiter(Counts.withMax(grade.total - 2), Nil), GuessPack.stream)
    }

    case class Notes1(phraseLength: Int, spacingCandidates: List[Spacing], limiter: Limiter, guesses: Stream[GuessPack]) extends Notes(1) {
      def bestGuess = (chance match {
        case x if x < prob => guesses.head.spacing.take(phraseLength)
        case _             => spacingCandidates.head.mkString
      }) + guesses.head.charSet

      def totalFreq = spacingCandidates.foldLeft(0l)({ _ + _.freq })
      def chance = spacingCandidates.head.freq * 1.0 / totalFreq

      def update(guess: String, grade: Grade) = {
        val newLim = limiter.update(guess, grade)
        val newCands = spacingCandidates.filter(_.black(guess) == grade.black)

        newCands match {
          case best :: Nil if newLim.full => Notes3(newLim.allCandidates(best))
          case best :: Nil                => Notes2(best, newLim, guesses.tail)
          case _                          => Notes1(phraseLength, newCands, newLim, guesses.tail)
        }
      }
    }

    case class Notes2(spacing: Spacing, limiter: Limiter, guesses: Stream[GuessPack]) extends Notes(2) {
      def bestGuess = tile(guesses.head.pattern) + guesses.head.charSet

      def whiteSide(guess: String): String = guess.drop(spacing.phraseLength)
      def blackSide(guess: String): String = guess.take(spacing.phraseLength)

      def tile(guess: String) = spacing.lengths.map(guess.take).mkString(" ")
      def untile(guess: String) = blackSide(guess).split(" ").maxBy(_.length) + "-"

      def update(guess: String, grade: Grade) = {
        val newLim = limiter.updateBoth(whiteSide(guess), untile(guess), grade)

        if (newLim.full)
          Notes3(newLim.allCandidates(spacing))
        else
          Notes2(spacing, newLim, guesses.tail)
      }
    }

    case class Notes3(candidates: Array[String]) extends Notes(3) {
      def bestGuess = sample.minBy(expLogNRC)

      def update(guess: String, grade: Grade) =
        Notes3(candidates.filter(phrase => grade == Grade.compute(guess, phrase)))

      def numRemCands(phrase: String, guess: String): Int = {
        val grade = Grade.compute(guess, phrase)
        sample.count(phrase => grade == Grade.compute(guess, phrase))
      }

      val sample = if (candidates.size <= 32) candidates else candidates.sortBy(_.hashCode).take(32)

      def expLogNRC(guess: String): Double = sample.map(phrase => Math.log(1.0 * numRemCands(phrase, guess))).sum
    }

    case class Spacing(wl1: Int, wl2: Int, phraseLength: Int) {
      def wl3 = phraseLength - 2 - wl1 - wl2
      def lengths = Array(wl1, wl2, wl3)
      def pos = Array(wl1, wl1 + 1 + wl2)
      def freq = lengths.map(WordList.freq).product
      def black(guess: String) = pos.count(guess(_) == ' ')
      def mkString = lengths.map("-" * _).mkString(" ")
    }

    case class Limiter(counts: Counts, guesses: List[String], extraGuesses: List[(String, Grade)] = Nil) {
      def full = guesses.size >= minCounts

      def update(guess: String, grade: Grade) =
        if (guesses.size < Counts.Max)
          Limiter(counts.update(grade.total - 2), guess :: guesses)
        else
          Limiter(counts, guesses, (guess, grade) :: extraGuesses)

      def updateBoth(whiteSide: String, blackSide: String, grade: Grade) =
        Limiter(counts.update(grade.total - 2).update(grade.black - 2), blackSide :: whiteSide :: guesses)

      def isCandidate(phrase: String): Boolean = extraGuesses forall {
        case (guess, grade) => grade == Grade.compute(guess, phrase)
      }

      def allCandidates(spacing: Spacing): Array[String] = {

        val order = Array(0, 1, 2).sortBy(-spacing.lengths(_)) //longest word first
        val unsort = Array.tabulate(3)(i => order.indexWhere(i == _))

        val wordListI = WordList.byLength(spacing.lengths(order(0)))
        val wordListJ = WordList.byLength(spacing.lengths(order(1)))
        val wordListK = WordList.byLength(spacing.lengths(order(2)))

        val gsr = guesses.reverse
        val countsI = wordListI.map(Counts.compute(_, gsr).z)
        val countsJ = wordListJ.map(Counts.compute(_, gsr).z)
        val countsK = wordListK.map(Counts.compute(_, gsr).z)

        val rangeI = 0 until wordListI.size
        val rangeJ = 0 until wordListJ.size
        val rangeK = 0 until wordListK.size

        (for {
          i <- rangeI.par
          if Counts(countsI(i)) <= counts
          j <- rangeJ
          countsIJ = countsI(i) + countsJ(j)
          if Counts(countsIJ) <= counts
          k <- rangeK
          if countsIJ + countsK(k) == counts.z
          words = Array(wordListI(i), wordListJ(j), wordListK(k))
          phrase = unsort.map(words).mkString(" ")
          if isCandidate(phrase)
        } yield phrase).seq.toArray
      }
    }

    object Counts {
      val Max = 9
      val range = 0 until Max
      def withMax(size: Int): Counts = Counts(range.foldLeft(size.toLong) { (z, i) => (z << 6) | size })

      def compute(word: String, x: List[String]): Counts = x.foldLeft(Counts.withMax(word.length)) { (c: Counts, s: String) =>
        c.update(if (s.last == '-') Grade.computeBlack(word, s) else Grade.computeTotal(word, s))
      }
    }

    case class Counts(z: Long) extends AnyVal {
      @inline def +(that: Counts): Counts = Counts(z + that.z)
      @inline def apply(i: Int): Int = ((z >> (6 * i)) & 0x3f).toInt
      @inline def size: Int = this(Counts.Max)

      def <=(that: Counts): Boolean =
        Counts.range.forall { i => (this(i) <= that(i)) && (this.size - this(i) <= that.size - that(i)) }

      def update(c: Int): Counts = Counts((z << 6) | c)
      override def toString = Counts.range.map(apply).map(x => f"$x%2d").mkString(f"Counts[$size%2d](", " ", ")")
    }

    case class GuessPack(spacing: String, charSet: String, pattern: String)

    object GuessPack {
      util.Random.setSeed(rngSeed)
      val RBF: Any => Boolean = _ => util.Random.nextBoolean() //Random Boolean Function

      def genCharsGuess(q: Char => Boolean): String =
        (for (c <- 'a' to 'z' if q(c); j <- 1 to WordList.maxCount(c)) yield c).mkString

      def charChooser(i: Int)(c: Char): Boolean = c match {
        case 'e' => Array(true, true, true, false, false, false)(i % 6)
        case 'i' => Array(false, true, false, true, false, true)(i % 6)
        case 'a' => Array(true, false, false, true, true, false)(i % 6)
        case 's' => Array(false, false, true, false, true, true)(i % 6)
        case any => RBF(any)
      }

      def genSpaceGuess(q: Int => Boolean = RBF): String = genPatternGuess(" -", q)

      def genPatternGuess(ab: String, q: Int => Boolean = RBF) =
        (for (i <- 0 to 64) yield (if (q(i)) ab(0) else ab(1))).mkString

      val firstGuess = genSpaceGuess(i => (i % 2) == 1) + genCharsGuess(_ => true)

      val stream: Stream[GuessPack] = Stream.from(0).map { i =>
        GuessPack(genSpaceGuess(), genCharsGuess(charChooser(i)), genPatternGuess("eias".filter(charChooser(i))))
      }
    }
  }

  object WordList {
    val lengthRange = wordList.map(_.length).min until wordList.map(_.length).max

    val byLength = Array.tabulate(lengthRange.end)(i => wordList.filter(_.length == i))

    def freq(wordLength: Int): Long = if (lengthRange contains wordLength) byLength(wordLength).size else 0

    val maxCount: Map[Char, Int] = ('a' to 'z').map(c => (c -> wordList.map(_.count(_ == c)).max * 3)).toMap
  }

  object Grade {
    def apply(black: Int, white: Int): Grade = Grade(black | (white << 8))
    val Success = Grade(-1)

    def computeBlack(guess: String, phrase: String): Int = {
      @inline def posRange: Range = 0 until Math.min(guess.length, phrase.length)
      @inline def sameChar(p: Int): Boolean = (guess(p) == phrase(p)) && guess(p) != '-'
      posRange count sameChar
    }

    def computeTotal(guess: String, phrase: String): Int = {
      @inline def minCount(c: Char): Int = Math.min(phrase.count(_ == c), guess.count(_ == c))
      minCount(' ') + ('a' to 'z').map(minCount).sum
    }

    def compute(guess: String, phrase: String): Grade = {
      val black = computeBlack(guess, phrase)
      if (black == guess.length && black == phrase.length)
        Grade.Success
      else
        Grade(black, computeTotal(guess, phrase) - black)
    }
  }

  case class Grade(z: Int) extends AnyVal {
    def black: Int = z & 0xff
    def white: Int = z >> 8
    def total: Int = black + white
    def success: Boolean = this == Grade.Success
    override def toString = if (success) "SUCCESS" else f"($black%2d/$white%2d)"
  }
}

C - total: 37171, min: 24, máx: 55, tempo: cerca de 10 segundos

Peguei emprestada a ideia de Ray para descobrir o comprimento de cada palavra, adivinhando com espaços, exceto que estou fazendo uma pesquisa binária em vez de linear, o que me poupa muitos palpites.

Depois de determinar o comprimento de uma palavra, acho que com a primeira palavra que corresponde ao seu comprimento e registro o número de posições corretas. Depois, seleciono a primeira palavra do conjunto de todas as palavras que compartilham o mesmo número de posições com a minha primeira suposição que a palavra misteriosa. Para minha terceira suposição, seleciono a primeira palavra do conjunto de todas as palavras que compartilham o mesmo número de posições com minha primeira suposição que a palavra mistério e o mesmo número de posições que minha segunda suposição com a palavra mistério, etc.

Usando esse método, sou capaz de adivinhar cada palavra, uma de cada vez, em cerca de 5 a 10 palpites. Obviamente, a terceira palavra eu tenho que fazer um pouco diferente, porque não sei o comprimento, mas o método é semelhante. Eu uso um arquivo que contém uma matriz do número de posições que cada palavra compartilha em comum que eu pré-computei. A maior parte do tempo de execução é incorrida ao carregar os dados pré-computados. Você pode baixar tudo aqui .

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

#define DICTIONARY_SIZE 10000
#define PHRASE_COUNT 1000
#define MAX_STRING 512
#define MAX_SAVED_GUESSES 100
#define DEBUG

typedef struct {
    int wordlen;
    char word[MAX_STRING];
} dictionary_entry;

static int g_guesses;
static int g_max_word_len;
static int g_min_word_len;
static char *g_password;
static dictionary_entry g_dictionary[DICTIONARY_SIZE];
static char g_phrases[PHRASE_COUNT][MAX_STRING];
static int g_pos_matrix[DICTIONARY_SIZE][DICTIONARY_SIZE];

/* Returns true if the guess was correct and false otherwise */
int guess(char *in, int *chars, int *positions)
{
    int i, j, contains;
    char c, pw[1024];

    /* Increment the total guess count */
    g_guesses++;

    strcpy(pw, g_password);
    *chars = 0;
    *positions = 0;
    for (i = 0; (i < strlen(in)) && (i < strlen(pw)); i++)
        if (in[i] == pw[i])
            (*positions)++;
    if (strcmp(in, pw) == 0) {
        *chars = -1;
        return 1;
    }
    for (i = 0; i < strlen(in); i++) {
        for (j = 0; j < strlen(pw); j++) {
            if (pw[j] == in[i]) {
                (*chars)++;
                pw[j] = '*';
                break;
            }
        }
    }
    (*chars) -= (*positions);
    return 0;
}

int checker() {
    char guess_str[MAX_STRING], *guess_ptr;
    int i, j, saved_guesses, word;
    int guesses;
    int chars, positions;
    int wordlen[3], wordidx[3];
    int guesswordidx[MAX_SAVED_GUESSES];
    int guesswordpos[MAX_SAVED_GUESSES];
    int tryit, finished;

    /* Initialize everything */
    finished = 0;
    guess_ptr = guess_str;
    for (i = 0; i < 3; i++) {
        wordlen[i] = -1;
        wordidx[i] = -1;
    }

    guesses = 0;
    for (word = 0; word < 3; word++) {
        saved_guesses = 0;

        // If we're not on the last word, figure out how long the word is by
        // doing a binary search using spaces
        if (word < 2) {
            int a = g_min_word_len, b = g_max_word_len;
            int c;
            while (wordlen[word] == -1) {
                c = (b + a) / 2;
                for (i = 0; i <= c; i++) {
                    guess_ptr[i] = ' ';
                }
                guess_ptr[i] = '\0';
                guess(guess_str, &chars, &positions);
                guesses++;
                if (positions == 0) {
                    if (b - a < 2)
                        wordlen[word] = b;
                    a = c;
                } else {
                    if (b - a < 2)
                        wordlen[word] = c;
                    b = c;
                }
            }
            #ifdef DEBUG
            printf("\tLength of next word is %d.\n", wordlen[word]);
            #endif
        }


        // Look for words using matching positions from previous guesses to improve our search
        for (i = 0; i < DICTIONARY_SIZE; i++) {
            tryit = 1;
            for (j = 0; j < saved_guesses; j++) {
                if (g_pos_matrix[guesswordidx[j]][i] != guesswordpos[j]) {
                    tryit = 0;
                    break;
                }
            }
            // If the word length is incorrect then don't bother
            if ((word < 2) && (g_dictionary[i].wordlen != wordlen[word]))
                tryit = 0;
            if (tryit) {
                strcpy(guess_ptr, g_dictionary[i].word);
                guess(guess_str, &chars, &positions);
                guesses++;
                #ifdef DEBUG
                printf("\tWe guessed \"%s\", it had %d correct positions.\n", g_dictionary[i].word, positions);
                #endif
                guesswordidx[saved_guesses] = i;
                guesswordpos[saved_guesses] = positions;
                saved_guesses++;

                // If we're on the last word and all the positions matched then check if we've found the phrase
                if ((word == 2) && (g_dictionary[i].wordlen == positions)) {
                    sprintf(guess_ptr, "%s %s %s", g_dictionary[wordidx[0]].word, g_dictionary[wordidx[1]].word, g_dictionary[i].word);
                    guesses++;
                    if (guess(guess_ptr, &chars, &positions)) {
                        finished = 1;
                        break;
                    }
                }
            }
        }
        wordidx[word] = guesswordidx[saved_guesses - 1];
        wordlen[word] = g_dictionary[guesswordidx[saved_guesses - 1]].wordlen;
        #ifdef DEBUG
        printf("\tThe next word is \"%s\".\n", g_dictionary[wordidx[word]].word);
        #endif
        guess_ptr += wordlen[word] + 1;
        for (i = 0; i < guess_ptr - guess_str; i++) {
            guess_str[i] = '#';
        }
    }
    #ifdef DEBUG
    if (finished) {
        sprintf(guess_str, "%s %s %s", g_dictionary[wordidx[0]].word, g_dictionary[wordidx[1]].word, g_dictionary[wordidx[2]].word);
        printf("\tPhrase is \"%s\". Found in %d guesses.\n", guess_str, guesses);
    } else {
        printf("Oh noes! Something went wrong!\n");
        exit(1);
    }
    #endif
    return guesses;
}

int main(int argc, char **argv)
{
    FILE *dictfp, *phrasefp, *precompfp;
    int i, j, total_count, chars, positions;

    g_max_word_len = 0;
    g_min_word_len = 9999;
    dictfp = fopen("dictionary.txt", "r");
    for (i = 0; i < DICTIONARY_SIZE; i++) {
        fgets(g_dictionary[i].word, MAX_STRING, dictfp);
        while (!isalpha(g_dictionary[i].word[strlen(g_dictionary[i].word) - 1]))
            g_dictionary[i].word[strlen(g_dictionary[i].word) - 1] = '\0';
        g_dictionary[i].wordlen = strlen(g_dictionary[i].word);
        if (g_dictionary[i].wordlen < g_min_word_len)
            g_min_word_len = g_dictionary[i].wordlen;
        if (g_dictionary[i].wordlen > g_max_word_len)
            g_max_word_len = g_dictionary[i].wordlen;
    }
    fclose(dictfp);

    phrasefp = fopen("phrases.txt", "r");
    for (i = 0; i < PHRASE_COUNT; i++) {
        fgets(g_phrases[i], MAX_STRING, phrasefp);
        while (!isalpha(g_phrases[i][strlen(g_phrases[i]) - 1]))
            g_phrases[i][strlen(g_phrases[i]) - 1] = '\0';
    }
    fclose(phrasefp);

    precompfp = fopen("precomp.txt", "r");
    for (i = 0; i < DICTIONARY_SIZE; i++) {
        for (j = 0; j < DICTIONARY_SIZE; j++) {
            fscanf(precompfp, "%d ", &(g_pos_matrix[i][j]));
        }
    }

    g_guesses = 0;
    int min = 9999, max = 0, g;
    for (i = 0; i < PHRASE_COUNT; i++) {
        g_password = g_phrases[i];
        #ifdef DEBUG
        printf("Testing passphrase \"%s\"...\n", g_password);
        #endif
        g = checker();
        if (g < min) min = g;
        if (g > max) max = g;
    }

    printf("Total %d. Min %d. Max %d.\n", g_guesses, min, max);
    return 0;
}

Também é divertido observar as palavras:

Testing passphrase "somebody sighed intimater"...
    Length of next word is 8.
    We guessed "abashing", it had 0 correct positions.
    We guessed "backlogs", it had 1 correct positions.
    We guessed "befitted", it had 0 correct positions.
    We guessed "caldwell", it had 0 correct positions.
    We guessed "disgusts", it had 0 correct positions.
    We guessed "encroach", it had 0 correct positions.
    We guessed "forenoon", it had 3 correct positions.
    We guessed "hotelman", it had 2 correct positions.
    We guessed "somebody", it had 8 correct positions.
    The next word is "somebody".
    Length of next word is 6.
    We guessed "abacus", it had 0 correct positions.
    We guessed "baboon", it had 0 correct positions.
    We guessed "celery", it had 0 correct positions.
    We guessed "diesel", it had 2 correct positions.
    We guessed "dimple", it had 1 correct positions.
    We guessed "duster", it had 1 correct positions.
    We guessed "hinged", it had 3 correct positions.
    We guessed "licked", it had 3 correct positions.
    We guessed "sighed", it had 6 correct positions.
    The next word is "sighed".
    We guessed "aaas", it had 0 correct positions.
    We guessed "b", it had 0 correct positions.
    We guessed "c", it had 0 correct positions.
    We guessed "debauchery", it had 2 correct positions.
    We guessed "deceasing", it had 0 correct positions.
    We guessed "echinoderm", it had 3 correct positions.
    We guessed "enhanced", it had 1 correct positions.
    We guessed "intimater", it had 9 correct positions.
    The next word is "intimater".
    Phrase is "somebody sighed intimater". Found in 38 guesses.

Python 3.4 - min: 21, máx: 29, total: 25146, tempo: 20min

min: 30, máx: 235, total: 41636, tempo: 4min

Atualizar:

1. Use a pesquisa binária para encontrar espaço. A idéia é emprestada da resposta de Orby . Um ponto que otimizei é que, se você encontrar 2 espaços em um intervalo ao pesquisar o primeiro espaço, poderá restringir o intervalo de pesquisa do segundo espaço.
2. Salve suposições erradas junto com o resultado. Compare com eles nas seguintes suposições. Isso pode economizar muito.
3. Reduza a contagem de letras para 12, graças à atualização nº 2.

Esse método não usa aleatoriedade para que a pontuação não seja alterada.

Primeiro, use suposições como as seguintes para encontrar o primeiro e o segundo espaços na resposta.

. ......................
.. .....................
... ....................
.... ...................
# more follows, until two spaces found.

Então, conte a ocorrência de cada letra, adivinhando aaaaa..., bbbbb....... Depois disso, custará cerca de 40 etapas. De fato, não precisamos tentar todas as letras e podemos julgá-las em ordem arbitrária. Na maioria dos casos, tentar cerca de 20 letras é suficiente. Aqui eu escolho 21.

Agora, ele sabe o tamanho da primeira e da segunda palavra para poder filtrar uma lista de candidatos para essas duas palavras. Normalmente, restam cerca de 100 candidatos para cada um.

Depois, apenas enumere a primeira e a segunda palavra. Depois que as duas primeiras palavras são enumeradas, podemos inferir toda a terceira palavra válida, pois sabemos que ela conta.

Para otimizar a velocidade, eu uso o concurrent.futurespara adicionar multiprocessamento ao programa. Então você precisa do Python 3 para executá-lo e eu o testei com o Python 3.4 na minha caixa do Linux. Além disso, você precisa instalar numpy.

import sys
import functools
from collections import defaultdict
from concurrent.futures import ProcessPoolExecutor
import numpy as np


def debug(*args, **kwargs):
    return
    print(*args, **kwargs)


def compare(answer, guess):
    b = sum(1 for x, y in zip(guess, answer) if x == y)
    a = 0
    c = defaultdict(int)
    for x in answer:
        c[x] += 1

    for x in guess:
        if c.get(x, 0) > 0:
            a += 1
            c[x] -= 1
    return a, b


def checker_task(guesser):
    @functools.wraps(guesser)
    def task(case):
        i, answer = case
        return (i, answer, run_checker(answer, guesser))
    return task


def run_checker(answer, guesser):
    guess_count = 0
    guesser = guesser()
    guess = next(guesser)
    while True:
        guess_count += 1
        if answer == guess:
            break
        try:
            guess = guesser.send(compare(answer, guess))
        except StopIteration:
            raise Exception('Invalid guesser')
    try:
        guesser.send((-1, -1))
    except StopIteration:
        pass
    return guess_count


# Preprocessing
words = list(map(str.rstrip, open('dict.txt')))
words_with_len = defaultdict(list)
for word in words:
    words_with_len[len(word)].append(word)

M = 12
chars = 'eiasrntolcdupmghbyfvkwzxjq'[:M]
char_ord = {c: i for i, c in enumerate(chars)}

def get_fingerprint(word):
    counts = [0] * (M + 1)
    for c in word:
        counts[char_ord.get(c, M)] += 1
    return tuple(counts[:-1])

word_counts = {word: np.array(get_fingerprint(word)) for word in words}

# End of preprocessing


# @profile
@checker_task
def guesser1():
    # Find spaces using binary search
    max_word_len = max(map(len, words))
    max_len = max_word_len * 3 + 2
    # debug('max_len', max_len)
    s_l = [1, 3]
    s_r = [max_len - 3, max_len - 1]

    for i in range(2):
        while s_l[i] + 1 < s_r[i]:
            # debug(list(zip(s_l, s_r)))
            mid = (s_l[i] + s_r[i]) // 2
            guess = '.' * s_l[i] + ' ' * (mid - s_l[i])
            a, b = yield guess
            if b > 1 and i == 0:
                s_l[1] = max(s_l[1], s_l[0] + 2)
                s_r[1] = min(s_r[1], mid)
                s_r[0] = mid - 2
            elif b > 0:
                s_r[i] = mid
            else:
                s_l[i] = mid
        if i == 0:
            s_l[1] = max(s_l[1], s_l[0] + 2)

    spaces = s_l
    del s_l, s_r

    word_lens = [spaces[0], spaces[1] - spaces[0] - 1, None]
    debug('word_lens', word_lens)
    debug('spaces', spaces)
    char_counts = [0] * M
    for i, c in enumerate(chars):
        guess = c * max_len
        _, char_counts[i] = yield guess

    char_counts = np.array(char_counts)

    candidates = [words_with_len[word_lens[0]], words_with_len[word_lens[1]], words]
    for i, ws in enumerate(candidates):
        candidates[i] = [word for word in ws if np.alltrue(char_counts >= word_counts[word])]
    P = defaultdict(list)
    for word in candidates[2]:
        P[get_fingerprint(word)].append(word)
    debug('candidates', list(map(len, candidates)))

    wrong_guesses = []
    # @profile
    def search(i, counts, current):
        if i == 2:
            rests = tuple(char_counts - counts)
            for word in P[rests]:
                current[i] = word
                guess_new = ' '.join(current)
                for guess, t in wrong_guesses:
                    if t != compare(guess_new, guess):
                        break
                else:
                    yield current
            return
        for word in candidates[i]:
            counts += word_counts[word]
            if np.alltrue(char_counts >= counts):
                current[i] = word
                yield from search(i + 1, counts, current)
            counts -= word_counts[word]

    try_count = 0
    for result in search(0, np.array([0] * M), [None] * 3):
        guess = ' '.join(result)
        a, b = yield guess
        try_count += 1
        if a == -1:
            break
        wrong_guesses.append((guess, (a, b)))
    debug('try_count', try_count)


def test(test_file, checker_task):
    cases = list(enumerate(map(str.rstrip, open(test_file))))
    scores = [None] * len(cases)
    with ProcessPoolExecutor() as executor:
        for i, answer, score in executor.map(checker_task, cases):
            print('-' * 80)
            print('case', i)
            scores[i] = score
            print('{}: {}'.format(answer, score))
            sys.stdout.flush()
    print(scores)
    print('sum:{} max:{} min:{}'.format(sum(scores), max(scores), min(scores)))


if __name__ == '__main__':
    test(sys.argv[1], guesser1)

Java 13.923 (min: 11, máx: 17)

Atualização: pontuação melhorada (quebrou o <14 / crack avg!), Novo código

• Verificação de caracteres conhecidos agora mais densos (agora ABABAB *, em vez de -AAAA *)
• Quando nenhum caractere conhecido estiver disponível, duas incógnitas serão contadas em um único palpite
• Adivinhações erradas são armazenadas e usadas para verificar possíveis correspondências
• Alguns ajustes constantes com a nova lógica em vigor

Postagem original

Decidi me concentrar completamente na quantidade de palpites em vez de no desempenho (de acordo com as regras). Isso resultou em um programa inteligente muito lento.

Em vez de roubar os programas conhecidos, decidi escrever tudo do zero, mas acontece que algumas / a maioria das idéias são iguais.

Algoritmo

É assim que o meu funciona:

1. Faça uma única consulta que resulte na quantidade de e e caracteres no total
2. Em seguida, procuramos os espaços, acrescentando alguns caracteres desconhecidos no final para obter uma contagem de caracteres
3. Quando os espaços são encontrados, ainda queremos descobrir mais contagens de caracteres. Nesse meio tempo, também obtenho mais dados sobre os personagens conhecidos (se eles estiverem em posições pares) que me ajudarão a eliminar muitas frases.
4. Quando atingimos um determinado limite (rastreio / erro), ele gera todas as frases possíveis e inicia uma pesquisa binária, na maioria das vezes ainda anexando caracteres desconhecidos no final.
5. Finalmente fazemos algumas suposições!

Palpites de exemplo

Aqui está um exemplo real:

Phase 1 (find the e's and total character count):
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbccccccccccccccccccddddddddddddddddddffffffffffffffffffgggggggggggggggggghhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkllllllllllllllllllmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnooooooooooooooooooppppppppppppppppppqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrssssssssssssssssssttttttttttttttttttuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzz
Phase 2 (find the spaces):
        ----------------iiiiiiiiiiiiiiiiii
              ----------aaaaaaaaaaaa
           -------------sssssssssssssss
          --------------rrrrrrrrrrrr
         ---------------nnnnnnnnnnn
                 -------ttttttttt
               ---------oooooooo
                --------lllllll
Phase 3 (discovery of characters, collecting odd/even information):
eieieieieieieieieieieieicccccc
ararararararararararararddddd
ntntntntntntntntntntntntuuuuu
Phase 4 (binary search with single known character):
------------r------------ppppp
Phase 5 (actual guessing):
enveloper raging charter
racketeer rowing halpern

Como meu código nunca realmente se concentra em palavras únicas e apenas coleta informações sobre a frase completa, ele precisa gerar muitas dessas frases, tornando-o muito lento.

Código

E finalmente, aqui está o código (feio), nem tente entendê-lo, desculpe:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MastermindV3 {

    // Order of characters to analyze:
    // eiasrntolcdupmghbyfvkwzxjq - 97
    private int[] lookup = new int[] {4, 8, 0, 18, 17, 13, 19, 14, 11, 2, 3, 20, 15, 12, 6, 7, 1, 24, 5, 21, 10, 22, 25, 23, 9, 16};

    public static void main(String[] args) throws Exception {
        new MastermindV3().run();
    }

    private void run() throws Exception {
        long beforeTime = System.currentTimeMillis();
        Map<Integer, List<String>> wordMap = createDictionary();
        List<String> passPhrases = createPassPhrases();

        int min = Integer.MAX_VALUE;
        int max = 0;
        for(String phrase:passPhrases) {

            int before = totalGuesses;
            solve(wordMap, phrase);
            int amount = totalGuesses - before;

            min = Math.min(min, amount);
            max = Math.max(max, amount);
            System.out.println("Amount of guesses: "+amount+" : min("+min+") max("+max+")");
        }
        System.out.println("Total guesses: " + totalGuesses);
        System.out.println("Took: "+ (System.currentTimeMillis()-beforeTime)+" ms");
    }

    /**
     * From the original question post:
     * I've added a boolean for the real passphrase.
     * I'm using this method to check previous guesses against my own matches (not part of Mastermind guesses)
     */
    int totalGuesses = 0;
    int[] guess(String in, String pw, boolean againstRealPassphrase) {
        if(againstRealPassphrase) {
            //Only count the guesses against the password, not against our own previous choices
            totalGuesses++;
        }
        int chars=0, positions=0;
        for(int i=0;i<in.length()&&i<pw.length();i++){
            if(in.charAt(i)==pw.charAt(i))
                positions++;
        }
        if(positions == pw.length() && pw.length()==in.length())
            return new int[]{-1,positions};
        for(int i=0;i<in.length();i++){
            String c = String.valueOf(in.charAt(i));
            if(pw.contains(c)){
                pw = pw.replaceFirst(c, "");
                chars++;
            }
        }
        chars -= positions;
        return new int[]{chars,positions};
    }

    private void solve(Map<Integer, List<String>> wordMap, String pw) {

        // Do one initial guess which gives us two things:
        // The amount of characters in total
        // The amount of e's

        int[] initialResult = guess(Facts.INITIAL_GUESS, pw, true);

        // Create the object that tracks all the known facts/bounds:
        Facts facts = new Facts(initialResult);

        // Determine a pivot and find the spaces (binary search)
        int center = ((initialResult[0] + initialResult[1]) / 3) + 1;
        findSpaces(center, facts, pw);

        // When finished finding the spaces (and some character information)
        // We can calculate the lengths:
        int length1 = (facts.spaceBounds[0]-1);
        int length2 = (facts.spaceBounds[2]-facts.spaceBounds[0]-1);
        int length3 = (facts.totalLength-facts.spaceBounds[2]+2);

        // Next we enter a discovery loop where we find out two things:
        // 1) The amount of a new character
        // 2) How many of a known character are on an even spot
        int oddPtr = 0;
        int pairCnt = 0;

        // Look for more characters, unless we have one HUGE word, which should be brute forcible easily
        int maxLength = Math.max(length1, Math.max(length2, length3));
        while(maxLength<17 && !facts.doneDiscovery()) { // We don't need all characters, the more unknowns the slower the code, but less guesses

            // Try to generate a sequence with ABABABABAB... with two characters with known length
            String testPhrase = "";
            int expected = 0;
            while(oddPtr < facts.charPtr && (facts.oddEvenUsed[oddPtr]!=-1 || facts.charBounds[lookup[oddPtr]] == 0)) {
                oddPtr++;
            }
            // If no character unknown, try pattern -A-A-A-A-A-A-A... with just one known pattern
            int evenPtr = oddPtr+1;
            while(evenPtr < facts.charPtr && (facts.oddEvenUsed[evenPtr]!=-1 || facts.charBounds[lookup[evenPtr]] == 0)) {
                evenPtr++;
            }

            if(facts.oddEvenUsed[oddPtr]==-1 && facts.charBounds[lookup[oddPtr]] > 0 && oddPtr < facts.charPtr) {
                if(facts.oddEvenUsed[evenPtr]==-1 && facts.charBounds[lookup[evenPtr]] > 0 && evenPtr < facts.charPtr) {
                    for(int i = 0; i < (facts.totalLength + 3) / 2; i++) {
                        testPhrase += ((char)(lookup[oddPtr] + 97) +""+ ((char)(lookup[evenPtr] + 97)));
                    }
                    expected += facts.charBounds[lookup[oddPtr]] + facts.charBounds[lookup[evenPtr]];
                } else {
                    for(int i = 0; i < (facts.totalLength + 3) / 2; i++) {
                        testPhrase += ((char)(lookup[oddPtr] + 97) + "-");
                    }
                    expected += facts.charBounds[lookup[oddPtr]];
                }
            }

            // If we don't have known characters to explore, use the phrase-length part to discover the count of an unknown character
            boolean usingTwoNew = false;
            if(testPhrase.length() == 0 && facts.charPtr < 25) {
                usingTwoNew = true;
                //Fill with a new character
                while(testPhrase.length() < (facts.totalLength+2)) {
                    testPhrase += (char)(lookup[facts.charPtr+1] + 97);
                }
            } else {
                while(testPhrase.length() < (facts.totalLength+2)) {
                    testPhrase += "-";
                }
            }

            // Use the part after the phrase-length to discover the count of an unknown character
            for(int i = 0; i<facts.charBounds[lookup[facts.charPtr]];i++) {
                testPhrase += (char)(lookup[facts.charPtr] + 97);
            }

            // Do the actual guess:
            int[] result = guess(testPhrase, pw, true);

            // Process the results, store the derived facts:
            if(oddPtr < facts.charPtr) {
                if(evenPtr < facts.charPtr) {
                    facts.oddEvenUsed[evenPtr] = pairCnt;
                }
                facts.oddEvenUsed[oddPtr] = pairCnt;
                facts.oddEvenPairScore[pairCnt] = result[1];
                pairCnt++;

            }
            if(usingTwoNew) {
                facts.updateCharBounds(result[0]);
                if(result[1] > 0) {
                    facts.updateCharBounds(result[1]);
                }
            } else {
                facts.updateCharBounds((result[0]+result[1]) - expected);
            }
        }

        // Next we generate a list of possible phrases for further analysis:
        List<String> matchingPhrases = new ArrayList<String>();

        // Hacked in for extra speed, loop over longest word first:
        int[] index = sortByLength(length1, length2, length3);

        @SuppressWarnings("unchecked")
        List<String>[] lists = new List[3];
        lists[index[0]] = wordMap.get(length1);
        lists[index[1]] = wordMap.get(length2);
        lists[index[2]] = wordMap.get(length3);

        for(String w1:lists[0]) {
            //Continue if (according to our facts) this word is a possible partial match:
            if(facts.partialMatches(w1)) {
                for(String w2:lists[1]) {
                    //Continue if (according to our facts) this word is a partial match:
                    if(facts.partialMatches(w1+w2)) {
                        for(String w3:lists[2]) {

                            // Reconstruct phrase in correct order:
                            String[] possiblePhraseParts = new String[] {w1, w2, w3};
                            String possiblePhrase = possiblePhraseParts[index[0]]+" "+possiblePhraseParts[index[1]]+" "+possiblePhraseParts[index[2]];

                            //If the facts form a complete match, continue:
                            if(facts.matches(possiblePhrase)) {
                                matchingPhrases.add(possiblePhrase);
                            }
                        }
                    }
                }
            }
        }
        //Sometimes we are left with too many matching phrases, do a smart match on them, binary search style:
        while(matchingPhrases.size() > 8) {
            int lowestError = Integer.MAX_VALUE;
            boolean filterCharacterIsKnown = false;
            int filterPosition = 0;
            int filterValue = 0;
            String filterPhrase = "";

            //We need to filter some more before trying:
            int targetBinaryFilter = matchingPhrases.size()/2;
            int[][] usedCharacters = new int[facts.totalLength+2][26];
            for(String phrase:matchingPhrases) {
                for(int i = 0; i<usedCharacters.length;i++) {
                    if(phrase.charAt(i) != ' ') {
                        usedCharacters[i][phrase.charAt(i)-97]++;
                    }
                }
            }

            //Locate a certain character/position combination which is closest to 50/50:
            for(int i = 0; i<usedCharacters.length;i++) {
                for(int x = 0; x<usedCharacters[i].length;x++) {
                    int error = Math.abs(usedCharacters[i][x]-targetBinaryFilter);
                    if(error < lowestError || (error == lowestError && !filterCharacterIsKnown)) {

                        //If we do the binary search with a known character we can append more information as well
                        //Reverse lookup if the character is known
                        filterCharacterIsKnown = false;
                        for(int f = 0; f<facts.charPtr; f++) {
                            if(lookup[f]==x) {
                                filterCharacterIsKnown = true;
                            }
                        }

                        filterPosition = i;
                        filterValue = x;
                        filterPhrase = "";
                        for(int e = 0; e<i; e++) {
                            filterPhrase += "-"; 
                        }
                        filterPhrase += ""+((char)(x+97));
                        lowestError = error;
                    }
                }
            }

            //Append new character information as well:
            while(filterPhrase.length() <= (facts.totalLength+2)) {
                filterPhrase += "-";
            }

            if(filterCharacterIsKnown && facts.charPtr < 26) {
                //Append new character to discover
                for(int i = 0; i<facts.charBounds[lookup[facts.charPtr]];i++) {
                    filterPhrase += (char)(lookup[facts.charPtr] + 97);
                }
            }
            //Guess with just that character:
            int[] result = guess(filterPhrase, pw, true);

            //Filter the 50%
            List<String> inFilter = new ArrayList<String>();
            for(String phrase:matchingPhrases) {
                if(phrase.charAt(filterPosition) == (filterValue+97)) {
                    inFilter.add(phrase);
                }
            }
            if(result[1]>0) {
                //If we have a match, retain all:
                matchingPhrases.retainAll(inFilter);
            } else {
                //No match, filter all
                matchingPhrases.removeAll(inFilter);
            }

            if(filterCharacterIsKnown && facts.charPtr < 26) {
                //Finally filter according to the discovered character:
                facts.updateCharBounds((result[0]+result[1]) - 1);

                List<String> toKeep = new ArrayList<String>();
                for(String phrase:matchingPhrases) {
                    if(facts.matches(phrase)) {
                        toKeep.add(phrase);
                    }
                }
                matchingPhrases = toKeep;
            }

        }

        // Finally we have some phrases left, try them!
        for(String phrase:matchingPhrases) {

            if(facts.matches(phrase)) {
                int[] result = guess(phrase, pw, true);

                System.out.println(phrase+" "+Arrays.toString(result));
                if(result[0]==-1) {
                    return;
                }
                // No match, update facts:
                facts.storeInvalid(phrase, result);
            }
        }
        throw new IllegalArgumentException("Unable to solve!?");
    }

    private int[] sortByLength(int length1, int length2, int length3) {
        //God this code is ugly, can't be bothered to fix
        int[] index;
        if(length3 > length2 && length2 > length1) {
             index = new int[] {2, 1, 0};
        } else if(length3 > length1 && length1 > length2) {
             index = new int[] {2, 0, 1};
        } else if(length2 > length3 && length3 > length1) {
             index = new int[] {1, 2, 0};
        } else if(length2 > length1 && length1 > length3) {
             index = new int[] {1, 0, 2};
        } else if(length2 > length3) {
            index = new int[]{0, 1, 2};
        } else {
            index = new int[]{0, 2, 1};
        }
        return index;
    }

    private void findSpaces(int center, Facts facts, String pw) {
        String testPhrase = "";
        //Place spaces for analysis:
        for(int i = 0; i<center; i++) {testPhrase+=" ";}while(testPhrase.length()<(facts.totalLength+2)) {testPhrase+="-";}

        //Append extra characters for added information early on:
        for(int i = 0; i<facts.charBounds[lookup[facts.charPtr]];i++) {
            testPhrase += (char)(lookup[facts.charPtr]+97);
        }

        //Update space lower and upper bounds:
        int[] answer = guess(testPhrase, pw, true);
        if(answer[1] == 0) {
            facts.spaceBounds[0] = Math.max(facts.spaceBounds[0], center+1);
            facts.spaceBounds[2] = Math.max(facts.spaceBounds[2], center+3);
        } else if(answer[1] == 1) {
            facts.spaceBounds[1] = Math.min(facts.spaceBounds[1], center);
            facts.spaceBounds[2] = Math.max(facts.spaceBounds[2], center+1);
        } else {
            facts.spaceBounds[3] = Math.min(facts.spaceBounds[3], center);
            facts.spaceBounds[1] = Math.min(facts.spaceBounds[1], center-2);
        }
        int correctAmountChars = (answer[0] + answer[1]) - 2;
        facts.updateCharBounds(correctAmountChars);
        //System.out.println(Arrays.toString(facts.spaceBounds));
        if(facts.spaceBounds[0]==facts.spaceBounds[1]) {
            if(facts.spaceBounds[2]==facts.spaceBounds[3]) return;
            findSpaces(facts.spaceBounds[2] + ((facts.spaceBounds[3]-facts.spaceBounds[2])/3), facts, pw);
        } else {
            findSpaces((facts.spaceBounds[0]+facts.spaceBounds[1])/2, facts, pw);
        }
    }

    private class Facts {

        private static final String INITIAL_GUESS = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbccccccccccccccccccddddddddddddddddddffffffffffffffffffgggggggggggggggggghhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkllllllllllllllllllmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnooooooooooooooooooppppppppppppppppppqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrssssssssssssssssssttttttttttttttttttuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzz";
        private final int totalLength;
        private final int[] spaceBounds;
        // Pre-filled with maximum bounds obtained from dictionary:
        private final int[] charBounds = new int[] {12, 9, 9, 9, 15, 9, 12, 9, 18, 6, 9, 12, 9, 12, 12, 9, 3, 12, 15, 9, 12, 6, 6, 3, 9, 6};
        private final int[] oddEvenUsed = new int[] {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
        private final int[] oddEvenPairScore = new int[26];
        private int charPtr;

        public Facts(int[] initialResult) {

            totalLength = initialResult[0] + initialResult[1];
            spaceBounds = new int[] {2, Math.min(totalLength - 2, 22), 4, Math.min(totalLength + 1, 43)};

            //Eliminate firsts
            charBounds[lookup[0]] = initialResult[1];
            //Adjust:
            for(int i = 1; i<charBounds.length; i++) {
                charBounds[lookup[i]] = Math.min(charBounds[lookup[i]], totalLength-initialResult[1]);
            }
            charPtr = 1;
        }

        private List<String> previousGuesses = new ArrayList<String>();
        private List<int[]> previousResults = new ArrayList<int[]>(); 
        public void storeInvalid(String phrase, int[] result) {
            previousGuesses.add(phrase);
            previousResults.add(result);
        }

        public boolean doneDiscovery() {
            if(charPtr<12) { //Always do at least N guesses (speeds up and slightly improves score)
                return false;
            }
            return true;
        }

        public void updateCharBounds(int correctAmountChars) {

            // Update the bounds we know for a certain character:
            int knownCharBounds = 0;
            charBounds[lookup[charPtr]] = correctAmountChars;
            for(int i = 0; i <= charPtr;i++) {
                knownCharBounds += charBounds[lookup[i]];
            }
            // Also update the ones we haven't checked yet, we might know something about them now:
            for(int i = charPtr+1; i<charBounds.length; i++) {
                charBounds[lookup[i]] = Math.min(charBounds[lookup[i]], totalLength-knownCharBounds);
            }
            charPtr++;
            while(charPtr < 26 && charBounds[lookup[charPtr]]==0) {
                charPtr++;
            }
        }

        public boolean partialMatches(String phrase) {

            //Try to match a partial phrase, we can't be too picky because we don't know what else is next
            int[] cUsed = new int[26];
            for(int i = 0; i<phrase.length(); i++) {
                cUsed[phrase.charAt(i)-97]++;
            }
            for(int i = 0; i<cUsed.length; i++) {

                //Only eliminate the phrases that definitely have wrong characters:
                if(cUsed[lookup[i]] > charBounds[lookup[i]]) {
                    return false;
                }
            }
            return true;
        }

        public boolean matches(String phrase) {

            // Try to match a complete phrase, we can now use all information:
            int[] cUsed = new int[26];
            for(int i = 0; i<phrase.length(); i++) {
                if(phrase.charAt(i)!=' ') {
                    cUsed[phrase.charAt(i)-97]++;
                }
            }

            for(int i = 0; i<cUsed.length; i++) {
                if(i < charPtr) {
                    if(cUsed[lookup[i]] != charBounds[lookup[i]]) {
                        return false;
                    }
                } else {
                    if(cUsed[lookup[i]] > charBounds[lookup[i]]) {
                        return false;
                    }
                }
            }

            //Check against what we know for odd/even
            for(int pair = 0; pair < 26;pair++) {
                String input = "";
                for(int i = 0; i<26;i++) {
                    if(oddEvenUsed[i] == pair) {
                        input += (char)(lookup[i]+97);
                    }
                }
                if(input.length() == 1) {
                    input += "-";
                }
                String testPhrase = "";
                for(int i = 0; i<=(totalLength+1)/2 ; i++) {
                    testPhrase += input;
                }

                int[] result = guess(testPhrase, phrase, false);
                if(result[1] != oddEvenPairScore[pair]) {
                    return false;
                }
            }

            //Check again previous guesses:
            for(int i = 0; i<previousGuesses.size();i++) {
                // If the input phrase is the correct phrase it should score the same against previous tries:
                int[] result = guess(previousGuesses.get(i), phrase, false);
                int[] expectedResult = previousResults.get(i);
                if(!Arrays.equals(expectedResult, result)) {
                    return false;
                }
            }
            return true;
        }
    }


    private List<String> createPassPhrases() throws Exception {
        BufferedReader reader = new BufferedReader(new FileReader(new File("pass.txt")));
        List<String> phrases = new ArrayList<String>();
        String input;
        while((input = reader.readLine()) != null) {
            phrases.add(input);
        }
        return phrases;
    }

    private Map<Integer, List<String>> createDictionary() throws Exception {
        BufferedReader reader = new BufferedReader(new FileReader(new File("words.txt")));
        Map<Integer, List<String>> wordMap = new HashMap<Integer, List<String>>();
        String input;
        while((input = reader.readLine()) != null) {
            List<String> words = wordMap.get(input.length());
            if(words == null) {
                words = new ArrayList<String>();
            }
            words.add(input);
            wordMap.put(input.length(), words);
        }
        return wordMap;
    }

}

Java - 18.708 consultas; 2,4 segundos 11.077 consultas; 125 min.

Mín: 8, Máx: 13, Consultas efetivas: 10.095

Passei muito tempo nisso. : P

O código está disponível em http://pastebin.com/7n9a50NM

Rev 1. disponível em http://pastebin.com/PSXU2bga

Rev 2. disponível em http://pastebin.com/gRJjpbbu

Minha segunda revisão. Eu esperava quebrar a barreira dos 11K para ganhar o prêmio, mas fiquei sem tempo para otimizar esta fera.

Ele opera em um princípio totalmente separado das duas versões anteriores (e leva aproximadamente 3.500 vezes mais tempo para ser executado). O princípio geral é usar espaço e peneiração de caracteres pares / ímpares para reduzir a lista de candidatos a um tamanho gerenciável (geralmente entre 2 a 8 milhões) e, em seguida, executar consultas repetidas com o máximo poder de discriminação (ou seja, cuja distribuição de saída tenha maximizado a entropia).

Não velocidade, mas a memória é a principal limitação. Minha Java VM não me permite reservar um monte maior que 1.200 MB por algum motivo obscuro (provavelmente o Windows 7), e ajustei os parâmetros para me fornecer a melhor solução possível que não esgote esse limite. Me incomoda que uma execução adequada com os parâmetros adequados quebre 11K sem aumento significativo no tempo de execução. Eu preciso de um computador novo. : P

O que mais me incomoda é que 982 das consultas nesta implementação são inúteis "validação". Eles não têm outro propósito senão satisfazer a regra de que o oráculo deve retornar um valor especial "você conseguiu" em algum momento, embora em minha implementação a resposta correta tenha sido deduzida com certeza antes dessa consulta em 98,2% dos casos. A maioria dos outros envios sub-11K depende de técnicas de filtragem que usam cadeias candidatas como cadeias de consulta e, portanto, não sofrem a mesma penalidade.

Por esse motivo, embora minha contagem de consultas oficial seja 11.077 (abaixo dos líderes, desde que o código deles seja compatível, fiel às especificações etc.), afirmo com ousadia que meu código faz 10.095 consultas efetivas , o que significa que apenas 10.095 consultas são realmente necessário para determinar todas as frases secretas com 100% de certeza. Não tenho certeza de que nenhuma das outras implementações corresponda a isso; portanto, considerarei minha pequena vitória. ;)

Java - min: 22, máx: 41, total: 28353, tempo: 4 segundos

O programa adivinha a senha em 3 etapas:

1. encontre as posições espaciais com uma pesquisa binária
2. conte as ocorrências dos caracteres mais frequentes nas 3 palavras
3. encontre as palavras que começam da esquerda, usando as informações reunidas acima

Ele também lida com um conjunto de "caracteres inválidos" que retornam um resultado zero na pesquisa e um conjunto de "caracteres válidos" que são colocados em outro lugar na frase secreta.

Abaixo de um exemplo dos valores enviados sucessivamente para adivinhação, você pode ver as 3 etapas:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
**  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  *
****    ****    ****    ****    ****    ****    ****    ****    *
********        ********        ********        ********        *
****************                ****************                *
********** ******** *********************************************
eeeeeeeeeee
eeeeeeeeeee eeeeee
iiiiiiiiiii
iiiiiiiiiii iiiiii
aaaaaaaaaaa
aaaaaaaaaaa aaaaaa
sssssssssss
sssssssssss ssssss
rrrrrrrrrrr
rrrrrrrrrrr rrrrrr
nnnnnnnnnnn
ttttttttttt
ooooooooooo
ooooooooooo oooooo
lllllllllll
a
facilitates 
facilitates w
facilitates wis
facilitates widows 
facilitates widows e
facilitates widows briefcase 

O código:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;



public class Main5 {

    private static String CHARS = "eiasrntolcdupmghbyfvkwzxjq "; 
    private static String currentPassword;
    private static List<String> words;
    private static List<String> passphrases;

    private static char [] filters = {'e', 'i', 'a', 's', 'r', 'n', 't', 'o', 'l'};

    private static int maxLength;       

    public static void main(String[] args) throws IOException {

        long start = System.currentTimeMillis();
        passphrases = getFile("passphrases.txt");
        words = getFile("words.txt");
        maxLength = 0;
        for (String word : words) {
            if (word.length() > maxLength) {
                maxLength = word.length();
            }
        }

        int total = 0;
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (String passphrase : passphrases) {
            currentPassword = passphrase;
            int tries = findPassword();
            if (tries > max) max = tries;
            if (tries < min) min = tries;
            total += tries;
        }
        long end = System.currentTimeMillis();
        System.out.println("Min : " + min);
        System.out.println("Max : " + max);
        System.out.println("Total : " + total);
        System.out.println("Time : " + (end - start) / 1000);
    }


    public static int findPassword() {

        /**************************************
         * STEP 1 : find the spaces positions *
         **************************************/
        int tries = 0;
        Map<String, int []> res = new HashMap<String, int[]>();
        long maxBits = (long) Math.log((maxLength * 3+2) * Math.exp(2));
        for (int bit = 0; bit < maxBits-2; bit++) {
            String sp = buildSpace(maxLength*3+2, bit);
            tries++;
            int [] ret = guess(sp);
            res.put(sp, ret);
        }
        List<String> candidates = new ArrayList<String>();
        List<String> unlikely = new ArrayList<String>();
        for (int x1 = 1; x1 < maxLength + 1; x1++) {
            for (int x2 = x1+2; x2 < Math.min(x1+maxLength+1, maxLength*3+2); x2++) {
                boolean ok = true;
                for (String key : res.keySet()) {
                    int [] ret = res.get(key);
                    if (key.charAt(x1) == ' ' && key.charAt(x2) == ' ') {
                        // ret[1] should be 2
                        if (ret[1] != 2) ok = false;
                    } else if (key.charAt(x1) == '*' && key.charAt(x2) == '*') {
                        // ret[1] should be 0
                        if (ret[1] != 0) ok = false;
                    } else if (key.charAt(x1) == ' ' || key.charAt(x2) == ' ') {
                        // ret[1] should be 1
                        if (ret[1] != 1) ok = false;
                    }
                }
                if (ok) {
                    String s = "";
                    for (int i = 0; i < maxLength*3+2; i++) {
                        s += i == x1 || i == x2 ? " " : "*";
                    }
                    // too short or too long words are unlikely to occur
                    if (x1 < 4 || x2 - x1 - 1 < 4 || x1 > 12 || x2 - x1 - 1 > 12) {
                        unlikely.add(s);
                    } else {
                        candidates.add(s);
                    }
                }
            }
        }
        candidates.addAll(unlikely);
        String correct = null;
        if (candidates.size() > 1) {

            for (int i = 0; i < candidates.size(); i++) {
                String cand = candidates.get(i);
                int [] ret = null;
                if (i < candidates.size() - 1) {
                    tries++;
                    ret = guess(cand);
                }
                if (i == candidates.size() - 1 || ret[1] == 2) {
                    correct = cand;
                    break;
                }
            }
        } else {
            correct = candidates.get(0);
        }
        int spaceIdx1 = correct.indexOf(' ');
        int spaceIdx2 = correct.lastIndexOf(' ');

        /********************************************
         * STEP 2 : count the most frequent letters *
         ********************************************/
        // test the filter characters in the first, second, last words
        List<int []> f = new ArrayList<int []>();
        for (int k = 0; k < filters.length; k++) {
            char filter = filters[k];
            String testE = "";
            for (int i = 0; i < spaceIdx1; i++) {
                testE += filter;
            }
            int tmpCount = 0;
            for (int [] tmp : f) {
                tmpCount += tmp[0];
            }
            int [] result;
            if (tmpCount == spaceIdx1) {
                // we can infer the result
                result = new int[] {1, 0};
            } else {
                tries++;
                result = guess(testE);
            }
            int [] count = {result[1], 0, 0};
            if (result[0] > 0) {
                // test the character in the second word
                testE += " ";
                for (int i = 0; i < spaceIdx2-spaceIdx1-1; i++) {
                    testE += filter;
                }                   
                tries++;
                result = guess(testE);
                count[1] = result[1] - count[0] - 1;
                if (testE.length() - count[0] - count[1] > 8) { // no word has more than 8 similar letters
                    count[2] = result[0]; 
                } else {
                    if (result[0] > 0) {
                        // test the character in the third word
                        testE += " ";
                        for (int i = 0; i < maxLength; i++) {
                            testE += filter;
                        }
                        tries++;
                        result = guess(testE);
                        count[2] = result[1] - count[0] - count[1] - 2;
                    }
                }
            }
            f.add(new int[] {count[0], count[1], count[2]});
        }

        /***********************************************
         * STEP 3 : find the words, starting from left *
         ***********************************************/
        String phrase = "", word = "";
        int numWord = 0;
        Set<Character> badChars = new HashSet<Character>();
        Set<Character> goodChars = new HashSet<Character>();
        while (true) {
            boolean found = false;
            int wordLength = -1; // unknown
            if (numWord == 0) wordLength = spaceIdx1;
            if (numWord == 1) wordLength = spaceIdx2-spaceIdx1-1;


            // compute counts
            List<Integer> counts = new ArrayList<Integer>();
            for (int [] tmp : f) {
                counts.add(tmp[numWord]);
            }
            // what characters should we test after?
            String toTest = whatNext(word, badChars, numWord == 2 ? goodChars : null,
                    wordLength, counts);
            // if the word is already found.. complete it, no need to call guess
            if (toTest.length() == 1 && !toTest.equals(" ")) {
                phrase += toTest;
                word += toTest;
                goodChars.remove(toTest.charAt(0));
                continue;
            }
            // try all possible letters             
            for (int i = 0; i < toTest.length(); i++) {
                int [] result = null;
                char c = toTest.charAt(i);
                if (badChars.contains(c)) continue;
                boolean sureGuess = c != ' ' && i == toTest.length() - 1;
                if (!sureGuess) {
                    // we call guess ; increment the number of tries
                    tries++;
                    result = guess(phrase + c);
                    // if the letter is not present, add it to the set of "bad" characters
                    if (result[0] == 0 && result[1] == phrase.length()) {                       
                        badChars.add(c);
                    }
                    // if the letter is present somewhere else, add it to the set of "good" characters
                    if (result[0] == 1 && result[1] == phrase.length()) {                       
                        goodChars.add(c);
                    }
                }
                if (sureGuess || result[1] == phrase.length()+1) {
                    goodChars.remove(c);
                    phrase += c;
                    word += c;
                    if (toTest.charAt(i) == ' ') {
                        word = "";
                        numWord++;
                    }
                    found = true;
                    break;
                }
            }
            if (!found) break;
        }
        if (!phrase.equals(currentPassword)) System.err.println(phrase);
        return tries;
    }

    public static int[] guess(String in) {
        int chars=0, positions=0;
        String pw = currentPassword; // set elsewhere, contains current pass
        for(int i=0;i<in.length()&&i<pw.length();i++){
            if(in.charAt(i)==pw.charAt(i))
                positions++;
        }
        if(positions == pw.length() && pw.length()==in.length())
            return new int[]{-1,positions};
        for(int i=0;i<in.length();i++){
            String c = String.valueOf(in.charAt(i));
            if(pw.contains(c)){
                pw = pw.replaceFirst(c, "");
                chars++;
            }
        }
        chars -= positions;
        return new int[]{chars,positions};
    }


    private static String buildSpace(int length, int bit) {
        String sp = "";
        for (int i = 0; i < length; i++) {
            if (((i >> bit) & 1) != 0) {
                sp += " ";
            } else {
                sp += "*";
            }
        }
        return sp;
    }

    public static String whatNext(String s, Set<Character> badChars, Set<Character> goodChars, int length, List<Integer> counts) {
        String ret = "";
        Map<Character, Integer> freq = new HashMap<Character, Integer>();
        for (char c : CHARS.toCharArray()) {
            if (badChars.contains(c)) continue;
            freq.put(c, 0);
        }
        for (String word : words) {
            if (word.startsWith(s) && (word.length() == length || length == -1)) {
                char c1 = word.equals(s) ? ' ' : word.charAt(s.length());
                if (badChars.contains(c1)) continue;

                boolean badWord = false;
                for (int j = 0; j < counts.size(); j++) {
                    int cpt = 0;
                    for (int i = 0; i < word.length(); i++) {
                        if (word.charAt(i) == filters[j]) cpt++;    
                    }
                    if (cpt != counts.get(j)) {
                        badWord = true;
                        break;
                    }
                }
                if (badWord) continue;
                String endWord = word.substring(s.length());

                for (char bad : badChars) {
                    if (endWord.indexOf(bad) != -1) {
                        badWord = true;
                        break;
                    }
                }
                if (badWord) continue;
                if (goodChars != null) {
                    for (char good : goodChars) {
                        if (endWord.indexOf(good) == -1) {
                            badWord = true;
                            break;
                        }
                    }
                }
                if (badWord) continue;
                freq.put(c1, freq.get(c1)+1);
            }
        }
        while (true) {
            char choice = 0;
            int best = 0;
            for (char c : CHARS.toCharArray()) {
                if (freq.containsKey(c) && freq.get(c) > best) {
                    best = freq.get(c);
                    choice = c;
                }
            }
            if (choice == 0) break;
            ret += choice;
            freq.remove(choice);
        }
        return ret;
    }



    public static List<String> getFile(String filename) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(filename));
        List<String> lines = new ArrayList<String>();
        String line = null;
        while ((line = reader.readLine()) != null) {
            lines.add(line);
        }
        reader.close();
        return lines;
    }
}

PYTHON 2.7 - 156821 palpites, 0.6 segundos

Fui pela velocidade, e não pelo número mais baixo de palpites, embora imagine que meu número ainda seja menor do que, por exemplo, um ataque direto ao dicionário. Não calculo o número de letras na senha, mas no lugar errado, pois meu método não a utiliza, mas se você acha que isso me dá uma vantagem injusta, eu a implementarei. Eu simplesmente começo com uma seqüência de suposições vazia e adiciono um único sufixo de caractere que aumenta a minha lista de caracteres, verificando o resultado de 'check' para ver se o número de caracteres corretos é igual ao comprimento da suposição. Por exemplo, se a senha fosse 'ruim', eu diria:

a, b

uma

a, b, c, d

Também tentei classificar as letras pela frequência das letras em inglês, que diminuíram cerca de 35% do número de palpites, além do tempo. Eu quebrei todas as senhas em 0,82 segundos. As estatísticas são impressas no final.

import string
import time

class Checker():

    def __init__(self):
        #self.chars          = string.ascii_lowercase + ' '  #ascii letters + space
        self.baseChars     = "eiasrnt olcdupmghbyfvkwzxjq"  #ascii letters in order of frequency, space thrown in a reasonable location
        self.subfreqs      = {}

        self.chars         = "eiasrnt olcdupmghbyfvkwzxjq"
        self.subfreqs['a'] = "tnlrcsb dmipguvykwfzxehajoq"
        self.subfreqs['b'] = "leaiour sbytjdhmvcnwgfpkqxz"
        self.subfreqs['c'] = "oaehtik rulcysqgnpzdmvbfjwx"
        self.subfreqs['d'] = "eioarus ldygnmvhbjwfptckqxz"
        self.subfreqs['e'] = "rsndlat cmepxfvgwiyobuqhzjk"
        self.subfreqs['f'] = "ioefalu rtysbcdgnhkjmqpwvxz"
        self.subfreqs['g'] = "erailho usngymtdwbfpckjqvxz"
        self.subfreqs['h'] = "eaoiurt ylmnsfdhwcbpgkjqvxz"
        self.subfreqs['i'] = "notscle amvdgrfzpbkuxqihjwy"
        self.subfreqs['j'] = "ueaoicb dgfhkjmlnqpsrtwvyxz"
        self.subfreqs['k'] = "eisalny owmurfptbhkcdjgqvxz"
        self.subfreqs['l'] = "eialyou stdmkvpfcngbhrwjqxz"
        self.subfreqs['m'] = "eaiopub msnylchfrwqvdgkjtxz"
        self.subfreqs['n'] = "gtesdia conufkvylhbmjrqpwzx"
        self.subfreqs['o'] = "nrumlts opcwdvgibafkeyxzhjq"
        self.subfreqs['p'] = "eroalih ptusybfgkdmwjcnqvxz"
        self.subfreqs['q'] = "uacbedg fihkjmlonqpsrtwvyxz"
        self.subfreqs['r'] = "eaiostm rdyuncgbplkvfhwjqzx"
        self.subfreqs['s'] = "tesihoc upalmnykwqfbdgrvjxz"
        self.subfreqs['t'] = "iearohs tyulcnwmfzbpdgvkjqx"
        self.subfreqs['u'] = "srnltmc adiebpgfozkxvyqhwuj"
        self.subfreqs['v'] = "eiaouyr bhpzcdgfkjmlnqstwvx"
        self.subfreqs['w'] = "aieonhs rlbcmpdkyfgutwvjqxz"
        self.subfreqs['x'] = "pitcaeh oyulgfbdkjmnqsrwvxz"
        self.subfreqs['y'] = "sepminl acortdwgubfkzhjqvyx"
        self.subfreqs['z'] = "eaizoly usrkmwxcbdgfhjnqptv"


        self.numGuessesTot  = 0
        self.numGuessesCur  = 0
        self.currentIndex   = 0
        self.passwords      = [line.strip() for line in open('passwords.txt', 'r').readlines()]
        self.currentPass    = self.passwords[self.currentIndex]
        self.numPasswords   = len(self.passwords)
        self.mostGuesses    = (0,   '')
        self.leastGuesses   = (1e9, '')

    def check(self, guess):
        self.numGuessesTot += 1
        self.numGuessesCur += 1
        numInPass  = 0
        numCorrect = 0
        lenPass    = len(self.currentPass)
        lenGuess   = len(guess)

        minLength  = min(lenPass, lenGuess)

        for i in range(minLength):
            if guess[i] == self.currentPass[i]:
                numCorrect += 1

        if numCorrect == len(self.currentPass):
            return -1, -1

        # numInPass is not calculated, as I don't use it
        return numInPass, numCorrect

    def nextPass(self):

        if self.numGuessesCur < self.leastGuesses[0]:
            self.leastGuesses = (self.numGuessesCur, self.currentPass)
        if self.numGuessesCur > self.mostGuesses[0]:
            self.mostGuesses  = (self.numGuessesCur, self.currentPass)

        self.numGuessesCur = 0
        self.currentIndex += 1

        if self.currentIndex < self.numPasswords:
            self.currentPass = self.passwords[self.currentIndex]

    def main(self):

        t0 = time.time()

        while self.currentIndex < self.numPasswords:
            guess = ''
            result = (0, 0)
            while result[0] is not -1:
                i = 0
                while i < len(self.chars) and result[1] < len(guess)+1 and result[1] is not -1:
                    result = self.check(guess + self.chars[i])

                    i += 1
                guess += self.chars[i-1]

                if self.chars[i-1] == " ":
                    self.chars = self.baseChars
                    i = 0
                else:
                    self.chars = self.subfreqs[self.chars[i-1]]
                    i = 0
            if result[0] == -1:
                #print self.currentIndex, self.currentPass
                self.nextPass()    

        elapsedTime = time.time() - t0
        print "  Total number of guesses: {}".format(self.numGuessesTot)
        print "  Avg number of guesses:   {}".format(self.numGuessesTot/self.numPasswords)
        print "  Least number of guesses: {} -> {}".format(self.leastGuesses[0], self.leastGuesses[1])
        print "  Most number of guesses:  {} -> {}".format(self.mostGuesses[0],  self.mostGuesses[1])
        print "  Total time:              {} seconds".format(elapsedTime)

if __name__ == "__main__":
    checker = Checker()
    checker.main()

EDIT: Removido um +1 e -1 disperso de dois loops while de iterações anteriores de teste, também adicionou estatísticas adicionais para menos palpites e mais palpites para uma senha individual.

EDIT2: tabela de pesquisa adicionada para a letra 'próxima' mais comum, por letra. Maior velocidade e menor contagem de adivinhações

C ++ - 11383 10989 resultados!

Atualizar

Corrigimos vazamentos de memória e removemos mais 1 tentativa de reduzir os tamanhos individuais do dicionário de palavras. Demora cerca de 50 minutos no meu mac pro. O código atualizado está no github.

Mudei para a estratégia de correspondência de frase, reformulei o código e atualizei-o no github https://github.com/snjyjn/mastermind

Com a correspondência baseada em frases, reduzimos para 11383 tentativas! É caro em termos de computação! Eu também não gosto da estrutura de código! E ainda está muito atrás dos outros :-(

É assim que eu estou fazendo:

1. Meça o comprimento da frase - usando uma sequência com todos os 26 caracteres no máximo (max = 3 * maxwordlen + 2) e 2 espaços. Os primeiros caracteres maxlen são os mais frequentes no dicionário, ou seja, e
2. Use um tipo de estratégia de peneira binária para identificar os espaços - faça um número definido de tentativas e identifique possíveis pares de espaços. Crie sequências de teste específicas para reduzir para um único par.

3. Paralelamente, acrescente sequências de teste 'criadas' para obter mais informações sobre a frase. A estratégia atual é a seguinte:

   uma. Use caracteres na ordem de sua frequência no dicionário.

   b. Já sabemos a contagem dos mais frequentes

   c. 1º teste = próximos 5 caracteres. Isso nos dá a contagem desses caracteres na frase.

   d. próximas 3 sequências de teste = próximos 5 caracteres cada, cobrindo um total de 20 caracteres em 4 tentativas, além do primeiro caractere. Isso nos dá a contagem desses cinco últimos caracteres também. conjuntos com contagem de 0 são ótimos para reduzir o tamanho do dicionário!

   e Agora, para o teste anterior que teve menos contagens diferentes de zero, divida a sequência em 2 e use 1 para o teste. A contagem resultante também nos fala sobre a outra divisão.

   f. Agora repita os testes com caracteres (com base em 0),

       1,6,11,16,21
       2,7,12,17,22
       3,8,13,18,23
       4,9,14,19,24
       Isso deve nos dar 5,10,15,20,25

g. After this, the next set of test strings are all 1 character long.
   though we dont expect to get so many tries!

1. Depois que os espaços forem identificados, use as restrições até o momento (o maior número possível de testes nessas tentativas) para reduzir o tamanho do dicionário. Crie também 3 sub dicionários, 1 para cada palavra.

2. Agora faça algumas suposições para cada palavra e teste-a.
   Use estes resultados para reduzir os tamanhos de dicionário individuais.
   Decore isso com os caracteres de teste também (após o comprimento) para obter mais restrições sobre a frase! Eu usei 3 palpites na versão final - 2 para a palavra 1 e 1 para a palavra 2

3. Isso leva o dicionário a um tamanho gerenciável. Execute um produto cruzado, aplicando todas as restrições como antes para criar um dicionário de frases.

4. Resolva o dicionário de frases através de uma série de suposições - desta vez usando informações de posição e de correspondência de caracteres.

5. Essa abordagem nos leva a 11383 tentativas:

    Estatísticas do Matcher
    ------------------
    Comprimento: 1000
    Espaços: 6375
    Palavra 1: 1996
    Palavra 2: 999
    Frase: 1013
    TOTAL: 11383

    Estatísticas do Dicionário
    palavra 0 6517
    palavra 1 780 221 92
    palavra 2 791 233
    palavra 3 772
    frase 186 20 4 2

    Tempo de solução: 20 minutos no meu macbook pro.

Postagem anterior

Limpei o código e enviei-o para https://github.com/snjyjn/mastermind No processo, aprimorei-o e ainda tenho mais uma ideia para experimentar. Há uma grande diferença em relação ao que eu fiz ontem:

Removida a adivinhação individual de caracteres com base em caracteres de alta frequência no dicionário para as palavras 1 e 2 e, em vez disso, uso uma string com base no caractere de frequência mais alta para essa posição.

As estatísticas agora se parecem com:

Espaços: 6862
Palavra 1: 5960
Palavra 2: 5907
Palavra 3: 2953
TOTAL: 21682

Correio Original

Desculpas pela 'resposta', mas acabei de criar uma conta e não tenho reputação suficiente para adicionar um comentário.

Eu tenho um programa c ++, que leva cerca de 6,5 segundos e 24107 tentativas de correspondência. São cerca de 1400 linhas de c ++. Não estou satisfeito com a qualidade do código e o limpo antes de colocá-lo em outro dia. Mas no interesse da comunidade e contribuindo para a discussão, é isso que eu faço:

• Leia o dicionário, obtenha algumas informações básicas sobre ele - comprimento mínimo / máximo de palavra, frequência de caracteres etc.

• Primeiro identifique espaços - Isso tem 2 metades, a primeira é um conjunto de consultas que continuam a particionar o espaço (semelhante a um C. Chafouin):

        ********
    **** ****
  ** ** ** **
 - * * * * * * *

Isso não é exatamente preciso, pois eu uso o comprimento mínimo / máximo das palavras e as contagens de correspondência em cada estágio, mas você entendeu. Neste ponto, ainda não há informações suficientes para obter os 2 espaços, mas tenho o suficiente para reduzi-las a um pequeno número de combinações. A partir dessas combinações, posso fazer algumas consultas específicas, que reduzirão para uma combinação.

• Primeira Palavra - Obtenha um Subdictionary, que possui palavras do tamanho certo. O subdictionary tem suas próprias estatísticas. Faça algumas suposições com os caracteres mais frequentes, para que você possa contar esses caracteres na palavra. Reduza o dicionário novamente com base nesta informação. Crie uma palavra de adivinhação, com os mais diferentes caracteres, e use-a. Cada resposta causa uma redução no dicionário até termos uma correspondência exata ou o tamanho do dicionário é 1.

• Segunda palavra - semelhante à primeira palavra

• Terceira palavra - isso é mais diferente do outro 2. Não temos informações de tamanho para isso, mas temos todas as consultas anteriores (que mantivemos). Essas consultas permitem reduzir o dicionário. A lógica está nas linhas de:

 - query abc retornou uma contagem de correspondências de 1
 - as palavras 1 e 2 não têm b ou c
 - É claro que b ou c não pode fazer parte da palavra 3

Use o dicionário reduzido para adivinhar, com os caracteres mais diversos, e continue a reduzir o dicionário até o tamanho 1 (como nas palavras 1 e 2).

As estatísticas se parecem com:

    Encontrar espaço: 7053
    Caracteres da palavra 1: 2502
    Palavras 1 palavras: 3864
    Palavra 2 caracteres: 2530
    Palavras 2: 3874
    Palavra 3 caracteres: 2781
    Palavras 3: 1503
    TOTAL: 24107

Go - Total: 29546

Semelhante a alguns outros, com algumas otimizações.

1. Obter comprimento total testando AAAAAAAABBBBBBBBCCCCCCCC...ZZZZZZZZ
2. Determine os comprimentos reais das três palavras movendo espaços de ambas as extremidades.
3. Filtre cada palavra pela contagem de letras de algumas letras comuns.
4. Reduza o conjunto de candidatos testando uma sequência e removendo outros candidatos que não fornecem os mesmos resultados. Repita até que o vencedor seja encontrado.

Não é particularmente rápido.

package main

import (
    "bytes"
    "fmt"
    "strings"
)

var totalGuesses = 0
var currentGuesses = 0

func main() {
    for i, password := range passphrases {
        currentGuesses = 0
        fmt.Println("#", i)
        currentPassword = password
        GuessPassword()
    }
    fmt.Println(totalGuesses)
}

func GuessPassword() {
    length := GetLength()
    first, second, third := GetWordSizes(length)

    firstWords := GetWordsOfLength(first, "")
    secondWords := GetWordsOfLength(second, strings.Repeat(".", first+1))
    thirdWords := GetWordsOfLength(third, strings.Repeat(".", first+second+2))
    //tells us number of unique letters in solution. As good as any for an initial pruning mechanism.
    RecordGuess("abcdefghijklmnopqrstuvwxyz")
    candidates := []string{}
    for _, a := range firstWords {
        for _, b := range secondWords {
            for _, c := range thirdWords {
                candidate := a + " " + b + " " + c
                if MatchesLastGuess(candidate) {
                    candidates = append(candidates, candidate)
                }
            }
        }
    }

    for {
        //fmt.Println(len(candidates))
        RecordGuess(candidates[0])
        if lastExist == -1 {
            fmt.Println(lastGuess, currentGuesses)
            return
        }
        candidates = Prune(candidates[1:])
    }
}

var lastGuess string
var lastExist, lastExact int

func RecordGuess(g string) {
    a, b := MakeGuess(g)
    lastGuess = g
    lastExist = a
    lastExact = b
}
func Prune(candidates []string) []string {
    surviving := []string{}
    for _, x := range candidates {
        if MatchesLastGuess(x) {
            surviving = append(surviving, x)
        }
    }
    return surviving
}
func MatchesLastGuess(candidate string) bool {
    a, b := Compare(candidate, lastGuess)
    return a == lastExist && b == lastExact
}

func GetWordsOfLength(i int, prefix string) []string {
    candidates := []string{}
    guess := prefix + strings.Repeat("e", i)
    _, es := MakeGuess(guess)
    guess = prefix + strings.Repeat("a", i)
    _, as := MakeGuess(guess)
    guess = prefix + strings.Repeat("i", i)
    _, is := MakeGuess(guess)
    guess = prefix + strings.Repeat("s", i)
    _, ss := MakeGuess(guess)
    guess = prefix + strings.Repeat("r", i)
    _, ts := MakeGuess(guess)
    for _, x := range allWords {
        if len(x) == i && strings.Count(x, "e") == es &&
            strings.Count(x, "a") == as &&
            strings.Count(x, "i") == is &&
            strings.Count(x, "r") == ts &&
            strings.Count(x, "s") == ss {
            candidates = append(candidates, x)
        }
    }
    return candidates
}

func GetLength() int {
    all := "  "
    for i := 'a'; i <= 'z'; i++ {
        all = all + strings.Repeat(string(i), 8)
    }
    a, b := MakeGuess(all)
    return a + b
}

func GetWordSizes(length int) (first, second, third int) {
    first = 0
    second = 0
    third = 0
    guess := bytes.Repeat([]byte{'.'}, length)
    left := 1
    right := length - 2
    for {
        guess[left] = ' '
        guess[right] = ' '
        _, exact := MakeGuess(string(guess))
        guess[left] = '.'
        guess[right] = '.'
        if exact == 0 {
            left++
            right--
        } else if exact == 1 {
            break
        } else if exact == 2 {
            first = left
            second = right - first - 1
            third = length - first - second - 2
            return
        }
    }
    //one end is decided, the other is not
    //move right in to see
    right--
    guess[left] = ' '
    guess[right] = ' '
    _, exact := MakeGuess(string(guess))
    guess[left] = '.'
    guess[right] = '.'
    if exact == 2 {
        //match was on left. We got lucky and found other match too!
        first = left
        second = right - first - 1
        third = length - first - second - 2
        return
    } else if exact == 0 {
        //match was on right, but we lost it.
        //keep going on left
        right++
        left++
        guess[right] = ' '
        for {
            guess[left] = ' '
            _, exact = MakeGuess(string(guess))

            guess[left] = '.'
            if exact == 2 {
                first = left
                second = right - first - 1
                third = length - first - second - 2
                return
            }
            left++
        }
    } else if exact == 1 {
        //exact == 1. Match was on left and still is. Keep going on right
        right--
        guess[left] = ' '
        for {
            guess[right] = ' '
            _, exact = MakeGuess(string(guess))

            guess[right] = '.'
            if exact == 2 {
                first = left
                second = right - first - 1
                third = length - first - second - 2
                return
            }
            right--
        }
    }
    return first, second, third
}

var currentPassword string

func MakeGuess(guess string) (exist, exact int) {
    totalGuesses++
    currentGuesses++
    return Compare(currentPassword, guess)
}

func Compare(target, guess string) (exist, exact int) {

    if guess == target {
        return -1, len(target)
    }
    exist = 0
    exact = 0
    for i := 0; i < len(target) && i < len(guess); i++ {
        if target[i] == guess[i] {
            exact++
        }
    }
    for i := 0; i < len(guess); i++ {
        if strings.IndexByte(target, guess[i]) != -1 {
            exist++
            target = strings.Replace(target, string(guess[i]), "", 1)
        }
    }
    exist -= exact
    return
}

Java: 58.233

(programa de referência)

Um bot simples para que todos possam vencer. Ele usa 26 suposições iniciais para cada frase para estabelecer uma contagem de caracteres. Em seguida, elimina todas as palavras que contêm letras não encontradas na frase.

Em seguida, surge um loop O (n ³ ) massivo sobre as palavras restantes. Primeiro, ele verifica cada frase candidata para ver se é um anagrama. Nesse caso, ele adivinha, ignorando os resultados, a menos que seja uma combinação perfeita. Eu já vi usar entre 28-510 palpites para qualquer frase até agora.

Isso é lento e depende inteiramente de quantas palavras podem ser eliminadas diretamente das 26 suposições iniciais. Na maioria das vezes, deixa entre 1000 e 4000 palavras para repetir. No momento, ele está em execução há cerca de 14 horas, a uma taxa de ~ 180s / frase. Eu estimo que levará 50 horas para concluir e atualizarei a pontuação naquele momento. Você provavelmente deve fazer algo mais inteligente ou mais rápido do que isso.

(atualização) Finalmente terminou, com um pouco menos de 60k palpites.

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class Mastermind {

    String currentPassword;
    String[] tests;
    HashSet<String> dict;
    ArrayList<HashSet<String>> hasLetter;
    int maxLength = 0;
    int totalGuesses;

    public static void main(String[] args) {
        Mastermind master = new Mastermind();
        master.loadDict("dict-small");
        master.loadTests("passwords");
        System.out.println();
        master.run();
    }

    public Mastermind(){
        totalGuesses = 0;
        dict = new HashSet<String>();
        hasLetter = new ArrayList<HashSet<String>>(26);
        for(int i=0;i<26;i++)
            hasLetter.add(new HashSet<String>());
    }

    int run(){
        long start = System.currentTimeMillis();
        for(int i=0;i<tests.length;i++){
            long wordStart = System.currentTimeMillis();
            currentPassword = tests[i];
            int guesses = test();
            if(guesses < 0){
                System.out.println("Failed!");
                System.exit(0);
            }
            totalGuesses += guesses;
            long time = System.currentTimeMillis() - wordStart;
            System.out.println((i+1) + " found! " + guesses + " guesses, " + (time/1000) + "s ("+ ((System.currentTimeMillis()-start)/1000) +" total) : " + tests[i]);
        }
        System.out.println("\nTotal for " + tests.length + " tests: " + totalGuesses + " guesses, " + ((System.currentTimeMillis()-start)/1000) + " seconds total");
        return totalGuesses;
    }

    int[] guess(String in){
        int chars=0, positions=0;
        String pw = currentPassword;
        for(int i=0;i<in.length()&&i<pw.length();i++){
            if(in.charAt(i)==pw.charAt(i))
                positions++;
        }
        if(positions == pw.length() && pw.length()==in.length())
            return new int[]{-1,positions};
        for(int i=0;i<in.length();i++){
            String c = String.valueOf(in.charAt(i));
            if(pw.contains(c)){
                pw = pw.replaceFirst(c, "");
                chars++;
            }
        }
        chars -= positions;
        return new int[]{chars,positions};
    }

    int test(){
        int guesses = 0;
        HashSet<String> words = new HashSet<String>();
        words.addAll(dict);
        int[] counts = new int[26];
        for(int i=0;i<counts.length;i++){
            char[] chars = new char[maxLength];
            Arrays.fill(chars, (char)(i+97));
            int[] result = guess(new String(chars));
            counts[i] = result[0] + result[1];
            guesses++;
        }

        int length = 2;
        for(int i=0;i<counts.length;i++){
            length += counts[i];
            if(counts[i]==0)
                words.removeAll(hasLetter.get(i));
        }
        System.out.println(words.size() + ", " + Math.pow(words.size(),3));
        for(String a : words){
            for(String b : words){
                for(String c : words){
                    String check = a + " " + b + " " + c;
                    if(check.length() != length)
                        continue;
                    int[] letters = new int[26]; 
                    for(int i=0;i<check.length();i++){
                        if(check.charAt(i)!=' ')
                            letters[check.charAt(i)-97]++;
                    }
                    int matches = 0;
                    for(int i=0;i<letters.length;i++)
                        if(letters[i] == counts[i])
                            matches+=letters[i];
                    if(matches == check.length()-2){
                        guesses++;
                        int[] result = guess(check);
                        System.out.println(check + " : " + result[0] +", " + result[1]);
                        if(result[0] < 0)
                            return guesses;
                    }
                }
            }
        }
        return -guesses;
    }

    int loadDict(String filename){
        try {
            BufferedReader br = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = br.readLine()) != null){
                if(line.length()*3+2 > maxLength)
                    maxLength = line.length()*3+2;
                dict.add(line);
                for(int i=0;i<line.length();i++){
                    hasLetter.get(line.charAt(i)-97).add(line);
                }
            }
            br.close();
        } catch (Exception e){};
        System.out.println("Loaded " + dict.size() + " words.");
        return dict.size();
    }

    int loadTests(String filename){
        ArrayList<String> tests = new ArrayList<String>();
        try {
            BufferedReader br = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = br.readLine()) != null)
                if(line.length()>0)
                    tests.add(line);
            br.close();
        } catch (Exception e){};
        this.tests = tests.toArray(new String[tests.size()]);
        System.out.println("Loaded " + this.tests.length + " tests.");
        return this.tests.length;
    }
}

Java: 28.340 26.185

Mín. 15, Máx. 35, Tempo 2,5s

Desde que meu bot estúpido finalmente terminou de correr, eu queria enviar algo um pouco mais rápido. Ele roda em apenas alguns segundos, mas obtém uma boa pontuação (não vencendo muito> <).

Primeiro, ele usa uma corda grande para obter o comprimento total da frase. Em seguida, procure binário para encontrar espaços semelhantes a outros. Ao fazer isso, ele também começa a verificar as letras uma por vez (em ordem dinâmica) para eliminar palavras que contenham mais letras do que a frase inteira.

Depois de ter o tamanho das palavras, ele usa uma etapa de redução binária para restringir as opções das listas de palavras. Ele escolhe a maior lista e uma letra que contém aproximadamente metade das palavras. Ele adivinha um bloco de palavras com essa letra para determinar qual metade jogar fora. Ele também usa os resultados para se livrar das palavras nas outras listas que contêm muitas letras.

Uma vez que uma lista consiste apenas em anagramas, isso não funciona. Nesse ponto, eu apenas os percorro até restarem apenas duas (ou uma se as outras palavras não forem conhecidas).

Se eu tiver uma contagem total de quatro palavras (duas conhecidas e uma com duas opções), pulo as verificações de redução e anagrama e adivinho uma das opções como uma frase completa. Se não funcionar, tem que ser o outro, mas economizo um palpite em 50% do tempo.

Aqui está um exemplo, mostrando a primeira frase sendo quebrada:

                                             aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccccddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffgggggggggggggggggggghhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnooooooooooooooooooooppppppppppppppppppppqqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrrssssssssssssssssssssttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzz
         ..................................................................oooooooooooooooooooo
                 ..................................................................tttttttttttttttttttt
             ..................................................................nnnnnnnnnnnnnnnnnnnn
           ..................................................................llllllllllllllllllll
            ..................................................................iiiiiiiiiiiiiiiiiiii
                    ..................................................................dddddddddddddddddddd
                 ..................................................................uuuuuuuuuuuuuuuuuuuu
                   ..................................................................ssssssssssssssssssss
                  ..................................................................yyyyyyyyyyyyyyyyyyyy
............rrrrrr
............ssssss
...................ttttttttt
............aaaaaa
...................aaaaaaaaa
............iiiiii
sssssssssss
...................lllllllll
............dddddd
............eeeeee
lllllllllll
ccccccccccc
...................ccccccccc
rrrrrrrrrrr
...................bbbbbbbbb
facilitates wisdom briefcase
facilitates widows briefcase

E, claro, o código:

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Splitter {

    int crack(){
        int curGuesses = guesses;
        none = "";
        int[] lens = getLengths();
        List<Set<String>> words = new ArrayList<Set<String>>();
        for(int i=0;i<3;i++){
            words.add(getWordsOfLength(lens[i]));
            exclude[i] = "";

            for(int j=0;j<26;j++){
                if(pCounts[j]>=0)
                    removeWordsWithMoreThan(words.get(i), pivots.charAt(j), pCounts[j]);
            }
        }
        while(!checkSimple(words)){
            if(numWords(words)>4)
                reduce(words, lens);
            if(numWords(words)>4)
                findAnagrams(words, lens);
        }
        return guesses - curGuesses;
    }

    boolean checkSimple(List<Set<String>> words){
        int total = numWords(words);
        if(total - words.size() == 1){
            int big=0;
            for(int i=0;i<words.size();i++)
                if(words.get(i).size()>1)
                    big=i;
            String pass = getPhrase(words);
            if(guess(pass)[0]<0)
                return true;
            words.get(big).remove(pass.split(" ")[big]);
        }

        total = numWords(words);
        if(total==words.size()){
            String pass = getPhrase(words);
            if(guess(pass)[0]<0)
                return true;
        }
        return false;
    }

    boolean findAnagrams(List<Set<String>> words, int[] lens){
        String test;
        Set<String> out;
        for(int k=0;k<words.size();k++){
            if(words.get(k).size() < 8){
                String sorted = "";
                boolean anagram = true;
                for(String word : words.get(k)){
                    char[] chars = word.toCharArray();
                    Arrays.sort(chars);
                    String next = new String(chars);
                    if(sorted.length()>1 && !next.equals(sorted)){
                        anagram = false;
                        break;
                    }
                    sorted = next;
                }
                if(anagram){
                    test = "";
                    for(int i=0;i<k;i++){
                        for(int j=0;j<=lens[i];j++)
                            test += '.';
                    }                   
                    while(words.get(k).size()>(numWords(words)>4?1:2)){
                        out = new HashSet<String>();
                        for(String word : words.get(k)){
                            int correct = guess(test+word)[1];
                            if(correct == lens[k]){
                                words.set(k, new HashSet<String>());
                                words.get(k).add(word);
                                break;
                            }else{
                                out.add(word);
                                break;
                            }
                        }
                        words.get(k).removeAll(out);
                    }
                }
            }
        }
        return false;
    }

    int numWords(List<Set<String>> words){
        int total = 0;
        for(Set<String> set : words)
            total += set.size();
        return total;
    }

    String getPhrase(List<Set<String>> words){
        String out = "";
        for(Set<String> set : words)
            for(String word : set){
                out += word + " ";
                break;
            }
        return out.trim();
    }

    void reduce(List<Set<String>> words, int[] lens){
        int k = 0;
        for(int i=1;i<words.size();i++)
            if(words.get(i).size()>words.get(k).size())
                k=i;
        if(words.get(k).size()<2)
            return;

        char pivot = getPivot(words.get(k), exclude[k]);
        exclude[k] += pivot;
        String test = "";
        for(int i=0;i<k;i++){
            for(int j=0;j<=lens[i];j++)
                test += '.';
        }
        for(int i=0;i<lens[k];i++)
            test += pivot;
        int[] res = guess(test);

        Set<String> out = new HashSet<String>();
        for(String word : words.get(k)){
            int charCount=0;
            for(int i=0;i<word.length();i++)
                if(word.charAt(i)==pivot)
                    charCount++;
            if(charCount != res[1])
                out.add(word);
            if(res[1]==0 && charCount>0)
                out.add(word);
        }
        words.get(k).removeAll(out);

        if(lens[k]>2 && res[0]<lens[k]-res[1]){
            for(int l=0;l<words.size();l++)
                if(l!=k)
                    removeWordsWithMoreThan(words.get(l), pivot, res[0]);
        }
    }

    void removeWordsWithMoreThan(Set<String> words, char c, int num){
        Set<String> out = new HashSet<String>();
        for(String word : words){
            int count = 0;
            for(int i=0;i<word.length();i++)
                if(word.charAt(i)==c)
                    count++;
            if(count > num)
                out.add(word);
        }
        words.removeAll(out);
    }

    char getPivot(Set<String> words, String exclude){
        int[] count = new int[26];
        for(String word : words){
            for(int i=0;i<26;i++)
                if(word.indexOf((char)(i+'a'))>=0)
                    count[i]++;
        }
        double diff = 999;
        double pivotPoint = words.size()/1.64d;
        int pivot = 0;
        for(int i=0;i<26;i++){
            if(exclude.indexOf((char)(i+'a'))>=0)
                continue;
            if(Math.abs(count[i]-pivotPoint)<diff){
                diff = Math.abs(count[i]-pivotPoint);
                pivot = i;
            }
        }
        return (char)(pivot+'a');
    }

    Set<String> getWordsOfLength(int len){
        Set<String> words = new HashSet<String>();
        for(String word : dict)
            if(word.length()==len)
                words.add(word);
        return words;
    }

    int[] pCounts;
    int[] getLengths(){
        String test = "";
        int pivot = 0;
        pCounts = new int[27];
        for(int i=0;i<27;i++)
            pCounts[i]=-1;
        for(int i=0;i<45;i++)
            test += ' ';
        for(int i=0;i<26;i++){
            for(int j=0;j<20;j++){
                test += (char)(i+'a');
            }
        }
        int[] res = guess(test);
        int len = res[0]+res[1];
        int[] lens = new int[3];

        int[] min = {1,3};
        int[] max = {len-4,len-2};
        int p = (int)((max[0]-min[0])/3+min[0]);
        while(lens[0] == 0){
            if(max[0]==min[0]){
                lens[0] = min[0];
                break;
            }
            String g = "", h = "";
            for(int i=0;i<=p;i++)
                g+=' ';
            if(pivot < pivots.length()){
                h += pad;
                for(int i=0;i<20;i++)
                    h += pivots.charAt(pivot);
            }
            res = guess(g+h);
            if(res[1]==0){
                min[0] = p+1;
                min[1] = max[0];
                pCounts[pivot] = g.length()>1?res[0]-2:res[0]-1; 
            }else if(res[1]==2){
                max[0] = p-2;
                max[1] = p;
                pCounts[pivot] = res[0]; 
            }else if(res[1]==1){
                max[0] = p;
                min[1] = p+1;
                pCounts[pivot] = g.length()>1?res[0]-1:res[0]; 
            }
            p = (int)((max[0]-min[0])/2+min[0]);
            pivot++;
        }

        min[1] = Math.max(min[1], lens[0]+2);
        while(lens[1] == 0){
            p = (max[1]-min[1])/2+min[1];
            if(max[1]==min[1]){
                lens[1] = min[1] - lens[0] - 1;
                break;
            }
            String g = "", h = "";
            for(int i=0;i<=p;i++)
                g+=' ';
            if(pivot < pivots.length()){
                h += pad;
                for(int i=0;i<20;i++)
                    h += pivots.charAt(pivot);
            }
            res = guess(g+h);
            if(res[1]<2){
                min[1] = p+1;
                pCounts[pivot] = res[0]-1;
            }else if(res[1]==2){
                max[1] = p;
                pCounts[pivot] = res[0]; 
            }
            pivot++;
        }
        lens[2] = len - lens[0] - lens[1] - 2;  
        return lens;
    }

    int[] guess(String in){
        guesses++;
        int chars=0, positions=0;
        String pw = curPhrase;

        for(int i=0;i<in.length()&&i<pw.length();i++){
            if(in.charAt(i)==pw.charAt(i))
                positions++;
        }
        if(positions == pw.length() && pw.length()==in.length()){
            System.out.println(in);
            return new int[]{-1,positions};
        }

        for(int i=0;i<in.length();i++){
            String c = String.valueOf(in.charAt(i));
            if(pw.contains(c)){
                pw = pw.replaceFirst(c, "");
                chars++;
            }
        }
        System.out.println(in);
        chars -= positions;
        return new int[]{chars,positions};
    }

    void start(){
        long timer = System.currentTimeMillis();
        loadDict("dict-small");
        loadPhrases("passwords");
        exclude = new String[3];
        int min=999,max=0;
        for(String phrase : phrases){
            curPhrase = phrase;
            int tries = crack();
            min=tries<min?tries:min;
            max=tries>max?tries:max;
        }
        System.out.println("\nTotal: " + guesses);
        System.out.println("Min: " + min);
        System.out.println("Max: " + max);
        System.out.println("Time: " + ((System.currentTimeMillis()-timer)/1000d));
    }

    int loadPhrases(String filename){
        phrases = new ArrayList<String>(1000);
        try {
            BufferedReader br = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = br.readLine()) != null)
                if(line.length()>0)
                    phrases.add(line);
            br.close();
        } catch (Exception e){};
        System.out.println("Loaded " + phrases.size() + " phrases.");
        return phrases.size();
    }

    int loadDict(String filename){  
        dict = new HashSet<String>(10000);
        try {
            BufferedReader br = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = br.readLine()) != null)
                dict.add(line);
            br.close();
        } catch (Exception e){};
        System.out.println("Loaded " + dict.size() + " words");     
        return dict.size();
    }

    int guesses;
    double sum = 0;
    List<String> phrases;
    Set<String> dict;
    String curPhrase;
    String[] exclude;
    String none;
    String pivots = "otnlidusypcbwmvfgeahkqrxzj";   // 26185
    String pad = "..................................................................";
    public static void main(String[] args){
        new Splitter().start();
    }   
}