Wyzwanie polega na znalezieniu najdłuższego łańcucha angielskich słów, w którym pierwsze 3 znaki następnego słowa pasują do ostatnich 3 znaków ostatniego słowa. Użyjesz wspólnego słownika dostępnego w dystrybucjach Linuksa, który można pobrać tutaj:

https://www.dropbox.com/s/8tyzf94ps37tzp7/words?dl=0

który zawiera 99171 angielskich słów. Jeśli twój lokalny Linux /usr/share/dict/wordsto ten sam plik (ma md5sum == cbbcded3dc3b61ad50c4e36f79c37084), możesz tego użyć.

Słowa mogą być użyte tylko raz w odpowiedzi.

EDYCJA: Litery muszą być dokładnie takie same, jak duże / małe litery, apostrofy i akcenty.

Przykład prawidłowej odpowiedzi to: idea deadpan panoramic micra craftsman mantra traffic fiche która uzyska 8 punktów.

Odpowiedź z najdłuższym prawidłowym łańcuchem słów zostanie zwycięzcą. W przypadku remisu wygra najwcześniejsza odpowiedź. Twoja odpowiedź powinna zawierać listę znalezionych słów i (oczywiście) program, który napisałeś, aby to zrobić.

Java, heurystyka faworyzująca wierzchołek, który wywołuje największy wykres: 1825 1855 1873

Poniższy kod działa w niecałe 10 minut i znajduje następującą ścieżkę:

[wad, wadis, dis, dismay, may, mayfly, flywheels, elsewhere, erecting, ingratiate, ateliers, ersatzes, zest, esthetic, tickled, ledger, germicide, idealizes, zestful, fulling, ingrains, institute, uterine, ineptness, essaying, ingeniously, slyness, essences, cessations, onshore, ores, resoundingly, glycerine, inertness, essay, say, saying, ingenuous, ousted, tediously, sly, slyest, estrogen, genuflecting, ingestion, ionizer, zeros, roses, sesames, mes, meshed, hedonist, isthmuses, sesame, amending, ingredient, entrapment, enthuses, session, ionosphere, erectness, essayist, isthmus, mustaches, hesitatingly, glycogen, generation, ions, onset, settable, blew, lewder, deriding, ingratiates, testicles, lessen, sensitization, ionization, ionizing, ingratiating, ingenious, ouster, terrorizing, ingest, estranges, gesticulating, ingrates, testis, tissue, sue, suede, edelweiss, issuing, ingraining, ingrown, owner, nerdiest, estimation, ionospheres, rescue, cue, cueing, ingesting, ingot, got, gotten, tensor, sorrowing, ingratiated, tedious, ousting, ingratiatingly, glycerin, ringside, identifiable, bleariest, ester, terminological, calibrator, torrent, entraps, apse, pseudonym, nymphomania, niacin, cinema, emailed, led, ledges, gesticulates, testicle, clement, entail, ail, ailment, enter, terrains, inspires, restaurateur, euros, rosiest, estimates, tester, termite, iterator, torture, urethras, raspiest, estimator, tore, oregano, anointment, enthuse, useful, fulfil, filmstrip, riposte, stereotyped, pedicure, urea, readmits, itself, elf, elfin, finagles, lesbians, answerable, bleat, eatery, erythrocytes, testosterone, one, ones, nest, esteemed, medicine, inextricable, blessed, sediment, entry, try, tryout, outsources, cesarians, answered, redressed, seducer, cervical, calumniates, test, establishment, entombment, enthusiastic, tickles, lessens, ensemble, blemishes, hesitant, antic, tick, ickiest, estimable, blemished, hedgehog, hogan, gantlet, letdown, own, ownership, hippest, estates, testates, testiest, establishes, hes, hesitates, testable, bleakest, esthetes, testament, entice, iceberg, erg, ergonomic, microscope, operatives, vestibules, lesser, serenade, adenoidal, dales, lest, estrangement, entrap, raptures, resourceful, fulsome, omen, menswear, earthliest, established, hedges, gestates, testy, styes, yeshivot, voter, terrible, blender, derides, descent, enticed, cedillas, lass, assailable, bleacher, hermit, mite, item, temperas, rash, ashtray, rayon, yonder, dermis, mismanage, agendas, dash, ashy, shy, shyster, terrapins, insatiable, bleeder, derives, vestment, entangle, glen, lengthens, ensconced, ceded, deduced, cedars, arsenic, nice, ice, iced, cedar, daredevil, villa, llamas, masseuse, use, useable, bleach, achievable, bleached, hedonistic, tic, ticker, kerchieves, vessel, sell, ell, elliptic, ticket, kettles, lessee, seeps, epsilon, longboat, oath, atherosclerosis, sisterhood, oodles, lesson, sonatas, tassel, selvage, age, agent, entranced, cedes, descender, deranges, gestures, restraint, interment, enthused, seduced, cedilla, llama, amalgam, gamut, mutable, blend, endear, earthy, thymus, mussel, seltzer, zero, erodes, despot, potful, fulfillment, enthrall, allot, lotus, tussle, sledgehammered, redolent, entrapped, pedestal, talk, alkalis, listen, tended, deductible, bleeped, pedigree, reentered, redistribute, uterus, rustproofed, fed, fedora, oranges, gesundheit, either, herdsman, manes, nestles, lessor, sorrowful, fullback, acknowledges, gestured, redoubtable, blended, deduces, cesareans, answer, werewolves, vesper, perseveres, restructures, reside, ideogram, rammed, meddlesome, omens, ensign, ignores, restrains, insolent, entanglement, entrenchment, enticement, entomological, calligraphy, physical, calico, iconoclast, astringent, entertainment, entrant, antennas, nasty, stymie, miens, enslave, averred, redefine, inexorable, blenched, hedgerow, rowboat, oat, oaten, tend, endears, arson, songwriter, terminable, blent, entreaty, atypical, calypso, psoriasis, sister, term, ermine, ineligible, bleaker, kerosene, enema, emancipator, tormentor, torrider, derailment, entertains, instil, tildes, destine, inelegant, anthropomorphic, hiccup, cupolas, lastingly, glycerol, rollback, acknowledgment, entombed, bedridden, denser, servicewomen, menopause, used, sedatives, vesicle, clearinghouse, user, servant, antipodes, descry, crystalline, inexpedient, enthusiast, astonishment, entirety, etymological, calendared, redbreast, astronomer, merinos, nosedove, overpay, pay, paymaster, termagant, antiaircraft, aftercare, ares, resentful, fulcrum, rumpus, pushcart, artiste, stethoscopes, pesetas, taste, steadfast, astride, ides, destitute, utensil, silvan, vanguard, ardent, entryway, waysides, despair, airdrop, ropes, pestered, redder, derangement, entered, redeemed, medullas, lasagnas, nasal, salsas, sashay, hay, haymow, mow, mowed, wedder, derringer, germane, anemic, microfilmed, media, diatom, tomboys, oyster, terminator, toreador, dorsal, salespeople, pleased, sedater, terabit, bitten, tentacle, clergyman, manifesto, stomach, achoo, hoopla, plaza, azalea, leaven, vendor, dormant, antiparticle, cleared, redraft, afterword, ordains, insufficient, entitlement, entomb, ombudsmen, men, mental, tallyhos, hospice, icecap, cape, aperitif, tiffed, fedoras, rasped, pediatric, rickshaw, hawker, keratin, tinctures, reset, setback, acknowledgement, enthronement, entwine, inexact, actor, torpedos, dosed, sedan, dancer, cerebrum, rumple, plea, leach, ache, cheaper, per, periscopes, pestilent, entreat, eater, terser, serape, ape, apes, pesky, skycap, capped, pederast, astuter, terrace, acetaminophen, henchmen, menopausal, saltcellar, lard, ardor, dormice, icebound, underbrush, ushered, redrew, rewound, underclass, assassin, sinew, newscast, astrologer, gerund, undertaken, ken, kens, ensnared, redcap, cappuccinos, nostrum, rum, rumored, redraw, rawhide, identical, calcine, inertia, tiara, arabesque, queerer, reruns, unsold, oldie, diesel, selectmen, mentored, redden, dental, talon, longhand, and, androgen, genome, omelet, lethal, hallucinogenic, nickname, amen, menhaden, denudes, despaired, redevelop, lope, operas, rasp, aspired, redskin, kindergartens, ensnares, resultant, anthropological, callus, lustful, fulcra, crammed, mediocre, crepes, pesticide, ideas, eastbound, under, derrières, respired, rediscovered, redundant, antihero, erode, ode, odes, described, bedevil, villager, gerrymander, deride, ideograph, aphid, hid, hides, describes, besides, despoil, oilskin, kingdom, dominant, ant, antipasti, stiffens, ensured, redeemer, merchant, antiwar, warped, pederasty, stylus, lush, usher, her, hereafter, terrapin, pinnacle, clerical, caliber, bereave, avenger, geriatric, rickshas, haste, stereoscopes, pester, termini, initiator, tortures, restorer, reran, ransomed, medulla, llanos, nostril, rill, illogical, calif, lifer, fervor, vortex, textures, resister, termed, medieval, valor, lord, ordered, rediscover, verbatim, times, mesdames, mescal, caliper, periscope, opera, erasures, restart, artichokes, kestrel, reliant, antebellum, lumbago, agog, goggle, gleeful, fulfill, illustrator, tor, torque, questionnaires, resumed, mediator, tort, orthodoxy, oxymora, oratorio, riot, iotas, taster, terrific, fiche, checkpoint, interloper, perfumes, mesas, sassafras, rasher, heraldry, drywall, all, allergens, ensnare, area, rearm, armchair, airman, manufactures, resurface, acerbic, bicycle, cleverer, rerun, runt, untidy, idyllic, lichens, ensures, resend, endemic, microchip, hippopotamus, muscatel, telecast, astronaut, autopilot, lot, loth, other, heros, rosin, single, gleamed, mediaeval, valet, lettered, redound, underside, ideological, calliper, perihelia, liaison, sonic, nicknames, messenger, germicides, descendant, antigen, genital, tall, allergen, gentleman, mangos, gossipped, pedicures, resistant, antlered, redeveloped, pedagogical, calligrapher, heroins, inside, idea, deafen, fen, fencer, cerebra, bravuras, rascal, calculus, lusher, herbivores, resins, instill, illicit, citric, ricochet, heterodoxy, oxygen, generic, rice, icebox, box, boxcar, cartography, physique, quell, ellipsis, sis, sisal, sallow, lowbrow, rowel, well, elliptical, calf, alfresco, scow, cow, cowboy, boy, boyfriend, end, endeared, red, redesign, ignoramus, musket, kettledrum, rump, umped, pedlar, larvas, vassal, salmonellas, last, astronomical, calfskin, kingfisher, hereupon, ponchos, hospital, talisman, mantel, telethon, honcho, chomped, pedant, antitoxins, instant, antipastos, tossup, superintend, endangered, redskins, instigator, torpor, portico, icon, conquistador, dormer, merganser, seraphic, hiccuped, pedagogue, guerrillas, laser, sera, eraser, seraph, aphasic, sickbed, bed, bedsores, resign, ignorant, anthropocentric, richer, herdsmen, menu, enures, resuscitator, tornado, ado, adobe, obeisant, anthill, illegal, gallon, longshoremen, menace, ace, acetylene, enemas, mas, mascot, cot, cotton, tonsures, restores, result, ultraviolet, letterbox, boxer, xerography, physiological, calmer, merchantmen, mentor, torus, russet, settee, teenager, gerbil, billfold, old, olden, denatures, resubmit, mitten, ten, tenon, nonchalant, antique, queasy, asymmetric, ricksha, shanghai, haircut, cutups, upsides, descriptor, torpid, pidgin, gins, instep, tepee, peeper, perturb, urbane, anemia, miasmas, mascaras, raspy, spy, spyglass, assures, resonator, tortilla, llano, anon, nontechnical, calabash, ashram, rampart, arthropod, podia, diagram, ramp, amp, amphitheatres, resistor, tortillas, lasagna, gnat, natal, talc, alcoholic, licensee, seemed, medical, calm, almanac, nacho, choreography, phylum, lumbar, barman, mannequins, insures, respires, resound, underarm, armatures, resides, desideratum, tumult, ultrasound, underdog, dogcatcher, herald, alderwoman, mandarins, insecticides, desires, respirator, torrid, rid, rides, descant, anticlimax, maximum, mum, mummer, meringue, guesser, sermon, monogram, ramrod, rodeo, deodorant, antelopes, peso, esophagus, gusset, setups, upshot, hotel, telescope, open, penicillin, lingos, gossip, sip, siphon, honor, normal, maltreat, eaten, tenet, nether, herpes, pesticides, descend, endow, downfall, alleyway, way, waylay, layman, manicures, reshuffle, flea, lea, leash, ashen, henchman, mandolin, linchpins, inscribes, bestow, townspeople, plectrum, rumbas, baste, sternum, numb, umbilici, icicle, cleaver, vertebra, brains, insouciant, antidepressant, anthem, hemoglobin, binocular, largos, gossamer, mermaid, aid, aides, desperado, adopt, opt, optima, imam, mambos, bosun, sun, sunspot, potpourris, risky, sky, skyscraper, perturbed, bedraggle, glee, lee, leech, echo, choreographer, heraldic, dictum, tumid, midday, day, daybed, bedsides, desktop, topknot, notepaper, periodical, calendar, dare, areas, easel, selfsame, amebas, basins, ins, insulin, linnet, nettlesome, omegas, gasp, aspartame, amend, endures, researcher, herbal, balsas, sass, assault, ultimatum, tumor, mortgagor, gores, resort, orthopaedic, dictatorship, hipper, person, sonar, narc, arc, archduke, ukelele, elegant, anther, hereabout, outfox, fox, foxtrot, rotogravures, restaurant, antechamber, beret, retriever, verbena, enamor, morsel, sellout, outmaneuver, vertical, call, allergenic, niche, chessman, mandolins, insipid, pidgins, install, allures, rescind, indignant, antithetical, calicos, cosmonaut, auto, utopia, piano, another, heretical, calk, alkali, alibi, ibis, bistro, troupe, upend, endorser, serviceman, mandarin, rind, inductee, teepee, pee, peekaboo, bootstrap, rape, apertures, resin, singular, larval, valiant, antiperspirant, antipasto, stop, topical, calisthenic, nicer, cervix, vixen, xenophobic, bicep, cephalic, licit, citizenship, hippopotami, amigos, gospel, pellet, letups, upstart, artificer, cerebellum, lumberman, manic, nicknamed, medic, dickie, kielbasas, sash, ash, ashcan, cannon, nonskid, kid, kidnaper, perjures, resolver, vernacular, larkspur, puree, reefer, ferret, retains, insofar, far, fart, artisan, sandbag, bagel, gelatin, tinsel, selectman, manacle, clever, versus, sustains, inscribed, bedpan, pandemic, microprocessor, sorbet, bet, betcha, char, harem, remodel, deli, elicit, citadel, deliver, verandas, dashikis, kisser, servicemen, menthol, holiday, daydreamer, merchantman, manikins, insane, anew, newsprint, interwove, overreach, achieve, even, venom, nomad, mad, madrigal, gala, alarm, armpit, pitchman, manor, northbound, underbid, bidet, detox, toxemia, miasma, smarten, tenderloins, insult, ultra, travel, velvet, veteran, random, domino, inopportune, uneconomic, microbes, bestir, tiro, ironware, arena, enamel, melodramas, mastodon, don, donut, nut, nutmeg, meg, megalopolis, lissom, sombre, breathe, therefrom, romper, performer, merman, mangrove, overshadow, downcast, astir, tiros, rostra, trachea, heaven, ventricle, clergywoman, maneuver, verbal, ballad, ladyship, hippie, pie, piebald, alderman, manatee, teethe, thereupon, poncho, choicer, ceramic, microscopic, picayune, uneaten, tendon, donor, northeast, astound, underpass, assessor, sorghum, hum, human, mantra, trainee, needlepoint, interplay, laywoman, mannikin, kinsman, mantillas, lassie, sieve, ever, verdigris, risen, sensor, sorrel, relabel, belabor, borsch, schlep, leprechauns, unsnap, nap, napkin, kin, kingpin, pinkeye, eyeglass, assemblyman, manikin, kingship, hip, hippos, postpartum, tumbrel, relic, lichee, heehaw, haw, hawser, servicewoman, many, anyhow, howsoever, vertex, text, extra, trap, rap, rapper, periwig, wigwag, wag, wagon, gonorrhea, heave, aver, vermin, minesweeper, perplex, lexicon, congas, gastronomic, microfiche, cheapen, pentathlon, longhair, air, aircraft, aft, aftertaste, stem, tempos, postwar, war, wart, article, clear, earshot, hotshot, hotbed, bedlam, lam, lambkin, kindergarten, tenser, serum, rumor, mortar, tarmac, macabre, breech, echos, hostel, telescopic, pickerel, relay, laypeople, pleas, east, astronomic, micra, crackpot, pot, potato, atom, tombed, bedbug, bugaboo, bootleg, leg, legato, atop, topple, plethora, orangutang, angora, orangutan, tan, tandem, democrat, rat, rattan, tang, angry, gryphon, honeybee, bee, beeswax, waxen, xenon, nonplus, lustre, trellis, lisle, sleepwear, earwig, wig, wigwam, wampum, pummel, melanomas, massacre, cretin, tin, tint, interviewee, wee, weeper, persimmon, monsignori, origin, gingham, ham, hamper, pericardia, diarrhea, heartthrob, rob, robes, besom, sombreros, rosebud, bud, budgerigar, garret, retrodden, denim, nimbus, bus, bushel, helmet, metaphor, horsefly, flypaper, peritonea, near, ear, earlobes, bestowal, wall, allay, layout, outlast, astrakhan, handicapper, perusal, saltpetre, tremor, moribund, undercut, cut, cutoff, off, offal, falcon, con, consul, sultan, tannin, ninepin, pinball, allegro, grommet, metro, trot, rot, rotten, tenpin, pineapple, plectra, transit, sitar, tar, taro, arousal, salmon, moneybag, bagpipe, ipecac, cache, checkout, outrun, runaround, undersea, sea, sear, earache, cherub, rub, rubicund, underpin, pin, pint, intagli, glib, lib, libel, bellyache, cherubim, bimbos, bosuns, unsound, undertow, tow, towel, wellington, ton, tonsil, silicon, concoct, octet, tetrahedra, drachmae, maestri, tripos, possum, sum, sumac, macro, crocus, custom, tom, tomcat, catsup, sup, superstar, tarpaulin, linchpin, pinpoint, intercom, comet, met, metacarpus, pussycat, catastrophe, phenomenon, nonverbal, ballpoint, interurban, bani, animal, malt, altar, tartar, tarot, rotund, undergrad, radio, diocesan, sandbar, bar, barren, renewal, walkout, outstrip, ripen, pen, pencil, cilantro, trout, outran, rancor, corncob, cob, cobra, bra, brag, rag, ragas, gas, gasohol, holdout, output, put, putsch, schwas, was, waste, stereo, reoccur, cur, curb, urban, ban, bantam, tam, tamp, ampul, pullout, outwit, wit, withal, halo, alohas, hasp, asparagus, gusto, stove, overlap, lapel, pelvis, visit, sit, sitcom, compendia, diadem, demigod, god, goddam, dam, dampen, pennon, non, noncom, compel, pelican, cancan, can, cancel, celesta, starlit, lit, litmus, muscat, cat, catnap, naphtha, than, handcar, carpel, pellagra, grammar, mar, mariachi, chichi, chi, chimp, imp, impel, pelvic, vicar, car, caribou, bourgeoisie, siesta, stab, tab, tabu, abut, but, butterfat, fat, fathom, homespun, pun, puns, unsheathe, the, theorem, remove, overtax, tax, taxicab, cab, cabal, balsam, sambas, basal, salamis, missal, salt, altho, tho, thou, housebound, underground, underclassman, man, mannikins, insectivores, resonant, antelope, operator, torn, ornamental, tallow, low, lowered, reddens, enshrine, inefficient, entertainer, nerves, vestiges, gesturing, ingested, tediousness, essentials]

