# 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<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 from xkcd.com/936 Aug 27, 2014 at 16:28
• Can I put characters other than a..z and space in the string to submit?
– Ray
Aug 27, 2014 at 17:13
• @Ray I can't think of a reason why not at the moment, but I'm not sure what it gains you. Go for it, I'm curious. Aug 27, 2014 at 17:19
• Can humans submit themselves? I'll start: "worth a shot' Aug 27, 2014 at 17:29
• @AndoDaan For the first phrase? 9 0. This might take a while :P Aug 27, 2014 at 17:33

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

*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++) {
#ifdef DEBUG
#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.

• I like this one, an intuitive next step could be to make sure the wordlist that you use for guessing is ordered in a powerfull way. At least make sure you have a good starting word for each amount of letters. Aug 28, 2014 at 9:22
• That's a good idea. Thanks for the feedback.
– Orby
Aug 29, 2014 at 0:26

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

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

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

@functools.wraps(guesser)

guess_count = 0
guesser = guesser()
guess = next(guesser)
while True:
guess_count += 1
break
try:
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
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)

cases = list(enumerate(map(str.rstrip, open(test_file))))
scores = [None] * len(cases)
with ProcessPoolExecutor() as executor:
print('-' * 80)
print('case', i)
scores[i] = 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)

• I'm having a really hard time getting bellow this. Nice job.
– Orby
Aug 29, 2014 at 0:24
• How did you generate the graph? Aug 29, 2014 at 9:52
• @BetaDecay A script using matplotlib.
– Ray
Aug 29, 2014 at 10:51
• @DennisJaheruddin Yes, it's very ugly. Fixed now.
– Ray
Aug 29, 2014 at 15:48
• I feel that you should use matplotlibs xkcdify for the graph matplotlib.org/xkcd/examples/showcase/xkcd.html Sep 3, 2014 at 13:04

# 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)" } }  • Welcome to the site, and congratulations! You didn't make the bounty cutoff by much, but you made it. Have some imaginary internet points! Sep 5, 2014 at 20:01 • Simply brillant. – user16991 Sep 5, 2014 at 22:50 • Awesome solution! It is the only one below the 10,000 mark! Sep 6, 2014 at 9:02 # 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; } }  • You guys are so smart. – Ray Sep 1, 2014 at 19:21 • It's a brilliant idea to count character freqs in parallel with finding spaces. – Ray Sep 1, 2014 at 19:25 • I must say I can't even begin to wrap my head around your even/odd technique, neither by abstract thinking or reverse engineering. I also don't understand the way you call the password matching function without counting an extra guess. A bit of explanation would be welcome. – user16991 Sep 5, 2014 at 6:19 # 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. ;) • ZPCs are fine, other entries are using them as well. I think the most common is .. Aug 30, 2014 at 3:33 • The current code doesn't include a "validating" query. I'll add one now. – COTO Aug 30, 2014 at 4:03 • I've updated to rev. 1, which includes the validating query. Not surprisingly, the number of queries is exactly 1,000 greater than the previous version. – COTO Aug 30, 2014 at 4:11 • This is very nice. Your Java is so Java-y it hurts. I'm not used to seeing code like that on this site :D Aug 30, 2014 at 5:03 • +1 for both being epic and "perpetually exhausting pool" Aug 31, 2014 at 18:30 ## 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; } }  ## 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 • While very fast, this definitely uses a bunch of guesses. You may be able to improve a bit by using the letter frequency of the dict file rather than common English. Aug 27, 2014 at 19:57 • @Geobits Fixed the bugs, I had a -1 in the if statement in nextPass() and a +1 in the while loop in main(), both from earlier testing iterations. Now prints out each password once if you keep line 65 in. Aug 27, 2014 at 20:13 # 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  • Actually you can know the total length with a single query. – Ray Sep 3, 2014 at 6:22 • Thanks @Ray. I did do that eventually, but not on my first pass through the problem. I just did not edit my original post. Sep 4, 2014 at 20:12 # 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 }  • I can not compile this code. The compiler said that passphases and allWords are undefined. – Ray Aug 28, 2014 at 7:38 • you will need these two files: gist.github.com/captncraig/a136d0b9819d0ea948e6 Aug 28, 2014 at 14:50 # 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(n3) 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; } }  • Posted: yesterday. Title includes (still running). Made me laugh, +1 Aug 28, 2014 at 19:50 • @insta It really is. I think about 6-7 more hours should do it. Estimating ~58k guesses. Aug 28, 2014 at 19:51 • I wouldn't be patient enough to let this run on for so long Aug 29, 2014 at 10:29 # 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(); } }  # 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. • I can't find the Main function in your code. Does it have one ? – Ray Sep 3, 2014 at 6:35 • The unit test SolverFixture.SolveSerialAll is what I used to get the test results posted above and Solver.Solve is the core of the program. It's a unit test project with no single official entry point, so no main function. Sep 3, 2014 at 6:42 # 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]; } } }  # 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)  # 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 );
};
};


# 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.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();

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

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);
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);
}
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];
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) {
}

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
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 {
List<String> phrases = new ArrayList<String>();
String input;
}
return phrases;
}

private Map<Integer, List<char[]>> createDictionary() throws Exception {
Map<Integer, List<char[]>> wordMap = new HashMap<Integer, List<char[]>>();
String input;