Objektif

Diberikan daftar kata sandi tiga kata, pecahkan semuanya. Setiap kali Anda menebak, Anda akan diberi petunjuk dalam gaya Mastermind , menggambarkan berapa banyak karakter yang cocok dengan kata sandi, dan berapa banyak yang berada di posisi yang benar. Tujuannya adalah untuk meminimalkan jumlah tebakan dari semua kasus uji.

Frasa sandi

Dari daftar kata default sistem saya, saya secara acak memilih 10.000 kata yang berbeda untuk membuat kamus untuk tantangan ini. Semua kata a-zhanya terdiri dari . Kamus ini dapat ditemukan di sini ( mentah ).

Dari kamus ini, saya menghasilkan 1000 frasa sandi yang masing-masing terdiri dari tiga kata yang dipisahkan ruang secara acak ( apple jacks fever, misalnya). Setiap kata dapat digunakan kembali dalam setiap frasa sandi ( hungry hungry hippos). Anda dapat menemukan daftar frasa sandi di sini ( mentah ), dengan satu frasa per baris.

Program Anda dapat menggunakan / menganalisis file kamus seperti yang Anda inginkan. Anda tidak dapat menganalisis frasa sandi untuk mengoptimalkan untuk daftar khusus ini. Algoritme Anda harus tetap berfungsi mengingat daftar frasa yang berbeda

Menebak

Untuk menebak, Anda mengirimkan string ke pemeriksa. Seharusnya mengembalikan hanya :

• Jumlah karakter dalam string Anda juga di frasa sandi ( tidak pada posisi yang benar)
• Jumlah karakter di posisi yang benar

Jika string Anda sangat cocok, string tersebut dapat menampilkan sesuatu yang menunjukkan (tambang menggunakan -1nilai pertama).

Misalnya, jika frasa sandi adalah the big catdan Anda tebak tiger baby mauling, pemeriksa harus kembali 7,1. 7 karakter ( ige<space>ba<space>) berada di kedua string tetapi posisi berbeda, dan 1 ( t) berada di posisi yang sama di keduanya. Perhatikan bahwa spasi dihitung.

Saya telah menulis contoh (baca: tidak dioptimalkan) fungsi di Jawa, tetapi jangan ragu untuk menulis sendiri selama hanya memberikan informasi yang diperlukan.

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

Mencetak gol

Skor Anda hanyalah jumlah tebakan yang Anda kirim ke pemeriksa (menghitung final, yang benar) untuk semua frasa uji. Skor terendah menang.

Anda harus memecahkan semua frasa dalam daftar. Jika program Anda gagal pada salah satu dari mereka, itu tidak valid.

Program Anda harus bersifat deterministik. Jika dijalankan dua kali pada kumpulan frasa sandi yang sama, ini harus mengembalikan hasil yang sama.

Dalam kasus seri pertama, saya akan menjalankan entri terikat di komputer saya masing-masing empat kali, dan waktu rata-rata terendah untuk menyelesaikan semua 1.000 kasus menang. Komputer saya menjalankan Ubuntu 14.04, dengan i7-3770K dan 16GB semacam RAM, dalam kasus yang membuat perbedaan pada program Anda. Untuk alasan itu, dan untuk memudahkan pengujian, jawaban Anda harus dalam bahasa yang memiliki kompiler / juru bahasa yang dapat diunduh dari web gratis (tidak termasuk uji coba gratis) dan tidak memerlukan pendaftaran / pendaftaran.

_{Judul diadaptasi dari XKCD}

Scala 9146 (min 7, maks 15, rata-rata 9,15) waktu: 2000 detik

Seperti banyak entri saya mulai dengan mendapatkan total panjang, kemudian menemukan spasi, mendapatkan informasi lebih banyak, mengurangi ke kandidat yang tersisa dan kemudian menebak frasa.

Terinspirasi oleh komik xkcd asli, saya mencoba menerapkan pemahaman mendasar saya tentang teori informasi. Ada satu triliun frase yang mungkin atau hanya di bawah 40 bit entropi. Saya menetapkan sasaran di bawah 10 tebakan per frasa uji, yang berarti kita harus belajar rata-rata hampir 5 bit per kueri (karena yang terakhir tidak berguna). Dengan setiap tebakan kami mendapatkan kembali dua angka dan secara kasar berbicara tentang kisaran potensial yang lebih besar dari angka-angka itu, semakin banyak yang kami harapkan untuk dipelajari.

