Python word games. The last letter of the first word == the first letter of the second word. Find the largest possible sequence of words
I am trying to write a program that simulates a play on words, where from a given set of words it finds the largest possible sequence of words. The word cannot be used twice.
I can make matching letters and words up and store them in lists, but I am having problems with how to handle the potentially exponential number of possibilities of words in lists. If word 1 matches word 2 and then I go down that route, how can I go back to see if words 3 or 4 match word one and then start their own routes, all from the first word?
I was thinking of some way to call a function inside myself, maybe?
I know he doesn't do what I need anywhere, but this is a start. Thanks in advance for any help!
g = "audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig gulpin haxorus"
def pokemon():
count = 1
names = g.split()
first = names[count]
master = []
for i in names:
print (i, first, i[0], first[-1])
if i[0] == first[-1] and i not in master:
master.append(i)
count += 1
first = i
print ("success", master)
if len(master) == 0:
return "Pokemon", first, "does not work"
count += 1
first = names[count]
pokemon()
source to share
Your idea to call a function within yourself is good. We can solve this with recursion:
def get_neighbors(word, choices):
return set(x for x in choices if x[0] == word[-1])
def longest_path_from(word, choices):
choices = choices - set([word])
neighbors = get_neighbors(word, choices)
if neighbors:
paths = (longest_path_from(w, choices) for w in neighbors)
max_path = max(paths, key=len)
else:
max_path = []
return [word] + max_path
def longest_path(choices):
return max((longest_path_from(w, choices) for w in choices), key=len)
Now we'll just define our wordlist:
words = ("audino bagon baltoy banette bidoof braviary bronzor carracosta "
"charmeleon cresselia croagunk darmanitan deino emboar emolga "
"exeggcute gabite girafarig gulpin haxorus")
words = frozenset(words.split())
Invoke longest_path
with a set of words:
>>> longest_path(words)
['girafarig', 'gabite', 'exeggcute', 'emolga', 'audino']
A few things to know: as you point out, this has exponential complexity, so be careful! Also, know that python has a recursion limit!
source to share
Using black magic and graph theory, I found a partial solution that might be good (not fully tested).
The idea is to map your problem to a graph problem, not a simple iterative problem (although it might work too!). Therefore, I have defined the nodes of the graph as the first letters and the last letters of your words. I can only create edges between nodes like first
and last
. I cannot map node first
number X to node last
number X (it cannot be followed by the word self). And from that your problem is the same as the longest path problem , which is usually NP-hard for the general case :)
Getting some info here: fooobar.com/questions/1165218 / ... I managed to write this:
g = "audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig gulpin haxorus"
words = g.split()
begin = [w[0] for w in words] # Nodes first
end = [w[-1] for w in words] # Nodes last
links = []
for i, l in enumerate(end): # Construct edges
ok = True
offset = 0
while ok:
try:
bl = begin.index(l, offset)
if i != bl: # Cannot map to self
links.append((i, bl))
offset = bl + 1 # next possible edge
except ValueError: # no more possible edge for this last node, Next!
ok = False
# Great function shamelessly taken from stackoverflow (link provided above)
import networkx as nx
def longest_path(G):
dist = {} # stores [node, distance] pair
for node in nx.topological_sort(G):
# pairs of dist,node for all incoming edges
pairs = [(dist[v][0]+1,v) for v in G.pred[node]]
if pairs:
dist[node] = max(pairs)
else:
dist[node] = (0, node)
node,(length,_) = max(dist.items(), key=lambda x:x[1])
path = []
while length > 0:
path.append(node)
length,node = dist[node]
return list(reversed(path))
# Construct graph
G = nx.DiGraph()
G.add_edges_from(links)
# TADAAAA!
print(longest_path(G))
While it looks good, there is a big drawback. You, for example, are working because there is no loop in the resulting graph of the input words, however this solution does not work on cyclic graphs. The way around this is to detect loops and break them. Detection can be done as follows:
if nx.recursive_simple_cycles(G):
print("CYCLES!!! /o\")
Breaking a loop can be done by simply removing a random edge in a loop, and then you accidentally find the optimal solution for your problem (imagine a loop with a tail, you should shorten the loop on a node having 3), so I suggest to roughly force that part by trying all possible loop breaks, calculating the longest path and taking the longest of the longest paths. If you have multiple loops, it gets a little more explosive in the number of possibilities ... but hey it's NP-hard, at least the way I see it, and I wasn't planning on solving this now :)
Hope it helps
source to share
Here's a solution that doesn't require recursion. It uses the itertools permutation function to look at all possible word orders and find the one with the longest length. To save time, as soon as the order hits a word that is not working, it stops checking what is being ordered and moved.
>>> g = 'girafarig eudino exeggcute omolga gabite'
... p = itertools.permutations(g.split())
... longestword = ""
... for words in p:
... thistry = words[0]
... # Concatenates words until the next word doesn't link with this one.
... for i in range(len(words) - 1):
... if words[i][-1] != words[i+1][0]:
... break
... thistry += words[i+1]
... i += 1
... if len(thistry) > len(longestword):
... longestword = thistry
... print(longestword)
... print("Final answer is {}".format(longestword))
girafarig
girafariggabiteeudino
girafariggabiteeudinoomolga
girafariggabiteexeggcuteeudinoomolga
Final answer is girafariggabiteexeggcuteeudinoomolga
source to share
First, let's see what the problem looks like:
from collections import defaultdict
import pydot
words = (
"audino bagon baltoy banette bidoof braviary bronzor carracosta "
"charmeleon cresselia croagunk darmanitan deino emboar emolga "
"exeggcute gabite girafarig gulpin haxorus"
).split()
def main():
# get first -> last letter transitions
nodes = set()
arcs = defaultdict(lambda: defaultdict(list))
for word in words:
first = word[0]
last = word[-1]
nodes.add(first)
nodes.add(last)
arcs[first][last].append(word)
# create a graph
graph = pydot.Dot("Word_combinations", graph_type="digraph")
# use letters as nodes
for node in sorted(nodes):
n = pydot.Node(node, shape="circle")
graph.add_node(n)
# use first-last as directed edges
for first, sub in arcs.items():
for last, wordlist in sub.items():
count = len(wordlist)
label = str(count) if count > 1 else ""
e = pydot.Edge(first, last, label=label)
graph.add_edge(e)
# save result
graph.write_jpg("g:/temp/wordgraph.png", prog="dot")
if __name__=="__main__":
main()
leads to
which makes the solution fairly obvious (the path is shown in red), but only because the graph is acyclic (except for two trivial self-learning).
source to share