Cel

Biorąc pod uwagę listę trzech słów, złam je wszystkie. Za każdym razem, gdy zgadniesz, otrzymasz wskazówkę w stylu Mastermind , przedstawiającą, ile znaków pasuje do hasła i ile jest na właściwej pozycji. Celem jest zminimalizowanie całkowitej liczby domysłów we wszystkich przypadkach testowych.

Hasła

Z domyślnej listy słów mojego systemu losowo wybrałem 10 000 różnych słów, aby stworzyć słownik dla tego wyzwania. Wszystkie słowa składają się a-ztylko z. Słownik ten można znaleźć tutaj ( raw ).

Z tego słownika wygenerowałem 1000 haseł składających się z trzech losowych słów oddzielonych spacjami ( apple jacks feverna przykład). Poszczególne słowa mogą być ponownie użyte w ramach każdego hasła ( hungry hungry hippos). Możesz znaleźć listę haseł tutaj ( raw ), z jednym w wierszu.

Twój program może używać / analizować plik słownika w dowolny sposób. Nie można analizować haseł w celu optymalizacji dla tej konkretnej listy. Twój algorytm powinien nadal działać, biorąc pod uwagę inną listę fraz

Zgadywanie

Aby zgadnąć, prześlij ciąg do kontrolera. Powinien zwrócić tylko :

• Liczba znaków w ciągu również w haśle ( nie w prawidłowym położeniu)
• Liczba znaków we właściwej pozycji

Jeśli ciąg znaków jest idealnie dopasowany, może wygenerować coś wskazującego na to (moje używa -1 pierwszej wartości).

Na przykład, jeśli hasło jest the big cati wydaje się tiger baby mauling, że moduł sprawdzający powinien powrócić 7,1. 7 znaków ( ige<space>ba<space>) znajduje się w obu ciągach, ale w różnych pozycjach, a 1 ( t) znajduje się w tej samej pozycji w obu. Zauważ, że spacje się liczą.

Napisałem przykładową funkcję (czytaj: niezoptymalizowaną) w Javie, ale możesz napisać własną, pod warunkiem, że zawiera tylko wymagane informacje.

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};
}

Punktacja

Twój wynik to po prostu liczba zgadnięć, które przesyłasz do kontrolera (licząc ostatni, poprawny) dla wszystkich fraz testowych. Najniższy wynik wygrywa.

Musisz złamać wszystkie frazy na liście. Jeśli twój program zawiedzie na którymkolwiek z nich, jest nieprawidłowy.

Twój program musi być deterministyczny. Jeśli zostanie uruchomiony dwukrotnie na tym samym zestawie haseł, powinien zwrócić ten sam wynik.

W przypadku remisu po raz pierwszy uruchomię powiązane wpisy na komputerze cztery razy, a wygrywa najniższy średni czas na rozwiązanie wszystkich 1000 przypadków. Na moim komputerze działa Ubuntu 14.04 z i7-3770K i 16 GB pamięci RAM, na wypadek, gdyby miało to wpływ na twój program. Z tego powodu oraz w celu ułatwienia testowania twoja odpowiedź powinna być w języku, w którym znajduje się kompilator / tłumacz, który można pobrać bezpłatnie z sieci (bez darmowych wersji próbnych) i nie wymaga rejestracji / rejestracji.

_{Tytuł dostosowany z XKCD}

Scala 9146 (min. 7, maks. 15, średnio 9,15) czas: 2000 sekund

Podobnie jak wiele wpisów, zaczynam od uzyskania całkowitej długości, a następnie od znalezienia spacji, uzyskania nieco więcej informacji, zredukowania do pozostałych kandydatów, a następnie odgadnięcia fraz.

Zainspirowany oryginalnym komiksem xkcd, próbowałem zastosować moje podstawowe zrozumienie teorii informacji. Istnieje trylion możliwych zwrotów lub nieco mniej niż 40 bitów entropii. Wyznaczam cel poniżej 10 zgadnięć na frazę testową, co oznacza, że ​​musimy nauczyć się średnio prawie 5 bitów na zapytanie (ponieważ ostatni jest bezużyteczny). Przy każdym zgadywaniu otrzymujemy dwie liczby i z grubsza mówiąc, im większy potencjalny zakres tych liczb, tym więcej oczekujemy się nauczyć.

Aby uprościć logikę, używam każdego zapytania jako efektywnie dwóch osobnych pytań, więc każdy ciąg zgadywania składa się z dwóch części, lewej strony zainteresowanej liczbą prawidłowych pozycji (czarne kołki w mastermind) i prawej strony zainteresowanej liczbą poprawnych znaków ( kołki ogółem). Oto typowa gra:

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

Zgadywanie przestrzeni

Każda próba spacji może zwrócić maksymalnie 2 czarne kołki; Próbowałem skonstruować domysły zwracające 0,1 i 2 kołki o prawdopodobieństwach odpowiednio 1 / 4,1 / 2 i 1/4. Uważam, że jest to najlepsze, co możesz zrobić dla oczekiwanych 1,5 bitów informacji. Postawiłem na naprzemienny ciąg dla pierwszego odgadnięcia, po którym następują losowo generowane, chociaż okazuje się, że zwykle warto po prostu zacząć zgadywać przy drugiej lub trzeciej próbie, ponieważ znamy częstotliwości długości słowa.

Liczy się zestaw znaków do nauki

W przypadku domysłów po prawej stronie wybieram losowe (zawsze 2 z e / i / a / s) zestawy znaków, aby oczekiwana zwrócona liczba była o połowę krótsza. Większa wariancja oznacza więcej informacji, a ze strony wikipedii w rozkładzie dwumianowym szacuję około 3,5 bitu na zapytanie (przynajmniej dla pierwszych kilku, zanim informacje staną się zbędne). Kiedy znane są odstępy, używam losowych ciągów najczęstszych liter po lewej stronie, wybranych tak, aby nie kolidowały z prawą stroną.

Łączenie pozostałych kandydatów

Ta gra stanowi kompromis między szybkością obliczeniową / wydajnością zapytań, a wyliczenie pozostałych kandydatów może zająć naprawdę dużo czasu bez uporządkowanych informacji, takich jak określone postacie. Zoptymalizowałem tę część, zbierając głównie informacje niezmienne w kolejności słów, co pozwala mi wstępnie obliczyć liczbę zestawów znaków dla każdego pojedynczego słowa i porównać je z liczbą uzyskaną z zapytań. Pakuję te liczby do Długiej liczby całkowitej, używając komparatora i sumatora równości maszyn, aby przetestować wszystkie liczby moich postaci w parralelu. To była ogromna wygrana. Mogę spakować do 9 rachunków w Long, ale stwierdziłem, że zbieranie dodatkowych informacji nie było tego warte i ustaliłem na 6 do 7.

Po poznaniu pozostałych kandydatów, jeśli zestaw jest dość mały, wybieram ten z najniższym oczekiwanym logem pozostałych kandydatów. Jeśli zestaw jest wystarczająco duży, aby ten czas był czasochłonny, wybieram z małego zestawu próbek.

Dziękuję wszystkim. To była fajna gra i zachęciła mnie do zarejestrowania się na stronie.

Aktualizacja: Oczyszczony kod dla uproszczenia i czytelności, z drobnymi poprawkami algorytmu, co skutkuje poprawą wyniku.
Oryginalny wynik: 9447 (min. 7, maks. 13, średnio 9,45) czas: 1876 sekund

Nowy kod to 278 linii Scali poniżej

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 - ogółem: 37171, min: 24, maks: 55, czas: około 10 sekund

Pożyczyłem pomysł Raya, aby znaleźć długość każdego słowa, zgadując ze spacjami, tyle że szukam raczej binarnego niż liniowego, co oszczędza mi wielu domysłów.

Gdy określę długość słowa, domyślam się, że pierwsze słowo odpowiada jego długości i zapisuję liczbę poprawnych pozycji. Następnie wybieram pierwsze słowo ze zbioru wszystkich słów, które dzielą tę samą liczbę pozycji z moim pierwszym odgadnięciem jako słowo tajemnicze. Przy trzecim zgadywaniu wybieram pierwsze słowo ze zbioru wszystkich słów, które dzielą tę samą liczbę pozycji z moim pierwszym odgadnięciem jako słowo tajemnicze i taką samą liczbę pozycji jak moje drugie przypuszczenie ze słowem tajemniczym itp.