Untuk menyederhanakan logika, saya menggunakan setiap kueri secara efektif dua pertanyaan terpisah sehingga setiap string tebakan adalah dua bagian, sisi kiri tertarik pada jumlah posisi yang benar (pasak hitam di dalang) dan sisi kanan tertarik pada jumlah karakter yang benar ( pasak total). Ini adalah permainan khas:

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

Menebak spasi

Setiap ruang menebak dapat mengembalikan paling banyak 2 pasak hitam; Saya mencoba membuat tebakan untuk mengembalikan 0,1, dan 2 pasak dengan probabilitas 1 / 4,1 / 2, dan 1/4 masing-masing. Saya percaya ini adalah yang terbaik yang dapat Anda lakukan untuk 1,5bits informasi yang diharapkan. Saya memilih string yang bergantian untuk tebakan pertama diikuti oleh tebakan yang dibuat secara acak, meskipun ternyata biasanya bermanfaat untuk mulai menebak pada percobaan kedua atau ketiga, karena kita tahu frekuensi panjang kata.

Mempelajari himpunan karakter

Untuk tebakan di sebelah kanan, saya memilih set karakter acak (selalu 2 dari huruf / huruf / huruf) sehingga jumlah yang diharapkan dikembalikan setengah dari panjang frasa. Varian yang lebih tinggi berarti lebih banyak informasi dan dari halaman wikipedia pada distribusi binomial, saya memperkirakan sekitar 3,5 bit per kueri (setidaknya untuk beberapa pertama sebelum informasi menjadi redundan). Setelah spasi diketahui, saya menggunakan string acak dari huruf yang paling umum di sisi kiri, dipilih agar tidak bertentangan dengan sisi kanan.

Menggabungkan kandidat yang tersisa

Game ini adalah penghitungan kecepatan / kueri efisiensi tradeoff dan penghitungan kandidat yang tersisa dapat memakan waktu sangat lama tanpa informasi terstruktur seperti karakter tertentu. Saya mengoptimalkan bagian ini dengan terutama mengumpulkan informasi yang tidak tetap dengan urutan kata, yang memungkinkan saya menghitung jumlah set karakter untuk setiap kata individual dan membandingkannya dengan jumlah yang dipelajari dari query. Saya mengemas penghitungan ini menjadi bilangan bulat panjang, menggunakan komparator dan penambah kesetaraan mesin untuk menguji semua jumlah karakter saya di parralel. Ini adalah kemenangan besar. Saya dapat mengemas hingga 9 hitungan di Long, tetapi saya menemukan mengumpulkan informasi tambahan tidak layak dan diselesaikan pada 6 sampai 7.

Setelah sisa kandidat diketahui, jika set cukup kecil saya memilih satu dengan log yang diharapkan terendah dari kandidat yang tersisa. Jika set cukup besar untuk membuat ini memakan waktu, saya memilih dari set sampel kecil.

Terimakasih semuanya. Ini adalah permainan yang menyenangkan dan membujuk saya untuk mendaftar ke situs.

Pembaruan: Kode yang dibersihkan untuk kesederhanaan dan keterbacaan, dengan sedikit perubahan pada algoritma, menghasilkan skor yang ditingkatkan.
Skor asli: 9447 (min 7, maks 13, rata-rata 9,45) waktu: 1876 detik

