f4hack.py

#!/usr/bin/env python3
"""

ROBCO Industries (TM) Password Recovery Tool
----
Next-generation hacking assistant for your RobCo Pip-Boy 3000.

"""

from collections import namedtuple
import re


Branch = namedtuple('Branch', ['word', 'constraints', 'subset', 'n_branches',
                               'likenesses'])


def get_branch(words, constraints, word):
    constraints = constraints.copy()
    constraints[word] = 'any'
    subset = {x: sim(word, x) for x in filter_words(words, constraints)}

    return Branch(
        word=word,
        constraints=constraints,
        subset=subset,
        n_branches=len([1 for x, s in subset.items() if s > 0]),
        likenesses=["dud", 0] + sorted(set(s for x, s in subset.items())),
    )


def sim(a, b):
    assert len(a) == len(b)
    return sum(1 for (ac, bc) in zip(a, b) if ac == bc)


def filter_words(words, constraints):
    def check(w, c):
        if c[1] == 'any':
            return sim(w, c[0]) > 0
        return sim(w, c[0]) == c[1]
    return [w for w in words
            if all(check(w, c) for c in constraints.items())
            and w not in constraints]


def input_constraint(words, default_word):
    while True:
        print("result? [likeness of %s, word:likeness, or Ctrl-C] " %
              default_word.upper(), end="")
        i = input()

        if ':' in i:
            a, b = i.split(':')
            new_word = a.strip()
            try:
                new_likeness = int(b.strip())
            except ValueError:
                print("Invalid likeness number.")
                continue
            if new_word not in words:
                print("Invalid word.")
                continue
            return new_word, new_likeness

        try:
            new_likeness = int(i.strip())
        except ValueError:
            print("Invalid likeness number.")
            continue
        return default_word, new_likeness


def prompt():
    print()
    print("Welcome to ROBCO Industries (TM) Password Recovery Tool")
    print()

    print("Words: ", end="")
    words = input().lower()
    words = re.sub('[^a-z]', ' ', words)
    words = re.split(' +', words)
    print()
    return words


def run(words):
    constraints = {}
    while True:
        subset = filter_words(words, constraints)

        if len(subset) == 0:
            print("No words left, impossible constraints.")
            break

        if len(subset) == 1:
            print("Password: %s" % subset[0])
            break

        branches = {}

        print("Guesses:")

        for word in words:
            if word not in subset:
                print("    %s" % word.upper())
                continue

            b = get_branch(words, constraints, word)
            branches[word] = b

            print("  * %s: %s (%d words)" % (
                word.upper(),
                " ".join("[%s]" % x for x in b.likenesses),
                b.n_branches,
            ))

        print()

        # "the one in the middle"
        best = min(branches.values(),
                   key=lambda b: abs(b.n_branches - (len(words) / 2)))
        print("Suggested: %s (%d words)" % (
            best.word.upper(), best.n_branches))

        c_w, c_n = input_constraint(subset, best.word)
        constraints[c_w] = c_n

        subset = filter_words(words, constraints)

        print("OK, updating constraints: %r" % constraints)
        print("%d constraints, %d words left" % (
            len(constraints), len(subset)))
        print()


if __name__ == '__main__':
    words = prompt()
    run(words)