Podstawowe pomysły

W przybliżeniu najdłuższych kierowanych ścieżek i cykli , Bjorklund, Husfeldt i Khanna, Lecture Notes in Computer Science (2004), 222-233, autorzy sugerują, że na rzadkich wykresach ekspanderów można znaleźć długą ścieżkę poprzez chciwe wyszukiwanie, które wybiera się przy każdym przesuń sąsiada bieżącego ogona ścieżki, który obejmuje największy podgraph w G ', gdzie G' jest oryginalnym wykresem z usuniętymi wierzchołkami w bieżącej ścieżce. Nie jestem pewien, czy jest dobry sposób na sprawdzenie, czy wykres jest wykresem ekspandera, ale z pewnością mamy do czynienia z wykresem rzadkim, a ponieważ jego rdzeń ma około 20000 wierzchołków i ma średnicę tylko 15, musi mieć dobry właściwości ekspansyjne. Przyjmuję więc tę chciwą heurystykę.

Na podstawie wykresu G(V, E)możemy ustalić, ile wierzchołków jest osiągalnych z każdego wierzchołka za pomocą Floyd-Warshall w Theta(V^3)czasie lub za pomocą algorytmu Johnsona w Theta(V^2 lg V + VE)czasie. Wiem jednak, że mamy do czynienia z wykresem, który ma bardzo duży silnie połączony komponent (SCC), więc podchodzę do innego podejścia. Jeśli zidentyfikujemy SCC za pomocą algorytmu Tarjana, otrzymamy również sortowanie topologiczne skompresowanego wykresu G_c(V_c, E_c), który z O(E)czasem będzie znacznie mniejszy . Ponieważ G_cjest to DAG, możemy obliczyć osiągalność G_cna O(V_c^2 + E_c)czas. (Następnie odkryłem, że jest to wskazane w ćwiczeniu 26-2.8 CLR ).