Kode baru adalah 278 baris Scala, di bawah ini

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

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

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

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

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

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

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

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

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

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

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

  object Querent {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C - total: 37171, min: 24, maks: 55, waktu: sekitar 10 detik

Saya meminjam ide Ray untuk menemukan panjang setiap kata dengan menebak spasi, kecuali saya melakukan pencarian biner daripada linear, yang menyelamatkan saya dari banyak tebakan.

Setelah saya menentukan panjang kata, saya kira dengan kata pertama yang cocok dengan panjangnya dan saya mencatat jumlah posisi yang benar. Kemudian saya memilih kata pertama dari himpunan semua kata yang memiliki jumlah posisi yang sama dengan tebakan pertama saya sebagai kata misteri. Untuk tebakan ketiga saya, saya memilih kata pertama dari himpunan semua kata yang memiliki jumlah posisi yang sama dengan tebakan pertama saya sebagai kata misteri dan jumlah posisi yang sama dengan tebakan kedua saya dengan kata misteri, dll.

Dengan menggunakan metode ini saya dapat menebak setiap kata, satu per satu, dalam sekitar 5-10 tebakan. Jelas kata ketiga yang harus saya lakukan sedikit berbeda karena saya tidak tahu panjangnya, tetapi metodenya mirip. Saya menggunakan file yang berisi matriks dari jumlah posisi yang setiap kata bagikan secara umum yang telah saya perhitungan sebelumnya. Mayoritas run-time terjadi saat memuat data yang dihitung sebelumnya. Anda dapat mengunduh semuanya di sini .

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

Sangat menyenangkan menontonnya dengan kata-kata:

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, maks: 29, total: 25146, waktu: 20 menit

min: 30, maks: 235, total: 41636, waktu: 4 menit

Memperbarui:

1. Gunakan pencarian biner untuk menemukan ruang. Idenya dipinjam dari jawaban Orby . Satu tempat yang saya optimalkan adalah jika Anda menemukan 2 spasi dalam rentang saat mencari ruang pertama, Anda dapat mempersempit rentang pencarian ruang kedua.
2. Simpan tebakan yang salah beserta hasilnya. Bandingkan dengan mereka dalam tebakan berikut. Ini bisa menghemat banyak.
3. Kurangi hitung enumerasi huruf menjadi 12, terima kasih untuk memperbarui # 2.

Metode ini tidak menggunakan keacakan sehingga skor tidak akan berubah.

Pertama menggunakan tebakan seperti berikut untuk menemukan spasi pertama dan kedua dalam jawabannya.

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

Kemudian, ia menghitung kemunculan setiap huruf dengan menebak aaaaa..., bbbbb....... Setelah ini biayanya sekitar 40 langkah. Faktanya, kita tidak perlu mencoba semua surat dan kita dapat mencobanya dalam urutan arbiter. Dalam kebanyakan kasus, mencoba sekitar 20 huruf sudah cukup. Di sini saya memilih 21.

Sekarang ia tahu panjang kata pertama dan kata kedua sehingga bisa menyaring daftar kandidat untuk dua kata ini. Biasanya akan ada sekitar 100 kandidat yang tersisa untuk masing-masing.

Kemudian hanya menyebutkan kata pertama dan kedua. Setelah dua kata pertama disebutkan, kita dapat menyimpulkan semua kata ketiga yang valid karena kita tahu jumlah karakternya.

Untuk mengoptimalkan kecepatan, saya menggunakan concurrent.futuresuntuk menambahkan multiprosesing ke program. Jadi Anda perlu Python 3 untuk menjalankannya dan saya mengujinya dengan Python 3.4 pada kotak Linux saya. Anda juga harus menginstal numpy.

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


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


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

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


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


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


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

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

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

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

# End of preprocessing


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

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

    spaces = s_l
    del s_l, s_r

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

    char_counts = np.array(char_counts)

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

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

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


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


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

Java 13.923 (min: 11, maks: 17)

Pembaruan: peningkatan skor (pecahkan <14 / crack avg!), Kode baru

• Memeriksa karakter yang dikenal sekarang lebih padat (sekarang ABABAB *, bukan -AAAA *)
• Saat tidak ada karakter yang dikenal tersedia, dua yang tidak dikenal akan dihitung dalam satu tebakan tunggal
• Tebakan yang salah disimpan dan digunakan untuk memeriksa kemungkinan kecocokan
• Beberapa tweaker konstan dengan logika baru di tempat

Pos asli

Saya telah memutuskan untuk sepenuhnya berfokus pada jumlah tebakan daripada kinerja (mengingat aturan). Ini menghasilkan program pintar yang sangat lambat.

Alih-alih mencuri dari program yang dikenal saya memutuskan untuk menulis semuanya dari awal, tetapi ternyata beberapa / kebanyakan ide adalah sama.

Algoritma

Beginilah cara kerja saya:

1. Lakukan permintaan tunggal yang menghasilkan jumlah e dan karakter secara total
2. Selanjutnya kita mencari spasi, menambahkan beberapa karakter yang tidak dikenal di akhir untuk mendapatkan jumlah karakter
3. Setelah spasi ditemukan, kami masih ingin mengetahui jumlah karakter yang lebih banyak, sementara itu saya juga mendapatkan lebih banyak data tentang karakter yang dikenal (jika mereka berada pada posisi genap) yang akan membantu saya menghilangkan banyak frasa.
4. Ketika kita mencapai batas tertentu (jejak / kesalahan) itu menghasilkan semua frase yang mungkin dan memulai pencarian biner, sebagian besar waktu masih menambahkan karakter yang tidak dikenal di akhir.
5. Akhirnya kami melakukan beberapa tebakan!

Contoh tebakan

Ini adalah contoh aktual:

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

Karena kode saya tidak pernah benar-benar fokus pada satu kata dan hanya mengumpulkan informasi tentang frasa lengkap, itu harus menghasilkan banyak frasa sehingga sangat lambat.

Kode

Dan akhirnya di sini adalah kode (jelek), jangan coba-coba memahaminya, maaf:

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 Permintaan; 2,4 detik 11,077 Pertanyaan; 125 mnt.

Min: 8, Maks: 13, Kueri Efektif: 10.095

Saya menghabiskan waktu terlalu lama untuk ini. : P

Kode tersedia di http://pastebin.com/7n9a50NM

Rev 1. tersedia di http://pastebin.com/PSXU2bga

Rev 2. tersedia di http://pastebin.com/gRJjpbbu

Revisi kedua saya. Saya berharap untuk memecahkan rintangan 11K untuk memenangkan hadiah, tapi saya kehabisan waktu untuk mengoptimalkan binatang ini.

Ini beroperasi pada prinsip yang sepenuhnya terpisah dari dua versi sebelumnya (dan memakan waktu sekitar 3.500 kali lebih lama untuk dijalankan). Prinsip umum adalah menggunakan ruang dan genap / karakter ganjil untuk mengurangi daftar kandidat menjadi ukuran yang dapat dikelola (biasanya antara 2-8 juta), dan kemudian melakukan kueri berulang dengan kekuatan diskriminasi maksimum (yaitu distribusi keluaran yang telah memaksimalkan entropi).

Bukan kecepatan tetapi memori adalah batasan utama. VM Java saya tidak akan membiarkan saya memesan tumpukan lebih dari 1.200 MB untuk alasan yang tidak jelas (mungkin Windows 7), dan saya menyetel parameter untuk memberi saya solusi terbaik yang tidak menghabiskan batas ini. Ini mengganggu saya bahwa menjalankan yang tepat dengan parameter yang tepat akan merusak 11K tanpa peningkatan waktu eksekusi yang berarti. Saya membutuhkan komputer baru. : P

Yang paling mengganggu saya adalah bahwa 982 pertanyaan dalam implementasi ini adalah pertanyaan "validasi" yang tidak berguna. Mereka tidak memiliki tujuan selain untuk memenuhi aturan bahwa oracle harus mengembalikan nilai "Anda mendapatkannya" di beberapa titik, meskipun dalam implementasi saya jawaban yang benar telah dikurangkan dengan pasti sebelum kueri ini dalam 98,2% kasus. Sebagian besar kiriman sub-11K lainnya mengandalkan teknik penyaringan yang menggunakan string kandidat sebagai string kueri dan karenanya tidak mengalami penalti yang sama.

Untuk alasan ini, meskipun jumlah permintaan resmi saya adalah 11.077 (kurang dari pemimpin, asalkan kode mereka terbukti sesuai, benar-untuk-spek, dll.), Saya dengan berani menyatakan bahwa kode saya membuat 10.095 kueri efektif , artinya hanya 10.095 kueri yang sebenarnya perlu untuk menentukan semua frasa lulus dengan kepastian 100%. Saya tidak yakin implementasi lainnya akan cocok dengan itu, maka saya akan menganggapnya sebagai kemenangan saya. ;)

