#!/usr/local/pypy-2.2/bin/pypy

# pylint: disable=superfluous-parens
# superfluous-parens: Parentheses are good for clarity and portability

"""Find anagrams of a sentence."""

from __future__ import print_function

import sys
# port pprint
# port functools
# port itertools
import collections


def contains_vowel(string):
    """Return True iff string contains a vowel (including y)."""
    vowels = set('aeiouy')

    string_set = set(string)

    return bool(vowels & string_set)


def get_words_dict(file_):
    """Read a file with words.  Prune out anything with punctuation."""
    # These are the only one-letter-words we want to keep; /usr/share/dict/words
    # has all the single-letter-words as valid "words", but we don't want that.
    good_single_letter = {'a', 'i'}

    result_dict = collections.defaultdict(set)

    for candidate_line in file_:
        candidate_word = candidate_line.lower().rstrip()
        if candidate_word.isalpha() and contains_vowel(candidate_word):
            length = len(candidate_word)
            if length == 1:
                # length 1 - check if this is a valid single-character word
                if candidate_word in good_single_letter:
                    result_dict[length].add(candidate_word)
            else:
                # Not of length 1, so always add
                result_dict[length].add(candidate_word)

    return result_dict


def get_alphabet(sentence):
    """Compute the alphabet used by a sentence - IOW, return a set of just those characters actually used."""
    result = LetterFrequencies(sentence)
    if ' ' in result:
        del result[' ']
    return result


def is_word_of_alphabet(alphabet, word):
    """
    Check if a word conforms to our alphabet.

    Note that when we say "alphabet", we mean letters with frequencies, not a set of characters!
    """
    words_alphabet = LetterFrequencies(word)

    return bool(words_alphabet.is_subset(alphabet))


def prune_words_dict_for_alphabet(words_dict, alphabet):
    """Eliminate words that aren't over the appropriate alphabet from our words_dict."""
    result_dict = collections.defaultdict(set)
    for length, words_of_length in words_dict.items():
        for word in words_of_length:
            if is_word_of_alphabet(alphabet, word):
                result_dict[length].add(word)
    return result_dict


class LetterFrequencies(object):
    # pylint: disable=too-few-public-methods
    """Basically a collections.Counter that allows comparison operations."""

    def __init__(self, sentence):
        """Initialize a LetterFrequencies."""
        self.frequencies = collections.Counter(sentence)
        # We ignore blanks
        if ' ' in self.frequencies:
            del self.frequencies[' ']

    def __str__(self):
        """Convert to string."""
        return str(self.frequencies)

    __repr__ = __str__

    def __getitem__(self, key):
        """Look up an item by key."""
        return self.frequencies[key]

    def __contains__(self, key):
        """Enable "in" operator."""
        return key in self.frequencies

    def __len__(self):
        """Get length of frequencies."""
        return len(self.frequencies)

    def __delitem__(self, key):
        """Delete by key."""
        del self.frequencies[key]

    def __setitem__(self, key, value):
        """Set a frequency."""
        self.frequencies[key] = value

    def __sub__(self, other):
        """Subtract two LetterFrequencies."""
        result = LetterFrequencies('')

        result.frequencies = self.frequencies - other.frequencies

        return result

    def is_subset(self, other):
        """Return True iff self is a subset of other."""
        self_keys = set(self.frequencies)
        other_keys = set(other.frequencies)

        if self_keys <= other_keys:
            for key in self_keys:
                if self.frequencies[key] > other.frequencies[key]:
                    # We have equal keys, but the value for this keypair is not a subset relationship
                    return False
            # All checks out - keys are a subset, as are values at the given pairwise keys
            return True

        # self has at least one key that isn't in other
        return False

    def is_equal(self, other):
        """Return True iff self has the same keys as other, and the same values as well."""
        self_items = set(self.frequencies.items())
        other_items = set(other.frequencies.items())

        return self_items == other_items


def is_anagram(original_sentence_frequencies, candidate_sentence):
    """Test if candidate_sentence is of the same letter frequency as original_sentence_frequencies."""
    candidate_sentence_frequencies = LetterFrequencies(candidate_sentence)
    return bool(original_sentence_frequencies.is_equal(candidate_sentence_frequencies))


def del_blanks(input_string):
    """
    Delete blanks from input_string, returning the result.

    If the input was a list, return a list.
    If the input was anything else, return a str.
    """
    output_list = []
    for character in input_string:
        if character == ' ':
            pass
        else:
            output_list.append(character)

    if isinstance(input_string, list):
        return output_list

    output_string = ''.join(output_list)
    return output_string


def find_anagrams_recursive(
        result_anagrams,
        original_sentence,
        original_sentence_frequencies,
        previous_words_dict,
        previous_candidate_sentence,
):
    """Find anagrams for original_sentence."""
    usable_letter_counts = LetterFrequencies(original_sentence) - LetterFrequencies(previous_candidate_sentence)

    current_words_dict = prune_words_dict_for_alphabet(previous_words_dict, usable_letter_counts)

    max_word_len = len(del_blanks(original_sentence)) - len(del_blanks(previous_candidate_sentence))

    # We have an equally "long" (minus blanks) sentence, so we either have an anagram, or something's wrong with our algorithm
    if max_word_len == 0:
        if is_anagram(original_sentence_frequencies, previous_candidate_sentence):
            # Append to the result list, converted to a string
            if result_anagrams is None:
                print(''.join(previous_candidate_sentence))
            else:
                result_anagrams.append(''.join(previous_candidate_sentence))
        else:
            sys.stderr.write('{}: Not an anagram: {}\n'.format(sys.argv[0], previous_candidate_sentence))
            raise AssertionError('How did we get here?')
        return

    for current_word_len in range(1, max_word_len + 1):
        if current_word_len in current_words_dict:
            for current_word in current_words_dict[current_word_len]:
                current_candidate_sentence = previous_candidate_sentence[:]
                if current_candidate_sentence:
                    current_candidate_sentence.append(' ')

                current_candidate_sentence.extend(current_word)

                find_anagrams_recursive(
                    result_anagrams,
                    original_sentence,
                    original_sentence_frequencies,
                    current_words_dict,
                    current_candidate_sentence,
                    )


def find_anagrams(to_stdout, dictionary_file, original_sentence_string):
    """Find anagrams for original_sentence_string."""
    if to_stdout:
        result_anagrams = None
    else:
        result_anagrams = []

    original_sentence_list = list(original_sentence_string)

    original_sentence_frequencies = LetterFrequencies(original_sentence_list)

    original_words_dict = get_words_dict(dictionary_file)

    previous_words_dict = prune_words_dict_for_alphabet(original_words_dict, original_sentence_frequencies)

    previous_candidate_sentence = []

    find_anagrams_recursive(
        result_anagrams,
        original_sentence_list,
        original_sentence_frequencies,
        previous_words_dict,
        previous_candidate_sentence,
        )

    return result_anagrams