Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Vertex:
def __init__(self, word, dist=9999):
self.word = word
self.dist = dist
def gen_all_neighbours(v, forbidden):
""" Generate all neighbours for a vertex, i.e. all
words that are one letter off. Uses ascii values and
excludes any words in list(forbidden).
"""
base = [ord(c) for c in v.word]
neighbours = []
for i in range(8):
candidate = list(base)
n = candidate[i % 4]
if i < 4:
candidate[i % 4] = ((n + 1 - 97 ) % 26 ) + 97
else:
candidate[i % 4] = ((n - 1 - 97 ) % 26 ) + 97
candidate_str = "".join([chr(c) for c in candidate])
if candidate_str not in forbidden:
neighbours.append(candidate_str)
return neighbours
def minPresses(start, finish, forbid):
queue = [Vertex(start, 0)]
visited = []
while queue:
v = queue.pop(0)
visited.append(v.word)
dist = v.dist
if v.word == finish:
return v.dist
else:
neighbours = gen_all_neighbours(v, forbid)
for n in neighbours:
if n not in visited:
queue.append(Vertex(n, dist + 1))
return -1
# minPresses("aaaa", "zzzz", ["aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza"]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.