Deutsch   English   Français   Italiano  
<v6d9sf$79kv$1@dont-email.me>

View for Bookmarking (what is this?)
Look up another Usenet article

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: Sat, 6 Jul 2024 22:42:38 -0700
Organization: A noiseless patient Spider
Lines: 127
Message-ID: <v6d9sf$79kv$1@dont-email.me>
References: <v4q168$sgqr$1@dont-email.me> <v4qgiu$ve3b$1@dont-email.me>
 <v4qrkr$157vp$1@dont-email.me> <v6cf9l$3vtoo$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 07 Jul 2024 07:42:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="cf7c2fa96044547c90e4fddda328c141";
	logging-data="239263"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18kYQjE93Fs6RQCbNpOZd9HBT2jLlHYn5E="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:/yN3WPyses/ZWSqk81sFHC3gehI=
Content-Language: en-US
In-Reply-To: <v6cf9l$3vtoo$1@dont-email.me>
Bytes: 7721

On 7/6/2024 3:08 PM, James Waldby wrote:
> 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


menomini + minidisc +

        ( discover overhang hangover overhung hungover overtake
          takeover overturn turnover overacts )


> 
> 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


my PC is slow... but i got curious... (about 6-letter/3-overlap)

.........,  massig,signal,nalfon, +

.........,  reshun,hungry,gryfon, +

   95  ( fondak, dakota, otakus, kuskus, kussos, sossed, sedate, ateles, 
lesses, sestet, tethys, hyssop, sophia, hiatus, tuscan, canell, ellops, 
opsins, insoul, oulder, dermol, molten, tenure, uretal, talpas, passes, 
seskin, kindie, dietal, tallis, lisbon, bonagh, aghast, astony, onymal, 
malice, icecap, caplin, lingas, gassit, situps, upsend, endore, oregon, 
gonads, adsorb, orbits, itself, elfish, ishtar, tarpot, potboy, boyaux, 
auxins, inship, hippus, pusley, leymus, muslin, linsey, seyens, ensure, 
uredia, diamat, matlos, losels, elsins, insunk, unkill, illing, ingoes, 
oesogi, ogived, vedism, ismdom, domett, ettles, lessee, seeing, ingans, 
anshar, hardim, dimply, plying, inglut, lutzes, zester, ternar, narica, 
icarus, rushes, hestia, tiamat, mating, ingots )



i think... A long (straight)  chain  like this (below) is harder to find
(no dict for them)

    Survey -
    Monkey - Business - Casual - Sex - Work - Visa - Card - Shark - Tank
    - Top - Secret - Agent - Orange - Julius - Caesar - Salad - Dressing