mastermind horse battery staple

Question

Objective

Given a list of three-word passphrases, crack them all. Each time you guess, you will be given a clue in the style of Mastermind, depicting how many characters match the password, and how many are in their correct position. The objective is to minimize the total number of guesses over all test cases.

Passphrases

From my system's default word list, I randomly chose 10,000 distinct words to make the dictionary for this challenge. All words consist of a-z only. This dictionary can be found here (raw).

From this dictionary, I generated 1000 passphrases consisting of three random space-separated words each (apple jacks fever, for example). Individual words can be reused within each passphrase (hungry hungry hippos). You can find the list of passphrases here (raw), with one per line.

Your program can use/analyze the dictionary file however you want. You cannot analyze the passphrases to optimize for this specific list. Your algorithm should still work given a different list of phrases

Guessing

To make a guess, you submit a string to a checker. It should return only:

• The number of characters in your string also in the passphrase (not in the correct position)
• The number of characters in the correct position

If your string is a perfect match, it may output something indicating that (mine uses -1 for the first value).

For example, if the passphrase is the big cat and you guess tiger baby mauling, the checker should return 7,1. 7 characters (ige<space>ba<space>) are in both strings but different positions, and 1 (t) is in the same position in both. Notice that spaces count.

I've written an example (read: not optimized) function in Java, but feel free to write your own as long as it gives only the information required.

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

Scoring

Your score is simply the number of guesses you submit to the checker (counting the final, correct one) for all test phrases. The lowest score wins.

You must crack all the phrases in the list. If your program fails on any of them, it is invalid.

Your program must be deterministic. If run twice on the same set of passphrases, it should return the same result.

In the case of a tie for first, I will run the tied entries on my computer four times each, and the lowest average time to solve all 1000 cases wins. My computer is running Ubuntu 14.04, with an i7-3770K and 16GB of some sort of RAM, in case that makes a difference to your program. For that reason, and to facilitate testing, your answer should be in a language which has a compiler/interpreter that can be downloaded from the web free of charge (not including free trials) and does not require sign up/registration.

_{Title adapted from XKCD}

Answer 1

C - total: 37171, min: 24, max: 55, time: around 10 seconds

I borrowed Ray's idea to find the length of each word by guessing with spaces, except I am doing a binary search rather than a linear one, which saves me a lot of guesses.

Once I determine the length of a word, I guess with the first word which matches its length and I record the number of correct positions. Then I select the first word from the set of all words which share the same number of positions with my first guess as the mystery word. For my third guess I select the first word from the set of all words which share the same number of positions with my first guess as the mystery word and the same number of positions as my second guess with the mystery word, etc.

Using this method I'm able to guess each word, one at a time, in about 5-10 guesses. Obviously the third word I have to do a little differently because I don't know its length, but the method is similar. I use a file which contains a matrix of the number of positions each word share in common that I've precomputed. The majority of the run-time is incurred while loading the precomputed data. You can download everything here.

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

It's also fun to watch it narrow in on words:

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.

Answer 2

Python 3.4 - min: 21, max: 29, total: 25146, time: 20min

min: 30, max: 235, total: 41636, time: 4min

Update:

1. Use binary search to find space. The idea is borrowed from Orby's answer. One spot I optimized is that if you found 2 spaces in a range when searching for the first space, you can narrow the search range of the second space.
2. Save wrong guesses along with their result. Compare with them in following guesses. This can save a lot.
3. Reduce letter enumerate count to 12, thanks to update #2.

---

This mehod don't use randomness so the score will not change.

First it use guesses like the following to find the first and second spaces in the answer.

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

Then, it count occurrence of each letter by guessing aaaaa..., bbbbb....... After these it will cost about 40 steps. In fact, we don't need to try all the letters and we can try them in arbitary order. In most cases, trying about 20 letters is enough. Here I choose 21.

Now it know the length of the first word and the second word so it can filter out a list of candidates for these two words. Normally it will have about 100 candidates left for each.

Then it just enumerate the first and the second word. Once the first two words is enumerated, we can infer all valid third word since we know it's character counts.

To optimize for speed, I use the concurrent.futures to add multiprocessing to the program. So you need Python 3 to run it and I tested it with Python 3.4 on my Linux box. Also, you need to install 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)

Answer 3

Scala 9146 (min 7, max 15, avg 9.15) time: 2000 seconds

Like many entries I start by getting the total length, then finding the spaces, getting a bit more information, reducing down to the remaining candidates and then guessing phrases.

Inspired by the original xkcd comic, I tried to apply my rudimentary understanding of information theory. There are a trillion possible phrases or just under 40 bits of entropy. I set a goal of under 10 guesses per test phrase, which means we need to learn on average nearly 5 bits per query (since the last one is useless). With each guess we get back two numbers and roughly speaking the bigger potential range of those numbers, the more we expect to learn.

To simplify the logic, I use each query as effectively two separate questions so each guess string is two parts, a left side interested in the number of correct positions (black pegs in mastermind) and a right side interested in the number of correct chars (total pegs). Here is a typical game:

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

Guessing spaces

Each space guess can return at most 2 black pegs; I tried to construct guesses to return 0,1, and 2 pegs with probabilities 1/4,1/2, and 1/4 respectively. I believe this is the best you can do for an expected 1.5bits of information. I settled on an alternating string for the first guess followed by randomly generated ones, though it turns out it's usually worthwhile to just start guessing on the second or third try, since we know the word length frequencies.

Learning character set counts

For the right side guesses I pick random (always 2 of e/i/a/s) sets of characters so that the expected number returned is half the phrase length. A higher variance means more information and from the wikipedia page on the binomial distribution I'm estimating about 3.5 bits per query (at least for the first few before the information becomes redundant). Once spacing is known, I use random strings of the most common letters on the left side, chosen so as not to conflict with the right side.

Coalescing the remaining candidates

This game is a compute speed / query efficiency tradeoff and the enumeration of remaining candidates can take a really long time without structured information like specific characters. I optimized this part by mainly collecting information that's invariant with word order, which lets me precompute the character-set counts for each individual word and compare them with the counts learned from the queries. I pack these counts into a Long integer, using the machine equality comparator and adder to test all my character counts in parralel. This was a huge win. I can pack up to 9 counts in the Long, but I found collecting the additional information wasn't worth it and settled on 6 to 7.

After the remaining candidates are known, if the set is reasonably small I pick the one with the lowest expected log of remaining candidates. If the set is large enough to make this time consuming, I choose from a small sample set.

Thanks everyone. This was a fun game and enticed me to sign up to the site.

Update: Cleaned code for simplicity and readability, with minor tweaks to the algorithm, resulting in an improved score.
Original score: 9447 (min 7, max 13, avg 9.45) time: 1876 seconds

New code is 278 lines of Scala, below

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)"
  }
}

Answer 4

Java 13,923 (min: 11, max: 17)

Update: improved score (broke the <14/crack avg!), new code

• Checking of known characters now denser (now ABABAB*, instead of -A-A-A-A*)
• When no known characters are available, two unknowns will be counted in a single guess
• Wrong guesses are stored and used to check possible matches
• Some constant tweaking with new logic in place

Original post

I've decided to focus completely on the amount of guesses instead of performance (given the rules). This has resulted in a very slow smart program.

Instead of stealing from the known programs I decided to write everything from scratch, but it turns out some/most ideas are the same.

Algorithm

This is how mine works:

1. Do a single query which results in the amount of e's and characters in total
2. Next we look for the spaces, appending some unknown characters at the end to get a character count
3. Once the spaces are found we still want to find out more character counts, in the mean time I also get more data on the known characters (if they are on even positions) that will help me eliminate a lot of phrases.
4. When we reach a certain limit (trail/error) it generates all possible phrases and starts a binary search, most of the time still appending unknown characters at the end.
5. Finally we do some guesses!

Example guesses

Here is an actual example:

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

Because my code never really focusses on single words and only collects information about the complete phrase it has to generate a lot of those phrases making it very slow.

Code

And finally here is the (ugly) code, don't even try to understand it, sorry:

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

}

Answer 5

Java - 18,708 Queries; 2.4 seconds 11,077 Queries; 125 min.

Min: 8, Max: 13, Effective Queries: 10,095

I spent way too long on this. :P

Code is available at http://pastebin.com/7n9a50NM

Rev 1. available at http://pastebin.com/PSXU2bga

Rev 2. available at http://pastebin.com/gRJjpbbu

My second revision. I'd hoped to crack the 11K barrier to win the prize, but I've run out of time to optimize this beast.

It operates on an entirely separate principle from the previous two versions (and takes approximately 3,500 times as long to run). The general principle is to use space and even/odd character sieving to reduce the candidate list to manageable size (usually between 2-8 million), and then perform repeated queries with maximum discrimination power (i.e. whose output distribution has maximized entropy).

Not speed but memory is the principal limitation. My Java VM won't let me reserve a heap larger than 1,200 MB for some obscure reason (probably Windows 7), and I tuned the parameters to give me the best possible solution that doesn't exhaust this limit. It irks me that a proper run with the proper parameters would break 11K with no meaningful increase in execution time. I need a new computer. :P

What irks me just as much is that 982 of the queries in this implementation are useless "validation" queries. They have no purpose other than to satisfy the rule that the oracle must return a special "you got it" value at some point, even though in my implementation the correct answer has been deduced with certainty prior to this query in 98.2% of cases. Most of the other sub-11K submissions rely on filtering techniques that use candidate strings as query strings and hence don't suffer the same penalty.

For this reason, although my official query count is 11,077 (short of the leaders, provided their code proves compliant, true-to-spec, etc.), I boldly state that my code makes 10,095 effective queries, meaning that only 10,095 queries are actually necessary to determine all pass phrases with 100% certainty. I'm not sure any of the other implementations will match that, hence I'll consider it my wee victory. ;)

Answer 6

Java - min: 22, max: 41, total: 28353, time: 4 seconds

The program guesses the password in 3 steps :

1. find the space positions with a binary search
2. count the occurrences of most frequent characters in the 3 words
3. find the words starting from left, using the info gathered above

It also handles a set of "bad characters" that return a zero result in the search, and a set of "good characters" that are placed somewhere else in the passphrase.

Below an example of the values successively sent for guessing, you can see the 3 steps:

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

The code:

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

Answer 7

PYTHON 2.7 - 156821 guesses, 0.6 seconds

I went for speed rather than lowest number of guesses, although I figure my number of guesses is still lower than for example a straight up dictionary attack would be. I do not calculate the number of letters in the password but in the wrong place, as my method doesn't use it, but if you feel this gives me an unfair advantage, I will implement it. I simply start with an empty guess string, and add a single character suffix on it which increments over my list of chars, checking the result of 'check' to see if the number of correct characters is equal to the length of the guess. For example, if the password was 'bad', I would guess:

a,b

a

a,b,c,d

I also tried sorting the letters by english letter frequency, which shaved off about 35% of the number of guesses, as well as the time. I cracked all passwords in 0.82 seconds. Stats are printed at the end.

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: Removed a stray +1 and -1 from two of the while loops from previous iterations of testing, also added additional stats for least guesses and most guesses for an individual password.

EDIT2: added lookup table for most common 'next' letter, per letter. Greatly increased speed and decreased guess count

Answer 8

C++ - 1138310989 Matches!

Update

Fixed memory leaks, and removed 1 more attempt to reduce the individual word dictionary sizes. Takes about 50 minutes on my mac pro. Updated code is on github.

---

I switched over to the phrase matching strategy, and reworked the code, and updated it on github https://github.com/snjyjn/mastermind

