# /r/dailyprogrammer
# Challenge 150
# by /u/Sakuya_Lv9

class WordList

    def initialize arr
        @list = arr
        @list.each { |s| s.chomp! }
    end

    def has_prefix? word
        has_word? word, :partial
    end

    def has_word? word, mode=:exact
        if mode == :partial
            partial = true
        elsif mode == :exact
            partial = false
        else
            raise ArgumentError
        end

        range = 0..@list.length
        regexp = Regexp.compile('\A' + word) if partial
        while not range.begin == range.end
            mid = (range.end - range.begin) / 2 + range.begin
            w = @list[mid]
            case w <=> word
            when -1
                range = (mid + 1)..range.end
            when 0
                return true
            when 1
                return true if partial && regexp =~ w
                range = range.begin..mid
            end
        end
        false
    end

end

class Solution
    attr_accessor :words

    def initialize words
        @words = words
    end

    def to_s
        return words.join(" ").capitalize + "."
    end

end

class PartialSolution
    attr_accessor :wordlist
    attr_accessor :list
    attr_accessor :words
    attr_accessor :done

    def initialize wordlist, list, words=[]
        @wordlist = wordlist
        @list = list
        @words = words
    end

    def add_word word
        list = list_minus_word word
        PartialSolution.new @wordlist, list, (@words.clone << word)
    end

    def list_minus_word word
        list = @list.dup
        list.map! do |x|
            x.dup
        end
        word.each_char do |char|
            list.each do |string|
                string.slice! 0 if string[0] == char
            end
        end
        list
    end

    # returns array containing list of
    # PartialSolutions with one more word
    #
    # returns Solution object if it is done
    def explode
        return [Solution.new(@words)] if list[0].empty? and list[1].empty?
        words = get_words
        array = []
        words.each do |word|
            array << (self.add_word word)
        end
        return array
    end

    def get_words word=""
        words = []
        list = list_minus_word word

        [0, 1].each do |n|
            next if list[n].empty?
            w = word + list[n][0]
            if @wordlist.has_prefix? w
                words << (get_words w)
                if @wordlist.has_word? w
                    words << w
                end
            end
        end

        words.flatten
    end

end

class DisemvoweledString
    attr_accessor :list
    attr_accessor :mode

    def initialize list, mode=:return_everything
        @list = list
        @mode = mode
    end

    # this is almost the main method
    def solve_for_original
        # wordlist = WordList.new(IO.readlines("enable1.txt"))
        wordlist = WordList.new(%w{ asteroids cheating daff dis et eth fen fend host lo off rids sae the this tor we wile will })
        partial_solutions = [PartialSolution.new(wordlist, @list)]
        solutions = []

        while partial_solutions.length != 0
            if partial_solutions.last.class == Solution
                solutions << partial_solutions.pop
                if @mode == :return_ASAP
                    return solutions
                end
            else
                partial_solutions.concat partial_solutions.pop.explode
            end
        end

        return solutions
    end

end

# nah, not going to change it
input = ["wwllfndffthstrds","eieoeaeoi"]
input.each do |s| s.chomp! end

puts DisemvoweledString.new(input).solve_for_original