Korzystając z tej metody, jestem w stanie odgadnąć każde słowo, pojedynczo, w około 5-10 domysłów. Oczywiście trzecie słowo muszę zrobić nieco inaczej, ponieważ nie znam jego długości, ale metoda jest podobna. Korzystam z pliku zawierającego macierz liczby wspólnych pozycji każdego słowa, które wcześniej obliczyłem. Większość czasu wykonywania jest ponoszona podczas ładowania wstępnie obliczonych danych. Możesz pobrać wszystko tutaj .

#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;
}

Przyjemnie jest też oglądać zawężające się słowa:

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, max: 29, łącznie: 25146, czas: 20min

min: 30, max: 235, łącznie: 41636, czas: 4 min

Aktualizacja:

1. Użyj wyszukiwania binarnego, aby znaleźć miejsce. Pomysł zapożyczono z odpowiedzi Orby'ego . Jednym ze zoptymalizowanych przeze mnie miejsc jest to, że jeśli podczas szukania pierwszego miejsca znalazłeś 2 spacje w zakresie, możesz zawęzić zakres wyszukiwania drugiego spacji.
2. Zapisz błędne domysły wraz z ich wynikiem. Porównaj z nimi w następujących przypuszczeniach. To może dużo zaoszczędzić.
3. Zmniejsz liczbę wyliczeń liter do 12, dzięki aktualizacji nr 2.

Ten sposób nie używa losowości, więc wynik się nie zmieni.

Najpierw użyj przypuszczeń takich jak poniżej, aby znaleźć pierwszą i drugą spację w odpowiedzi.

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

Następnie liczyć występowania każdej litery zgadując aaaaa..., bbbbb....... Po nich będzie kosztować około 40 kroków. W rzeczywistości nie musimy wypróbowywać wszystkich liter i możemy wypróbować je w dowolnej kolejności. W większości przypadków wystarczy około 20 liter. Tutaj wybieram 21.

Teraz zna długość pierwszego słowa i drugiego słowa, dzięki czemu może odfiltrować listę kandydatów na te dwa słowa. Zwykle na każdego pozostanie około 100 kandydatów.

Następnie wystarczy wyliczyć pierwsze i drugie słowo. Po wyliczeniu pierwszych dwóch słów możemy wywnioskować wszystkie prawidłowe trzecie słowo, ponieważ wiemy, że liczy się liczba znaków.

Aby zoptymalizować szybkość, używam concurrent.futuresdo dodawania do programu wielu procesów. Potrzebujesz więc Pythona 3, aby go uruchomić, a ja przetestowałem go z Pythonem 3.4 na moim Linux-ie. Musisz także zainstalować 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 13923 (min: 11, maks .: 17)

Aktualizacja: poprawiony wynik (złamał <14 / crack avg!), Nowy kod

• Sprawdzanie znanych znaków jest teraz gęstsze (teraz ABABAB *, zamiast -AAAA *)
• Gdy nie są dostępne żadne znane postacie, dwie niewiadome zostaną policzone za jednym razem
• Błędne domysły są przechowywane i wykorzystywane do sprawdzania możliwych dopasowań
• Trwałe poprawki z nową logiką

Oryginalny post

Postanowiłem całkowicie skoncentrować się na liczbie domysłów zamiast na wydajności (biorąc pod uwagę zasady). Spowodowało to bardzo powolny inteligentny program.

Zamiast kraść ze znanych programów postanowiłem napisać wszystko od zera, ale okazuje się, że niektóre / większość pomysłów jest taka sama.

Algorytm

Oto jak działa mój:

1. Wykonaj jedno zapytanie, które daje w sumie liczbę e i znaków
2. Następnie szukamy spacji, dodając na końcu kilka nieznanych znaków, aby uzyskać liczbę znaków
3. Po znalezieniu spacji nadal chcemy dowiedzieć się więcej znaków, tymczasem otrzymuję także więcej danych o znanych postaciach (jeśli są one na równych pozycjach), które pomogą mi wyeliminować wiele fraz.
4. Kiedy osiągniemy określony limit (ślad / błąd), generuje wszystkie możliwe frazy i rozpoczyna wyszukiwanie binarne, przez większość czasu na końcu dodając nieznane znaki.
5. Wreszcie dokonujemy domysłów!