Java - min: 22, maks: 41, total: 28353, waktu: 4 detik

Program menebak kata sandi dalam 3 langkah:

1. temukan posisi ruang dengan pencarian biner
2. hitung kemunculan karakter paling sering dalam 3 kata
3. temukan kata-kata mulai dari kiri, menggunakan info yang dikumpulkan di atas

Itu juga menangani satu set "karakter buruk" yang mengembalikan hasil nol dalam pencarian, dan satu set "karakter baik" yang ditempatkan di tempat lain di frasa sandi.

Di bawah ini adalah contoh nilai yang dikirimkan secara berturut-turut untuk menebak, Anda dapat melihat 3 langkah:

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

Kode:

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 menebak, 0,6 detik

Saya mencari kecepatan daripada jumlah tebakan terendah, meskipun saya pikir jumlah tebakan saya masih lebih rendah daripada misalnya serangan kamus langsung. Saya tidak menghitung jumlah huruf dalam kata sandi tetapi di tempat yang salah, karena metode saya tidak menggunakannya, tetapi jika Anda merasa ini memberi saya keuntungan yang tidak adil, saya akan menerapkannya. Saya cukup mulai dengan string tebakan kosong, dan tambahkan akhiran karakter tunggal di atasnya yang menambah daftar karakter saya, memeriksa hasil 'centang' untuk melihat apakah jumlah karakter yang benar sama dengan panjang tebakan. Misalnya, jika kata sandi 'buruk', saya kira:

