Fallout New Vegas Hacking: Optimal guessing strategy

example.txt

monitoring
contending
strategies
lieutenant
scavenging
descendent
delivering
concerning
resounding
casualties
meditation
endorphins
attracting
conspiring
containing
television
contenting
conducting
ceremonial
exchanging

new_vegas_hacking.py

#!/usr/bin/env python2
import sys
from collections import Counter
from pprint import pprint
from copy import deepcopy
import pdb

def main():
    words = read_words()
    matrix = make_matrix(words)
    while matrix:
        pprint_matrix(matrix)
        print "Current hypothesis sizes:"
        for word in matrix:
            print word, ":", hypothesize(matrix, word)
        matrix = matrix_loop(matrix)
    print "You won!"

def matrix_loop(matrix):
    val, good_words = lowest_hypothesis(matrix)
    print "Lowest hypothesis size was", val
    print "Guess one of", ', '.join(good_words)
    guess_word, answer = get_guess_and_answer(good_words)
    maybe_solution = check_if_one_possibility_left(matrix, guess_word, answer)
    if maybe_solution:
        print "The answer is", maybe_solution
    return shrink_matrix(matrix, guess_word, answer)

def pprint_matrix(matrix):
    '''Prints the nice shared-letters matrix'''
    words = sorted(matrix.keys())
    word_len = len(words[0])
    initial_pad = " "*word_len
    for i in xrange(word_len):
        print initial_pad,
        for word in words:
            print ' {}'.format(word[i]),
        print
    print
    reg_matrix = to_regular_matrix(matrix)
    running_certainty = 0
    for i, row in enumerate(reg_matrix):
        certainty = weighted_certainty(matrix[words[i]])
        print words[i], ' '.join("{:#2}".format(x) for x in row), certainty
        running_certainty += certainty

    print 'average certainty:', running_certainty / len(words)

def read_words():
    if len(sys.argv) > 1:
        words = []
        with open(sys.argv[1]) as f:
            for line in f:
                words.append(line.strip())
    else:
        words = get_words()
    return words

def get_words():
    words = []
    winput = raw_input('word> ')
    while winput.strip():
        words.append(winput.strip())
        winput = raw_input('word> ')
    print
    return words

def get_guess_and_answer(good_words):
    errored = True
    while errored:
        try:
            guess_word = raw_input("What word did you guess? ").strip()
            if guess_word not in good_words:
                print 'Grumble... suboptimal guess!'
            phrase = "How many letters did it say {} had in common with the answer? ".format(guess_word)
            answer = int(raw_input(phrase).strip())
            errored = False
        except Exception:
            pass
    print
    return guess_word, answer


def letters_in_common(word_a, word_b):
    return len([1 for a,b in zip(word_a, word_b) if a == b])

def make_matrix(words):
    matrix = {}
    for word_a in words:
        mat = matrix.setdefault(word_a, {})
        for word_b in words:
            mat[word_b] = letters_in_common(word_a, word_b)
    return matrix

def to_regular_matrix(matrix):
    words = sorted(matrix)
    mat = [[0]*len(words) for _ in words]
    for i in xrange(0, len(words)):
        for j in xrange(0, len(words)):
            mat[i][j] = matrix[words[i]][words[j]]
    return mat

def partitions_for_word(word_row):
    c = Counter(word_row.values())
    return c.most_common()

def weighted_certainty(word_row):
    partitions = len(partitions_for_word(word_row))
    row_len = len(word_row)
    return partitions/float(row_len)

def average_partition_size(partitions):
    denom = len(partitions)
    num = sum(count for _,count in partitions)
    return float(num)/denom

def lowest_average_partition_size(matrix):
    "L.A.P.S."
    word_dict = {}
    for word, row in matrix.items():
        partitions = partitions_for_word(row)
        word_dict[word] = average_partition_size(partitions)
    minavg = min(word_dict.values())
    words = [word for word, val in word_dict.items() if val == minavg]
    return minavg, words

def lowest_hypothesis(matrix):
    word_dict = {}
    for word in matrix.keys():
        word_dict[word] = hypothesize(matrix, word)
    minavg = min(word_dict.values())
    words = [word for word, val in word_dict.items() if val == minavg]
    return minavg, words

def shrink_matrix(matrix, guess, answer):
    matrix = deepcopy(matrix)
    guess_row = matrix[guess]
    valid_words = []
    for word, in_common in guess_row.items():
        if in_common == answer:
            valid_words.append(word)
    del matrix[guess]
    for row_word, row in matrix.items():
        if row_word not in valid_words:
            del matrix[row_word]
            continue
        for word in row.keys():
            if word not in valid_words:
                del row[word]
        if not row: # row is now empty
            del matrix[row_word]
    return matrix

def hypothesize(matrix, guess, round=1):
    row = matrix[guess]
    partitions_for_guess = partitions_for_word(row)
    # for each partition, determine the LAPS return the weighted
    # average of the LAPS based on partition size (so larger
    # partitions will have their LAPS weighted more heavily)
    row_len = len(row)
    weighted_hypothesis = 0
    for in_common, part_size in partitions_for_guess:
        chance_of_part_selected = float(part_size) / row_len
        sub_answer = None
        if part_size == 1:
            sub_answer = 1.0
        else:
            shrunken_matrix = shrink_matrix(matrix, guess, in_common)
            sub_answer = sum(hypothesize(shrunken_matrix, w, round+1)
                             for w in shrunken_matrix.keys())
        weighted_hypothesis += chance_of_part_selected * sub_answer
    return weighted_hypothesis


def check_if_one_possibility_left(matrix, guess_word, answer):
    row = matrix[guess_word]
    partitions = dict(partitions_for_word(row))
    if partitions[answer] == 1:
        for word, in_common in row.items():
            if in_common == answer:
                return word
    return None

if __name__ == '__main__':
    main()