Przykładowe domysły

Oto rzeczywisty przykład:

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

Ponieważ mój kod nigdy tak naprawdę nie koncentruje się na pojedynczych słowach i gromadzi tylko informacje o pełnej frazie, musi wygenerować wiele z tych fraz, co czyni ją bardzo powolną.

Kod

I wreszcie jest (brzydki) kod, nawet nie próbuj go zrozumieć, przepraszam:

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 zapytań; 2,4 sekundy 11 077 zapytań; 125 min.

Min .: 8, Maks .: 13, Skuteczne zapytania: 10 095

Zbyt długo spędziłem nad tym. : P

Kod jest dostępny na stronie http://pastebin.com/7n9a50NM

Wersja 1. dostępna na stronie http://pastebin.com/PSXU2bga

Wersja 2. dostępna na stronie http://pastebin.com/gRJjpbbu

Moja druga wersja. Miałem nadzieję przekroczyć barierę 11 000, aby wygrać nagrodę, ale zabrakło mi czasu na optymalizację tej bestii.

Działa na zupełnie innej zasadzie niż poprzednie dwie wersje (i zajmuje około 3500 razy więcej czasu). Ogólną zasadą jest stosowanie spacji i przesiewania znaków parzystych / nieparzystych w celu zmniejszenia listy kandydatów do możliwego do zarządzania rozmiaru (zwykle między 2-8 milionów), a następnie wykonywanie powtarzających się zapytań z maksymalną mocą dyskryminacji (tj. Których rozkład wyjściowy zmaksymalizował entropię).

Nie ograniczenie, ale pamięć jest głównym ograniczeniem. Moja wirtualna maszyna Java nie pozwala mi zarezerwować sterty większej niż 1200 MB z jakiegoś niejasnego powodu (prawdopodobnie Windows 7), a ja dostroiłem parametry, aby uzyskać najlepsze możliwe rozwiązanie, które nie wyczerpuje tego limitu. Denerwuje mnie, że poprawne uruchomienie z właściwymi parametrami złamałoby 11K bez znaczącego wydłużenia czasu wykonania. Potrzebuję nowego komputera. : P

Najbardziej denerwuje mnie to, że 982 zapytań w tej implementacji to bezużyteczne zapytania „sprawdzania poprawności”. Nie mają innego celu niż spełnienie zasady, że wyrocznia musi w pewnym momencie zwrócić specjalną wartość „masz”, mimo że w mojej implementacji poprawnie wydano prawidłową odpowiedź przed tym zapytaniem w 98,2% przypadków. Większość innych zgłoszeń poniżej 11K opiera się na technikach filtrowania, które wykorzystują ciągi kandydujące jako ciągi zapytania, a zatem nie podlegają takiej samej karze.

Z tego powodu, chociaż moja oficjalna liczba zapytań wynosi 11 077 (brak liderów, pod warunkiem, że ich kod jest zgodny, zgodny ze specyfikacją itp.), Śmiało stwierdzam, że mój kod wykonuje 10 095 efektywnych zapytań, co oznacza, że ​​tylko 10 095 zapytań jest faktycznie konieczne jest określenie wszystkich fraz z 100% pewnością. Nie jestem pewien, czy którakolwiek inna implementacja będzie do tego pasować, dlatego uznam to za moje małe zwycięstwo. ;)

Java - min: 22, max: 41, łącznie: 28353, czas: 4 sekundy

Program zgaduje hasło w 3 krokach:

1. znaleźć pozycje spacji za pomocą wyszukiwania binarnego
2. policz wystąpienia najczęstszych postaci w 3 słowach
3. znajdź słowa zaczynające się od lewej, korzystając z informacji zebranych powyżej

Obsługuje również zestaw „złych znaków”, które zwracają zero wyników wyszukiwania, oraz zestaw „dobrych znaków”, które są umieszczane gdzie indziej w haśle.

Poniżej przykład wartości wysyłanych kolejno do zgadywania, możesz zobaczyć 3 kroki:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
**  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  *
****    ****    ****    ****    ****    ****    ****    ****    *
********        ********        ********        ********        *
****************                ****************                *
********** ******** *********************************************
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 