a, b

Sebuah

a, b, c, d

Saya juga mencoba mengurutkan huruf berdasarkan frekuensi huruf bahasa Inggris, yang mencukur sekitar 35% dari jumlah tebakan, dan juga waktu. Saya memecahkan semua kata sandi dalam 0,82 detik. Statistik dicetak di akhir.

import string
import time

class Checker():

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

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


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

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

        minLength  = min(lenPass, lenGuess)

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

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

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

    def nextPass(self):

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

        self.numGuessesCur = 0
        self.currentIndex += 1

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

    def main(self):

        t0 = time.time()

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

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

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

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

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

EDIT: Menghapus satu nyasar +1 dan -1 dari dua sementara loop dari iterasi pengujian sebelumnya, juga menambahkan statistik tambahan untuk tebakan paling sedikit dan tebakan terbanyak untuk satu kata sandi.

EDIT2: menambahkan tabel pencarian untuk huruf 'berikutnya' yang paling umum, per huruf. Kecepatan meningkat pesat dan jumlah tebakan menurun

C ++ - 11383 10989 Cocok!

Memperbarui

Memperbaiki kebocoran memori, dan menghapus 1 upaya lagi untuk mengurangi ukuran kamus kata individual. Memakan waktu sekitar 50 menit pada mac pro saya. Kode yang diperbarui ada di github.

Saya beralih ke strategi pencocokan frasa, dan menyusun ulang kode, dan memperbaruinya di github https://github.com/snjyjn/mastermind

