Re: given Dict=(act, eat, sat, ...) make a long chain (no repeats) with 2-letter overlaps

In sci.math HenHanna <HenHanna@devnull.tb> wrote:

On 6/17/2024 4:24 PM, James Waldby wrote:

In sci.math HenHanna <HenHanna@devnull.tb> wrote:

given (a list of 3-letter words)
   Dict=(act, ATT, eat, sat, sit, cat, bat, dog, god, mat, tim, kim, ...)
>
The object is to make a long chain (no repeats) with 2-letter overlaps.
                               e.g. -- [cat, ate, tea, eat, ATT, ...]
What's a good approach (in Python)?

 
According to ref 1, longest-path problems are NP-complete.  At the
moment there's no method known that is "good" in general for the
problem.  However, if all of the dictionary words are chosen from a
natural-language, then we have a special (not general) case.  I think
in this special case a method like finding pairs, then combining pairs
to triple, then triples to fives, fives to nines, etc, might work
well, given obvious fallbacks to combining different-length sequences
when at some length same-length combinations don't exist.
 
*Ref 1 <https://en.wikipedia.org/wiki/Longest_path_problem#NP-hardness>
*Ref 2 <https://en.wikipedia.org/wiki/NP-completeness>

              in Mathematica, it's easy to find   THE Longest    chain?
                             is this a typical NP-complete problem?

 
As noted in ref 2, "A problem p in NP is NP-complete if every other
problem in NP can be transformed (or reduced) into p in polynomial
time", so there is a sense in which every NP-complete problem is a
typical NP-complete problem.

...

word Chain    with 3-letter overlaps (between successive words)
 
10 (shtoomest, estrayed, yedo, edomitish,
                              ish, ishime, imelle, ller, lerps, rps)

I wrote some programs to look for word chains, first on the plan
mentioned earlier -- finding pairs, then combining pairs to triples,
triples to fives, etc which worked ok to find chains of up to 30 or 40
words, but this turned out to be fairly slow and of course memory
intensive, running out of memory after a few hours on my 64GB-ram
system.  Then I tried depth-first recursion, which in .1 second can
find chains of 150+ words, using 6-letter dictionary words with
3-letter overlaps, but taking 1.5 hours to find its first 171-word
chain, 11 hours to find a 174-chain, 30 hours for a 177-chain, then no
progress in the next 142 hours of computation.  With a couple of minor
program changes I got the 174 time below 6 minutes, and time to 177
around 14 minutes, but no progress beyond that in the next 18 hours.

Here's an 8-letter/4-overlap 10-chain example, based on an
88-word dictionary of 8-letter words, all containing `over`:
10 : discover overhang hangover overhung hungover overtake
     takeover overturn turnover overacts at 0.201194 seconds

Example 6-letter/3-overlap 177-chain:
177 :  abacus cuspid pidgin ginger gerbil billet lethal halter terser
serene enemas mascot cotton tonsil silent entice icebox boxcar carbon
bonbon bongos gospel pellet letups upshot hotbed bedbug bugles lessee
seeped pedant anthem hempen pennon noncom combat bather herbal balder
dermis misfit fitful fulcra craven vendor dormer merman manful fulfil
filthy thymus muscat catnap napped pedlar largos gossip siphon honcho
choice icecap captor torpor portal talent entrap rapper permit mitten
tenpin pintos tosses sesame amebas basins instil tildes despot potash
ashcan cancan cancel cellar larvas vassal salver verbal ballad ladles
lessen sensor sorbet betcha chapel pelvis viscus custom tombed bedlam
lambed bedpan pantry tryout outlay layout outran rancor cornea neared
redden denser server vermin minute uterus russet settee teepee peewee
weevil villas lassie siesta stamen mentor torque queasy asylum lumbar
barfed fedora orator torrid ridden dentin tinsel selves vessel selfie
fiesta stadia dialog logout outrun runway waylay layman mantra trains
insult ultras rascal callus lustre tremor mortar tartar tarpon poncho
chores resend endear earwig wigwam wampum pumper person sonnet nether
hernia niacin cinder derail ailing ingest esters ersatz at 820.516 seconds

Example 8-letter/4-overlap 79-chain:
79: abjuring ringside sidekick kickback backbone bonehead headland
    landlady ladyship shipload loadstar starfish fishtail tailgate
    gatepost postdate dateline linefeed feedback backfire fireside
    sidelong longhand handbook bookcase casework workbook bookworm
    wormwood woodcock cocksure surefire firewood woodland landmark
    markdown downhill hillside sideshow showdown downturn turnover
    overcome comeback backhand handrail railroad roadkill killdeer
    deerskin skinhead headword wordplay playback backstop stopover
    overhand handsome somewhat whatever evermore moreover overhang
    hangover overhung hungover overtake takeover overdraw drawback
    backrest restrain raindrop dropouts outshone honester sternest
    nestling lingered at 54577.844678 seconds