Kod:

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 domysłów, 0,6 sekundy

Poszedłem raczej do szybkości niż do najmniejszej liczby domysłów, chociaż uważam, że moja liczba domysłów jest wciąż niższa niż na przykład byłby zwykły atak słownikowy. Nie obliczam liczby liter w haśle, ale w niewłaściwym miejscu, ponieważ moja metoda go nie używa, ale jeśli uważasz, że daje mi to niesprawiedliwą przewagę, to go wdrożę. Po prostu zaczynam od pustego ciągu zgadywania i dodam do niego przyrostek jednego znaku, który zwiększa się nad moją listą znaków, sprawdzając wynik „sprawdzenia”, aby sprawdzić, czy liczba poprawnych znaków jest równa długości zgadywania. Na przykład, jeśli hasło byłoby „złe”, zgadłbym:

a, b

za

a, b, c, d

Próbowałem też posortować litery według angielskiej częstotliwości, co zmniejszyło liczbę domysłów o 35%, a także o czasie. Złamałem wszystkie hasła w 0,82 sekundy. Statystyki są drukowane na końcu.

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()

EDYCJA: Usunięto zbłąkane +1 i -1 z dwóch pętli while z poprzednich iteracji testowania, dodano także dodatkowe statystyki dla najmniejszej liczby domysłów i większości domysłów dla indywidualnego hasła.

EDYCJA 2: dodano tabelę odnośników dla najczęstszej „następnej” litery na literę. Znacznie większa prędkość i mniejsza liczba zgadnięć

C ++ - 11383 10989 meczów!

Aktualizacja

Naprawiono wycieki pamięci i usunięto jeszcze jedną próbę zmniejszenia rozmiarów poszczególnych słowników słów. Moje Mac Pro zajmuje około 50 minut. Zaktualizowany kod znajduje się na github.

Przerzuciłem się na strategię dopasowywania fraz, przerobiłem kod i zaktualizowałem go na github https://github.com/snjyjn/mastermind