Dengan pencocokan berbasis Frasa, kami berupaya sebanyak 11383! Itu mahal dalam hal menghitung! Saya juga tidak suka struktur kode! Dan masih jauh di belakang yang lain :-(

Inilah yang saya lakukan:

1. Ukur panjang frasa - menggunakan string dengan semua 26 karakter kali maksimum (maks = 3 * makswordlen + 2) dan 2 spasi. Maxlen karakter pertama adalah yang paling sering dalam kamus yaitu e
2. Gunakan jenis strategi saringan biner untuk mengidentifikasi ruang - lakukan sejumlah upaya, dan mengidentifikasi pasangan ruang potensial. Buat string uji khusus untuk direduksi menjadi satu pasangan.

3. Secara paralel, tambahkan string uji 'dibuat' untuk mendapatkan informasi lebih lanjut tentang frasa. Strategi saat ini adalah sebagai berikut:

   Sebuah. Gunakan karakter sesuai frekuensi mereka dalam kamus.

   b. Kita sudah tahu hitung untuk yang paling sering

   c. String Tes 1 = 5 karakter berikutnya. Ini memberi kita hitungan karakter ini dalam frasa.

   d. 3 string tes berikutnya = masing-masing 5 karakter berikutnya, mencakup total 20 karakter dalam 4 upaya sebagai tambahan dari 1 karakter pertama. Ini memberi kami hitungan untuk 5 karakter terakhir ini juga. set dengan 0 hitungan sangat bagus untuk mengurangi ukuran kamus!

   e. Sekarang untuk pengujian sebelumnya yang memiliki jumlah terkecil, bukan nol, pisahkan string menjadi 2, dan gunakan 1 untuk pengujian. Hitungan yang dihasilkan memberi tahu kita tentang pemisahan lainnya juga.

   f. Sekarang ulangi tes dengan karakter (berbasis 0),

       1,6,11,16,21
       2,7,12,17,22
       3,8,13,18,23
       4,9,14,19,24
       Ini seharusnya memberi kita 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. Setelah spasi diidentifikasi, gunakan kendala sejauh ini (sebanyak mungkin tes yang bisa dilakukan dalam upaya ini) untuk mengurangi ukuran kamus. Juga buat 3 sub kamus, 1 untuk setiap kata.

2. Sekarang lakukan beberapa tebakan untuk setiap kata, dan ujilah.
   Gunakan hasil ini untuk mengurangi ukuran kamus individu.
   Hiasi ini dengan karakter uji juga (setelah panjang) untuk mendapatkan lebih banyak kendala pada frasa! Saya menggunakan 3 tebakan di versi final - 2 untuk kata 1, dan 1 untuk kata 2

3. Ini membawa kamus ke ukuran yang dapat dikelola. Lakukan lintas produk, terapkan semua kendala seperti sebelumnya untuk membuat kamus frasa.

4. Pecahkan kamus frasa melalui serangkaian tebakan - kali ini menggunakan informasi kecocokan posisi dan karakter.

5. Pendekatan ini membawa kita ke bawah upaya 11383:

    Statistik Pencocokan
    ------------------
    Panjangnya: 1000
    Spasi: 6375
    Word 1: 1996
    Word 2: 999
    Ungkapan: 1013
    JUMLAH: 11383

    Statistik Kamus
    kata 0 6517
    kata 1 780 221 92
    kata 2 791 233
    kata 3 772
    frasa 186 20 4 2

    Waktu solusi: 20 menit di macbook pro saya.

Posting Sebelumnya

Saya telah membersihkan kode, dan mengunggahnya ke https://github.com/snjyjn/mastermind Dalam prosesnya, saya memperbaikinya, dan masih punya 1 ide lagi untuk dicoba. Ada satu perbedaan besar dari apa yang saya lakukan kemarin:

Menghapus tebakan individu untuk karakter berdasarkan karakter frekuensi tinggi dalam kamus untuk kata 1 & 2, dan sebagai gantinya saya menggunakan string berdasarkan karakter frekuensi tertinggi untuk posisi itu.

Statistik sekarang terlihat seperti:

Spasi: 6862
Word 1: 5960
Word 2: 5907
Kata 3: 2953
JUMLAH: 21682

Pos Asli

Permintaan maaf untuk 'jawaban', tapi saya baru saja membuat akun, dan tidak memiliki reputasi yang cukup untuk menambahkan komentar.

Saya memiliki program c ++, yang memakan waktu sekitar 6,5 detik, dan 24107 upaya pencocokan. Ini adalah sekitar 1400 baris c ++. Saya tidak senang dengan kualitas kode, dan akan membersihkannya sebelum saya memasangnya di lain hari. Tetapi demi kepentingan komunitas dan berkontribusi dalam diskusi, inilah yang saya lakukan:

• Baca kamus, dapatkan beberapa info dasar tentangnya - panjang kata minimum, frekuensi karakter, dll.

• Identifikasi spasi pertama - Ini memiliki 2 bagian, yang pertama adalah seperangkat kueri yang terus mempartisi ruang (mirip dengan satu C. Chafouin):

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

Ini tidak sepenuhnya akurat, karena saya menggunakan panjang kata min / maks, dan saya menggunakan jumlah kecocokan pada setiap tahap, tetapi Anda mendapatkan idenya. Pada titik ini, masih belum ada informasi yang cukup untuk mendapatkan 2 ruang, tetapi saya memiliki cukup untuk menguranginya menjadi sejumlah kecil kombinasi. Dari kombinasi itu, saya bisa membuat beberapa pertanyaan spesifik, yang akan mempersempitnya menjadi 1 kombinasi.

• Kata Pertama - Dapatkan Subdictionary, yang memiliki kata-kata dengan panjang yang tepat. Subictionary memiliki statistik sendiri. Lakukan beberapa tebakan dengan karakter paling sering, sehingga Anda mendapatkan jumlah karakter ini dalam kata. Kurangi kamus lagi berdasarkan informasi ini. Buat kata tebakan, yang memiliki karakter paling berbeda, dan gunakan itu. Setiap respons menyebabkan pengurangan kamus hingga kami memiliki kecocokan yang tepat, atau kamus berukuran 1.

• Kata Kedua - mirip dengan Kata pertama

• Kata ketiga - ini sangat berbeda dari yang lain 2. Kami tidak memiliki informasi ukuran untuk ini, tetapi kami memiliki semua pertanyaan sebelumnya (yang telah kami simpan). Kueri ini memungkinkan Anda untuk mengurangi kamus. Logikanya ada pada baris:

 - kueri abc mengembalikan hitungan kecocokan 1
 - kata 1 dan 2 tidak memiliki b atau c
 - Jelas bahwa b atau c tidak dapat menjadi bagian dari kata 3

Gunakan kamus yang diperkecil untuk menebak, dengan karakter yang paling beragam, dan terus mengurangi kamus hingga ukuran 1 (seperti dalam kata 1 dan 2).

Statistiknya terlihat seperti:

    Temuan luar angkasa: 7053
    Kata 1 karakter: 2502
    Kata 1 kata: 3864
    Kata 2 karakter: 2530
    Kata 2 kata: 3874
    Kata 3 karakter: 2781
    Kata 3 kata: 1503
    JUMLAH: 24107

Go - Total: 29546

Mirip dengan yang lain, dengan beberapa optimasi.

1. Dapatkan total panjang dengan pengujian AAAAAAAABBBBBBBBCCCCCCCC...ZZZZZZZZ
2. Tentukan panjang sebenarnya dari ketiga kata dengan memindahkan spasi dari kedua ujungnya.
3. Saring setiap kata dengan jumlah surat dari beberapa huruf umum.
4. Kurangi kandidat yang ditetapkan dengan menguji string, dan menghapus kandidat lain yang tidak memberikan hasil yang sama. Ulangi sampai pemenang ditemukan.

Ini tidak terlalu cepat.

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
}

