Message Boards Message Boards

GROUPS:

Find the longest word path in dictionary?

Posted 1 year ago
1286 Views
|
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

SeedRandom[2]
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]]

{calm,muir,reef,fray,yaws,seed,deaf,fnma,axis,stow,waft,tint,trig,good,duns,sill,loge,etch,hill,lath,howl}

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
Attachments
Remove
or Discard

Group Abstract Group Abstract