With Phrase based matching, we are down to 11383 attempts! It is expensive in terms of compute! I also dont like the code structure! And it is still way behind the others :-(

This is how I am doing it:

1. Measure the length of the phrase - using a string with all 26 characters max times (max = 3 * maxwordlen + 2) and 2 spaces. First maxlen characters are the most frequent in the dictionary i.e. e
2. Use a binary sieve kind of strategy to identify the spaces - do a set number of attempts, and identify potential pairs of spaces. Create specific test strings to reduce to a single pair.

3. In parallel, append 'crafted' test strings to get more information about the phrase. The current strategy is as follows:

   a. Use characters in order of their frequency in the dictionary.

   b. We already know the count for the most frequent

   c. 1st Test string = next 5 characters. This gives us the count of these characters in the phrase.

   d. next 3 test strings = next 5 characters each, covering a total of 20 characters in 4 attempts in addition to the first 1 char. This gives us the count for these last 5 characters as well. sets with 0 count are great for reducing the dictionary size!

   e. Now for the previous test that had the least, non-zero counts, split the string into 2, and use 1 for testing. The resulting count tells us about the other split as well.

   f. Now repeat tests with characters (0-based),

       1,6,11,16,21
       2,7,12,17,22
       3,8,13,18,23
       4,9,14,19,24
       This should give us 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. Once the spaces are identified, use the constraints so far (as many tests as could be done in these attempts) to reduce the size of the dictionary. Also create 3 sub dictionaries, 1 for each word.

2. Now do some guesses for each word, and test it.
   Use these results to reduce the individual dictionary sizes.
   Decorate this with test characters as well (after the length) to get more constraints on the phrase! I used 3 guesses in the final version - 2 for word 1, and 1 for word 2

3. This brings the dictionary to a manageable size. Perform a cross product, applying all constraints as before to create a phrase dictionary.

4. Solve for the phrase dictionary through a series of guesses - this time using both position and character match information.

5. This approach brings us to under 11383 attempts:

    Matcher Statistics
    ------------------
    Length : 1000
    Spaces : 6375
    Word 1 : 1996
    Word 2 : 999
    Phrase : 1013
    TOTAL  : 11383

    Dictionary Statistics
    word 0  6517
    word 1  780 221 92
    word 2  791 233
    word 3  772
    phrase  186 20  4   2

    Solution time: 20 minutes on my macbook pro.

Previous Post

I have cleaned up the code, and uploaded it to https://github.com/snjyjn/mastermind In the process, I improved it, and still have 1 more idea to try out. There 1 one major difference from what I had done yesterday:

Removed the individual guessing for characters based on high frequency characters in the dictionary for words 1 & 2, and instead I use a string based on the highest frequency character for that position.

The statistics now look like:

Spaces  :  6862
Word 1  :  5960
Word 2  :  5907
Word 3  :  2953
TOTAL   : 21682

Original Post

Apologies for the 'answer', but I just created an account, and dont have enough reputation to add a comment.

I have a c++ program, which takes about 6.5seconds, and 24107 match attempts. It is about 1400 lines of c++. I am not happy about the code quality, and will clean it before I put it up in another day or so. But in the interest of the community and contributing to the discussion, this is what I do:

• Read the dictionary, get some basic info about it - min/max word length, character frequency, etc.

• First identify spaces - This has 2 halves, the first is a set of queries which continue to partition the space (similar to one C. Chafouin):

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

This is not exactly accurate, since I use the min / max word length, and I use the match counts at each stage, but you get the idea. At this point, there is still not sufficient information to get the 2 spaces, but I do have enough to reduce it to a small number of combinations. From those combinations, I can make a couple of specific queries, which will narrow it down to 1 combination.

• First Word - Get a Subdictionary, which has words of the right length. The subdictionary has its own stats. Do a few guesses with the most frequent characters, so you get a count of these characters in the word. Reduce the dictionary again based on this inforamtion. Create a guess word, which has the most different characters, and use that. Each response causes a reduction in the dictionary till we have an exact match, or the dictionary is size 1.

• Second Word - similar to First word

• Third word - this is most different from the other 2. We dont have size information for this, but we do have all the previous queries (which we have kept). These queries allow you to reduce the dictionary. The logic is on the lines of:

 - query abc returned a match count of 1
 - words 1 and 2 dont have b or c
 - It is clear that b or c cannot be a part of word 3

Use the reduced dictionary to make a guess, with the most diverse characters, and continue to reduce the dictionary till size 1 (as in words 1 and 2).

The statistics look like:

    Space finding:  7053
    Word 1 chars :  2502
    Word 1 words :  3864
    Word 2 chars :  2530
    Word 2 words :  3874
    Word 3 chars :  2781
    Word 3 words :  1503
    TOTAL        : 24107

Answer 9

Go - Total: 29546

Similar to some others, with some optimizations.

1. Get total length by testing AAAAAAAABBBBBBBBCCCCCCCC...ZZZZZZZZ
2. Determine actual lengths of all three words by moving spaces in from both ends.
3. Filter each word by letter counts of some common letters.
4. Reduce candidate set by testing a string, and removing other candidates that don't provide the same results. Repeat until winner found.

It is not particularly fast.

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
}

Answer 10

Java : 58,233

(reference program)

A simple bot for everyone to beat. It uses an initial 26 guesses for each phrase to establish a character count. Then it eliminates all words that contain letters not found in the phrase.

Then comes a massive O(n³) loop over the remaining words. First it checks each candidate phrase to see if it's an anagram. If so, it guesses it, ignoring the results unless it's a perfect match. I've seen it use between 28-510 guesses for any given phrase so far.

This is slow, and it entirely depends on how many words can be eliminated straight from the initial 26 guesses. Most of the time it leaves between 1000-4000 words to loop over. Right now it's been running for somewhere around 14 hours, at a rate of ~180s/phrase. I estimate it will take 50 hours to complete, and will update the score at that time. You should probably do something smarter or more thready than this.

(update) It finally finished, with a bit under 60k guesses.

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

Answer 11

Java : 28,340 26,185

Min 15, Max 35, Time 2.5s

Since my stupid bot finally finished running, I wanted to submit something a little faster. It runs in just a few seconds, but gets a good score (not quite winning ><).

First it uses a big pad string to get the total length of the phrase. Then binary search to find spaces, similar to others. While doing this, it also starts checking letters one at a time (in pivot-order) so it can eliminate words that contain more of any letter than the entire phrase.

Once it has the word lengths, it uses a binary reduction step to narrow down the choices for the word lists. It chooses the largest list and a letter that's in approx half the words. It guesses a word-length pad of that letter to determine which half to throw away. It also uses the results to get rid of words in the other lists that have too many of the letter.

Once a list consists of anagrams only, this doesn't work. At that point I just loop through them until only two remain (or one if the other words are not known).

If I have a total word count of four (two known and one with two options), I skip the reduction and anagram checks and just guess one of the options as a full phrase. If it doesn't work, then it's gotta be the other, but I save a guess 50% of the time.

Here's an example, showing the first phrase being cracked:

                                             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

And of course, the code:

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

Answer 12

C# - 10649 (min 8, max 14, avg: 10.6) time: ~12 hours

This is what it looks like:

    13, whiteface rends opposed, 00:00:00.1282731, 00:01:53.0087971, 00:00:09.4368140
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeefffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkklllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooopppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppppppppqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssstttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz  
.. . . .  . .  . .  .............................................rrrrrrrrrrrrrrrrrrssssssssssssssssssttttttttttttttttttiiiiiiiiiiiiiiiiiinnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaa
. . .  . . . . . .  .............................................sssssssssssssssssslllllllllllllllllldddddddddddddddddduuuuuuuuuuuuuuuuuummmmmmmmmmmmmmmmmmrrrrrrrrrrrrrrrrrr
.. . .. ....... .................................................nnnnnnnnnnnnnnnnnnddddddddddddddddddiiiiiiiiiiiiiiiiiiggggggggggggggggggllllllllllllllllllffffffffffffffffff
.. . ............ ...............................................rrrrrrrrrrrrrrrrrrtttttttttttttttttthhhhhhhhhhhhhhhhhhddddddddddddddddddooooooooooooooooooffffffffffffffffff
....... . .......................................................ssssssssssssssssssttttttttttttttttttuuuuuuuuuuuuuuuuuuhhhhhhhhhhhhhhhhhhmmmmmmmmmmmmmmmmmmpppppppppppppppppp
....... ... .....................................................aaaaaaaaaaaaaaaaaa
......... ..... .................................................iiiiiiiiiiiiiiiiii
sheffield eject postwar
projected leigh gathers
portfolio felts escapee
fortescue ethyl affixes
whiteface rends opposed

Solver

It uses a forward-looking solver. Before it makes a guess, it estimates the number of distinct values returned from the mastermind given the currently possible passphrases. The guess that maximizes the number of distinct results is the one used.

For the space guessing phase it considers only possible combinations of " " and ".". For the phrase guessing phase, it creates the whole list of currently possible passphrases (which is why its so slow).

Letter Counts

Letter counts are thrown in with the space finding. The letter sets were chosen by a greedy search, adding one letter at a time and sampling random test phrases to see how effective the set is.