Jawa: 58.233

(program referensi)

Bot sederhana untuk dikalahkan semua orang. Ini menggunakan 26 tebakan awal untuk setiap frasa untuk menetapkan jumlah karakter. Maka itu menghilangkan semua kata yang mengandung huruf tidak ditemukan dalam frasa.

Kemudian muncul lingkaran O (n ³ ) yang masif di atas kata-kata yang tersisa. Pertama ia memeriksa setiap frase kandidat untuk melihat apakah itu anagram. Jika demikian, tebakanlah, abaikan hasilnya kecuali itu adalah pasangan yang sempurna. Saya telah melihatnya menggunakan antara 28-510 tebakan untuk frasa yang diberikan sejauh ini.

Ini lambat , dan sepenuhnya tergantung pada berapa banyak kata yang bisa dihilangkan langsung dari 26 tebakan awal. Sebagian besar waktu menyisakan antara 1000-4000 kata untuk diulang. Saat ini sudah berjalan sekitar 14 jam, dengan kecepatan ~ 180s / frase. Saya perkirakan akan selesai 50 jam, dan akan memperbarui skor pada saat itu. Anda mungkin harus melakukan sesuatu yang lebih pintar atau lebih dari ini.

(pembaruan) Akhirnya selesai, dengan tebakan di bawah 60k.

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, Waktu 2,5s

Karena bot bodohku akhirnya selesai berjalan, aku ingin mengirimkan sesuatu yang sedikit lebih cepat. Ini berjalan hanya dalam beberapa detik, tetapi mendapat skor bagus (tidak cukup menang> <).

Pertama menggunakan string pad besar untuk mendapatkan panjang total frasa. Kemudian pencarian biner untuk menemukan spasi, mirip dengan yang lain. Saat melakukan ini, ia juga mulai memeriksa huruf satu per satu (dalam urutan pivot) sehingga dapat menghilangkan kata-kata yang mengandung lebih banyak huruf apa pun daripada seluruh frasa.

Setelah panjang kata, ia menggunakan langkah reduksi biner untuk mempersempit pilihan untuk daftar kata. Itu memilih daftar terbesar dan surat yang kira-kira setengah dari kata-kata. Itu menebak pad panjang kata dari surat itu untuk menentukan bagian mana yang dibuang. Ini juga menggunakan hasil untuk menghilangkan kata-kata di daftar lain yang memiliki terlalu banyak surat.

Setelah daftar hanya terdiri dari anagram, ini tidak berfungsi. Pada saat itu saya hanya mengulanginya sampai tinggal dua yang tersisa (atau satu jika kata-kata lainnya tidak diketahui).

Jika saya memiliki jumlah kata total empat (dua dikenal dan satu dengan dua opsi), saya melewatkan pengecekan pengurangan dan anagram dan hanya menebak salah satu opsi sebagai frase penuh. Jika tidak berhasil, maka itu pasti yang lain, tapi saya menghemat 50% dari waktu.

Berikut ini contohnya, menunjukkan frasa pertama sedang di-crack:

                                             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

Dan tentu saja, kodenya:

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