#!/usr/bin/env python # doublet.py - B. Blackmoor (bblackmoor@blackgate.net) - 2009-02-23 """Doublet solver for Python Finds a path of valid words between two other words Usage: doublet.py [-h] [-v] [-d DICTIONARY] START END Options: -d ..., --dictionary=... use specified dictionary file or URL -h, --help show this help -v, --verbose show debugging information while parsing Examples: doublet.py flower flour doublet.py love hate doublet.py -v dogs wolves doublet.py -d scrabble_dictionary.txt begin end doublet.py -v -d scrabble_dictionary.txt man woman doublet.py -v -d scrabble_dictionary.txt mouse elephant """ import os import urllib import sys import getopt import re import math import time end_stopwatch = 0 start_stopwatch = 0 found = False dictionary = [] head_word = None tail_word = None verbose = False search_path = list() dead_paths = list() path_found = False def usage(): print (__doc__) def find_path(): global dictionary global already_used global head_word global tail_word global verbose global search_path global dead_paths path_found = False for parent_path_id in range(0, len(search_path), 1): if parent_path_id not in dead_paths: parent = search_path[parent_path_id][-1] word_length = len(parent) children = [] regex_variations = [] relevant_words = " ".join(dictionary) dead_paths.append(parent_path_id) for j in range(0, word_length, 1): regex = r"\b" + parent[0:j] + "[^" + parent[j] + "]?" + parent[j+1:] + r"\b" regex_variations.append(regex) for j in range(0, word_length+1, 1): regex = r"\b" + parent[0:j] + "[\w]" + parent[j:] + r"\b" regex_variations.append(regex) joined_regex_variations = "|".join(regex_variations) children = re.compile(joined_regex_variations).findall(relevant_words) if children != []: for child in children: if path_found == False: child = child.strip() if child not in already_used: path_id = len(search_path) search_path.append([]) search_path[path_id] = search_path[parent_path_id][:] search_path[path_id].append(child) already_used.append(child) if verbose: print (search_path[path_id]) if child == tail_word: path_found = True if path_found == True: return path_id if path_found == True: return path_id else: try: return find_path() except: return None def failure(): global found global end_stopwatch global start_stopwatch global search_path if found == False: found = True search_path_length = len(search_path) end_stopwatch = time.time() elapsed_time = end_stopwatch - start_stopwatch print ('Fail: could not find a path between words') print (str(search_path_length) + " potential paths were examined, taking %9.4f seconds" % (elapsed_time)) def success(search_results): global found global end_stopwatch global start_stopwatch global search_path if found == False: found = True search_path_length = len(search_path) end_stopwatch = time.time() elapsed_time = end_stopwatch - start_stopwatch print (str(search_path_length) + " potential paths were examined, taking %9.4f seconds" % (elapsed_time)) print (*search_results, sep=" >> ") def main(argv): global end_stopwatch global start_stopwatch global dictionary global already_used global head_word global tail_word global verbose global search_path start_stopwatch = time.time() dictionary_file = None default_dictionary = ["hate", "have", "hove", "love"] default_dictionary += ["dogs", "does", "doles", "soles", "solves", "wolves"] default_dictionary += ["man", "ran", "roan", "roman", "woman"] default_dictionary += ["flour", "lour", "dour", "doer", "dower", "lower", "flower", "glower", "plower"] already_used = [] try: opts, args = getopt.getopt(argv, "hvd:", ["help", "verbose", "dictionary="]) except getopt.GetoptError: usage() sys.exit(2) for opt, arg in opts: if opt in ("-h", "--help"): usage() sys.exit() elif opt == '-v': verbose = True elif opt in ("-d", "--dictionary"): dictionary_file = arg try: head_word = args[0] tail_word = args[1] except: print ('Error: missing parameter') usage() sys.exit() if len(head_word) < 2 or len(tail_word) < 2: print ('Error: input error') print ('Both words must be at least 2 characters long.') usage() sys.exit() if head_word == tail_word: print ('Done: words already match') if len(head_word) < len(tail_word): flipped_order = True temp_word = tail_word tail_word = head_word head_word = temp_word else: flipped_order = False head_word_length = len(head_word) tail_word_length = len(tail_word) if dictionary_file == None: for word in default_dictionary: dictionary.append(word) else: try: dictionary_file_contents = open(dictionary_file,"rU") except: print ('Error: input error') print ('Could not open dictionary file.') sys.exit() while dictionary_file_contents: line = dictionary_file_contents.readline() line = line.lower() line = line.strip() line_length = len(line) if line_length == 0: break elif (head_word_length + 1) >= line_length and line_length >= (tail_word_length - 1): dictionary.append(line) if head_word not in dictionary: print ("Fail: " + head_word + " is not in the provided dictionary"); if tail_word not in dictionary: print ("Fail: " + tail_word + " is not in the provided dictionary"); search_path.append([head_word]) already_used.append(head_word) search_results = [] found_path_id = find_path() if (found_path_id == None): failure() else: search_results = search_path[found_path_id] if flipped_order: search_results.reverse() if (search_results): success(search_results) else: failure() sys.exit() if __name__ == "__main__": main(sys.argv[1:])