Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: HenHanna <HenHanna@devnull.tb>
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 19:32:58 -0700
Organization: A noiseless patient Spider
Lines: 52
Message-ID: <v4qrkr$157vp$1@dont-email.me>
References: <v4q168$sgqr$1@dont-email.me> <v4qgiu$ve3b$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 18 Jun 2024 04:33:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="54c3e15d7ec71e21a08feb29ba404444";
	logging-data="1220601"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/VsZ5yyVz9uMGuOm0/GhcHjQuoHb2p9dY="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:fjKc2GVF2JnTEvgxJEJ/0yOJmT8=
In-Reply-To: <v4qgiu$ve3b$1@dont-email.me>
Content-Language: en-US
Bytes: 3046

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.
> 
>> ________________
>>
>> -- Martha has aspirin in industrial allotments.
>>
>> -- Two women enter erotic icehouse, seduce celibate teacher.
>>
>> -- Rush showed editorial alarmism, smeared educational alliance ceaselessly.


thanks!




word Chain    with 3-letter overlaps (between successive words)

10 (shtoomest, estrayed, yedo, edomitish,
                               ish, ishime, imelle, ller, lerps, rps)