Dzięki dopasowaniu opartemu na wyrażeniach ograniczamy się do 11383 prób! Jest drogi pod względem obliczeniowym! Nie podoba mi się również struktura kodu! I wciąż jest daleko w tyle za innymi :-(

Tak to robię:

1. Zmierz długość frazy - używając ciągu zawierającego wszystkie 26 znaków maksymalnie razy (maks. = 3 * maks. Słowo + 2) i 2 spacje. Pierwsze znaki maksymalne występują najczęściej w słowniku, np
2. Użyj strategii binarnego sita, aby zidentyfikować spacje - wykonaj określoną liczbę prób i zidentyfikuj potencjalne pary spacji. Utwórz określone ciągi testowe, aby zredukować do jednej pary.

3. Równolegle dołącz „spreparowane” ciągi testowe, aby uzyskać więcej informacji na temat frazy. Obecna strategia jest następująca:

   za. Używaj znaków w kolejności ich częstotliwości w słowniku.

   b. Znamy już liczbę najczęstszych

   do. 1. ciąg testowy = kolejne 5 znaków. To daje nam liczbę tych znaków w zdaniu.

   re. kolejne 3 ciągi testowe = każde kolejne 5 znaków, obejmujące łącznie 20 znaków w 4 próbach oprócz pierwszego 1 znaku. Daje nam to również liczbę ostatnich 5 znaków. zestawy z liczbą 0 świetnie nadają się do zmniejszenia rozmiaru słownika!

   mi. Teraz w poprzednim teście, który miał najmniej niezerową liczbę, podziel ciąg na 2 i użyj 1 do testowania. Wynikowa liczba mówi nam również o innym podziale.

   fa. Teraz powtórz testy ze znakami (na podstawie 0),

       1,6,11,16,21
       2,7,12,17,22
       3,8,13,18,23
       4,9,14,19,24
       To powinno dać nam 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. Po zidentyfikowaniu spacji użyj dotychczasowych ograniczeń (tyle testów, ile można wykonać w tych próbach), aby zmniejszyć rozmiar słownika. Utwórz także 3 słowniki, po 1 dla każdego słowa.

2. Teraz zrób przypuszczenia dla każdego słowa i przetestuj je.
   Użyj tych wyników, aby zmniejszyć poszczególne rozmiary słowników.
   Udekoruj to również znakami testowymi (po długości), aby uzyskać więcej ograniczeń dla frazy! Użyłem 3 domysłów w ostatecznej wersji - 2 dla słowa 1 i 1 dla słowa 2

3. Sprowadza to słownik do rozsądnego rozmiaru. Wykonaj krzyżowy produkt, stosując wszystkie ograniczenia jak poprzednio, aby utworzyć słownik fraz.

4. Rozwiąż słownik fraz poprzez szereg domysłów - tym razem wykorzystując informacje o położeniu i dopasowaniu znaków.

5. Takie podejście prowadzi nas do 11383 prób:

    Statystyka Matchera
    ------------------
    Długość: 1000
    Miejsca: 6375
    Słowo 1: 1996
    Słowo 2: 999
    Fraza: 1013
    RAZEM: 11383

    Statystyka słownika
    słowo 0 6517
    słowo 1 780 221 92
    słowo 2 791 233
    słowo 3 772
    fraza 186 20 4 2

    Czas rozwiązania: 20 minut na moim MacBooku Pro.

Poprzedni post

Wyczyściłem kod i przesłałem go na https://github.com/snjyjn/mastermind W tym czasie ulepszyłem go i nadal mam jeszcze jeden pomysł do wypróbowania. Jest jedna zasadnicza różnica w stosunku do tego, co zrobiłem wczoraj:

Usunąłem indywidualne zgadywanie dla znaków opartych na znakach wysokiej częstotliwości w słowniku dla słów 1 i 2, a zamiast tego używam ciągu opartego na znaku najwyższej częstotliwości dla tej pozycji.

Statystyki wyglądają teraz następująco:

Miejsca: 6862
Słowo 1: 5960
Słowo 2: 5907
Słowo 3: 2953
RAZEM: 21682

Oryginalny post

Przepraszamy za „odpowiedź”, ale właśnie utworzyłem konto i nie mam wystarczającej reputacji, aby dodać komentarz.

Mam program c ++, który zajmuje około 6,5 sekundy i 24107 prób dopasowania. Jest to około 1400 linii c ++. Nie podoba mi się jakość kodu i wyczyszczę go, zanim wprowadzę go w inny dzień. Ale w interesie społeczności i przyczynianiu się do dyskusji robię to:

• Przeczytaj słownik, uzyskaj podstawowe informacje na jego temat - minimalna / maksymalna długość słowa, częstotliwość znaków itp.

• Najpierw zidentyfikuj spacje - ma 2 połówki, pierwsza to zestaw zapytań, które nadal dzielą przestrzeń (podobnie jak jedna C. Chafouin):

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

Nie jest to do końca dokładne, ponieważ używam minimalnej / maksymalnej długości słowa i używam liczników dopasowania na każdym etapie, ale masz pomysł. W tym momencie wciąż nie ma wystarczających informacji, aby uzyskać 2 spacje, ale mam dość, aby sprowadzić je do niewielkiej liczby kombinacji. Z tych kombinacji mogę zrobić kilka konkretnych zapytań, które zawęzią go do 1 kombinacji.

• Pierwsze słowo - zdobądź subdictionary, który zawiera słowa o odpowiedniej długości. Indeks podrzędny ma własne statystyki. Zrób kilka zgadnięć z najczęstszymi postaciami, aby uzyskać liczbę tych znaków w słowie. Ponownie zmniejsz słownik w oparciu o te informacje. Utwórz słowo „zgadnij”, które ma najróżniejsze znaki i użyj go. Każda odpowiedź powoduje redukcję słownika, dopóki nie znajdziemy dokładnego dopasowania lub słownik będzie miał rozmiar 1.

• Drugie słowo - podobne do pierwszego słowa

• Trzecie słowo - najbardziej różni się od pozostałych 2. Nie mamy do tego informacji o rozmiarze, ale mamy wszystkie poprzednie zapytania (które zachowaliśmy). Te zapytania pozwalają zmniejszyć słownik. Logika jest następująca:

 - zapytanie abc zwróciło liczbę dopasowań równą 1
 - słowa 1 i 2 nie mają b lub c
 - Oczywiste jest, że b lub c nie może być częścią słowa 3

Użyj skróconego słownika, aby odgadnąć, używając najbardziej różnorodnych znaków, i kontynuuj zmniejszanie słownika do rozmiaru 1 (jak w słowach 1 i 2).

Statystyki wyglądają następująco:

    Znalezienie miejsca: 7053
    Znaki słowa 1: 2502
    Słowo 1 słowo: 3864
    Znaki słowa 2: 2530
    Słowo 2 słowa: 3874
    Znaki słowa 3: 2781
    Słowo 3 słowa: 1503
    RAZEM: 24107

Idź - ogółem: 29546

Podobne do niektórych, z pewnymi optymalizacjami.

1. Uzyskaj całkowitą długość, testując AAAAAAAABBBBBBBBCCCCCCCC...ZZZZZZZZ
2. Określ rzeczywiste długości wszystkich trzech słów, przesuwając spacje z obu końców.
3. Filtruj każde słowo według liczby popularnych liter.
4. Zmniejsz zestaw kandydatów, testując ciąg znaków i usuwając innych kandydatów, którzy nie zapewniają takich samych wyników. Powtarzaj aż do znalezienia zwycięzcy.

To nie jest szczególnie szybkie.

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

(program referencyjny)

Prosty bot dla każdego do pokonania. Używa początkowych 26 odgadnięć dla każdej frazy, aby ustalić liczbę znaków. Następnie eliminuje wszystkie słowa zawierające litery nie znalezione w wyrażeniu.

Potem pojawia się potężna pętla O (n ³ ) nad pozostałymi słowami. Najpierw sprawdza każde zdanie kandydujące, aby zobaczyć, czy jest to anagram. Jeśli tak, zgaduje, ignorując wyniki, chyba że jest to idealne dopasowanie. Do tej pory widziałem, że używa dowolnej liczby wyrażeń od 28 do 510.

Jest to powolne i całkowicie zależy od tego, ile słów można wyeliminować z początkowych 26 domysłów. Przeważnie pozostawia od 1000 do 4000 słów do zapętlenia. Obecnie działa od około 14 godzin w tempie ~ 180s / frazę. Szacuję, że ukończenie zajmie 50 godzin i zaktualizuję wynik w tym czasie. Prawdopodobnie powinieneś zrobić coś mądrzejszego lub bardziej niż to.

(aktualizacja) W końcu się skończyło, z nieco mniej niż 60 000 domysłów.

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

Min. 15, maks. 35, czas 2,5 s

Ponieważ mój głupi bot w końcu skończył działać, chciałem przesłać coś nieco szybciej. Działa w ciągu kilku sekund, ale otrzymuje dobry wynik (niezupełnie wygrywający> <).

Najpierw używa dużego ciągu padu, aby uzyskać całkowitą długość frazy. Następnie wyszukiwanie binarne w celu znalezienia spacji podobnych do innych. Robiąc to, zaczyna również sprawdzać litery pojedynczo (w kolejności przestawnej), aby wyeliminować słowa zawierające więcej dowolnej litery niż całą frazę.

Po uzyskaniu długości słowa wykorzystuje krok binarny, aby zawęzić wybór list słów. Wybiera największą listę i literę składającą się z około połowy słów. Odgaduje długość słowa tego listu, aby określić, którą połowę wyrzucić. Wykorzystuje również wyniki, aby pozbyć się słów z innych list, które mają za dużo litery.

Gdy lista składa się tylko z anagramów, to nie działa. W tym momencie po prostu przechodzę przez nie, aż pozostaną tylko dwa (lub jedno, jeśli pozostałe słowa nie są znane).

Jeśli mam całkowitą liczbę słów cztery (dwa znane i jedno z dwiema opcjami), pomijam sprawdzanie redukcji i anagramów i po prostu odgaduję jedną z opcji jako pełne wyrażenie. Jeśli to nie działa, to musi być drugi, ale oszczędzam przypuszczenie 50% czasu.

Oto przykład pokazujący pękanie pierwszej frazy:

                                             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

I oczywiście kod:

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();
    }   
}