Word transformation for learners


#1

When this challenge surfaced, I knew it would be out of my league. It is. And I'm still grappling with simple mechanics. Witness...

>>> def one_letter_diff(a, b):
	if len(a) is not len(b): raise ValueError
	c = [(a[x], b[x]) for x in range(len(a)) if a[x] is not b[x]]
	return c[0] if len(c) == 1 else -1

>>> one_letter_diff('wafer', 'water')
('f', 't')
>>>

This is as far as I've gotten to testing neighbours... The tool that will do it. I'm still lost on how to build a queue of words to test, or how to store them. Now that this challenge is past its submission date, perhaps this would be a good opportunity to explore the concepts in the challenge, starting with this question?


#2

L.C neat :relaxed:


do you mean returning the shortest transformation for multiple words?


#3

I really mean getting the queue in order. My head just doesn't want to wrap around that concept. There are N words in the dictionary. Which ones are neighbours? My tool starts to go down that path, but ends there.


#4

Perhaps creating relations using a dictionary. From what I understand you mean for example if the word is male it's neighbors should be moll made make maid?


#5

mall I would accept, but yes. You are correct in your reading.


#6

At this point we are given a box size. Compared words are given to be the same length. What torture was endured parsing the dictionary to get here is sonething to forego. Giggles.


#7

Hi @mtf, let me try to give you an overview of how I tried to solve this problem and see if it helps you.

So all the words we are given in the dictionary can be visualised as a graph where each vertex of the graph represents a word in the dictionary and each edge between words represents a one letter difference between them.

A breadth first search (BFS) starting at a vertex u finds the shortest distance between u and every other vertex in the graph G. A basic BFS works by having a queue data structure Q. To begin with, Q is initialised with u, a for loop then goes through every vertex adjacent with u, assigns it weight 1 and adds the vertex to Q. A while loop makes this sequence of events happen continuously until Q is empty. Each time the weight is incremented by 1 and if a vertex already has an assigned weight it isn't added to Q or given a new weight.

So now we just have to turn our dictionary graph into one that can implement a BFS.
To do this we take our start word and use a for loop to check every possible way it can change by 1 letter, i.e. inserting 1 letter in any place, deleting any letter, or changing any letter; each new word we create we check to see if it is in the dictionary if it is then there is an edge between the two words in our imaginary graph. We then add this word to our Q. This carry's on till the new word equals the target word, or we run out of words to check.

I hope this has cleared things up or at least given you something to think about. I'd strongly recommend looking over my code. Some other resources: BFS information , BFS Video, and someone's explanation of this exact problem who explains it clearer and more in depth than me.


#8

Thank you, @alexcraig. I've been reading quite extensively on these concepts but the fog is far from abating. Will keep reading and studying code until something clicks. I was heartily impressed with your code.

The concept of dropping a letter, adding a letter and looking it up in the dictionary is not the idea I had, but it makes sense. My idea was to search the dictionary for words with only one letter difference and and define them as neighbours to build a sort of tree. Looking at it now I can see it would not be very efficient, and would have to run my tool above many, many times. Got my head going in circles.

Appreciate you taking the time to enlighten me.


#9

Your idea would be building an actual graph. You would have to implement a graph and vertex class. It is still a good solution you just have the overhead of building the graph in the first place. With my solution you are just imagining the dictionary as a graph so that you can perform BFS on it, it isn't actually a graph. Perhaps try to implement both solutions and see which you prefer :slight_smile:


#10

Here is a proof a concept for building a graph…

dictionary = {"humic","mal","mail","humid","wane","jade","molt","moll","want","slag","wade","mist","dolt","doll","mate","fade","maze","wart","jake","wary","mitt","wake","gate","mite","wait","faze","malt","hemic","male"}
def is_neighbour(a, b):
    if len(a) is not len(b): return -1
    c = [(a[x], b[x]) for x in range(len(a)) if a[x] is not b[x]] 
    return b if len(c) == 1 else -1
graph = [{x: []} for x in dictionary]
for i in range(len(graph)):
  key = graph[i].keys()
  for k in key:
    for term in dictionary:
      if is_neighbour(k,term) != -1:
        graph[i][k].append(term)

https://repl.it/I3jO/0

Now to poke holes in the methodology. I chose to create a list of dictionaries, which might not be the best choice. It’s a bit clunky but it does generate the graph I envisioned. Best practice, or practical advice welcome.

Asked and answered, almost. This is a lot less clunky and makes more sense as a look-up table:

graph_dict = {x: [] for x in dictionary}
for key in graph_dict:
  for term in dictionary:
    if is_neighbour(key, term) != -1:
      graph_dict[key].append(term)
 > graph_dict
=> {'hemic': ['humic'], 'wade': ['wake', 'fade', 'wane', 'jade'], 'malt': ['molt', 'male'], 'humid': ['humic'], 'doll': ['moll', 'dolt'], 'mal': [], 'wait': ['want', 'wart'], 'mite': ['mate', 'mitt'], 'gate': ['mate'], 'humic': ['hemic', 'humid'], 'slag': [], 'mate': ['mite', 'gate', 'maze', 'male'], 'wake': ['wade', 'wane', 'jake'], 'maze': ['mate', 'faze', 'male'], 'fade': ['wade', 'faze', 'jade'], 'mitt': ['mite', 'mist'], 'moll': ['doll', 'molt'], 'wane': ['wade', 'wake', 'want'], 'mail': [], 'mist': ['mitt'], 'faze': ['maze', 'fade'], 'wary': ['wart'], 'dolt': ['doll', 'molt'], 'want': ['wait', 'wane', 'wart'], 'molt': ['malt', 'moll', 'dolt'], 'wart': ['wait', 'wary', 'want'], 'jake': ['wake', 'jade'], 'male': ['malt', 'mate', 'maze'], 'jade': ['wade', 'fade', 'jake']}   

#11

Venturing further down the rabbit hole, I’m working along the lines of building the graph and have somewhat of an idea, but really falling short on defining terminology. Am I on the right track with the names I give my ideas?

stack = []
for key in graph:
  queue = [key]
  for node in graph[key]:
    queue.extend([graph[node]])
  stack.extend([queue])

for path in stack:
  print ('{} => {}'.format(path[0], path[1:]))

https://repl.it/I3jO/2

I do realize we are a long way from the finish line in this exploration. Still wrapping my head around it.

The next concern rather obviously is removing the source term from the potential paths. That’s a real brain teaser.

And we’re still only at cost is 2.

Final disclaimer… At this point we would normally be checking for possible destination matches. Some would have already occured. For now I’m only looking for a way to populate the data structures. Refinement can come later.


#12

There's quite a few ways to represent graphs, and their edges, yours is a good way but there's also modules you could import if you wanted more features for your graph. You seem to be using all the correct terminology, this article might be worth a read https://www.python.org/doc/essays/graphs/


#13

Still trudging along with blinders on so I don’t pollute my ideas, though I did read up as you suggested, @alexcraig, When I finally do come around, it will be on account of more wherewithal.

This is a little more directed though it still only traverses to cost = 2.

https://repl.it/I3jO/3

One hates to think this is going nowhere, but clearly it is. Don’t know if I really want to peer further down this rabbit hole. Is it time to concede or do I pour on?


#14

You seem to understand most things about graphs you need to now. The only difficult thing is taking a problem and abstracting it into a problem where you can use a graph to solve it,e.g. Abstracting the dictionary into a graph. I'd recommend researching and implementing these:

1) Breadth first search
2) Depth first search
3) Finding a minimum spanning tree using Kruskals and Primms Algorithms.
4) Research problems and try to solve them using graphs, e.g. Travelling salesman problem.