Message Boards Message Boards

Find the longest word path in dictionary?

GROUPS:

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?

POSTED BY: Yode Japhe
Answer
4 months ago

Group Abstract Group Abstract