Code is here: https://github.com/Tyler-Gelvin/MastermindContest

No interface was specified, so all input is hardcoded and unit tests are the only interface. The "main" test is SolverFixture.SolveParallelAll.

Answer 13

C# - Total: 1000, Run Time: 305 Seconds, Avg: 24, Min: 14, Max: 32

Wow Avg's < 15 that's pretty good, well I can't beat that but I did take a stab at it so here's my approach. I broke it up word by word then solved them in succession. By determining the length of the first two words and then making a few strategic guesses(each time filtering by the previously guessed word) I was able to obtain the answer with a relatively small number of guesses. Over the period I developed this I was able to optimize most parts of it to preform efficiently(in number guesses) but the fault with it lies with the initial design decision to logically solve one word at a time, this causes me to discard parts of guesses and/or not run guesses as efficiently as possible, which in turn means I'm not winning this one ;(.

Still a interesting design(at least I think so), one thing to note with the included code, in certain cases I can determine the answer without ever running a guess that returns -1, if that is required simple uncomment the line of code labelled "ADD GUESS HERE(if required)"(and add up to +1 to all my scores :( )

Algorithm(My Sudo Code Thinking)

So really there's two parts to this, the first two words, and the last word. This may make no sense to anybody but me, but I've tried to add enough comments to the code so maybe that will make more sense:

NextWord(one of the two first two words)

{

var lengthOfPossibleWord = Determine length of the word(In code see: efficient way to find length)

List possibilities = All Words of that length(lengthOfPossibleWord)

Make a guess

possibilities = possibilities where(for the all guesses) { Number of characters in the same position is equal to the possible word

(if outOfPlace characters is equal to 0) then where all characters are different than the possible word }

}

LastWord(After the first two are solved)

{

List possibilities = All Words filtered by the number of offPosition characters in the second word(In code see: helperWords)

Make a guess

possibilities = possibilities where(for the all guesses ) {

Number of characters in the same position is equal to possible word

Sum of in and out of position characters == possible word ( for all guesses )

Length is equal of greater than (Sum of in and out of position characters) length of possible word

(if outOfPlace characters is equal to 0) then where all characters are different than the possible word

}

}

Code

Note for this to work you need to include the ppcg_mastermind_dict.txt and ppcg_mastermind_passes.txt in the running directory(or in the VS in the same directory and set "Copy to Output Directory" to true). I really apologize for the quality of code there's still allot of work to be done on this, it should work though.

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

namespace MastermindHorseBatteryStaple
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> results = new List<int>();
            var Start = DateTime.UtcNow;
            foreach (var element in File.ReadAllLines(Directory.GetCurrentDirectory() + "\\ppcg_mastermind_passes.txt").ToArray())
            {
                var pas1 = new PassPhrase(element);
                var pasSolve = new PassPhraseCracker();
                var answer = pasSolve.Solve(pas1);
                Console.WriteLine("Answer(C): " + answer);
                Console.WriteLine("Answer(R): " + pas1.currentPassword);
                Console.WriteLine("Equal: " + answer.Equals(pas1.currentPassword));
                Console.WriteLine("Total Cost: " + pas1.count);
                Console.WriteLine();
                results.Add(pas1.count);
            }
            Console.WriteLine("Final Run Time(Seconds): " + (DateTime.UtcNow - Start).TotalSeconds);
            Console.WriteLine("Final Total Cost: " + results.Average());
            Console.WriteLine("Min: " + results.Min());
            Console.WriteLine("Max: " + results.Max());
            Console.ReadLine(); 
        }
    }

class PassPhrase
    {
        public List<string> Words { get; set; }
        public int count = 0;         
        public string currentPassword { get; set; }

        /// <summary>
        /// Declare if you want the class to generate a random password
        /// </summary>
        public PassPhrase()
        {            
            Words = File.ReadAllLines(Directory.GetCurrentDirectory() + "\\ppcg_mastermind_dict.txt").ToList();
            Random random = new Random();
            currentPassword = Words[random.Next(Words.Count())] + " " + Words[random.Next(Words.Count())] + " " + Words[random.Next(Words.Count())];
        }
        /// <summary>
        /// Use if you want to supply a password
        /// </summary>
        /// <param name="Password">The password to be guessed agianst</param>
        public PassPhrase(string Password)
        {
            Words = File.ReadAllLines(Directory.GetCurrentDirectory() + "\\ppcg_mastermind_dict.txt").ToList();
            currentPassword = Password;
        }

        public int[] Guess(String guess)
        {
            count++;
            return Test(guess, currentPassword);
        }
        /// <summary>
        /// This method compares two string and return -1 if equal, 
        /// otherwise it returns the number of character with the same index matching, 
        /// and number of characters matching but in the wrong position
        /// </summary>
        /// <param name="value1">First value to compare</param>
        /// <param name="value2">Second value to compare</param>
        /// <returns>Returns {-1, -1} if equal, 
        /// Two ints the first(0) being the number of chars matching but not in the right postion
        /// The second(1) being the number of chars that match and are in the right position
        /// </returns>
        public int[] Test(String value1, String value2)
        {
            if (String.Equals(value1, value2)) return new int[] { -1, -1 };

            var results = new int[2];
            results[0] = TestNumberOfOutOfPositionCharacters(value1, value2);
            results[1] = TestNumberOfInPositionCharacters(value1, value2);

            return results;
        }
        public int TestNumberOfInPositionCharacters(String value1, String value2)
        {
            var result = 0;
            var value1Collection = value1.ToCharArray();
            var value2Collection = value2.ToCharArray();

            for (int i = 0; i < value1Collection.Count(); i++)
            {
                if (value2Collection.Count() - 1 < i) continue;
                if (value2Collection[i] == value1Collection[i]) result++;
            }
            return result;
        }
        public int TestNumberOfOutOfPositionCharacters(String value1, String value2)
        {
            return CommonCharacters(value1, value2) - TestNumberOfInPositionCharacters(value1, value2);                   
        }

        private int CommonCharacters(string s1, string s2)
        {
            bool[] matchedFlag = new bool[s2.Length];

            for (int i1 = 0; i1 < s1.Length; i1++)
            {
                for (int i2 = 0; i2 < s2.Length; i2++)
                {
                    if (!matchedFlag[i2] && s1.ToCharArray()[i1] == s2.ToCharArray()[i2])
                    {
                        matchedFlag[i2] = true;
                        break;
                    }
                }
            }

            return matchedFlag.Count(u => u);
        }
        private string GetRandomPassword()
        {
            Random rand = new Random();
            return Words[rand.Next(Words.Count())] + " " + Words[rand.Next(Words.Count())] + " " + Words[rand.Next(Words.Count())];
        }        
    }

