Deutsch English Français Italiano |
<v6cf9l$3vtoo$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!2.eu.feeder.erje.net!feeder.erje.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: Sat, 6 Jul 2024 22:08:53 -0000 (UTC) Organization: A noiseless patient Spider Lines: 86 Message-ID: <v6cf9l$3vtoo$1@dont-email.me> References: <v4q168$sgqr$1@dont-email.me> <v4qgiu$ve3b$1@dont-email.me> <v4qrkr$157vp$1@dont-email.me> Injection-Date: Sun, 07 Jul 2024 00:08:54 +0200 (CEST) Injection-Info: dont-email.me; posting-host="a8acc4ea2f043903feac0994c81a6548"; logging-data="4192024"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/KZ4/zQ2usyjyP7Dg7XRuC" User-Agent: tin/2.6.2-20220130 ("Convalmore") (Linux/5.15.0-107-generic (x86_64)) Cancel-Lock: sha1:7cm4TxNNrm9piyUru7i6JtE/VLA= Bytes: 6021 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