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

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.

________________
 
-- Martha has aspirin in industrial allotments.
 
-- Two women enter erotic icehouse, seduce celibate teacher.
 
-- Rush showed editorial alarmism, smeared educational alliance ceaselessly.