class PassPhraseCracker
    {
        public class LengthAttempt
        {
            public int Length { get; set; }
            public int Result { get; set; }
        }
        public class WordInformation
        {
            public string Word { get; set; }
            public int[] Result { get; set; }
        }

        public string Solve(PassPhrase pas)
        {
            //The helperWords is used in the final word to lower the number of starting possibilites 
            var helperWords = new List<WordInformation>();
            var first = GetNextWord(pas, "", ref helperWords);

            //TODO: I'm ignoring the helperWords from the first word, 
            //I should do some comparisions with the results of the seconds, this may make finding the last word slightly faster 
            helperWords = new List<WordInformation>();
            var second = GetNextWord(pas, first + " ", ref helperWords);

            //The final Word can be found much faster as we can say that letters in the wrong position are in this word
            var third = GetLastWord(pas, first + " " + second + " ", helperWords);

            return first + " " + second + " " + third;
        }

        private string GetNextWord(PassPhrase pas, string final, ref List<WordInformation> HelperWords)
        {
            var result = new int[] { 0, 0 };
            var currentGuess = final;
            Random random = new Random();
            var triedValues = new List<WordInformation>();

            //The most efficient way to find length of the word that I could come up with
            var triedLengths = new List<LengthAttempt>();
            var lengthAttempts = new List<LengthAttempt>();
            var lengthOptions = pas.Words.AsParallel().GroupBy(a => a.ToCharArray().Count()).OrderByDescending(a => a.Count()).ToArray();
            var length = 0;
            while (length == 0)
            {
                //Find most frequency number of character word between already guessed ones
                var options = lengthOptions.AsParallel().Where(a =>
                    (!lengthAttempts.Any(b => b.Result == 1) || a.Key < lengthAttempts.Where(b => b.Result == 1).Select(b => b.Length).Min()) &&
                    (!lengthAttempts.Any(b => b.Result == 0) || a.Key > lengthAttempts.Where(b => b.Result == 0).Select(b => b.Length).Max()));

                //Rare condition that occurs when the number of characters is equal to 20 and the counter
                //Guesses 18 and 20
                if (!options.Any())
                {
                    length = lengthAttempts.Where(a => a.Result == 1).OrderBy(a => a.Length).First().Length;
                    break;
                }

                var tryValue = options.First();

                //Guess with the current length, plus one space
                //TODO: I can append characters to this and make it a more efficient use of the Guess function, 
                //this would speed up the calculation of the final Word somewhat
                //but this really highlights the failing of this design as characters in the wrong positions can't be deterministically used until the final word
                result = pas.Guess(currentGuess + new String(' ', tryValue.Key) + " ");

                //This part looks at all the attempts and tries to determine the length of the word
                lengthAttempts.Add(new LengthAttempt { Length = tryValue.Key, Result = result[1] - final.Length });

                //For words with length 1
                if (lengthAttempts.Any(a => a.Length == 1 && a.Result == 1))
                    length = 1;

                //For words with the max length 
                if (lengthAttempts.Any(a => a.Length == lengthOptions.Select(b => b.Key).Max() && a.Result == 1))
                    length = lengthAttempts.Single(a => a.Length == lengthOptions.Select(b => b.Key).Max() && a.Result == 1).Length;

                else if (lengthAttempts
                    .Any(a =>
                        a.Result == 1 &&
                        lengthAttempts.Any(b => b.Length == a.Length - 1) &&
                        lengthAttempts.Single(b => b.Length == a.Length - 1).Result == 0))
                    length = lengthAttempts
                        .Single(a =>
                            a.Result == 1 &&
                            lengthAttempts.Any(b => b.Length == a.Length - 1) &&
                            lengthAttempts.Single(b => b.Length == a.Length - 1).Result == 0).Length;
            }

            //Filter by length
            var currentOptions = pas.Words.Where(a => a.Length == length).ToArray();

            //Now try a word, if not found then filter based on all words tried            
            while (result[1] != final.Length + length + 1)
            {
                //Get farthest value, or middle randomly
                //TODO: I've struggled with this allot, and tried many way to some up with the best value to try
                //This is the best I have for now, but there may be a better way of doing it
                var options = currentOptions.AsParallel().OrderByDescending(a => ComputeLevenshteinDistance(a, triedValues.Count() == 0 ? currentOptions[0] : triedValues.Last().Word)).ToList();
                if (random.Next(2) == 1)
                    currentGuess = options.First();
                else
                    currentGuess = options.Skip((int)Math.Round((double)(options.Count() / 2))).First();

                //try it
                result = pas.Guess(final + currentGuess + " ");

                //add it to attempts
                triedValues.Add(new WordInformation { Result = result, Word = currentGuess });

                //filter any future options to things with the same length and equal or more letters in the same position and equal or less letters in the wrong position
                currentOptions = currentOptions.Except(triedValues.Select(a => a.Word)).AsParallel()
                    .Where(a => triedValues.All(b => pas.TestNumberOfInPositionCharacters(a, b.Word) == b.Result[1] - 1 - final.Length))
                    //Special Zero Case
                    .Where(a => triedValues
                    .Where(b => b.Result[1] - 1 - final.Length == 0)
                    .All(b => pas.TestNumberOfInPositionCharacters(a, b.Word) == 0))
                    .ToArray();
            }

            //Add attempts to helper list
            HelperWords = HelperWords.Concat(triedValues.Where(a => a.Result[0] - pas.TestNumberOfOutOfPositionCharacters(a.Word, currentGuess) > 0)
                .Select(a => new WordInformation { Word = a.Word, Result = new int[] { a.Result[0] - pas.TestNumberOfOutOfPositionCharacters(a.Word, currentGuess), a.Result[1] } }).ToList()).ToList();
            return currentGuess;
        }

        private string GetLastWord(PassPhrase pas, string final, List<WordInformation> HelperWords)
        {
            Random rand = new Random();
            var triedList = new List<WordInformation>();
            var result = new int[] { 0, 0 };

            //This uses the helperList from the previous word to attempt help filter the initial possiblities of the last word before preforming the first check
            var currentOptions = pas.Words.AsParallel().Where(a => HelperWords
                .All(b => pas.TestNumberOfOutOfPositionCharacters(a, b.Word) + pas.TestNumberOfInPositionCharacters(a, b.Word) >= b.Result[0])).ToArray();
            var current = final;
            while (result[0] != -1)
            {
                //Here we know the final word but their is no reason to submit it to the guesser(that would cost one more), just return it
                if (currentOptions.Count() == 1)
                {
                    //ADD GUESS HERE(if required)
                    //pas.Guess(final + current);
                    return currentOptions[0];
                }

                //Get farthest value, or middle randomly
                var options = currentOptions.AsParallel()
                    .OrderByDescending(a => ComputeLevenshteinDistance(a, triedList.Count() == 0 ? currentOptions[0] : triedList.Last().Word)).ToList();

                //Get the next value to try
                if (rand.Next(2) == 1)
                    current = options.First();
                else
                    current = options.Skip((int)Math.Round((double)(options.Count() / 2))).First();

                //try it
                result = pas.Guess(final + current);

                //If its the right word return it
                if (result[0] == -1)                     
                    return current;

                //add it to attempts
                triedList.Add(new WordInformation { Result = result, Word = current });

                //filter any future options to things with the same length and equal or more letters in the same position and equal or less letters in the wrong position
                currentOptions = currentOptions.Except(triedList.Select(a => a.Word)).AsParallel()
                    .Where(a => triedList
                        .All(b => pas.TestNumberOfInPositionCharacters(a, b.Word) == b.Result[1] - final.Length &&
                            pas.TestNumberOfInPositionCharacters(a, b.Word) + pas.TestNumberOfOutOfPositionCharacters(a, b.Word) == b.Result[0] + b.Result[1] - final.Length &&
                            a.Length >= pas.TestNumberOfInPositionCharacters(a, b.Word) + pas.TestNumberOfOutOfPositionCharacters(a, b.Word) - final.Length))
                    //Special zero match condition
                    .Where(a => triedList
                    .Where(b => b.Result[1] - final.Length == 0)
                    .All(b => pas.TestNumberOfInPositionCharacters(a, b.Word) == 0)).ToArray();
            }

            return current;
        }

        /// <summary>
        /// http://www.dotnetperls.com/levenshtein
        /// Returns the number of character edits (removals, inserts, replacements) that must occur to get from string A to string B.
        /// </summary>
        /// <param name="s">First string to compare</param>
        /// <param name="t">Second string to compare</param>
        /// <returns>Number of edits needed to turn one string into another</returns>
        private static int ComputeLevenshteinDistance(string s, string t)
        {
            int n = s.Length;
            int m = t.Length;
            int[,] d = new int[n + 1, m + 1];

            // Step 1
            if (n == 0)
            {
                return m;
            }

            if (m == 0)
            {
                return n;
            }

            // Step 2
            for (int i = 0; i <= n; d[i, 0] = i++)
            {
            }

            for (int j = 0; j <= m; d[0, j] = j++)
            {
            }

            // Step 3
            for (int i = 1; i <= n; i++)
            {
                //Step 4
                for (int j = 1; j <= m; j++)
                {
                    // Step 5
                    int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                    // Step 6
                    d[i, j] = Math.Min(
                        Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                        d[i - 1, j - 1] + cost);
                }
            }
            // Step 7
            return d[n, m];
        }
    }
}

