Resource Library

BALLAREALEADLADY    

#!/usr/bin/env pythonimport collectionsimport sysdef find_word_squares(words):    # Preprocess words: O(#words * word-length) time and space    words_by_letter_position = collections.defaultdict(set)    for word in words:        for index, letter in enumerate(word):            words_by_letter_position[(index,letter)].add(word)    # For each word, see if we can make a square.  O(#words * word-length^2/2)    # for speed, assuming that set intersection is ~O(1) for small sets.    # Worst-case storage is O(#words * word-length) for very very contrived    # 'words'.  Normal English words will result in much smaller storage demand;    # there is a practical maximum of ~170,000 English words.    for word in words:        # Initialize a set of incomplete possible squares; each item is an N-tuple        # of words that are valid but incomplete word squares.  We could also do        # depth-first via recursion/generators, but this approach is a little        # simpler to read top-to-bottom.        possible_squares = set([(word,)])    # As long as we have any incomplete squares:    while possible_squares:        square = possible_squares.pop()        # When matching an incomplete square with N words already present,        # we need to match any prospective words to the tuples formed by        # (N, Nth character in word 0), (N, Nth character in word 1), ...        # Only words which satisfy all of those restrictions can be added.        keys = [(i, square[i][len(square)]) for i in xrange(len(square))]        possible_matches = [words_by_letter_position[key] for key in keys]        for valid_word in set.intersection(*possible_matches):            valid_square = square + (valid_word,)            # Save valid square in 'ret' if it's complete, or save it as            # a work-to-do item if it's not.            if len(valid_square) == len(word):                yield valid_square            else:                possible_squares.add(valid_square)if __name__ == '__main__':    for square in find_word_squares(sys.argv[1:]):        print '
'.join(square)        print    

#include <string>#include <unordered_map>#include <vector>using Words = std::vector<std::string>;class WordSquaresFinder { public:  std::vector<Words> GetWordSquares(const Words& words) {    all_words_ = words;    CreatePrefixLookup();    CollectWordSquares(/*partial_solution=*/Words());    return std::move(result_);  } private:  size_t word_length() const { return all_words_[0].length(); }  void CreatePrefixLookup() {    for (const std::string& word : all_words_) {      for (size_t length = 0; length < word.length(); length++) {        std::string prefix = word.substr(0, length);        AddToPrefixLookup(prefix, word);      }    }  }  void AddToPrefixLookup(const std::string& prefix, const std::string& word) {    if (prefix_lookup_.find(prefix) == prefix_lookup_.end())      prefix_lookup_[prefix] = std::vector<std::string>();    prefix_lookup_[prefix].push_back(word);  }  void CollectWordSquares(const Words& partial_solution) {    if (partial_solution.size() == word_length()) {      // The partial solution is complete      result_.push_back(partial_solution);      return;    }    std::vector<std::string> candidate_words =        FindAllCandidates(partial_solution);    for (const std::string& word : candidate_words) {      // Recurse      Words new_partial_solution = partial_solution;      new_partial_solution.push_back(word);      CollectWordSquares(new_partial_solution);      // Keep looking for other solutions    }    // When we come here we've checked all words, and all possible solitions    // have been stored. Time to start backtracking.  }  std::vector<std::string> FindAllCandidates(const Words& partial_solution) {    int num_words = partial_solution.size();    std::string prefix = GetNthLetters(partial_solution, num_words);    return prefix_lookup_[prefix];  }  std::string GetNthLetters(const Words& words, int n) {    std::string result;    for (const std::string& word : words)      result += std::string{word[n]};    return result;  }  Words all_words_;  std::unordered_map<std::string, std::vector<std::string>> prefix_lookup_;  std::vector<Words> result_;};