Background information: Given two different strings of equal length, the spacing between them is the number of other strings you would need to connect them on a word ladder. Alternately, this is 1 less than the number of letters that differ between the two strings.
The challenge: Given an input list of unique words and a maximum total spacing, output a list of distinct words taken from the input list. The output list's total spacing must not exceed the given maximum. The output list should be as long as possible.
My output list is 433 words long. May someone look over code proofreading/ efficiency? Much thanks.
Also, the text file used in the program can be found here: https://gist.githubusercontent.com/cosmologicon/0a4448e8fdb79ee620a68ed131eac58e/raw/a8831d08019f73e7d5a52042e2c4afe6fea70011/363-hard-words.txt
import operator MAX = 100 # Max word ladder score I'm allowed in this program with open("363-hard-words.txt") as f: data = f.read().splitlines() f.close() def merge_two_dicts(x, y): z = x.copy() z.update(y) return z # Returns numerical spacing between a and b on the word ladder def spacing(a, b): score = 0 for x, y in zip(a, b): if x != y: score += 1 return score - 1 # Returns a dictionary of txt file words as key, with number of words with sp spacing as value def space_dict(sp): totals =  for word in data: total = 0 for word1 in data: if word == word1: continue if spacing(word, word1) == sp: total += 1 totals.append(total) return dict(zip(data, totals)) # Given a word, returns a dictionary with every other word as the key, # and the spacing between the word and the other word as the value def words_dict(word): totals =  for w in data: if w == word: continue totals.append(spacing(word, w)) return dict(zip(data, totals)) # Sorts a dictionary by its keys in ascending order and returns a list def sort_dict(space): return sorted(space.items(), key=operator.itemgetter(1)) # Returns a list of words with number spacing to the word def get_connections(word, number): output =  for w in data: if (spacing(word, w) == number) and (word != w): output.append(w) return output # Attempts to return max list of words with a total word ladder score of 0 def method1(): output =  sorted_dict = sort_dict(space_dict(0)) output.append(sorted_dict[-1]) data.remove(sorted_dict[-1]) connections = get_connections(sorted_dict[-1], 0) while len(get_connections(connections[-1], 0)) != 0: connections = get_connections(connections[-1], 0) output.append(connections[-1]) print("connections:", connections, "Output size:", str(len(output))) data.remove(connections[-1]) return len(output) # Attempts to return max length of a word ladder given first word, inspired by # tajjet's solution def method2_iter(wd): score, length = 0, 0 output = [wd] sorted_dict = sort_dict(words_dict(wd)) data.remove(wd) while score <= 100: length += 1 word = sorted_dict score += sorted_dict if score > 100: break output.append(word) data.remove(word) sorted_dict = sort_dict(words_dict(word)) print(output) return length def main(): # print(str(method1())) print(str(method2_iter("kats"))) main()