Answer 14

Python - min: 87, max: 108, total: 96063, time: 4s

This is my second post. This method use less time but score worse. And it can be run using either:

• CPython 2
• CPython 3
• Pypy 2 (fastest)
• Pypy 3

Steps:

• Find the first 2 spaces using guesses like . ...., .. ..., ...
• Count character freqencies for each word in the password.
• Guess for each valid combinations after filtering by word length and character freqency.

It cost about 90 guesses for each password.

from __future__ import print_function
import sys
import itertools
from collections import defaultdict


def run_checker(answer, guesser):
    guess_count = 0
    guesser = guesser()
    guess = next(guesser)
    while True:
        char_count = len(set(guess) & set(answer))
        pos_count = sum(x == y for x, y in zip(answer, guess))
        guess_count += 1
        if answer == guess:
            break
        guess = guesser.send((char_count, pos_count))
    try:
        guesser.send((-1, -1))
    except StopIteration:
        pass
    return guess_count


# Preprocessing
words = list(map(str.rstrip, open('dict.txt')))

M = 26
ord_a = ord('a')

def get_fingerprint(word):
    counts = [0] * M
    for i in map(ord, word):
        counts[i - ord_a] += 1
    return tuple(counts)

P = defaultdict(list)
for word in words:
    P[get_fingerprint(word)].append(word)

# End of preprocessing


def guesser2():
    max_word_len = max(map(len, words))
    max_len = max_word_len * 3 + 2
    spaces = []
    for i in range(1, max_len - 1):
        guess = '.' * i + ' '
        char_count, pos_count = yield guess
        if pos_count > 0:
            spaces.append(i)
            if len(spaces) == 2:
                break

    word_lens = [spaces[0], spaces[1] - spaces[0] - 1, max_word_len]
    C = []
    for i in range(3):
        char_counts = [0] * M
        for j in range(M):
            guess = chr(ord_a + j) * (i + sum(word_lens[:i + 1]))
            _, char_counts[j] = yield guess
        C.append(char_counts)
    for i in (2, 1):
        for j in range(M):
            C[i][j] -= C[i - 1][j]

    candidates = []
    for i in range(3):
        candidates.append(P[tuple(C[i])])
    for i in range(2):
        candidates[i] = [w for w in candidates[i] if word_lens[i] == len(w)]

    try_count = 0
    for result in itertools.product(*candidates):
        guess = ' '.join(result)
        char_count, pos_count = yield guess
        try_count += 1
        if char_count == -1:
            break


def test(test_file, guesser):
    scores = []
    for i, answer in enumerate(map(str.rstrip, open(test_file))):
        print('\r{}'.format(i), end='', file=sys.stderr)
        scores.append(run_checker(answer, guesser))
    print(scores)
    print('sum:{} max:{} min:{}'.format(sum(scores), max(scores), min(scores)))


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

Answer 15

Perl (still running ... as of now min/avg/max of 8/9,2/11, estimate it at 1500300hours total runtime)

Update: Changed the initial guesses to speed it up somewhat. Fixed a bug.

Its probably not gonna finish before this contest does, but I might aswell post it. It does not determine individual word lengths, so it has to check the entire dictionary, which ... takes some time.

With the first two guesses it determines the total length, the count of 'e', and how many different characters there are.

Then it tries all combinations that suffice those statistics as well as all previous guesses.

This recent (and last) version has added mp and currently runs on a 24 core system.

use strict;
use POSIX ":sys_wait_h";

$| = 1;

my( $buckets );

