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)?
in Mathematica, it's easy to find THE Longest chain?
is this 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.
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.
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)
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
On 7/6/2024 3:08 PM, James Waldby wrote:...
...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
...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
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
In sci.math HenHanna <HenHanna@devnull.tb> wrote:
On 7/6/2024 3:08 PM, James Waldby wrote:...
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
...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
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 )
Do you have a link to the dictionary you're using? Among the first 17
words (for example) of that sequence, only sedate and hiatus are in
linux's /usr/share/dict/american-english file.
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
I think the basics of the problem are not more difficult, if a
dictionary of collocations were to be found. I don't know of a free
one, or whether the following would be accessible if paid for. https://www.oxfordlearnersdictionaries.com/us/definition/collocations
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 546 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 03:09:00 |
| Calls: | 10,386 |
| Calls today: | 1 |
| Files: | 14,057 |
| Messages: | 6,416,595 |