Esse desafio é encontrar a cadeia mais longa de palavras em inglês, onde os 3 primeiros caracteres da próxima palavra correspondem aos 3 últimos da última palavra. Você usará um dicionário comum disponível nas distribuições Linux, que pode ser baixado aqui:

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

que possui 99171 palavras em inglês. Se o seu Linux local /usr/share/dict/wordsfor o mesmo arquivo (md5sum == cbbcded3dc3b61ad50c4e36f79c37084), você poderá usá-lo.

Palavras só podem ser usadas uma vez em uma resposta.

EDIT: As letras devem corresponder exatamente, incluindo maiúsculas / minúsculas, apóstrofos e acentos.

Um exemplo de resposta válida é: idea deadpan panoramic micra craftsman mantra traffic fiche qual seria a pontuação 8.

A resposta com a cadeia de palavras válida mais longa será a vencedora. Em caso de empate, a resposta mais rápida vencerá. Sua resposta deve listar a cadeia de palavras que você encontrou e (é claro) o programa que você escreveu para fazê-lo.

Java, heurística a favor do vértice que induz o maior gráfico: 1825 1855 1873

O código abaixo é executado em menos de 10 minutos e encontra o seguinte caminho:

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

Idéias principais

Em Aproximando caminhos e ciclos diretos mais longos , Bjorklund, Husfeldt e Khanna, Lecture Notes in Computer Science (2004), 222-233, os autores propõem que, em gráficos esparsos de expansores, um caminho longo pode ser encontrado por uma pesquisa ambiciosa que seleciona a cada pise o vizinho da cauda atual do caminho que se estende pelo maior subgrafo em G ', onde G' é o gráfico original com os vértices no caminho atual excluídos. Não tenho certeza de uma boa maneira de testar se um gráfico é um gráfico expansor, mas certamente estamos lidando com um gráfico esparso, e como seu núcleo é de cerca de 20.000 vértices e tem um diâmetro de apenas 15, deve ter uma boa propriedades de expansão. Então, eu adoto essa heurística gananciosa.

Dado um gráfico G(V, E) , podemos encontrar quantos vértices são alcançáveis ​​de cada vértice usando Floyd-Warshall no Theta(V^3)tempo ou usando o algoritmo de Johnson no Theta(V^2 lg V + VE)tempo. No entanto, eu sei que estamos lidando com um gráfico que tem um componente fortemente conectado (SCC) muito grande, por isso adoto uma abordagem diferente. Se identificarmos SCCs usando o algoritmo de Tarjan , também obteremos uma classificação topológica para o gráfico compactado G_c(V_c, E_c), que será muito menor com o O(E)tempo. Como G_cé um DAG, podemos calcular a acessibilidade G_cno O(V_c^2 + E_c)tempo. (Descobri subseqüentemente que isso é sugerido no exercício 26-2.8 do CLR ).

Como o fator dominante no tempo de execução é E, eu o otimizo inserindo nós fictícios para os prefixos / sufixos. Então, em vez de 151 * 64 = 9664 arestas das palavras que terminam -res em palavras que começam com res- Eu tenho 151 arestas das palavras que terminam -res para # res # e 64 arestas de # res # para palavras que começam com res- .

E, finalmente, como cada pesquisa leva cerca de 4 minutos no meu PC antigo, tento combinar os resultados com caminhos longos anteriores. Isso é muito mais rápido e apareceu minha melhor solução atual.

Código

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" ( sequência completa )

Tentar encontrar a solução ideal mostrou-se muito caro no tempo. Então, por que não escolher amostras aleatórias, armazenar em cache o que pudermos e esperar o melhor?

Primeiro Hashé construído um que mapeia prefixos para mundos completos, começando com esse prefixo (por exemplo "the" => ["the", "them", "their", ...]). Então, para cada palavra da lista, o método sequenceé chamado. Ele obtém as palavras que poderiam seguir a partir de Hash, pega uma amostra 100e se chama recursivamente. O mais longo é tirado e exibido com orgulho. As sementes do RNG (Random::DEFAULT ) e o comprimento da sequência também são exibidos.

Eu tive que executar o programa algumas vezes para obter um bom resultado. Esse resultado específico foi gerado com sementes328678850348335483228838046308296635426328678850348335483228838046308296635426 .

Roteiro

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)}"

Pontuação: 1631 1662 palavras

['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"]

Você pode encontrar a sequência inteira aqui: http://pastebin.com/TfAvhP9X

Eu não tenho o código fonte completo. Eu estava tentando diferentes abordagens. Mas aqui estão alguns trechos de código que devem ser capazes de gerar uma sequência do mesmo tamanho. Desculpe, não é muito bonito.

Código (Python):

Primeiro, algum pré-processamento dos dados.

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)

Depois, defini uma função recursiva (primeira pesquisa de profundidade).

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

Claro que isso leva muito tempo. Mas depois de algum tempo, ele encontrou uma sequência com 1090 elementos e eu parei.

A próxima coisa a fazer é uma pesquisa local. Para cada dois vizinhos n1, n2 na sequência, tento encontrar uma sequência começando em n1 e terminando em n2. Se existe uma sequência, insiro-a.

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)

Claro que também tive que parar o programa manualmente.

PHP, 1742 1795

Eu tenho mexido com PHP sobre isso. O truque é definitivamente selecionar a lista para os cerca de 20 mil que são realmente válidos e jogar o resto fora. Meu programa faz isso iterativamente (algumas palavras que ele joga fora na primeira iteração significa que outras não são mais válidas) no início.

Meu código é horrível, ele usa várias variáveis ​​globais, usa muita memória (mantém uma cópia de toda a tabela de prefixos para cada iteração) e levou literalmente dias para chegar ao meu melhor atual, mas ainda gerencia para ganhar - por enquanto. Começa muito rapidamente, mas fica cada vez mais lento com o passar do tempo.

<?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]);

?>

Uma melhoria óbvia seria usar uma palavra órfã para o início e o fim.

Enfim, eu realmente não sei por que minha lista de pastas foi movida para um comentário aqui, ela está de volta como um link para pastas, pois agora eu incluí meu código.

http://pastebin.com/Mzs0XwjV

Python: 1702 - 1704 - 1733 palavras

Eu usei um Dict para mapear todos os prefixos para todas as palavras, como

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

Edite pequenas melhorias: removendo todas as uselesspalavras no início, se seus sufixos não estiverem na lista de prefixos (obviamente seria uma palavra final)

Em seguida, escolha uma palavra na lista e navegue no mapa de prefixos como um nó da árvore

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

O programa precisa de um número de palavras para saber quando parar, pode ser encontrado como 1733no métodocheckForNextWord̀

O programa precisa do caminho do arquivo como argumento

Não é muito pitonico, mas tentei.

Demorou menos de 2 minutos para calcular esta sequência: saída completa :

os estudos dessalinizados comeram ateliers ... abençoados estimando criaturas ingênuas

Pontuação: 249 500 1001

Aachen -> galinha -> doravante -> ardente -> implicar -> tudo -> afligido -> led -> razão -> gerbil -> bilateral -> reunião -> engenhoso - -> expulso -> tedioso -> expulso -> terabit -> bit -> bitched -> ouriço -> porco -> hogan -> hogan -> gander -> descarrilamento -> ailerons -> onset -> set -> recuo -> reconhecimento -> implicado -> ledgers -> ersatzes -> entusiasmo -> estabelecido -> hedgerow -> linha -> barco a remo -> aveia - -> aveia -> dez -> sustentável -> lixívia -> dor -> mais barato -> caneta -> penaliza -> zestful -> fulcra -> caranguejo -> rabínico -> cabaça -> cinza -> vergonha -> medalha -> dale -> ale -> alertado -> tediosamente -> manhoso ->astuto -> estabelece -> hes -> hesitante -> formiga -> antiácido -> cidra -> descarrilou -> bordas -> gestado -> tédio -> ensaio -> diz - -> dizendo -> engenhosamente -> astúcia -> ensaio -> ingênuo -> expulsão -> engenhosidade -> ensaísta -> istmo -> muscat -> gato -> cataclísmico -> ratos -> gelo -> iceberg -> erg -> ergonômico -> micra -> caranguejo -> cama -> deslumbramentos -> lésbicas -> resposta -> foram -> antes - -> montagem -> ingestão -> estabelecimento -> ingestão -> ingestão -> íon -> ionização -> ionizador -> zero -> erodir -> ode -> odes -> dessaliniza -> teste -> estabelecimento - -> implicando -> lingote -> obteve -> obteve ->inquilino -> antagonista -> isthmuses -> gergelim -> amebas -> basal -> salaamed -> medalhão -> ionizante -> entranhamento -> entranhas -> ins -> insano - -> anedótico -> talco -> álcool -> espera -> antigo -> antigo -> den -> denature -> uréia -> uréia -> alcance -> doido -> sebes -> gestates -> testável -> branqueado -> hedging -> ingratos -> testamento -> emaranhado -> brilhado -> medalhões -> onshore -> minério -> orégano -> ânodos - -> dessalinização -> ingratiates -> testados -> testador -> terabits -> seu -> próprio -> elfo -> elfin -> fin -> finagle -> brilhando -> cativante -> cativante -> glicerina -> casca -> endividamento -> essências ->cesarianas -> responsável -> arquibancada -> ela -> arauto -> amieiro -> descarrilamento -> ingrediente -> entrelaçamento -> entrelaçamento -> lesão -> ionosfera -> ereção - -> ionosferas -> revenda -> alerta -> entradas -> gergelim -> mes -> mesas -> faixa -> ashcan -> lata -> canard -> ardor -> dorkiest -> propriedades -> testículos -> testículo -> limpador -> nerdiest -> estimado -> meddles -> locatário -> ver -> semeado -> dedica -> dedica -> testículos - -> diminuir -> senados -> testiest -> estimando -> encravado -> próprio -> proprietário -> nervos -> vesícula -> mais limpa -> éster -> terabytes -> testículo -> tecido -> sue -> camurça -> edema -> emaciates ->testosterona -> um -> os -> ninho -> estetas -> irritadiço -> chiqueiro -> chiqueiros -> sim -> yeshivas -> vascular -> larício -> hesitante - -> glicerina -> não comestível -> alvejantes -> hesita -> testemunhar -> ingrato -> comeu -> ateliers

Aqui está o meu código:

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

Edição: 1001:

http://pastebin.com/yN0eXKZm

Edição: 500:

Aachen -> galinha -> doravante -> ardente -> implicar -> tudo -> afligido -> led -> razão -> gerbil -> bilateral -> reunião -> engenhoso - -> expulso -> tedioso -> expulso -> terabit -> bit -> bitched -> ouriço -> porco -> hogan -> hogan -> gander -> descarrilamento -> ailerons -> onset -> set -> recuo -> reconhecimento -> implicado -> ledgers -> ersatzes -> entusiasmo -> estabelecido -> hedgerow -> linha -> barco a remo -> aveia - -> aveia -> dez -> sustentável -> lixívia -> dor -> mais barato -> caneta -> penaliza -> zestful -> fulcra -> caranguejo -> rabínico -> cabaça -> cinza -> vergonha -> medalha -> dale -> ale -> alertado -> tediosamente -> manhoso ->astuto -> estabelece -> hes -> hesitante -> formiga -> antiácido -> cidra -> descarrilou -> bordas -> gestado -> tédio -> ensaio -> diz - -> dizendo -> engenhosamente -> astúcia -> ensaio -> ingênuo -> expulsão -> engenhosidade -> ensaísta -> istmo -> muscat -> gato -> cataclísmico -> ratos -> gelo -> iceberg -> erg -> ergonômico -> micra -> caranguejo -> cama -> deslumbramentos -> lésbicas -> resposta -> foram -> antes - -> montagem -> ingestão -> estabelecimento -> ingestão -> ingestão -> íon -> ionização -> ionizador -> zero -> erodir -> ode -> odes -> dessaliniza -> teste -> estabelecimento - -> implicando -> lingote -> obteve -> obteve ->inquilino -> antagonista -> isthmuses -> gergelim -> amebas -> basal -> salaamed -> medalhão -> ionizante -> entranhamento -> entranhas -> ins -> insano - -> anedótico -> talco -> álcool -> espera -> velho -> antigo -> den -> denature -> uréia -> uréia -> alcance -> doido -> sebes -> gestates -> testável -> branqueado -> hedging -> ingratos -> testamento -> emaranhado -> brilhado -> medalhões -> onshore -> minério -> orégano -> ânodos - -> dessalinização -> ingratiates -> testados -> testador -> terabits -> seu -> próprio -> elfo -> elfin -> fin -> finagle -> brilhando -> cativante -> cativante -> glicerina -> casca -> endividamento -> essências ->cesarianas -> responsável -> arquibancada -> ela -> arauto -> amieiro -> descarrilamento -> ingrediente -> entrelaçamento -> entrelaçamento -> lesão -> ionosfera -> ereção - -> ionosferas -> revenda -> alerta -> entradas -> gergelim -> mes -> mesas -> faixa -> ashcan -> lata -> canard -> ardor -> dorkiest -> propriedades -> testículos -> testículo -> limpador -> nerdiest -> estimado -> meddles -> locatário -> ver -> semeado -> dedica -> dedica -> testículos - -> diminuir -> senados -> testiest -> estimando -> encravado -> próprio -> proprietário -> nervos -> vesícula -> mais limpa -> éster -> terabytes -> testículo -> tecido -> sue -> camurça -> edema -> emaciates ->testosterona -> um -> os -> ninho -> estetas -> irritadiço -> chiqueiro -> chiqueiros -> sim -> yeshivas -> vascular -> larício -> hesitante - -> glicerina -> não comestível -> amolador -> queratina -> estanho -> tintura -> uretras -> malandro -> calamina -> ineducável -> sombrio -> estético -> tic -> tick -> ickiest -> estimable -> bleariest -> estimator -> tor -> torched -> hedonistic -> ticker -> kerchieves -> vesículas -> diminui - -> ensconced -> cedro -> desafio -> são -> área -> alcançável -> balido -> comer -> comestível -> sangrador -> descarrilamento -> entrar -> termo -> arminho -> inefável -> bipado -> pedagogo -> óculos -> óculos ->respondeu -> vermelho -> vermelho - - aster -> termagant -> antagônico -> bilhete -> kettledrum -> rum -> rumbas -> basalto -> altar -> altar -> alcatrão - -> tarântulas -> lasanha -> gnarliest -> estranhamento -> inserido -> redcap -> boné -> capaz -> bip -> epsilon -> mais solitário -> estranhos -> gesticulou -> redcaps -> abside -> pseudônimo -> ninfomania -> niacina -> cinchonas -> nasal -> vendável -> mistura -> final -> ameaçar -> geriátrica - -> arroz -> congelado -> não aceita -> vesper -> por -> carrinho de bebê -> rasgou -> minérios -> revendas -> menor -> soros -> era -> eras -> rash -> ashen -> capanga -> homem -> manacle -> mais limpo ->estrogênio -> gendarmes -> mescal -> calcina -> ineficiente -> divertido -> glicerol -> papel -> oleandro -> perturbação -> entretenimento -> entretém -> insaciável - -> misturado -> deduzido -> cedros -> arsênico -> agradável -> geladeira -> caixa -> boxcar -> carro -> caracul -> cullender -> desarranjos -> gestos -> reagendamentos -> lição -> filho -> sonar -> narc -> arco -> arcada -> adenoidal -> vales -> arrendador -> sorvete -> aposta - -> betaken -> ken -> kens -> conjunto -> liquidificador -> deride -> idéia -> diácono -> con -> côncavo -> vingador -> alemão -> anemia -> miaowed -> qua -> casado -> dedutível -> blent - -> encantar ->all -> allay -> lay -> layaway -> way -> wayfarer -> reran -> correu -> rancheiro -> anunciado -> dedutível -> abençoado -> sedan - -> dançou -> cede -> descendente -> tamanduá -> denominado -> intrometido -> ômegas -> gás -> corte -> ashram -> ram -> ram -> ramble -> soprou -> lewder -> zomba -> desce -> ameaçada -> redcoat -> juramento -> aterosclerose -> sis -> sisal - -> salada -> rapaz -> escada - -> derivados -> navio -> raramente -> domínios -> inscritos -> percevejos -> insetos -> insetos -> boo -> boo -> boobed -> bedder -> deriva -> vestígios -> gesundheit -> ou -> heráldico -> dados -> quebra-gelo -> querosene -> enema -> e-mail ->doença -> entronização -> entusiasmo -> uso -> usado -> sedador -> terminador -> toreador -> dormente -> antebellum - -> lumbago -> atrás -> agonizante - -> glicogênio -> gênero -> derme -> desventuras -> rescind -> indecente -> entusiasmado -> sedativos -> vestimenta -> entusiasta -> entusiasta -> astir -> tiradas -> descendente -> antecedente -> seduzir -> calota de gelo -> capacitor -> tormento -> seduzido -> cedilha -> lhama -> amálgama -> gambit -> cadelas -> hesita - -> testemunhar -> ingrato -> ate -> ateliersgênero -> derme -> desventuras -> rescindir -> indecente -> entusiasmado -> sedativos -> vestimentas -> entusiasta -> astir -> tiradas -> descendente -> antecedente - -> seduzir -> calota de gelo -> capacitor -> tormento -> seduzido -> cedilha -> lhama -> amálgama -> gambit -> cadelas -> hesita -> testemunhar -> ingrato -> ate -> ateliersgênero -> derme -> desventuras -> rescindir -> indecente -> entusiasmado -> sedativos -> vestimentas -> entusiasta -> astir -> tiradas -> descendente -> antecedente - -> seduzir -> calota de gelo -> capacitor -> tormento -> seduzido -> cedilha -> lhama -> amálgama -> gambit -> cadelas -> hesita -> testemunhar -> ingrato -> ate -> ateliers

Mathematica 1482 1655

Algo para começar ...

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

Os links são os prefixos e sufixos de interseção das palavras.

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

Arestas são todos os links direcionados de uma palavra para outras palavras:

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

Encontre um caminho entre "emendar" e "entusiasmo".

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

Resultado (1655 palavras)

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

franquias ascensas arrendatário alugado cônjuge casados ​​deduz cesarianos bênçãos responsáveis ​​gergelim malhas hesitação ereção de ionosfera ionizador zero corroem ode odes terminações de desertores onshore minérios residem minérios idealistas de tique cócegas canção das lições música em curso instilações comícios ilegais ingerir comícios iliberales ingerir estranhos gestos respostas sesame alterar finalizar reconhece gestos uretras erupções cutâneas hesitantes anticlímax máximos imagine inebriados testados tediosamente astúcia essências cesarianas resposta lobisomens colete estimado intrometido omelete alface cessão ionização ingestão ionizante ionosferas resgate sugestão de propriedade encravada hip hippie piedade etimologista isthmuses sessões início livros resolvidos

Primeiro eu limpo a lista manualmente, excluindo tudo

• palavras com letra maiúscula
• palavras com apóstrofo
• palavras com éêèáâàö
• Palavras de 1 e 2 letras

isso me custa no máximo 2 pontos, porque essas palavras só podem estar no começo ou no final da cadeia, mas reduz a lista de palavras em 1/3 e não preciso lidar com o unicode.

Em seguida, construo uma lista de todos os pré e sufixos, encontro a sobreposição e descarto todas as palavras, a menos que o pré e o sufixo estejam no conjunto de sobreposições. Novamente, isso diminui no máximo 2 pontos da minha pontuação máxima alcançável, mas reduz a lista de palavras para um terço do tamanho original (tente executar o algoritmo na lista curta para uma possível aceleração) e as palavras restantes estão altamente conectadas (exceto cerca de 3 letras que estão conectadas apenas a si mesmas). De fato, quase qualquer palavra pode ser alcançada a partir de qualquer outra palavra por um caminho com uma média de 4 arestas.

Eu armazeno o número de links em uma matriz de adjacência, o que simplifica todas as operações e permite que eu faça coisas legais, como olhar n passos à frente ou contar ciclos ... pelo menos em teoria, já que leva cerca de 15 segundos para quadrar a matriz. isso durante a pesquisa. Em vez disso, começo com um prefixo aleatório e ando aleatoriamente, escolhendo um final uniformemente, favorecendo aqueles que ocorrem com freqüência (como '-ing') ou aqueles que ocorrem com menos frequência.
Todas as três variantes são iguais e produzem correntes na faixa 20-40, mas pelo menos são rápidas. Acho que tenho que adicionar recursão, afinal.

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

Originalmente, eu queria tentar algo semelhante a isso, mas como esse é um gráfico direcionado com ciclos, nenhum dos algoritmos padrão para Classificação Topológica, Caminho Mais Longo, Maior Caminho Euleriano ou Problema do Carteiro Chinês funciona sem grandes modificações.

E só porque parece bom, aqui está uma imagem da matriz de adjacência M, M ^ 2 e M ^ infinito (infinito = 32, depois não muda) com entradas brancas = diferentes de zero