open my $dict, "<", "dict.txt";
while( <$dict> )
{
  chomp;
  push( @{$buckets->{length($_)}}, [ split // ] );
};
close $dict;


open my $pass, "<", "pass.txt";

my( @pids );
my( $ind ) = 0;

for( my $i = 0; $i < 1000; $i++ )
{
  my $phrase = <$pass>; chomp( $phrase );

  my( $pid ) = fork();

  if( $pid != 0 )
  {
    $pids[$ind] = $pid;
    print join( "; ", @pids ), "\n";

    for( my $j = 0; $j < 18; ++$j, $j %= 18 )
    {
      waitpid( $pids[$j], WNOHANG ) and $ind=$j,last;
      sleep( 1 );
    };
  }
  else
  {
    my( $r ) = &guessPassPhrase( $phrase, $buckets );

    open my $out, ">>", "result.txt";
    print $out "'$phrase' => $r\n";
    close $out;
    exit;
  };
};

close $pass;


sub guessPassPhrase
{
  our( $pp, $buckets ) = @_;
  our( @log ) = undef;
  our( @ppa ) = split //, $pp;
  our( $trys ) = 0;
  our( $invers ) = 1;
  our( $best ) = 0;

  print "Next   : ", $pp, "\n";

  my( @pw1 ) = map { @{$buckets->{$_}} } ( sort { $b <=> $a } keys( %$buckets ));
  my( @pw2, $llt1 );
  my( @pw3, $llt2 );

  my( $t ) = [ (" ")x9,("-")x58,("a".."z") x 64 ];
  my( $y, $c ) = &oracleMeThis( $t );
  my( $l ) = $y + $c;
  push( @log, [ [(" ")x9], 2-$c, $c ] );

  $t = [("a".."z")];
  my( $y, $c ) = &oracleMeThis( $t );
  push( @log, [ $t, $y, $c ] );
  if( $best < ($y + $c) ) { $best = ($y + $c); };
  print "Guessed ($pp:$trys/$best/$l):", @$t, "=> $y/$c             \n";

  $t = [("e")x4];
  my( $y, $c ) = &oracleMeThis( $t );
  push( @log, [ $t, $y, $c ] );
  if( $best < ($y + $c) ) { $best = ($y + $c); };
  print "Guessed ($pp:$trys/$best/$l):", @$t, "=> $y/$c             \n";

  $t = [("i")x6];
  my( $y, $c ) = &oracleMeThis( $t );
  push( @log, [ $t, $y, $c ] );
  if( $best < ($y + $c) ) { $best = ($y + $c); };
  print "Guessed ($pp:$trys/$best/$l):", @$t, "=> $y/$c             \n";

  LOOP1: for my $w1 ( @pw1 )
  {
    my( $t ) = [ @$w1, " " ];

    print "Pondering: ", @$t, "($trys;$best/$l;",$::e1,",",$::e2,")   \r";

    &EliminatePartial( $t ) && ++$::e1 && next;

    if( $llt1 != @$t )
    {
      @pw2 = map { $_ < $l - @$t ? @{$buckets->{$_}} : () } ( sort { $b <=> $a } keys( %$buckets ));
      $llt1 = @$t;
    };

    $llt2 = 0;

    LOOP2: for my $w2 ( @pw2 )
    {
      my( $t ) = [ @$w1, " ", @$w2, " " ];

#      print "Pondering: ", @$t, "(",$::e1,",",$::e2,")                             \r";

      &EliminatePartial( $t ) && ++$::e2 && next;

      if( $llt2 != @$t )
      {
        @pw3 = map { $_ == $l - @$t ? @{$buckets->{$_}} : () } ( sort { $b <=> $a } keys( %$buckets ));
        $llt2 = @$t;
      };

      LOOP3: for my $w3 ( @pw3 )
      {
        my( $t ) = [ @$w1, " ", @$w2, " ", @$w3 ];

        &EliminatePartial( $t ) && next LOOP3;

        my( $y, $c ) = &oracleMeThis( $t );
        push( @log, [ $t, $y, $c ] );
        if( $best < ($y + $c) ) { $best = ($y + $c); };
        print "Guessed ($pp:$trys/$best/$l):", @$t, "=> $y/$c             \n";

        if( $c == $l ) { return( $trys ); };

        if( $c == 0 ) { @pw2 = (); next LOOP1; };
        if( $c == 1 ) { @pw3 = (); next LOOP2; };
        if( $c < @$w1 ) { next LOOP1; };
        if( $c < @$w1 + @$w2 ) { next LOOP2; };

      };
    };
  };

  die( "Failed To Guess" );

  sub EliminatePartial
  {
    my( $guessn ) = @_;

    for my $log ( @log )
    {
      next if !$log;
      my( $guesso, $yo, $co ) = @$log;
      my( $guessos ) = join( "", @$guesso );

      my( $cn ) = scalar( map { $$guesso[$_] eq $$guessn[$_] ? ( 1 ) : () } ( 0 .. ( @$guesso < @$guessn ? @$guesso : @$guessn ) - 1 ));
      my( $yn ) = scalar( map { $guessos =~ s/$_// ? ( 1 ) : () } ( @$guessn )) - $cn;

      return( 1 ) if( $cn > $co || $yn > $yo );
      return( 1 ) if(( $yo - $yn ) + ( $co - $cn ) > $l - @$guessn );
      return( 1 ) if( @$guesso <= @$guessn && $co != $cn );
    };

    return( 0 );
  };

  sub oracleMeThis
  {
    my( $guessn ) = @_;

    $trys++;

    my( $pph ) = $pp;

    my( $cn ) = scalar( map { $ppa[$_] eq $$guessn[$_] ? ( 1 ) : () } ( 0 .. @$guessn - 1 ));
    my( $yn ) = scalar( map { $pph =~ s/$_// ? ( 1 ) : () } ( @$guessn )) - $cn;

    return( $yn, $cn );
  };
};

Answer 16

Java 10.026 (in 2.5 hours)

Here is my optimised code, now multi-threaded to improve speed:

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;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class MastermindV4MT {

    /*
     * Total guesses: 10026
     * Took: 8461801 ms
     */

    // 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 MastermindV4MT().run();
    }

    int done = 0;
    int totalGuesses = 0;

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

        ExecutorService executor = Executors.newFixedThreadPool(8);

        for(String phrase:passPhrases) {
            executor.execute(new Runnable() {
                public void run() {
                    int guesses = solve(wordMap, phrase);
                    totalGuesses+=guesses;
                    done++;
                    System.out.println("At "+done+" of "+passPhrases.size()+" just added "+guesses+" predicted score: "+((1.0*totalGuesses)/done)*passPhrases.size());
                };
            });
        }
        executor.shutdown();
        try {
            executor.awaitTermination(Long.MAX_VALUE, TimeUnit.HOURS);
        } catch (InterruptedException e) {
        }
        System.out.println("Total guesses: " + totalGuesses);
        System.out.println("Took: " + (System.currentTimeMillis() - beforeTime) + " ms");
    }

    int[] guess(char[] in, char[] pw, char[] pwsorted) {
        int chars = 0, positions = 0;

        char[] inc = Arrays.copyOf(in, in.length);

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

        Arrays.sort(inc);
        int i1 = 0;
        int i2 = 0;
        while(i1 < pwsorted.length && i2 < inc.length) {
            if(inc[i2]==pwsorted[i1]) {
                i1++;
                i2++;
                chars++;
            } else if(inc[i2]<pwsorted[i1]) {
                i2++;
            } else {
                i1++;
            }
        }

        chars -= positions;
        return new int[] { chars, positions };
    }

    private int solve(Map<Integer, List<char[]>> wordMap, String password) {

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

        char[] pw = password.toCharArray();
        char[] pwsorted = password.toCharArray();
        Arrays.sort(pwsorted);

        int[] initialResult = guess(Facts.INITIAL_GUESS.toCharArray(), pw, pwsorted);
        int guesses = 1;

        // 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]) / 2) + 1;
        guesses += findSpaces(center, facts, pw, pwsorted);

        // We know the first word length, the second might have some bounds, but
        // is unknown:
        // We can calculate the lengths:
        int minLength1 = facts.spaceBounds[0] - 1;
        int maxLength1 = facts.spaceBounds[1] - 1;

        char[] phraseBuilder = new char[facts.totalLength+2];

        for (int length1 = minLength1; length1 <= maxLength1;length1++) {

            if (wordMap.get(length1) == null) {
                continue;
            }

            for (char[] w1 : wordMap.get(length1)) {
                for(int i = 0; i<w1.length;i++) {
                    phraseBuilder[i] = w1[i];
                }
                phraseBuilder[w1.length] = ' ';

                if (facts.partialMatches(phraseBuilder, facts.totalLength+1-w1.length)) {

                    int minLength2 = (facts.spaceBounds[2] - length1 - 2);
                    int maxLength2 = (facts.spaceBounds[3] - length1 - 2);

                    for (int length2 = minLength2; length2 <= maxLength2;length2++) {

                        if (wordMap.get(length2) == null) {
                            continue;
                        }

                        for (char[] w2 : wordMap.get(length2)) {

                            // Continue if (according to our facts) this word is a
                            // partial match:
                            for(int i = 0; i<length2;i++) {
                                phraseBuilder[w1.length+1+i] = w2[i];
                            }
                            phraseBuilder[w1.length+w2.length+1] = ' ';

                            if (facts.partialMatches(phraseBuilder, facts.totalLength-(w1.length+w2.length))) {

                                if (wordMap.get(facts.totalLength - length2 - length1) == null) {
                                    continue;
                                }

                                int length3 = facts.totalLength - length2 - length1;
                                for (char[] w3 : wordMap.get(length3)) {

                                    for(int i = 0; i<length3;i++) {
                                        phraseBuilder[w1.length+w2.length+2+i] = w3[i];
                                    }

                                    if (facts.matches(phraseBuilder)) {
                                        int[] result = guess(phraseBuilder, pw, pwsorted);
                                        guesses++;

                                        //String possiblePhrase = new String(phraseBuilder);
                                        //System.out.println(possiblePhrase + " " + Arrays.toString(result));
                                        if (result[0] == -1) {
                                            return guesses;
                                        }
                                        // No match, update facts:
                                        facts.storeInvalid(phraseBuilder.clone(), result);
                                    }
                                }
                                for(int i = 0; i<phraseBuilder.length-(w1.length+2+w2.length);i++) {
                                    phraseBuilder[w1.length+w2.length+2+i] = '-';
                                }
                            }
                        }
                        for(int i = 0; i<phraseBuilder.length-(w1.length+1);i++) {
                            phraseBuilder[w1.length+1+i] = '-';
                        }

                    }
                }
            }
        }
        throw new IllegalArgumentException("Unable to solve!?");
    }

    private int findSpaces(int center, Facts facts, char[] pw, char[] pwsorted) {
        char[] testPhrase = new char[facts.totalLength + 2+facts.charBounds[lookup[facts.charPtr]]];
        // Place spaces for analysis:
        int ptr = 0;
        for (int i = 0; i < center; i++) {
            testPhrase[ptr++] = ' ';
        }
        while (ptr < (facts.totalLength + 2)) {
            testPhrase[ptr++] = '-';
        }

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

        // Update space lower and upper bounds:
        int[] answer = guess(testPhrase, pw, pwsorted);
        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[1]-facts.spaceBounds[0]<5) {
            // Only find the first space
            return 1;
            //if(facts.spaceBounds[3]-facts.spaceBounds[2]<4) return;
            //findSpaces(facts.spaceBounds[2] + ((facts.spaceBounds[3]-facts.spaceBounds[2])/3), facts, pw, pwsorted);
        } else {
            return 1+findSpaces((facts.spaceBounds[0] + facts.spaceBounds[1]) / 2, facts, pw, pwsorted);
        }
    }

    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 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<char[]> previousGuesses = new ArrayList<char[]>();
        private List<int[]> previousResults = new ArrayList<int[]>();

        public void storeInvalid(char[] phrase, int[] result) {
            previousGuesses.add(phrase);
            previousResults.add(result);
        }

        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(char[] phrase, int amountUnknown) {

            //Try to match a partial phrase, we can't be too picky because we don't know what else is next
            Arrays.fill(cUsed, 0);
            for(int i = 0; i<phrase.length; i++) {
                if(phrase[i]!=' ' && phrase[i]!='-'&&phrase[i]!=0) {
                    cUsed[phrase[i]-97]++;
                }
            }
            for(int i = 0; i<cUsed.length; i++) {
                //Only eliminate the phrases that definitely have wrong characters:
                if(cUsed[i] > charBounds[i]) {
                    return false;
                }
            }
            //Check again previous guesses:
            int cnt = 0;
            char[] phraseSorted = phrase.clone();
            Arrays.sort(phraseSorted);
            for(char[] previousGuess:previousGuesses) {
                // If the input phrase is the correct phrase it should score the same against previous tries:
                int[] result = guess(previousGuess, phrase, phraseSorted);
                int[] expectedResult = previousResults.get(cnt);

                //Some cases we can stop early:
                if(result[0]+result[1] > expectedResult[0]+expectedResult[1]) {
                    return false;
                }
                if(result[1]>expectedResult[1]) {
                    return false;
                }
                if(result[0]+amountUnknown<expectedResult[0]) {
                    return false;
                }
                if(result[1]+amountUnknown<expectedResult[1]) {
                    return false;
                }
                if(result[0]+result[1]+amountUnknown < expectedResult[1]+expectedResult[0]) {
                    return false;
                }
                cnt++;
            }
            return true;
        }

        int[] cUsed = new int[26];
        public boolean matches(char[] phrase) {

            // Try to match a complete phrase, we can now use all information:
            Arrays.fill(cUsed, 0);
            for (int i = 0; i < phrase.length; i++) {
                if(phrase[i]!=' ' && phrase[i]!='-'&&phrase[i]!=0) {
                    cUsed[phrase[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 again previous guesses:
            char[] phraseSorted = phrase.clone();
            Arrays.sort(phraseSorted);
            int cnt = 0;
            for(char[] previousGuess:previousGuesses) {
                // If the input phrase is the correct phrase it should score the
                // same against previous tries:
                int[] result = guess(previousGuess, phrase, phraseSorted);
                int[] expectedResult = previousResults.get(cnt);
                if (!Arrays.equals(expectedResult, result)) {
                    return false;
                }
                cnt++;
            }
            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<char[]>> createDictionary() throws Exception {
        BufferedReader reader = new BufferedReader(new FileReader(new File("words.txt")));
        Map<Integer, List<char[]>> wordMap = new HashMap<Integer, List<char[]>>();
        String input;
        while ((input = reader.readLine()) != null) {
            List<char[]> words = wordMap.get(input.length());
            if (words == null) {
                words = new ArrayList<char[]>();
            }
            words.add(input.toCharArray());
            wordMap.put(input.length(), words);
        }
        return wordMap;
    }

}