Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: no@no.no (James Waldby)
Newsgroups: comp.lang.python,sci.lang,sci.math
Subject: Re: given Dict=(act, eat, sat, ...) make a long chain (no repeats) with 2-letter overlaps
Date: Mon, 17 Jun 2024 23:24:15 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 39
Message-ID: <v4qgiu$ve3b$1@dont-email.me>
References: <v4q168$sgqr$1@dont-email.me>
Injection-Date: Tue, 18 Jun 2024 01:24:15 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="585482d3d56ccbaea3432ff3b396faa0";
	logging-data="1030251"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19rlWMSHtjC4BjwXxfJtYor"
User-Agent: tin/2.6.2-20220130 ("Convalmore") (Linux/5.15.0-107-generic (x86_64))
Cancel-Lock: sha1:kA9IZKY8XAxgEgiC2JAj6BRHla8=
Bytes: 2587

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.