Ponieważ dominującym czynnikiem w czasie wykonywania jest E, optymalizuję go, wstawiając atrapy węzłów dla prefiksów / sufiksów. Więc zamiast 151 * 64 = 9664 krawędzie od słów kończących -res słów zaczynając li- mam 151 krawędzie od słów kończących -res do # # res i 64 krawędzi z # # res na słowa zaczynające się na li- .

Wreszcie, ponieważ każde wyszukiwanie zajmuje około 4 minut na starym komputerze, staram się łączyć wyniki z poprzednimi długimi ścieżkami. Jest to o wiele szybsze i znalazłem moje najlepsze najlepsze rozwiązanie.

Kod

org/cheddarmonk/math/graph/Graph.java:

package org.cheddarmonk.math.graph;

import java.util.Set;

public interface Graph<V> {
    public Set<V> getAdjacent(V node);
    public double getWeight(V from, V to);
}

org/cheddarmonk/math/graph/MutableGraph.java:

package org.cheddarmonk.math.graph;

import java.util.*;

public class MutableGraph<V> implements Graph<V> {
    private Map<V, Map<V, Double>> edgesBySource = new HashMap<V, Map<V, Double>>();

    public void addEdge(V from, V to, double weight) {
        if (!edgesBySource.containsKey(to)) edgesBySource.put(to, new HashMap<V, Double>());
        Map<V, Double> e = edgesBySource.get(from);
        if (e == null) edgesBySource.put(from, e = new HashMap<V, Double>());
        if (e.containsKey(to)) throw new IllegalArgumentException("There is already an edge between the vertices");
        e.put(to, weight);
    }

    @Override
    public Set<V> getAdjacent(V node) {
        Map<V, Double> e = edgesBySource.get(node);
        if (e == null) throw new IllegalArgumentException("node doesn't appear to be in the graph");
        return Collections.unmodifiableSet(e.keySet());
    }

    @Override
    public double getWeight(V from, V to) {
        Map<V, Double> e = edgesBySource.get(from);
        if (e == null) throw new IllegalArgumentException("from doesn't appear to be in the graph");
        if (!edgesBySource.containsKey(to)) throw new IllegalArgumentException("to doesn't appear to be in the graph");

        Double c = e.get(to);
        return c == null ? 0 : c.doubleValue();
    }
}

org/cheddarmonk/math/graph/StronglyConnectedComponents.java:

package org.cheddarmonk.math.graph;

import java.util.*;

/**
* A helper class for finding the strongly connected components of a graph using Tarjan's algorithm.
* http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
*/
public class StronglyConnectedComponents<V> {
    private final Graph<V> g;
    private List<Set<V>> topologicallySortedSccs = new ArrayList<Set<V>>();

    private final LinkedList<V> S = new LinkedList<V>();
    private final Set<V> S2 = new HashSet<V>();
    private final Map<V, Integer> index = new HashMap<V, Integer>();
    private final Map<V, Integer> lowlink = new HashMap<V, Integer>();

    private StronglyConnectedComponents(Graph<V> g) {
        this.g = g;
    }

    private void strongConnect(V v) {
        int idx = index.size();
        index.put(v, idx);
        lowlink.put(v, idx);

        S.push(v);
        S2.add(v);

        for (V w : g.getAdjacent(v)) {
            if (!index.containsKey(w)) {
                strongConnect(w);
                if (lowlink.get(w) < lowlink.get(v)) {
                    lowlink.put(v, lowlink.get(w));
                }
            }
            else if (S2.contains(w)) {
                if (index.get(w) < lowlink.get(v)) {
                    lowlink.put(v, index.get(w));
                }
            }
        }

        if (lowlink.get(v).equals(index.get(v))) {
            Set<V> scc = new HashSet<V>();
            V w;
            do {
                w = S.pop();
                S2.remove(w);
                scc.add(w);
            } while (!w.equals(v));

            topologicallySortedSccs.add(scc);
        }
    }

    public static <V> List<Set<V>> analyse(Graph<V> g, Set<V> sources) {
        if (g == null) throw new IllegalArgumentException("g");

        StronglyConnectedComponents<V> scc = new StronglyConnectedComponents<V>(g);
        for (V v : sources) {
            if (!scc.index.containsKey(v)) {
                scc.strongConnect(v);
            }
        }

        return scc.topologicallySortedSccs;
    }
}

org/cheddarmonk/ppcg/PPCG.java:

package org.cheddarmonk.ppcg;

import java.io.*;
import java.util.*;
import org.cheddarmonk.math.graph.*;

public class PPCG44922 {
    private static final String path = "/usr/share/dict/words";
    private static Set<String> allWords;
    private static Graph<String> fullGraph;

    public static void main(String[] args) {
        loadGraph();

        Random rnd = new Random();
        rnd.setSeed(8104951619088972997L);
        List<String> a = search(rnd);
        rnd.setSeed(-265860022884114241L);
        List<String> b = search(rnd);
        List<String> chain = spliceChains(a, b);
        System.out.println(chain.size());
        System.out.println(chain);
    }

    private static List<String> search(Random rnd) {
        List<String> chain = new ArrayList<String>();
        chain.add(selectOptimalReachabilityCount(fullGraph, allWords, rnd));
        while (true) {
            String tail = chain.get(chain.size() - 1);
            FilteredGraph g = new FilteredGraph(chain);

            // We know that tail only has one successor, so skip ahead.
            Set<String> candidates = new HashSet<String>(fullGraph.getAdjacent(suffix(tail)));
            candidates.removeAll(chain);
            if (candidates.isEmpty()) break;

            chain.add(selectOptimalReachabilityCount(g, candidates, rnd));
        }

        Iterator<String> it = chain.iterator();
        while (it.hasNext()) {
            if (it.next().charAt(0) == '#') it.remove();
        }
        return chain;
    }

    private static List<String> spliceChains(List<String> a, List<String> b) {
        Set<String> intersect = new HashSet<String>(b);
        intersect.retainAll(a);
        if (intersect.isEmpty()) return null;

        // Splice the longest bits. To avoid cycles, we look for intersection points which have the same set of reached intersection points.
        // Thus to get from one to the next we can take either route without violating the unique occurrence of each element in the spliced chain.
        Set<String> left = new HashSet<String>();
        Set<String> right = new HashSet<String>();
        List<String> newChain = new ArrayList<String>();

        // NB We assume that either a(0) and b(0) are the same or neither is in intersect.
        // This is a safe assumption in practice because they're both "wad".
        int idxA = 0, idxB = 0, nextA = 0, nextB = 0;
        while (idxA < a.size()) {
            nextA++;
            while (nextA < a.size() && !intersect.contains(a.get(nextA))) nextA++;
            String tailA = nextA < a.size() ? a.get(nextA) : "";
            left.add(tailA);

            nextB++;
            while (nextB < b.size() && !intersect.contains(b.get(nextB))) nextB++;
            String tailB = nextB < b.size() ? b.get(nextB) : "";
            right.add(tailB);

            if (left.equals(right) && tailA.equals(tailB)) {
                // We take the longer of idxA to nextA-1 or idxB to nextB - 1.
                if (nextA - idxA > nextB - idxB) newChain.addAll(a.subList(idxA, nextA));
                else newChain.addAll(b.subList(idxB, nextB));

                idxA = nextA;
                idxB = nextB;
            }
        }

        if (new HashSet<String>(newChain).size() == newChain.size()) return newChain;
        throw new IllegalStateException();
    }

    private static void loadGraph() {
        Set<String> words = new HashSet<String>();
        Set<String> prefixes = new HashSet<String>();
        Set<String> suffixes = new HashSet<String>();
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path), "UTF-8"));
            String line;
            while ((line = br.readLine()) != null) {
                if (line.length() >= 3) {
                    words.add(line);
                    prefixes.add(prefix(line));
                    suffixes.add(suffix(line));
                }
            }
            br.close();
        }
        catch (IOException ioe) {
            throw new RuntimeException(ioe);
        }

        // Filter down to a core with decent reachability.
        prefixes.retainAll(suffixes);
        MutableGraph<String> g = new MutableGraph<String>();
        Iterator<String> it = words.iterator();
        while (it.hasNext()) {
            String line = it.next();
            if (prefixes.contains(prefix(line)) && prefixes.contains(suffix(line))) {
                // In the interests of keeping the number of edges down, I insert fake vertices.
                g.addEdge(prefix(line), line, 1);
                g.addEdge(line, suffix(line), 1);
            }
            else it.remove();
        }

        fullGraph = g;
        allWords = Collections.unmodifiableSet(words);
    }

    private static String prefix(String word) {
        return "#" + word.substring(0, 3) + "#";
    }

    private static String suffix(String word) {
        return "#" + word.substring(word.length() - 3, word.length()) + "#";
    }

    private static <V> Map<V, Integer> reachabilityCount(Graph<V> g, Set<V> sources) {
        List<Set<V>> sccs = StronglyConnectedComponents.analyse(g, sources);
        int n = sccs.size();

        // Within a strongly connected component, each vertex can reach each other vertex.
        // Then we need to also take into account the other SCCs which they can reach.
        // We can exploit the fact that we already have a topological sort of the DAG of SCCs to do this efficiently.
        Map<V, Integer> index = new HashMap<V, Integer>();
        for (int i = 0; i < n; i++) {
            for (V v : sccs.get(i)) index.put(v, i);
        }

        BitSet[] reachableSccs = new BitSet[n];
        Map<V, Integer> reachabilityCounts = new HashMap<V, Integer>();
        for (int i = 0; i < n; i++) {
            Set<V> scc = sccs.get(i);
            reachableSccs[i] = new BitSet(n);
            reachableSccs[i].set(i);
            for (V v : scc) {
                for (V w : g.getAdjacent(v)) {
                    int j = index.get(w);
                    if (j < i) reachableSccs[i].or(reachableSccs[j]);
                }
            }

            int count = 0;
            for (int j = reachableSccs[i].nextSetBit(0); j >= 0; j = reachableSccs[i].nextSetBit(j+1)) {
                count += sccs.get(j).size();
            }
            for (V v : scc) {
                reachabilityCounts.put(v, count);
            }
        }

        return reachabilityCounts;
    }

    private static <V extends Comparable<? super V>> V selectOptimalReachabilityCount(Graph<V> g, Set<V> candidates, Random rnd) {
        Map<V, Integer> r = reachabilityCount(g, candidates);

        int max = 0;
        List<V> attaining = new ArrayList<V>();
        for (V candidate : candidates) {
            int score = r.get(candidate);
            if (score > max) {
                max = score;
                attaining.clear();
            }
            if (score == max) attaining.add(candidate);
        }

        return selectRandom(attaining, rnd);
    }

    private static <T extends Comparable<? super T>> T selectRandom(Collection<T> elts, Random rnd) {
        List<T> deterministic = new ArrayList<T>(elts);
        Collections.sort(deterministic);
        Collections.shuffle(deterministic, rnd);
        return deterministic.get(0);
    }

    private static class FilteredGraph implements Graph<String> {
        private final Set<String> filteredVertices;

        public FilteredGraph(Collection<String> filteredVertices) {
            this.filteredVertices = new HashSet<String>(filteredVertices);
        }

        @Override
        public Set<String> getAdjacent(String node) {
            if (filteredVertices.contains(node)) return Collections.emptySet();

            Set<String> adj = new HashSet<String>(fullGraph.getAdjacent(node));
            adj.removeAll(filteredVertices);
            return adj;
        }

        @Override
        public double getWeight(String from, String to) {
            throw new RuntimeException("Not used");
        }
    }
}

Ruby, 1701

"Del" -> "ersatz's" ( pełna sekwencja )

Próba znalezienia optymalnego rozwiązania okazała się zbyt kosztowna w czasie. Dlaczego więc nie wybierać losowych próbek, buforować, co możemy i mieć nadzieję na najlepsze?

Najpierw Hashbudowane jest a, które odwzorowuje prefiksy na pełne światy, zaczynając od tego prefiksu (np "the" => ["the", "them", "their", ...].). Następnie dla każdego słowa na liście sequencewywoływana jest metoda . Pobiera słowa, które mogą wynikać z Hash, pobiera próbkę 100i nazywa się rekurencyjnie. Najdłużej jest zajęty i dumnie pokazany. Ziarno dla RNG (Random::DEFAULT ) i długość sekwencji.

Musiałem uruchomić program kilka razy, aby uzyskać dobry wynik. Ten konkretny wynik został wygenerowany z nasionem328678850348335483228838046308296635426328678850348335483228838046308296635426 .

Scenariusz

require "json"

def prefix(word); word[0, 3];  end
def suffix(word); word[-3, 3]; end

def sequence(word, prefixes, skip)
  if SUBS.key?(word) && (SUBS[word] - skip) == SUBS[word]
    return SUBS[word]
  end

  skip         += [word] 
  suffix        = suffix(word)
  possibilities = (prefixes[suffix] ||= []) - skip

  if possibilities.empty?
    return [word]
  else
    sequences = possibilities.sample(100).map do |possibility|
      sequence(possibility, prefixes, skip)
    end

    return SUBS[word] = [word] + sequences.max_by(&:size)
  end
end

def correct?(sequence)
  once_only = sequence.all? { |y| sequence.count(y) == 1 }
  following = sequence.each_cons(2).all? { |a,b| a[-3,3] == b[0,3] }

  return once_only && following
end

words = open("words.txt", "r", &:read).split.select { |word| word.size >= 3 }

SUBS     = {}
PREFIXES = {}

# Built a Hash that maps prefixes to an Array of words starting with the prefix.
words.each do |word|
  prefix = prefix(word)

  PREFIXES[prefix] ||= []
  PREFIXES[prefix] << word
end

longest = [1]

words.each do |word|
  PREFIXES[prefix(word)].delete(word)

  sequence = sequence(word, PREFIXES, [word])

  if sequence.size > longest.size
    longest = sequence
  end
end

puts longest.inspect
puts 
puts "Generated with seed: #{Random::DEFAULT.seed}"
puts "Length: #{longest.size}"
puts "Correct: #{correct?(longest)}"

Wynik: 1631 1662 słów

['Aachen', 'hen', 'henceforward', 'ardor', 'dorsal', 'salmon', 'monolog', 'log', 'logjam', 
'jam', 'jamb', 'ambassador', 'dormouse', 'useable', 'bleeding', 'ingenious', 'ouster', 
'terminable', 'bleakness', 'essay', 'say', 'saying', 'ingress', 'essences', 'cession', 
....
....
'ionosphere', 'ere', 'erecting', 'ingratiating', 'ingrate', 'ate', 'ateliers', "ersatz's"]

Całą sekwencję można znaleźć tutaj: http://pastebin.com/TfAvhP9X

Nie mam pełnego kodu źródłowego. Próbowałem różnych podejść. Ale oto kilka fragmentów kodu, które powinny być w stanie wygenerować sekwencję o tej samej długości. Przepraszam, to nie jest bardzo piękne.

Kod (Python):

Najpierw wstępne przetwarzanie danych.

from collections import defaultdict

with open('words') as f:
    words = [line.strip() for line in f]
words = [word for word in words if len(word)>=3 and word[-2:]!="'s"]

word_connections = defaultdict(list)
for word in words:
    word_connections[word[:3]].append(word)

Następnie zdefiniowałem funkcję rekurencyjną (pierwsze wyszukiwanie głębokości).

global m
m=0
def find_chain(chain):
    s = set(word_connections[chain[-1][-3:]])-set(chain)
    if len(s)== 0:
        global m
        if len(chain) > m:
            m=len(chain)
            print(len(chain), chain)
    else:
        for w in s:
            if w not in chain:
                find_chain(chain + [w])

for word in words:
    find_chain([word])

Oczywiście trwa to zbyt długo. Ale po pewnym czasie znalazła sekwencję z 1090 elementami i zatrzymałem się.

Następną rzeczą do zrobienia jest wyszukiwanie lokalne. Dla każdego z dwóch sąsiadów n1, n2 w sekwencji próbuję znaleźć sekwencję rozpoczynającą się od n1 i kończącą się na n2. Jeśli taka sekwencja istnieje, wstawiam ją.

def tryimpove(chain, length, startvalue=0):
    s=set(chain)
    for i in range(startvalue,len(chain)-1):
        print(i)
        for sub in sorted(short_sequences([chain[i]],length,chain[i+1]),key=len,reverse=True):

            if len(s & set(sub))==1:
                chain[i:i+1]=sub
                print(i,'improved:',len(chain))
                return tryimpove(chain,length,i)
    return chain

def short_sequences(chain,length,end):
    if 2 <= len(chain):
        if chain[-1][-3:]==end[:3]:
            yield chain
    if len(chain) < length:
        s = set(word_connections[chain[-1][-3:]])-set(chain)
        for w in s:
            for i in short_sequences(chain + [w],length,end):
                yield i

for m in range(5, 100):
    seq = tryimpove(seq,m)

Oczywiście musiałem ręcznie zatrzymać program.

PHP, 1742 1795

W tym bałaganie z PHP. Sztuką jest na pewno skasowanie listy do około 20 tysięcy, które są rzeczywiście ważne, i po prostu wyrzucenie reszty. Mój program robi to iteracyjnie (niektóre słowa, które wyrzuca w pierwszej iteracji, oznacza, że ​​inne nie są już ważne) na początku.

Mój kod jest okropny, używa wielu zmiennych globalnych, używa o wiele za dużo pamięci (zachowuje kopię całej tabeli prefiksów dla każdej iteracji) i dosłownie kilka dni zajęło mi wymyślenie moich najlepszych, ale nadal zarządza wygrywać - na razie. Zaczyna się dość szybko, ale z czasem staje się coraz wolniejszy.

<?php

  function show_list($list)
  {
      $st="";
      foreach ($list as $item => $blah)
      $st.="$item ";
      return rtrim($st);
  }

  function mysort($a,$b)
  {
      global $parts;
      $a_count=isset($parts[substr($a,-3,3)])?count($parts[substr($a,-3,3)]):0;
      $b_count=isset($parts[substr($b,-3,3)])?count($parts[substr($b,-3,3)]):0;
      return $b_count-$a_count;
  }  

  function recurse($line,$list,$parts)
  {
    global $lines; 
    global $max;
    global $finished;
    global $best;
    $end=substr($line,-3,3);
    $count=0;
    if ($finished)
        return;
    if (isset($parts[$end]))
    {
        $maxp=count($parts[$end])-1;
        if ($maxp<0)
            return;
        $randa=array();
        for ($a=1;$a<3;$a++)
        {
            $randa[mt_rand(0,$maxp)]=1;
        }
        $n=mt_rand(0,$maxp);

        foreach ($parts[$end] as $key => $endpart)
        {

            if (!isset($list[$endpart]))
            {
                $this_part=$parts[$end];
                unset($this_part[$key]);
                $new_parts=$parts;
                unset($new_parts[$end][$key]);
                $list[$endpart]=1;
                recurse($endpart,$list,$new_parts);
                unset($list[$endpart]);
            }
        }

    }
    $count=count($list);
    if ($count>$max)
    {
        //echo "current best: $count\n";
        file_put_contents('best.txt',show_list($list) . "\n",FILE_APPEND);
        $max=$count;
        $best=$list;
    }
  }

  function cull_lines(&$lines)
  {
      global $parts;
      do 
      {    
          $wordcount=count($lines);
          $parts=array();$end_parts=array();
          foreach ($lines as $line)
          {
              if (strlen($line)<3)
                continue;
              $parts[substr($line,0,3)][]=$line;
              if (strlen($line)>3)
                $end_parts[substr($line,-3,3)][]=$line;
          }
          foreach ($lines as $key => $line)
          {
              $end=substr($line,-3,3);
              if (strlen($line)<3 || !isset($parts[$end]) || !isset($end_parts[substr($line,0,3)] ) )
                unset($lines[$key]);
          }
          foreach ($parts as $part)
          {
            if (count($part)==1)
            {
                $source_part=mt_rand(0,count($part)-1);
                $this_part = substr($part[0],0,3);
                $this_min = 10000;
                $this_key = 0;
                if (strlen($part[$source_part])==3)
                {
                    foreach ($lines as $key => $line)
                    if ($line == $part[$source_part])
                    {
                            unset($lines[$key]);
                            break;
                    }
                }
                elseif (isset($end_parts[$this_part]))
                {
                    foreach ($end_parts[$this_part] as $key => $end_part)
                    {
                        if (isset($parts[substr($end_part,0,3)]))
                        {
                            $n=count($parts[substr($end_part,0,3)]);
                            if ($n<$this_min)
                            {
                                $this_min=$n;
                                $this_key=$key;    
                            }
                        }
                    }

                    foreach ($lines as $key => $line)
                    if ($line == $part[$source_part])
                    {
                            unset($lines[$key]);

                    }
                    elseif ($line == $end_parts[$this_part][$this_key])
                    {
                        $lines[$key].=' ' . $part[$source_part];
                    }
                }

            }
          }
          echo "$wordcount words left\n";
      }
      while ($wordcount!=count($lines));
  }

  ini_set('xdebug.max_nesting_level',10000);
  ini_set('memory_limit','1024M');
  $lines = explode("\n",file_get_contents('words.txt'));
  cull_lines($lines);
  $max=0;
  foreach ($parts as $key=>$part)
    usort($parts[$key],'mysort');    

  $n=count($lines);
  foreach ($lines as $rand => $blah)
  {
      if (mt_rand(0,$n)==1)
        break;
  }
  $rand=$lines[$rand];
  $line[$rand]=1;
  echo "Starting with $rand...\n";
  recurse($rand,$line,$parts);
  unset($line[$rand]);

?>

Oczywistą poprawą byłoby użycie sierocego słowa na początek i koniec.

W każdym razie, naprawdę nie wiem, dlaczego moja lista pastebin została przeniesiona do komentarza tutaj, wrócił jako link do pastebin, ponieważ teraz umieściłem mój kod.

http://pastebin.com/Mzs0XwjV

Python: 1702 - 1704 - 1733 słów

Użyłem Dict, aby zmapować wszystkie prefiksy na wszystkie słowa, as

{
    "AOL" : [
        "AOL", "AOL's"
    ],...
    "oct" : [
         "octet","octets","octette's"
    ],...
}

Edytuj małe ulepszenie: usuwając wszystkie uselesssłowa na początku, jeśli ich przyrostki nie znajdują się na liście prefiksów (oczywiście byłoby to słowo końcowe)

Następnie weź słowo z listy i przejrzyj mapę prefiksów jak węzeł drzewa

import sys, fileinput
def p(w):return w[:3]

class Computing:
    def __init__(_):
        _.wordData = []; _.prefixes = {}
        _.seq = []; _.bestAttempt = []
        _.stop = False
        for l in fileinput.input():
            word = l.strip()
            if len(word) > 2:_.wordData.append(_.addPfx(word, p(word)))
        _.rmUseless();_.rmUseless()
        _.fromI = 0; _.toI = len(_.wordData)

    def rmUseless(_):
        for w in _.wordData:
            if not w[-3:] in _.prefixes: _.wordData.remove(_.rmPfx(w,p(w)))

    def addPfx(_, w, px):
        if not px in _.prefixes:_.prefixes[px] = []
        _.prefixes[px].append(w)
        return w
    def rmPfx(_,w,px):
        _.prefixes[px].remove(w)
        if len(_.prefixes[px]) == 0:del _.prefixes[px];
        return w

    def findBestSequence(_):
        def pickItem():
            r = None
            if _.fromI < _.toI:r = _.wordData[_.toI-1];_.toI -= 1;
            return r
        while not _.stop:
            w = pickItem()
            if not w:break;
            _.seq = [_.rmPfx(w,p(w))]
            _.checkForNextWord()
            _.addPfx(w, p(w))

        print " ".join(_.bestAttempt)

    def checkForNextWord(_):
        _.stop = len(_.seq) >= 1733
        cw = _.seq[-1]
        if not _.stop:
            if cw[-3:] in _.prefixes:
                lW = []
                for word in _.prefixes[cw[-3:]]:
                    if not word[-3:] in lW:
                        _.seq.append(_.rmPfx(word,p(word)))
                        _.checkForNextWord()
                        if _.stop :break;
                        _.addPfx(_.seq.pop(), p(word))
                        lW.append(word[-3:])
                    if _.stop :break;
        if len(_.bestAttempt) < len(_.seq):_.bestAttempt = _.seq[:];

sys.setrecursionlimit(6000)
Computing().findBestSequence()

Program potrzebuje kilku słów, aby wiedzieć, kiedy zatrzymać, można znaleźć jak 1733w metodziecheckForNextWord̀

Program potrzebuje ścieżki pliku jako argumentu

Niezbyt pytoniczny, ale próbowałem.

Obliczenie tej sekwencji zajęło mniej niż 2 minuty: pełne wyjście :

études desalinate zjadł ateliers ... najbardziej szanuje pomysłowe ousters

Wynik: 249 500 1001

Akwizgran -> kura -> odtąd -> żarliwy -> entail -> ail -> ailed -> led -> ledger -> gerbil -> dwustronny -> rallying -> genialny - -> ousted -> nużący -> ouster -> terabit -> bit -> bitched -> jeż -> wieprz -> hogan -> gander -> derail -> lotki -> początek -> zestaw -> cofnięcie -> potwierdzenie -> pociągnięty -> księgi -> ersatzes -> skórka -> ustalony -> żywopłot -> rząd -> łódka -> owies - -> owies -> dziesięć -> trwały -> wybielacz -> ból -> taniej -> długopis -> karze -> podstępny -> fulcra -> krab -> rabiniczny -> tykwa -> jesion -> zawstydzony -> medal -> dale -> ale -> zaalarmowany -> nużąco -> przebiegły ->chytry -> ustanawia -> hes -> niezdecydowany -> mrówka -> środek zobojętniający kwasy -> cydr -> wykolejony -> półki -> gested -> żmudność -> esej -> powiedz - -> powiedzenie -> genialnie -> przebiegłość -> esej -> pomysłowy -> ousting -> pomysłowość -> eseista -> przesmyk -> muszkat -> kot -> kataklizm -> myszy -> lód -> góra lodowa -> erg -> ergonomia -> micra -> kraba -> łóżko -> bedazzles -> lesbijki -> odpowiedź -> były -> ere - -> wznoszenie -> spożycie -> ustanowienie -> spożycie -> spożycie -> jon -> jonizacja -> jonizator -> zero -> erodowanie -> oda -> ody -> odsalanie -> test -> zakład - -> pociągający -> wlewki -> dostał -> dostał ->najemca -> antagonista -> isthmuses -> sezam -> amebas -> basal -> salaamed -> medalion -> jonizujący -> wrastanie -> ingrains -> ins -> szalony - -> anegdotyczne -> talk -> alkohol -> trzymaj -> stare -> stare -> legowisko -> denaturacja -> mocznik -> zasięg -> obolały -> żywopłoty -> gestates -> testable -> bielone -> żywopłot - - ingrates -> testament -> splątanie -> lśniące -> medaliony -> onshore -> ruda -> oregano -> anody - -> odsalanie -> niewdzięczności -> testaty -> tester -> terabity -> jego -> sam -> elf -> elfin -> płetwa -> finagle -> lśniące -> ingratiating -> ingratiatingly -> gliceryna -> skórka -> zadłużenie -> esencje ->cesarskie cięcie -> odpowiedzialne -> blicharz -> ona -> zwiastun -> olcha -> wykolejenie -> składnik -> splątanie -> splątanie -> uszkodzenie -> jonosfera -> erekcja - -> jonosfery -> odsprzedaż -> alarmowanie -> ingresy -> sezam -> mes -> mesas -> szarfa -> ashcan -> can -> canard -> ardor -> dorkiest -> nieruchomości -> jądra -> jądro -> czystsze -> najmądrzejsze -> cenione -> wtrącenia -> najemca -> patrz -> zaszczepione -> dedykowane -> jądra - -> zmniejszanie -> senaty -> testiest -> szacunek -> wrastanie -> własne -> właściciel -> nerwy -> pęcherzyk -> najczystszy -> ester -> terabajty -> jądra -> tkanka -> pozwać -> zamsz -> obrzęk -> wychudzić ->testosteron -> jeden -> jedyny -> gniazdo -> estety -> testy -> sty -> styes -> tak -> jesziwa -> naczyniowe -> modrzewie -> z wahaniem - -> gliceryna -> niejadalne -> wybielacze -> waha się -> zeznawanie -> niewdzięczne -> zjadł -> pracownie

Oto mój kod:

import sys
sys.setrecursionlimit(10000)
w=[i for i in open("words.txt").read().split("\n") if len(i)>=3 and "'" not in i]
b=[i[:3] for i in w]
e=[i[-3:] for i in w]
a=[i for i in zip(*(w,b,e))]
def pathfrom(i,a,l):
    longpath=[]
    for j in a:
        if j[1]==i[2]:
            r=pathfrom(j,[m for m in a if m!=j],l+1)
            path=[i]+r[0]
            if r[1]:
                return path,r[1]
            if len(path)>len(longpath):
                longpath=path
    if l>=250:
        return longpath,True
        sys.exit()
    return longpath,False
for i in a[:2]:
    print i
    p=pathfrom(i,[j for j in a if i!=j],1)
    if len(p)>len(chain_):
        chain_=p
        print p
    print p

Edycja: 1001:

http://pastebin.com/yN0eXKZm

Edycja: 500:

Akwizgran -> kura -> odtąd -> żarliwy -> entail -> ail -> ailed -> led -> ledger -> gerbil -> dwustronny -> rallying -> genialny - -> ousted -> nużący -> ouster -> terabit -> bit -> bitched -> jeż -> wieprz -> hogan -> gander -> derail -> lotki -> początek -> zestaw -> cofnięcie -> potwierdzenie -> pociągnięty -> księgi -> ersatzes -> skórka -> ustalony -> żywopłot -> rząd -> łódka -> owies - -> owies -> dziesięć -> trwały -> wybielacz -> ból -> taniej -> długopis -> karze -> podstępny -> fulcra -> krab -> rabiniczny -> tykwa -> jesion -> zawstydzony -> medal -> dale -> ale -> zaalarmowany -> nużąco -> przebiegły ->chytry -> ustanawia -> hes -> niezdecydowany -> mrówka -> środek zobojętniający kwasy -> cydr -> wykolejony -> półki -> gested -> żmudność -> esej -> powiedz - -> powiedzenie -> genialnie -> przebiegły -> esej -> pomysłowy -> ousting -> pomysłowość -> eseista -> przesmyk -> muszkat -> kot -> kataklizm -> myszy -> lód -> góra lodowa -> erg -> ergonomia -> micra -> kraba -> łóżko -> bedazzles -> lesbijki -> odpowiedź -> były -> ere - -> wznoszenie -> spożycie -> ustanowienie -> spożycie -> spożycie -> jon -> jonizacja -> jonizator -> zero -> erodowanie -> oda -> ody -> odsalanie -> test -> zakład - -> pociągający -> wlewki -> dostał -> dostał ->najemca -> antagonista -> isthmuses -> sezam -> amebas -> basal -> salaamed -> medalion -> jonizujący -> wrastanie -> ingrains -> ins -> szalony - -> anegdotyczne -> talk -> alkohol -> trzymaj -> stare -> stare -> legowisko -> denaturacja -> mocznik -> zasięg -> obolały -> żywopłoty -> gestates -> testable -> bielone -> żywopłot - - ingrates -> testament -> splątanie -> lśniące -> medaliony -> onshore -> ruda -> oregano -> anody - -> odsalanie -> niewdzięczności -> testaty -> tester -> terabity -> jego -> sam -> elf -> elfin -> płetwa -> finagle -> lśniące -> ingratiating -> ingratiatingly -> gliceryna -> skórka -> zadłużenie -> esencje ->cesarskie cięcie -> odpowiedzialne -> blicharz -> ona -> zwiastun -> olcha -> wykolejenie -> składnik -> splątanie -> splątanie -> uszkodzenie -> jonosfera -> erekcja - -> jonosfery -> odsprzedaż -> alarmowanie -> ingresy -> sezam -> mes -> mesas -> szarfa -> ashcan -> can -> canard -> ardor -> dorkiest -> nieruchomości -> jądra -> jądro -> sprzątaczka -> najmądrzejszy -> ceniony -> wścibski -> najemca -> patrz -> zaszczepiony -> poświęcony -> jądra - -> zmniejszanie -> senaty -> testiest -> szacunek -> wrastanie -> własne -> właściciel -> nerwy -> pęcherzyk -> najczystszy -> ester -> terabajty -> jądra -> tkanka -> pozwać -> zamsz -> obrzęk -> wychudzić ->testosteron -> jeden -> jedyny -> gniazdo -> estety -> testy -> sty -> styes -> tak -> jesziwa -> naczyniowe -> modrzewie -> z wahaniem - -> gliceryna -> niejadalne -> bleaker -> keratyna -> cyna -> nalewka -> cewki moczowe -> drażniący -> calamine -> niejadalny -> ponury -> estetyczny -> tic -> tik -> ickiest -> szacowany -> najbarwniejszy -> estymator -> tor -> podpalony -> hedonistyczny -> ticker -> chustki -> pęcherzyki -> zmniejsza -> ensconced -> cedr -> odważ się -> są -> obszar -> osiągalny -> beczenie -> jeść -> jadalny -> bleeder -> wykolejenie -> enter -> termin -> gronostaj -> niewysłowiony -> bleeped -> pedagog -> gogle -> gleans ->odpowiedział -> czerwony -> redbreast -> aster -> termagant -> antagonistyczny -> bilet -> kocioł -> rum -> rumbas -> bazalt -> ołtarz -> smoła - -> ptaszniki -> lasagna -> gnarliest -> wyobcowanie -> wszedł -> czapeczka czerwona -> czapka -> zdolna -> bleeps -> epsilon -> samotna -> obcy -> gestykulował -> czerwone czapki -> apsyda -> pseudonim -> nimfomania -> niacyna -> cinchonas -> nosowy -> nadający się do sprzedaży -> mieszanka -> koniec -> zagrożenie -> geriatryczny - -> ryż -> związany z lodem -> nieodkrywalne -> pęcherzyk -> per -> wózek dziecięcy -> rozdarcie -> rudy -> odsprzedaż -> mniejsze -> SERA -> era -> epoki -> wysypka -> popielaty -> poplecznik -> człowiek -> manacle -> najczystszy ->estrogen -> żandarmy -> meskal -> kalcyna -> nieefektywny -> rozrywkowo -> glicerol -> rola -> oleander -> zaburzenia -> rozrywka -> bawi -> nienasycony - -> mieszane -> dedukowane -> cedry -> arsen -> ładne -> icebox -> box -> boxcar -> car -> caracul -> cullender -> deranges -> gesty -> zmiany harmonogramu -> lekcja -> syn -> sonar -> narc -> arc -> arcade -> adenoidalne -> dales -> lekcja -> sorbet -> zakład - -> betaken -> ken -> kens -> ensemble -> blender -> deride -> idea -> diakon -> con -> wklęsły -> avenger -> germane -> niedokrwistość -> zrozpaczona -> wed - - wedded -> dedukowalna -> blent - -> enthrall ->wszystko -> allay -> lay -> layaway -> way -> wayfarer -> reran -> ran -> ranczer -> zwiastun -> odliczalny -> błogosławiony -> sedan - -> tańczony -> cedes -> descant -> anteater -> określany -> wścibski -> omegas -> gaz -> rana -> aśram -> baran -> wędrówka -> dmuchnął -> lewder -> derides -> zejść -> zagrożony -> płaszcz -> przysięga -> miażdżyca -> sis -> sizal - -> sałatka -> lad -> drabina - -> pochodne -> naczynie -> rzadko -> domeny -> wpisane -> pluskwa -> pluskwa -> bugaboo -> boo -> boobed -> bedder -> wywodzi -> ślady -> gesundheit -> albo -> heraldyczny -> kości -> lodołamacz -> nafta -> lewatywa -> email ->dolegliwość -> intronizacja -> entuzjazm -> użycie -> używany -> sedater -> terminator -> toreador -> uśpiony -> antebellum - -> lumbago -> temu -> agonizująco - -> glikogen -> płeć -> skóra właściwa -> nieszczęścia -> rescind -> nieprzyzwoite -> zachwycony -> środki uspokajające -> szaty -> entuzjasta -> astir -> tyradady -> potomek -> poprzednik -> entice -> pokrywa lodowa -> kondensator -> udręka -> kuszony -> cedilla -> lama -> amalgamat -> gambit -> suki -> waha się - -> zeznawanie -> niewdzięczność -> zjadł -> pracowniepłeć -> skóra właściwa -> nieszczęścia -> rescind -> nieprzyzwoite -> zachwycony -> środki uspokajające -> szaty -> entuzjasta -> astir -> tyradady -> potomek -> poprzednik - -> entice -> czapka lodowa -> kondensator -> udręka -> kuszona -> cedilla -> lama -> amalgamat -> gambit -> suki -> waha się -> zeznawanie -> ingrate -> ate -> atelierspłeć -> skóra właściwa -> nieszczęścia -> rescind -> nieprzyzwoite -> zachwycony -> środki uspokajające -> szaty -> entuzjasta -> astir -> tyradady -> potomek -> poprzednik - -> entice -> czapka lodowa -> kondensator -> udręka -> kuszona -> cedilla -> lama -> amalgamat -> gambit -> suki -> waha się -> zeznawanie -> ingrate -> ate -> ateliers

Mathematica 1482 1655

Coś na początek ...

dict=Import["words.txt"];
words=Union@Select[StringSplit[dict],(StringFreeQ[#,"'s"])\[And]StringLength[#]>2
  \[And]LowerCaseQ@StringTake[#,1]&]

Linki to przedrostki i sufiksy wyrazów przecięcia.

prefixes=Union[StringTake[#,3]&/@words];
suffixes=Union[StringTake[#,-3]&/@words];
links=Intersection[prefixes,suffixes];
linkableWords=(wds=RandomSample@Select[words,MemberQ[links,StringTake[#,3]]\[And]MemberQ[links,StringTake[#,-3]]& ])/.
w_String:> {w,StringTake[w,3],StringTake[w,-3]}

Krawędzie to wszystkie bezpośrednie linki od słowa do słowa:

edges[{w_,fr_,fin_}]:= Cases[linkableWords,{w1_,fin,_}:> (w\[DirectedEdge]w1)]
allEdges=Flatten[edges/@linkableWords];
g=Graph@allEdges;

Znajdź ścieżkę między „popraw” a „zest”.

FindPath[g, "begin", "end", {1480, 3000}, 1][[1]]

Wynik (1655 słów)

{"mend", "endorser", "server", "vertebral", "rallying", "ingrains", 
"insurrectionist", "isthmus", "mussels", "elsewhere", "erection", 
"ionizes", "zestful", "fullness", "essaying", "ingeniously", 
"slyest", "estimator", "tornados", "doses", "sesame", "amebic", 
"bicycled", "ledges", "gestation", "ionizing", "ingratiates", 
"testifying", "ingesting", "inglorious", "ouster", "terminated", 
"tediousness", "essayist", "isthmuses", "session", "ion", 
"ionization", "ionospheres", "resubmitted", "tedious", "ousting", 
"ingest", "ester", "terminates", "testicle", "cleanliness", "essay", 
"say", "saying", "ingratiating", "ingratiatingly", "glycerine", 
"inefficient", "entrances", "cesarians", "answering", "ingenious", 
"ousted", "tediously", "sly", "slyness", "essences", "cesareans", 
"answer", "were", "erecting", "ingredient", "enterprises", 
"sessions", "onshore", "oregano", "anorak", "raking", "ingraining", 
"ingrown", "owner", "nerdiest", "estranging", "ingot", "gotten", 
"tendonitis", "tissue", "suede", "edelweiss", "issuing", "ingestion", 
"ionosphere", "erections", "onset", "settles", "lesion", "ionizer", 
"zeroing", "ingresses", "sesames", "mesmerizing", "ingrates", 
"testes", "testiest", "estrangement", "entail", "ail", "ailment", 
"entice", "icecap", "captivates", "testy", "sty", "stylistic", 
"tickles", "lessee", "seeded", "deductibles", "lesser", 
"servicewoman", "many", "anymore", "ores", "resourceful", "fullback", 
"acknowledgment", "entertainer", "nerves", "vest", "esteemed", 
"mediates", "testament", "entered", "redbreast", "astonishes", 
"hesitatingly", "glycogen", "genera", "eras", "rashes", "hesitates", 
"testicles", "lest", "establishment", "entwines", "nest", "estates", 
"testates", "testosterone", "oneself", "elf", "elfin", "fingered", 
"redcaps", "apse", "pseudonym", "nymphomania", "niacin", "cinemas", 
"masochistic", "tickled", "led", "ledger", "geriatric", "rice", 
"icebreaker", "kerosine", "inexperienced", "ceded", "deductible", 
"blew", "lewder", "derivable", "blemished", "hedgerow", "rowel", 
"welfare", "arena", "enamel", "melded", "dedicates", "tester", 
"terabit", "bitmap", "mapped", "pedicures", "restored", "redeemer", 
"merchantman", "manipulator", "torpedos", "dosed", "seduced", 
"cedilla", "llano", "another", "heretic", "tic", "ticker", "keratin", 
"tinctures", "restaurateur", "euros", "rosettes", "testable", 
"bleaker", "kerosene", "energizer", "zero", "eroded", "deduced", 
"cedar", "dare", "ares", "respondent", "entranced", "cedillas", 
"lasagnas", "nastiest", "esthetic", "ticket", "ketches", "hes", 
"hesitant", "antipasto", "stoppered", "redounded", "deducible", 
"bleeped", "pedant", "antimatter", "terminable", "blent", "enthuse", 
"user", "serenade", "adenoidal", "dales", "lessen", "sentimental", 
"talker", "kerchieves", "vestry", "try", "tryout", "outdone", "ones", 
"nestles", "lesson", "songwriter", "terrapin", "pinched", 
"hedonistic", "tick", "ickiest", "established", "hedgehog", "hogan", 
"gander", "derringer", "gerbil", "billboard", "ardor", "dorkiest", 
"estrogen", "gent", "entirety", "etymological", "calk", "alkalis", 
"lissome", "omegas", "gasolene", "enema", "emaciates", "test", 
"estranges", "gestured", "redeemed", "medic", "diced", "cedars", 
"arsenic", "nice", "iceberg", "erg", "ergonomic", "microcomputer", 
"terser", "sergeant", "antipastos", "tost", "osteopathy", "thy", 
"thymus", "mussiest", "estimable", "blend", "endeavored", "redound", 
"undercover", "verbal", "balk", "alkali", "alibi", "ibis", "bison", 
"sonar", "narcosis", "sister", "terraced", "cede", "edema", 
"emancipator", "torpor", "portraiture", "urea", "reassign", 
"ignoble", "blenched", "hedges", "gesture", "urethras", "raspy", 
"spyglass", "ass", "assailant", "antiquarians", "answered", 
"reduced", "cedes", "despair", "airfares", "resumed", "medicine", 
"ineffable", "bleacher", "herdsmen", "menhaden", "dent", 
"entitlement", "enticement", "entangle", "gleamed", "medullas", 
"lassie", "sieve", "even", "vender", "derivatives", "vessel", 
"selectmen", "mentor", "toreador", "dormer", "meringue", "guerrilla", 
"llanos", "nosedove", "overact", "actionable", "bleeps", "epsilon", 
"longhorn", "ornament", "entreaty", "atypical", "calendar", "dares", 
"resurgent", "entreat", "eater", "term", "ermine", "inedible", 
"bleeder", "derrières", "resentful", "fulcra", "crabbed", 
"bedevilment", "entwine", "inelegant", "antitoxins", "inspired", 
"redder", "derides", "descendant", "antihistamine", "inequitable", 
"bleat", "eaten", "tenured", "redcap", "capstans", "answerable", 
"blender", "deranges", "gestures", "restart", "arteriosclerosis", 
"sis", "sisal", "saltpeter", "terrifyingly", "glycerin", "rink", 
"inkwell", "ellipsis", "sisterhood", "oodles", "lessor", "sorrowed", 
"wedges", "gesundheit", "either", "hereafter", "termite", "iterator", 
"tornado", "adobes", "bespoken", "ken", "kens", "ensnare", "area", 
"rear", "earful", "fulfil", "fillet", "letdown", "ownership", 
"hipped", "pediatric", "richer", "heretical", "calculus", "lusher", 
"heraldic", "dice", "icebound", "underscored", "redskins", "instant", 
"antiperspirant", "anthropomorphic", "hiccup", "cup", "cups", 
"upstage", "agendas", "dashingly", "glycerol", "role", "oleo", 
"leonine", "ineluctable", "blessed", "sedatives", "vesicles", 
"lessens", "ensured", "redefine", "inextinguishable", "bleach", 
"achoo", "hooch", "ocher", "hero", "erode", "ode", "odes", "desktop", 
"topple", "pleasured", "redeveloped", "pediment", "entrapped", 
"pederasty", "stylus", "lush", "usher", "hermaphrodite", "item", 
"tempos", "postpaid", "aide", "ideogram", "rampart", "artisan", 
"sandhog", "hog", "hogwash", "ash", "ashram", "rammed", "mediocre", 
"crestfallen", "lend", "endow", "downcast", "astronomer", 
"merriment", "entrant", "antiwar", "warden", "dentures", "restful", 
"fulfillment", "entrapment", "enthrall", "allay", "layout", 
"outbound", "underclassman", "manhole", "oleander", "dermis", 
"misused", "sedater", "terrific", "fiche", "cheapens", "ensnares", 
"restrains", "insolent", "entombed", "bedraggle", "gleeful", 
"fulfilment", "entrenchment", "entrap", "rapper", "persistent", 
"enthronement", "enthusiast", "astute", "uterus", "rustproofed", 
"fedora", "orangeades", "despised", "seducer", "ceramic", 
"microscopic", "picnic", "nicotine", "inexpedient", "entomb", 
"ombudsman", "mantel", "teletypewriter", "terminological", "calif", 
"lifetimes", "mescaline", "inertia", "tiaras", "raster", "terrace", 
"acetaminophen", "henchmen", "menhadens", "enslaves", "vesper", 
"peroxide", "ideograph", "aphid", "hides", "desideratum", "tumor", 
"mortgagee", "geegaw", "gawk", "awkward", "ardent", "enthused", 
"sediment", "enter", "termed", "mediaeval", "valentine", "inexact", 
"actives", "vestment", "entourage", "agent", "entryway", "wayside", 
"idea", "dear", "earache", "checkups", "upsides", "descent", 
"entertainment", "entomological", "calicos", "cosign", "ignored", 
"redcoat", "oaten", "tensed", "sedan", "dank", "anklet", "lettered", 
"redskin", "kingpin", "pinups", "ups", "upshot", "hotbed", 
"bedtimes", "mes", "messenger", "germicides", "destitute", "utensil", 
"silencer", "cervix", "vixens", "ensign", "ignorant", "antipasti", 
"stimulus", "lusty", "stymie", "miens", "enslave", "averred", 
"redrew", "rewritten", "tenpins", "instructor", "torrent", 
"entertains", "insult", "ultrasound", "undersides", "despoil", 
"oilcloth", "other", "hereupon", "pondered", "redundant", "anthill", 
"ill", "illicit", "citizens", "ensnared", "rediscovered", "redesign", 
"ignoramus", "muskmelon", "longer", "gerrymander", "deride", "ideas", 
"easy", "asylum", "lumbermen", "mendicant", "antlered", "redevelop", 
"lopes", "pester", "terrapins", "instil", "tildes", "deserves", 
"vesicle", "cleave", "avenger", "germane", "anemia", "miasmas", 
"mash", "ashy", "shy", "shyster", "termagant", "antiaircraft", 
"afterglow", "lowland", "and", "androgen", "genitalia", "liars", 
"arson", "sonatas", "taste", "stepsister", "termini", "initiator", 
"tor", "torn", "ornamental", "tallow", "lowered", "red", "redraft", 
"aft", "aftertaste", "stereotypes", "pesky", "skyrocket", 
"kettledrum", "rummer", "merciful", "fulsome", "omens", "ensures", 
"resultant", "antennas", "nasal", "saleswoman", "mane", "anemometer", 
"terrains", "insightful", "fulcrum", "rumbas", "baseman", 
"mannikins", "insures", "resound", "underpass", "assassins", "inset", 
"settee", "teethe", "theological", "calf", "alfresco", "scornful", 
"fulfill", "illustrator", "torpid", "pidgin", "gins", "instal", 
"talc", "alcove", "overtakes", "kestrel", "relabel", "beleaguered", 
"redraw", "rawhide", "identical", "caliber", "beret", "retrace", 
"acetylene", "enemas", "massacred", "redeploys", "oyster", 
"terminator", "tortillas", "last", "astronomical", "calliope", 
"operator", "tort", "orthographic", "hiccups", "upstart", 
"artificer", "cervical", "callus", "lustre", "trend", "endeavor", 
"vortex", "textures", "researcher", "heroins", "instill", "illegal", 
"galloped", "pedagogical", "callipered", "rediscover", "vertebra", 
"brasher", "herbicides", "descry", "cryptogram", "ramrod", "rodeo", 
"deodorizer", "zeros", "rosebush", "ushered", "redden", "denatures", 
"reset", "setups", "upside", "ides", "describes", "besides", 
"desperado", "adores", "reshuffle", "flea", "leaflet", "lethal", 
"halibut", "but", "button", "tonic", "niche", "cherubim", "bimbos", 
"bosun", "sunk", "unkind", "indentures", "resend", "endures", 
"restorer", "reran", "rang", "anger", "germicide", "ideological", 
"calabash", "ashamed", "medical", "caloric", "rickshas", "hasten", 
"tendon", "donkey", "keyword", "ordains", "insecticides", "desires", 
"resin", "sins", "inspector", "torrid", "rid", "rides", "despot", 
"potpie", "piebald", "aldermen", "menace", "ace", "acerbic", "bicep", 
"cephalic", "lichen", "hennas", "nasty", "styes", "yesterday", "day", 
"daybed", "bedridden", "dental", "talisman", "mankind", "indignant", 
"antique", "questionnaires", "resubmit", "mitten", "tenfold", "old", 
"olden", "denudes", "design", "ignores", "resumes", "mesdames", 
"mesas", "sass", "assemblywoman", "mangle", "glee", "leeway", 
"waylay", "laywomen", "menswear", "ear", "earldom", "domains", "ins", 
"instrumental", "tall", "all", "allegorical", "calm", "almanac", 
"nacre", "credit", "dittos", "tossup", "superman", "mandolin", 
"linesman", "manacle", "cleverer", "rerun", "runaway", "way", 
"wayfarer", "reruns", "unshaven", "ventures", "resell", "elliptical", 
"calmer", "mercuric", "ricochet", "heterodoxy", "oxymora", 
"orangutang", "angina", "inapt", "apt", "aptitudes", "descend", 
"endear", "earlobes", "bestowal", "walleyes", "yes", "yeshivas", 
"vassal", "saltcellar", "larval", "valiant", "anthropological", 
"calfskin", "kind", "inductee", "tee", "teenager", "gerund", 
"underclass", "assemblyman", "manservant", "antelopes", "peso", 
"esoteric", "rickshaw", "hawser", "servicewomen", "mental", 
"tallyhos", "hospital", "talon", "longshoremen", "men", "menthol", 
"holography", "phylum", "lumberman", "manikin", "kingpins", 
"install", "allures", "resuscitator", "tortilla", "llamas", 
"massacres", "resistor", "tormentor", "torque", "queasy", 
"asymmetric", "ricksha", "sharped", "pedlar", "largos", "gossamer", 
"merganser", "service", "icebox", "boxer", "xerography", "physical", 
"calculator", "tortures", "resonant", "anticlimax", "maxima", "imam", 
"mammon", "monograph", "aphelia", "liaison", "sonic", "nicknamed", 
"media", "diametrical", "calliper", "performed", "medulla", "llama", 
"amalgam", "gamins", "insulin", "lineman", "mantra", "transplant", 
"antigen", "genres", "respires", "resold", "oldie", "diesel", 
"seldom", "domed", "medieval", "valor", "lordship", "hipper", "per", 
"perspires", "restores", "restructures", "resort", "orthodoxy", 
"oxygen", "gentlemen", "menopausal", "saltpetre", "treacle", 
"cleaver", "verdigris", "risen", "send", "end", "endemic", 
"microfiche", "checkout", "outclass", "assault", "ultraviolet", 
"let", "letterbox", "boxcar", "carom", "roman", "manifesto", 
"stovepipes", "pesticides", "described", "bedsides", "descant", 
"anthem", "hempen", "penguins", "insignificant", "antebellum", 
"lumbar", "barracudas", "dash", "ashcan", "cannonball", "allover", 
"verbena", "enamor", "morgue", "guerrillas", "lash", "ashen", 
"henchman", "mandolins", "inspires", "resistant", "antechamber", 
"bereave", "aver", "vermin", "minim", "nimbus", "bus", "businessman", 
"mantras", "rasp", "asphalt", "altogether", "her", "hereabout", 
"outcast", "astrological", "calisthenic", "nicknames", "mescal", 
"calliopes", "pesetas", "tassel", "selectman", "mannikin", 
"kinswoman", "man", "manic", "nicer", "cerebra", "bravado", "adobe", 
"obeisant", "antiparticle", "clever", "versus", "sushi", "shirr", 
"irrelevant", "antelope", "open", "pentagon", "gonad", "nadir", 
"directorship", "hippopotami", "amid", "midwifed", "fedoras", 
"rasher", "herbal", "ball", "allot", "lot", "lotus", "tussle", 
"sledgehammer", "merchant", "ant", "antidepressant", "anther", 
"heraldry", "drywall", "allegros", "rosebud", "budgerigar", 
"garbageman", "manikins", "inscribes", "bestow", "townsmen", "menu", 
"enures", "restaurant", "antithetical", "calico", "icon", "confound", 
"underbid", "bidden", "denser", "seraphic", "hiccuped", "pedigree", 
"reeve", "ever", "vertical", "caliper", "perusal", "salami", "amir", 
"mires", "restraint", "interstellar", "larkspur", "puritanical", 
"calligrapher", "herdsman", "manatee", "teepee", "peeve", "everyday", 
"daydreamer", "meres", "result", "ultimatum", "tumbril", "rill", 
"illogical", "calligraphy", "physic", "sickbed", "bedsores", 
"resolver", "vertebras", "rascal", "call", "allergenic", "nickname", 
"amebas", "baste", "stepson", "son", "sonnet", "net", "nether", 
"heros", "rosins", "insular", "larvas", "vast", "astrakhan", 
"handyman", "manicures", "resins", "instep", "tepid", "pidgins", 
"inscribed", "bedbug", "bug", "bugbear", "earwax", "waxen", 
"xenophobia", "biathlon", "longhair", "airstrip", "ripple", "pleas", 
"eastbound", "underachiever", "verbatim", "timbre", "brew", 
"rewound", "underplay", "laywoman", "mandarins", "insofar", "farm", 
"armpit", "pitcher", "herald", "alderman", "mangos", "gossip", 
"sipped", "pedagogue", "guerillas", "laser", "serape", "aped", 
"pederast", "astound", "underground", "underpins", "insane", 
"anemic", "micra", "crane", "anew", "new", "newscast", "astir", 
"tiro", "ironware", "are", "areas", "east", "astronomic", 
"microchip", "hippopotamus", "mustache", "chervil", "villas", "lass", 
"assassin", "sinew", "newsman", "mangrove", "overtax", "taxicab", 
"cabana", "anathemas", "mast", "astronaut", "author", "horoscope", 
"opera", "eraser", "serfdom", "dominos", "nostrum", "rumpus", "pus", 
"pushcart", "arthropod", "podia", "diatom", "tomboy", "boycott", 
"ottoman", "manhunt", "untidy", "idyllic", "licensee", "seethe", 
"thereabout", "outplay", "layoff", "officer", "cerebrum", "rum", 
"rumple", "plethora", "oracle", "clergyman", "maneuver", "verandas", 
"dashikis", "kisser", "serum", "rumor", "morbid", "bidet", "detach", 
"achiever", "vertex", "text", "extremer", "merino", "inopportune", 
"uneaten", "tensor", "sort", "orthopedic", "dickie", "kielbasas", 
"sashay", "hayloft", "often", "ten", "tenpin", "pinkeye", "eyeball", 
"allegro", "grout", "outfox", "fox", "foxtrot", "rot", "rotund", 
"underwear", "earshot", "hot", "hotshot", "hotel", "telex", 
"lexicon", "congresswoman", "manor", "northbound", "undertow", 
"township", "hippos", "possessor", "sorbet", "betcha", "chart", 
"art", "article", "clear", "earwig", "wigwam", "wampum", "pummel", 
"melodic", "dictum", "tumbrel", "relic", "licit", "citadel", "delay", 
"lay", "laypeople", "plectra", "traumas", "mascot", "cotyledon", 
"donor", "nor", "normal", "malt", "altar", "tart", "artiste", 
"stencil", "cilantro", "trouper", "pericardia", "diadem", "democrat", 
"rattan", "tang", "angstrom", "romper", "perturb", "urban", "bang", 
"angel", "gelatin", "tint", "intros", "rostra", "trapper", 
"persimmon", "monsignori", "origin", "ginkgos", "gospel", "pelvis", 
"visor", "sorghum", "humid", "midair", "air", "airfoil", "oil", 
"oilskin", "kin", "kindergarten", "tentacle", "cleanser", "sermon", 
"monolog", "logarithmic", "microbes", "bestir", "tiros", "rosin", 
"sin", "singleton", "tonsil", "silicon", "con", "constraint", 
"intagli", "glint", "interwove", "overshadow", "downtrodden", 
"dentin", "tin", "tinsel", "sellout", "out", "output", "put", 
"putsch", "schoolmarm", "arm", "armor", "moribund", "underpin", 
"pint", "interloper", "periwig", "wig", "wigwag", "wagon", 
"gonorrhea", "hearten", "tenon", "nonverbal", "balsam", "samovar", 
"varmint", "interviewee", "weeper", "perturbed", "bed", "bedpan", 
"panache", "chestnut", "nut", "nutmeg", "meg", "megalopolis", 
"lissom", "somersault", "ultra", "tram", "ramp", "amputee", "teeth", 
"ethos", "hos", "hostel", "telescopic", "picayune", "uneven", 
"vendor", "dorsal", "salad", "ladybug", "bugaboo", "boomerang", 
"angora", "orangutan", "tandem", "demagogry", "gryphon", 
"honeycombed", "bedlam", "lamb", "ambergris", "risky", "sky", 
"skycap", "capstan", "tannin", "ninepin", "pinpoint", "interpret", 
"retiree", "reefer", "fer", "ferret", "returnee", "needlepoint", 
"interurban", "bantam", "tamp", "ampul", "pullout", "outrun", 
"runabout", "outstrip", "rip", "ripen", "pennon", "nonfat", "fathom", 
"homespun", "puns", "unsubscribes", "besom", "sombre", "breathe", 
"theatre", "tremor", "mortar", "tarpaulin", "lintel", "telethon", 
"honeydew", "dewlap", "lap", "lapel", "pelvic", "victim", "timpani", 
"animus", "muscat", "cat", "catsup", "sup", "superstar", "taro", 
"arousal", "salamis", "misprint", "interwoven", "venom", "nomad", 
"madam", "dam", "dampen", "penicillin", "lint", "intercom", 
"compound", "underpay", "pay", "payoff", "off", "offal", "fallout", 
"outwit", "withal", "halt", "altho", "tho", "thou", "housebound", 
"undergrad", "radio", "diocesan", "sanserif", "riffraff", 
"affidavit", "vitamin", "minicam", "campus", "pussycat", "catamaran", 
"rancor", "cornucopia", "piano", "anon", "non", "nonpartisan", 
"sandbar", "bar", "barren", "renewal", "walkout", "outruns", 
"unsnap", "naphtha", "thalamus", "musky", "skydove", "overrun", 
"run", "runs", "unsheathe", "the", "theorem", "remove", "overreach", 
"ache", "cherub", "rubes", "beseech", "echo", "chosen", "sensor", 
"sorrel", "relay", "layman", "mantillas", "lasagna", "gnat", 
"natures", "resonator", "torus", "russet", "set", "setback", 
"acknowledgement", "entanglement", "entombment", "entourages", 
"gestates", "testing", "ingratiate", "ate", "ateliers", "ersatzes", 
"zest"}

Python, 90

wywrócone odliczenia dzierżawca huśtawka poślubiona poślubiona dedukcje cesarscy odpowiedzialne błogosławieństwa sezam oczka wahanie jonosfera erekcja jonizator zero erodować oda ody odes dezerter zakończeń rudy na lądzie zamieszkać idealistyczne tic łaskocze lekcje piosenki trwające ingrains zaszczepić nieliberalne zebranie spożycie estranges gesty odpowiedzi odpowiedzi sezam z entuzjazmem entuzjastycznie entertainst entains docenia gest cewki moczowe wysypki wahające się antyklimaksymalne maksimum wyobraź sobie nietrzeźwe testowane żmudnie przebiegły esencje cesarskie cięcie wilkołaki kamizelka szanowany wścibski omlet sałaty jonizacja jonizacja jonizacja spożycie jonosfery ratowanie wskazanie wrastające własność hipis pobożność etymolog przesłuchania sesje ustalone księgi rachunkowe

Najpierw ręcznie czyszczę listę, usuwając wszystko

• słowa z wielką literą
• słowa z apostrofami
• słowa z éêèáâàö
• Słowa 1- i 2-literowe

kosztuje mnie to co najwyżej 2 punkty, ponieważ te słowa mogą znajdować się tylko na początku lub na końcu łańcucha, ale zmniejsza listę słów o 1/3 i nie mam do czynienia z Unicode.

Następnie tworzę listę wszystkich prefiksów i sufiksów, znajduję nakładkę i odrzucam wszystkie słowa, chyba że zarówno prefiks, jak i sufiks znajdują się w zestawie nakładek. Ponownie, to goli najwyżej 2 punkty w stosunku do mojego maksymalnego możliwego do osiągnięcia wyniku, ale zmniejsza listę słów do jednej trzeciej oryginalnego rozmiaru (spróbuj uruchomić algorytm na krótkiej liście dla możliwego przyspieszenia), a pozostałe słowa są ściśle powiązane (z wyjątkiem niektórych 3 -lety słów, które są powiązane tylko ze sobą). W rzeczywistości prawie każde słowo można uzyskać z dowolnego innego słowa na ścieżce o średnio 4 krawędziach.

Przechowuję liczbę łączy w macierzy przylegania, która upraszcza wszystkie operacje i pozwala mi robić fajne rzeczy, takie jak patrzenie n kroków do przodu lub liczenie cykli ... przynajmniej teoretycznie, ponieważ kwadrat zajmuje około 15 sekund to podczas wyszukiwania. Zamiast tego zaczynam od losowego przedrostka i chodzę losowo, albo wybieram zakończenie równomiernie, faworyzując te, które występują często (jak „-ing”) lub te, które występują rzadziej.
Wszystkie trzy warianty zasysają równomiernie i wytwarzają łańcuchy w zakresie 20-40, ale przynajmniej są szybkie. W końcu muszę dodać rekursję.

from numpy import *
f = open('words_short.txt')
words = f.read().split() # 62896
f.close()

prefix = [w[:3] for w in words]     # 2292
suffix = [w[-3:] for w in words]    # 2262
common = set(prefix) & set(suffix)  # 1265

PSW = [(p,s,w) for (p,s,w) in zip(prefix, suffix, words) if p in common and s in common] # 28673
common = list(common)
mapping = dict(zip(common, range(len(common)))) # enumerate trigrams

M = zeros((len(common), len(common)), dtype=int) # for fast processing
W = [[[] for i in range(len(common))] for j in range(len(common))] # for reconstruction
for p,s,w in PSW: # build adjacency matrix
    M[mapping[p], mapping[s]] += 1
    W[mapping[p]][mapping[s]].append(w)

def chain(A, rho=0):
    B = array(A)
    links = []
    start = random.randint(len(B))
    links.append(start)
    while 1:
        nextpos = where(B[links[-1],:]>0)[0]
        if len(nextpos)==0: return links
        nextnum = B[links[-1],nextpos]

        p = ones(len(nextnum))/len(nextnum) # pick uniformly
        if rho>0: p = nextnum*1./sum(nextnum) # prioritize many links
        if rho>1: p = 1/p; p = p/sum(p) # prioritize few links

        chosen = random.choice(nextpos, p=p)
        B[links[-1], chosen] -= 1
        links.append(chosen)

def chain2words(L):
    # can only be used once because of .pop()
    z = zip(L[:-1],L[1:])
    res = []
    for p,s in z:
        res.append(W[p][s].pop())
    return res

chains = [chain(M) for i in range(100)]
bestchain = chains[argmax(map(len, chains))]
print ' '.join(chain2words(bestchain))

Początkowo chciałem spróbować czegoś podobnego do tego, ale ponieważ jest to ukierunkowany wykres z cyklami, żaden ze standardowych algorytmów do sortowania topologicznego, najdłuższej ścieżki, największej ścieżki Eulera lub chińskiego listonosza nie działa bez większych modyfikacji.

I tylko dlatego, że wygląda ładnie, oto obraz macierzy przylegania M, M ^ 2 i M ^ nieskończoności (nieskończoność = 32, potem się nie zmienia) z białymi = niezerowymi wpisami