mastermind horse battery staple 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&lt;space&gt;ba&lt;space&gt;) 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&lt;in.length()&amp;&amp;i&lt;pw.length();i++){
        if(in.charAt(i)==pw.charAt(i))
            positions++;
    }
    if(positions == pw.length() &amp;&amp; pw.length()==in.length())
        return new int[]{-1,positions};
    for(int i=0;i&lt;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
Python 3.4 - min: 21, max: 29, total: 25146, time: 20min
min: 30, max: 235, total: 41636, time: 4min
Update:

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.
Save wrong guesses along with their result. Compare with them in following guesses. This can save a lot.
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) &gt; 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 &lt; 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 &gt; 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 &gt; 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 &gt;= 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 &gt;= 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)