Word ladders program in Python

Question

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][0])
 data.remove(sorted_dict[-1][0])
 connections = get_connections(sorted_dict[-1][0], 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[0][0]
 score += sorted_dict[0][1]
 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()

• vnp: I am not sure I understand the problem statement. How the output list's total spacing is defined?
• Bo Work: @vnp street -> streea | spacing: 0, street -> strefa | spacing: 1, street -> strifa | spacing: 2
• vnp: OK, I see what is the spacing between strings. Still, what is a total spacing of the list?
• Bo Work: @vnp the total spacing of the list will be the sum of each consecutive spacings between the words. given a list of street, streea, strefa, and strifa... their total spacing will be 0 + 1 + 2 = 3

Answer 1

def spacing(a, b):
 score = 0
 for x, y in zip(a, b):
 if x != y:
 score += 1
 return score - 1

can be simplified to:

def spacing(a, b):
 """Returns numerical spacing between a and b on the word ladder"""
 return sum(1 for x, y in zip(a, b) if x != y) - 1

I suggest writing the comments as a string inside the function (a docstring) like above, then you can later write

help(spacing) 

and get the documentation. It also helps your IDE to find the documentation.

Answer 2

I would suggest renaming your methods. method1, and method2_itr would be better if they were instead named what they did. Currently, these functions have comments above them explaining their functionality, instead of that, let the function name speak for the function itself. Also, the argument wd passed into method2_itr, it would be better if the argument actually described it. For an outside observer on first glance it's difficult to see what wd stands for.

As Robert Martin famously says "The code itself is the best comment"

It's important to remember this as you're writing code, instead of every function needing to be commented, many functions should be able to speak for themselves.