Message Boards Message Boards


Find the longest word path in dictionary?

Posted 4 years ago
0 Replies
0 Total Likes

Cross post here

A word path means the last character of the last word is same to the first character of the next word.If I have $55$ words,I can find it with this method.

Build a graph

string = Select[ToLowerCase[RandomSample[DictionaryLookup[]]], 
   3 < StringLength[#] < 5 &];
g = RelationGraph[StringTake[#, -1] == StringTake[#2, 1] &, 
  string[[;; 55]], VertexLabels -> "Name"]

Mathematica graphics

Find a longest word path by Jason's answer here

allPaths = 
  FindPath[g, #2, #1, Infinity, All] & @@@ 
    Subsets[VertexList[g], {2}] // Apply[Join];
First[TakeLargestBy[allPaths, Length@Union@# &, 1]]


Well I have to say this is a very very slow solution.I even cannot find more than $60$ words.Actually I want to find Length[DictionaryLookup[]]=92518 words. It seem I still have a long way to go.Do any suggestion can give?

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract