f4hackingsolver.py

#!/usr/bin/env python3.5
"""
    f4hackingsolver
    ~~~~~~~~~~~~~~~

    Solver for the Fallout 4 Hacking Mini Game.

    Within Fallout 4 you sometimes encounter terminals that need to be hacked.
    When hacking a terminal you are presented with a screen that contains a
    list of potential passwords all with the same length.

    You find the password by selecting a word from the list. If the word is the
    password you win, if it isn't you get a likeness score which is the number
    of characters in your selected word that match the password.

    This script assists you while playing this mini game. Simply enter the
    words you can choose from. The script will suggest a word to select, will
    ask you for the result and tell you which of the words remain potential
    candidates for the password.

    :copyright: 2015 Daniel Neuhäuser
    :license: Unlicense, see http://unlicense.org for more information
"""
from itertools import combinations
from collections import Counter


class Solver:
    """
    Implements the logic for the solver.

    Initialize this class with the list of available `words`. Figure out the
    password by calling :meth:`get_suggested_selection` and :meth:`select` in a
    loop. You can see which words remain after each attempt with the
    :attr:`words` instance attribute.
    """

    def __init__(self, words):
        #: The list of the words which remain candidates for the password.
        self.words = words

    def get_suggested_selection(self):
        """
        Returns a word with many characters matching many other of the
        remaining password candidates.

        If the suggestion doesn't match the password, it will hopefully
        eliminate as many candidates as possible from the pool.
        """
        char_counts = [Counter(column) for column in zip(*self.words)]
        return sorted(
            self.words,
            key=lambda w: sum(char_counts[i][c] for i, c in enumerate(w)),
            reverse=True
        )[0]

    def select(self, selected, likeness):
        """
        Eliminates words from :attr:`words` based on the `selected` word.
        """
        remaining_words = [word for word in self.words if word != selected]
        if likeness == 0:
            # Eliminate all words that have any matching characters.
            self.words = [
                word for word in remaining_words if
                not set(enumerate(word)) & set(enumerate(selected))
            ]
        else:
            # Find all characters in the selected word that could match any
            # other words. Keep all words that contain any of the `likeness`
            # number of combinations of these characters.
            alphabet = [set(column) for column in zip(*words)]
            potential_chars = [
                (i, char) for i, char in enumerate(selected)
                if char in alphabet[i]
            ]
            occurs_in = lambda c, w: all(w[i] == ch for i, ch in c)
            self.words = [
                word for word in remaining_words
                if any(
                    occurs_in(combination, word)
                    for combination in combinations(potential_chars, likeness)
                )
            ]


def prompt(question, allow_empty=False, type=None):
    """
    Prompts the user for input using `question`. Prompting repeatedly until
    an answer is given.

    You can prompt for things other than strings, by providing a function that
    converts the string into something else. That function may raise
    :exc:`ValueError` and the user will be prompted again, if that happens.

    If `allow_empty` is `True`, empty answers are allowed.
    """
    while True:
        raw_answer = input(question)
        if type is None:
            answer = raw_answer
        else:
            try:
                answer = type(raw_answer)
            except ValueError:
                continue
        if raw_answer or allow_empty:
            return answer


def ask_for_words():
    """
    Asks the user for a list of words.
    """
    return list(iter(lambda: prompt('WORD> ', allow_empty=True), ''))


def ask_for_selection():
    """
    Asks the user for a selection and likeness.
    """
    return prompt('SELECTED> '), prompt('LIKENESS> ', type=int)


def main():
    solver = Solver(ask_for_words())
    word_num = len(solver.words)
    while len(solver.words) > 1:
        print('SUGGESTION: {}'.format(solver.get_suggested_selection()))
        solver.select(*ask_for_selection())
        old_word_num = word_num
        word_num = len(solver.words)
        print('REMAINING WORDS (-{}):'.format(old_word_num - word_num))
        print('\n'.join(solver.words))


if __name__ == '__main__':
    main()