title: Building a long chain of words

text:
# Question
Title: Building a long chain of words
This challenge is to find the longest chain of English words where the first 3 characters of the next word match the last 3 characters of the last word. You will use an common dictionary available in Linux distributions which can be downloaded here:

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

which has 99171 English words. If your local Linux `/usr/share/dict/words` is the same file (has md5sum == cbbcded3dc3b61ad50c4e36f79c37084), you can use that.

Words may only be used once in an answer.

**EDIT:** Letters must match exactly including upper/lower case, apostrophes, and accents.

An example of a valid answer is: `idea deadpan panoramic micra craftsman mantra traffic fiche` which would score 8.

The answer with the longest valid chain of words will be the winner. In the event of a tie, the earliest answer will win. Your answer should list the chain of words you have found and (of course) the program you wrote to do it.

# Answer
## Java, heuristic favouring the vertex which induces the largest graph: 1825 1855 1873

The code below runs in under 10 minutes and finds the following path:

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

```

### Core ideas

In Approximating longest directed paths and cycles, Bjorklund, Husfeldt, and Khanna, *Lecture Notes in Computer Science* (2004), 222-233, the authors propose that in sparse expander graphs a long path can be found by a greedy search which selects at each step the neighbour of the current tail of the path which spans the largest subgraph in G', where G' is the original graph with the vertices in the current path deleted. I'm not sure of a good way to test whether a graph is an expander graph, but we're certainly dealing with a sparse graph, and since its core is about 20000 vertices and it has a diameter of only 15 it must have good expansion properties. So I adopt this greedy heuristic.

Given a graph \\$G\left(V, E\right)\\$, we can find how many vertices are reachable from each vertex using Floyd-Warshall in \\$\theta\left(V^3\right)\\$ time, or using Johnson's algorithm in \\$\theta\left(V^2 lg V + VE\right)\\$ time. However, I know that we're dealing with a graph which has a very large strongly connected component (SCC), so I take a different approach. If we identify SCCs using Tarjan's algorithm then we also get a topological sort for the compressed graph \\$G\_c(V\_c, E\_c)\\$, which will be much smaller, in \\$O\left(E\right)\\$ time. Since \\$G\_c\\$ is a DAG, we can compute reachability in \\$G\_c\\$ in \\$O\left(V\_c^2 + E\_c\right)\\$ time. (I have subsequently discovered that this is hinted at in exercise 26-2.8 of CLR).

Since the dominant factor in the running time is \\$E\\$, I optimise it by inserting dummy nodes for the prefixes/suffixes. So rather than 151 * 64 = 9664 edges from words ending *-res* to words starting *res-* I have 151 edges from words ending *-res* to *#res#* and 64 edges from *#res#* to words starting *res-*.

And finally, since each search takes about 4 minutes on my old PC, I try to combine the results with previous long paths. This is much faster, and turned up my current best solution.

### Code

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

```
> 11 votes

# Answer
# Ruby, 1701

`"Del" -> "ersatz's"` (full sequence)

Trying to find the optimal solution proved too costly in time. So why not pick random samples, cache what we can and hope for the best?

First a `Hash` is built that maps prefixes to full worlds starting with that prefix (e.g. `"the" => ["the", "them", "their", ...]`). Then for every word in the list the method `sequence` is called. It gets the words that could possibly follow from the `Hash`, takes a sample of `100` and calls itself recursively. The longest is taken and proudly displayed. The seed for the RNG (`Random::DEFAULT`) and the length of the sequence are also displayed.

I had to run the program a few times to get a good result. This particular result was generated with seed `328678850348335483228838046308296635426328678850348335483228838046308296635426`.

## Script

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

```
> 6 votes

# Answer
# Score: ~~1631~~ 1662 words

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

```

You can find the whole sequence here: http://pastebin.com/TfAvhP9X

I don't have the complete source code. I was trying out different approaches. But here are some code snippets, that should be able to generate a sequence of about the same length. Sorry, it's not very beautiful.

## Code (Python):

First some preprocessing of the data.

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

```

Then I defined a recursive function (Depth first search).

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

```

Of course this takes way too long. But after some time it found a sequence with 1090 elements, and I stopped.

The next thing to do, is a local search. For each two neighbors n1,n2 in the sequence, I try to find a sequence starting at n1 and ending at n2. If such a sequence exists, I insert it.

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

```

Of course I also had to stop the program manually.
> 5 votes

# Answer
# PHP, 1742 1795

I've been messing about with PHP on this. The trick is definitely culling the list to the around 20k that are actually valid, and just throwing the rest away. My program does this iteratively (some words it throws away in the first iteration mean others are no longer valid) at the start.

My code is horrible, it uses a number of global variables, it uses way too much memory (it keeps a copy of the entire prefix table for every iteration) and it took literally days to come up with my current best, but it still manages to be winning - for now. It starts off pretty quickly but gets slower & slower as time goes on.

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

?>

```

An obvious improvement would be using an orphan word for the start & finish.

Anyway, I really don't know why my pastebin list was moved to a comment here, it's back as a link to pastebin as I've now included my code.

http://pastebin.com/Mzs0XwjV
> 5 votes

# Answer
# Score: ~~249~~ ~~500~~ 1001

> Aachen --\> hen --\> henceforward --\> ardent --\> entail --\> ail --\> ailed --\> led --\> ledger --\> gerbil --\> bilateral --\> rallying --\> ingenious --\> ousted --\> tedious --\> ouster --\> terabit --\> bit --\> bitched --\> hedgehog --\> hog --\> hogan --\> gander --\> derail --\> ailerons --\> onset --\> set --\> setback --\> acknowledgement --\> entailed --\> ledgers --\> ersatzes --\> zest --\> established --\> hedgerow --\> row --\> rowboat --\> oat --\> oaten --\> ten --\> tenable --\> bleach --\> ache --\> cheapen --\> pen --\> penalizes --\> zestful --\> fulcra --\> crab --\> rabbinical --\> calabash --\> ash --\> ashamed --\> medal --\> dale --\> ale --\> alerted --\> tediously --\> sly --\> slyest --\> establishes --\> hes --\> hesitant --\> ant --\> antacid --\> cider --\> derailed --\> ledges --\> gestated --\> tediousness --\> essay --\> say --\> saying --\> ingeniously --\> slyness --\> essaying --\> ingenuous --\> ousting --\> ingenuousness --\> essayist --\> isthmus --\> muscat --\> cat --\> cataclysmic --\> mice --\> ice --\> iceberg --\> erg --\> ergonomic --\> micra --\> crabbed --\> bed --\> bedazzles --\> lesbians --\> answer --\> were --\> ere --\> erecting --\> ingest --\> establishing --\> ingesting --\> ingestion --\> ion --\> ionization --\> ionizer --\> zero --\> erode --\> ode --\> odes --\> desalinates --\> test --\> establishment - -\> entailing --\> ingot --\> got --\> gotten --\> tenant --\> antagonist --\> isthmuses --\> sesame --\> amebas --\> basal --\> salaamed --\> medallion --\> ionizing --\> ingraining --\> ingrains --\> ins --\> insane --\> anecdotal --\> talc --\> alcohol --\> hold --\> old --\> olden --\> den --\> denature --\> urea --\> reach --\> ached --\> hedges --\> gestates --\> testable --\> bleached --\> hedging --\> ingrates --\> testament --\> entangle --\> gleamed --\> medallions --\> onshore --\> ore --\> oregano --\> anodes --\> desalinating --\> ingratiates --\> testates --\> tester --\> terabits --\> its --\> itself --\> elf --\> elfin --\> fin --\> finagle --\> gleaming --\> ingratiating --\> ingratiatingly --\> glycerin --\> rind --\> indebtedness --\> essences --\> cesareans --\> answerable --\> bleacher --\> her --\> herald --\> alder --\> derailing -- \> ingredient --\> entanglement --\> entangles --\> lesion --\> ionosphere --\> erection --\> ionospheres --\> resale --\> alerting --\> ingresses --\> sesames --\> mes --\> mesas --\> sash --\> ashcan --\> can --\> canard --\> ardor --\> dorkiest --\> estates --\> testes --\> testicle --\> cleaner --\> nerdiest --\> esteemed --\> meddles --\> lessee --\> see --\> seeded --\> dedicates --\> testicles --\> lessen --\> senates --\> testiest --\> esteeming --\> ingrown --\> own --\> owner --\> nerves --\> vesicle --\> cleanest --\> ester --\> terabytes --\> testis --\> tissue --\> sue --\> suede --\> edema --\> emaciates --\> testosterone --\> one --\> ones --\> nest --\> esthetes --\> testy --\> sty --\> styes --\> yes --\> yeshivas --\> vascular --\> larches --\> hesitatingly --\> glycerine --\> inedible --\> bleaches --\> hesitates --\> testifying --\> ingrate --\> ate --\> ateliers

Here's my code:

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

```

Edit: 1001:

http://pastebin.com/yN0eXKZm

Edit: 500:

> Aachen --\> hen --\> henceforward --\> ardent --\> entail --\> ail --\> ailed --\> led --\> ledger --\> gerbil --\> bilateral --\> rallying --\> ingenious --\> ousted --\> tedious --\> ouster --\> terabit --\> bit --\> bitched --\> hedgehog --\> hog --\> hogan --\> gander --\> derail --\> ailerons --\> onset --\> set --\> setback --\> acknowledgement --\> entailed --\> ledgers --\> ersatzes --\> zest --\> established --\> hedgerow --\> row --\> rowboat --\> oat --\> oaten --\> ten --\> tenable --\> bleach --\> ache --\> cheapen --\> pen --\> penalizes --\> zestful --\> fulcra --\> crab --\> rabbinical --\> calabash --\> ash --\> ashamed --\> medal --\> dale --\> ale --\> alerted --\> tediously --\> sly --\> slyest --\> establishes --\> hes --\> hesitant --\> ant --\> antacid --\> cider --\> derailed --\> ledges --\> gestated --\> tediousness --\> essay --\> say --\> saying --\> ingeniously --\> slyness --\> essaying --\> ingenuous --\> ousting --\> ingenuousness --\> essayist --\> isthmus --\> muscat --\> cat --\> cataclysmic --\> mice --\> ice --\> iceberg --\> erg --\> ergonomic --\> micra --\> crabbed --\> bed --\> bedazzles --\> lesbians --\> answer --\> were --\> ere --\> erecting --\> ingest --\> establishing --\> ingesting --\> ingestion --\> ion --\> ionization --\> ionizer --\> zero --\> erode --\> ode --\> odes --\> desalinates --\> test --\> establishment - -\> entailing --\> ingot --\> got --\> gotten --\> tenant --\> antagonist --\> isthmuses --\> sesame --\> amebas --\> basal --\> salaamed --\> medallion --\> ionizing --\> ingraining --\> ingrains --\> ins --\> insane --\> anecdotal --\> talc --\> alcohol --\> hold --\> old --\> olden --\> den --\> denature --\> urea --\> reach --\> ached --\> hedges --\> gestates --\> testable --\> bleached --\> hedging --\> ingrates --\> testament --\> entangle --\> gleamed --\> medallions --\> onshore --\> ore --\> oregano --\> anodes --\> desalinating --\> ingratiates --\> testates --\> tester --\> terabits --\> its --\> itself --\> elf --\> elfin --\> fin --\> finagle --\> gleaming --\> ingratiating --\> ingratiatingly --\> glycerin --\> rind --\> indebtedness --\> essences --\> cesareans --\> answerable --\> bleacher --\> her --\> herald --\> alder --\> derailing -- \> ingredient --\> entanglement --\> entangles --\> lesion --\> ionosphere --\> erection --\> ionospheres --\> resale --\> alerting --\> ingresses --\> sesames --\> mes --\> mesas --\> sash --\> ashcan --\> can --\> canard --\> ardor --\> dorkiest --\> estates --\> testes --\> testicle --\> cleaner --\> nerdiest --\> esteemed --\> meddles --\> lessee --\> see --\> seeded --\> dedicates --\> testicles --\> lessen --\> senates --\> testiest --\> esteeming --\> ingrown --\> own --\> owner --\> nerves --\> vesicle --\> cleanest --\> ester --\> terabytes --\> testis --\> tissue --\> sue --\> suede --\> edema --\> emaciates --\> testosterone --\> one --\> ones --\> nest --\> esthetes --\> testy --\> sty --\> styes --\> yes --\> yeshivas --\> vascular --\> larches --\> hesitatingly --\> glycerine --\> inedible --\> bleaker --\> keratin --\> tin --\> tincture --\> urethras --\> rascal --\> calamine --\> ineducable --\> bleakest --\> esthetic --\> tic --\> tick --\> ickiest --\> estimable --\> bleariest --\> estimator --\> tor --\> torched --\> hedonistic --\> ticker --\> kerchieves --\> vesicles --\> lessens --\> ensconced --\> cedar --\> dare --\> are --\> area --\> reachable --\> bleat --\> eat --\> eatable --\> bleeder --\> derailment --\> enter --\> term --\> ermine --\> ineffable --\> bleeped --\> pedagog --\> goggle --\> gleans --\> answered --\> red --\> redbreast --\> aster --\> termagant --\> antagonistic --\> ticket --\> kettledrum --\> rum --\> rumbas --\> basalt --\> altar --\> tar --\> tarantulas --\> lasagna --\> gnarliest --\> estrangement --\> entered --\> redcap --\> cap --\> capable --\> bleeps --\> epsilon --\> loneliest --\> estranges --\> gestured --\> redcaps --\> apse --\> pseudonym --\> nymphomania --\> niacin --\> cinchonas --\> nasal --\> salable --\> blend --\> end --\> endanger --\> geriatric --\> rice --\> icebound --\> undeceives --\> vesper --\> per --\> perambulator --\> tore --\> ores --\> resales --\> lesser --\> sera --\> era --\> eras --\> rash --\> ashen --\> henchman --\> man --\> manacle --\> cleanliest --\> estrogen --\> gendarmes --\> mescal --\> calcine --\> inefficient --\> entertainingly --\> glycerol --\> role --\> oleander --\> derangement --\> entertainment --\> entertains --\> insatiable --\> blended --\> deduced --\> cedars --\> arsenic --\> nice --\> icebox -- \> box --\> boxcar --\> car --\> caracul --\> cullender --\> deranges --\> gestures --\> reschedules --\> lesson --\> son --\> sonar --\> narc --\> arc --\> arcade --\> adenoidal --\> dales --\> lessor --\> sorbet --\> bet --\> betaken --\> ken --\> kens --\> ensemble --\> blender --\> deride --\> idea --\> deacon --\> con --\> concave --\> avenger --\> germane --\> anemia --\> miaowed --\> wed --\> wedded --\> deducible --\> blent - -\> enthrall --\> all --\> allay --\> lay --\> layaway --\> way --\> wayfarer --\> reran --\> ran --\> rancher --\> heralded --\> deductible --\> blessed --\> sedan --\> danced --\> cedes --\> descant --\> anteater --\> termed --\> meddlesome --\> omegas --\> gas --\> gash --\> ashram --\> ram --\> ramble --\> blew --\> lewder --\> derides --\> descend --\> endangered --\> redcoat --\> oath --\> atherosclerosis --\> sis --\> sisal - -\> salad --\> lad --\> ladder --\> derivatives --\> vessel --\> seldom --\> domains -- \> inscribed --\> bedbug --\> bug --\> bugaboo --\> boo --\> boobed --\> bedder --\> derives --\> vestiges --\> gesundheit --\> either --\> heraldic --\> dice --\> icebreaker --\> kerosene --\> enema --\> email --\> ailment --\> enthronement --\> enthuse --\> use --\> used --\> sedater --\> terminator --\> toreador --\> dormant --\> antebellum - -\> lumbago --\> ago --\> agonizingly --\> glycogen --\> gender --\> dermis --\> misadventures --\> rescind --\> indecent --\> enthused --\> sedatives --\> vestment --\> enthusiast --\> astir --\> tirades --\> descendant --\> antecedent --\> entice --\> icecap --\> capacitor --\> torment --\> enticed --\> cedilla --\> llama --\> amalgam --\> gambit --\> bitches --\> hesitates --\> testifying --\> ingrate --\> ate --\> ateliers
> 4 votes

# Answer
# Python : ~~1702~~ \- ~~1704~~ \- 1733 words

I used a Dict to map all the prefixes to all the words , as

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

```

**Edit** little improvement: removing all `useless` words at the beginning, if their suffixes aren't in the prefixes list (would obviously be a end word)

Then take a word in the list and browse the prefix map like a tree Node

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

```

The program need a number of words to know when stop, can be find as `1733` in the method `checkForNextWord̀`

The program need the file path as argument

Not very pythonic but I tried.

It took less than 2 min to compute this sequence : full output:

> études desalinate ate ateliers ... blest esteeming ingenuous ousters
> 4 votes

# Answer
# Mathematica ~~1482~~ 1655

Something to get started...

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

```

Links are the intersection prefixes and suffixes for words.

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

```

Edges are all the directed links from a word to other words:

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

```

Find a path between "mend" and "zest".

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

```

Result (1655 words)

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

```
> 2 votes

# Answer
# Python, 90

> upended deductibles lessee seesawed wed wedded deduces cesarians answerable blesses sesames meshes hesitation ionosphere erection ionizer zero erode ode odes deserter terminations onshore ores reside idealistic tic tickles lesson song ongoing ingrains instill illiberal rallying ingest estranges gestures responses sesame amend endives vestment entertainer nervously slyest esters ersatzes zestful fullback acknowledges gesture urethras rashes hesitant anticlimax maxima imagine inebriates tested tediously slyness essences cesareans answer werewolves vest esteemed meddlesome omelet lettuces cession ionization ionizing ingestion ionospheres rescue cueing ingrown ownership hip hippie piety etymologist isthmuses sessions onset settled ledgers

First i clean up the list manually by deleting all

* words with a Capital letter
* words with apostrophe's
* words with éêèáâàö
* 1- and 2-letter words

this costs me at most 2 points because those words can only be in the beginning or the end of the chain but it reduces the wordlist by 1/3 and i dont have to deal with unicode.

Next I construct a list of all pre- and suffixes, find the overlap and discard all words unless both the pre- and suffix is in the overlap set. Again, this shaves off at most 2 points off my maximal achievable score, but it reduces the wordlist to a third of original size (try running your algorithm on the short\_list for a possible speedup) and the remaining words are highly connected (except some 3-letter words which are connected only to themselves). In fact, almost any word can be reached from any other word through a path with an average of 4 edges.

I store the number of links in an adjacency matrix which simplifies all operations and lets me do cool stuff like looking n steps ahead or counting cycles... at least in theory, since it takes around 15 seconds to square the matrix I dont actually do this during the search. Instead i start at a random prefix and walk around randomly, either picking an ending uniformly, favoring those that occur often (like '-ing') or those that occur less often.
All three variants suck equally and produce chains in 20-40 range, but at least its fast. Guess I gotta add recursion after all.

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

```

Originally I wanted to try something similar to this but since this is a directed graph with cycles, none of the standard algorithms for Topological Sorting, Longest Path, Largest Eulerian Path or Chinese Postman Problem work without heavy modifications.

And just because it looks nice, here is a picture of the adjacency matrix M, M^2 and M^infinity (infinity = 32, it doesnt change afterwards) with white = nonzero entries
> 1 votes

---
Tags: code-challenge, combinatorics, graph-theory
---


# Question
Title: Transferring the DNA of bacteria from generations
## Introduction

Scientists have recently found a new type of bacteria that replicates in odd ways. To reproduce, two bacteria each split into 3 (for a total of 6) and pairs combine (resulting in 3 bacteria, two parents, one child). However, the bacteria can only split if it has a partner. For example, 2 bacteria split and combine into 3, 3 into 4, 4 into 6, etc. Additionally, when a bacteria splits, only one of the daughter cells combines with the other parent cell's daughter cells, and vice versa. In other words, if bacteria A and B split, the daughter cells will combine to be AA, AB, and BB.

## The Challenge

Your challenge is to make a program that accepts or generates 4 bacteria's DNA, each with a strand in a 10-bit Quaternary format. An example DNA strand could be 0123302012. When two daughter bacteria combine, the DNA is merged in a punnet-square style (the DNA can be merged in every pair or only the AB pair, your choice). Meaning that 0 is the recessive trait, 1 is the mixed trait, and 2 is the dominant trait. However, when there is a 3, it is a mutated trait (more on this later). Starting with the 4 bacteria, have your program run 20 trials (4 splitting into 6 would be the first trial). Once it is done, have the program output through STDOUT (or equivalent) each cell's DNA on a seperate line, but only from the cells generated from the 20th trial.

## Key Features

* Each trial must calculate the new number of cells and each new cell's DNA (see below).
* The program must output each 20th-trial cell's DNA (The 4046 new bacteria) each on a seperate line in STDOUT (or equivalent).
* The bacteria must each replicate in the method stated above. (A and B split into AA, AB, and BB).

### How the DNA is Passed on

The DNA is passed from the parents to child in a punnet-square style where:

* 0 is a recessive trait (rr).
* 1 is a mixed trait (Rr).
* 2 is a dominant trait (RR).

If one of the traits is a 3 (a mutation), the ending trait is decided randomly, but if both are 3,the ending trait is a 3. Parents can be decided randomly or in order (A & B, C & D, etc).

Example:

```
    |   DNA A    |   DNA B    | DNA C (Child) |
    | 0123311200 | 1203123213 |  0113012203   |

```

## Scoring

This is code golf, so shortest character count wins! For legibility, please include a version that separates the code onto multiple lines, if possible. If the challenge is not explained well or you have suggestions, post a comment!

Here is an example program (in java) that successfully completes the challenge: Ideone Link.

# Answer
> 1 votes
# CJam: 71

Golfed:

```
qS/{mr2/{_,({3*$2/{z{:~_3#){~=Z4mr?}{{[0Ymr1]=}%:+}?`}%}/}{~}?}%}K*{N}/

```

Indented and commented:

```
qS/             "Read the input and split around spaces";
{               "Loop";
  mr2/            "Shuffle the DNA strings and group into pairs";
  {               "For each pair";
    _,(             "Check if it's really a pair";
    {               "If it's really a pair AB";
      3*$2/           "Create the breeding combinations AA AB BB";
      {               "For each breeding combination";
        z               "Pair the corresponding alleles together";
        {               "For each pair of alleles";
          :~              "Map each allele (currently a string) to an int";
          _3#)            "Check if one of the alleles is a 3";
          {               "If one allele is a 3";
            ~=              "Check if both alleles are 3";
            Z               "If so, generate a 3 as the new allele";
            4mr?            "Otherwise, generate a random number from 0 to 3 as the new allele";
          }{              "If neither allele is a 3";
            {[0Ymr1]=}%     "For each allele, map 0 to 0, 1 to 0 or 1 (random), and 2 to 1";
            :+              "Add the mapped values to generate the new allele";
          }?`             "Convert the allele back to a string";
        }%              "Result: two DNA strings bred into one";
      }/              "Result: two DNA strings combined and bred into three";
    }{~}?           "If it's not a pair, just unwrap it from its group";
  }%              "Result: all pairs of DNA strings combined and bred into three";
}K*             "Result: bred for 20 generations";
{N}/            "Put a newline after each DNA string";

```

You added the stipulation that DNA is only merged punnet-square-style for "AB" bacteria after I wrote my code, but mine generates all bacteria by merging that way. Based on your description of how breeding occurs, my interpretation (which also seems to be Siddhanathan's interpretation) seemed more accurate. Talking about bacteria splitting into 3 doesn't make any sense otherwise. But I'll change things if necessary.

I also assumed that breeding pairs should be decided randomly, but that seems like a safer assumption.

# Answer
> 1 votes
# Haskell -- 349

```
import Control.Monad
import System.Random
import Data.List
a=[0,1,2,3,3,1,1,2,0,0]
b=[a,a,a,a]
f 3 _=randomRIO(0,3)
f _ 3=randomRIO(0,3)
f x y=return$div(x+y)2
z::[Integer]->[Integer]->IO[Integer]
z x y=zipWithM f x y
c=filter(\x->length x==2).subsequences
r=sequence.map(\x->z(x!!0)(x!!1)).c
y=foldr(<=<)return.replicate 20
main=y r b>>=mapM_ print

```

Try it online with nicer looking source code: http://ideone.com/9FUMLd

The online example does only till 2 instead of 20 because of ideone's time limit.

---
Tags: code-golf
---


title: Array combinatoric comparison

text:
# Question
Title: Array combinatoric comparison
# Introduction

You may remember *sudoku*, where there can only be one of each number in each row, column and block of nine. The general idea is that if the array contains but one element, you can submit that as a deterministic solution. If there are already filtered arrays (by rows, columns and 3×3 blocks) the remainder can still be deterministic. Where

* a=\[1,2\];
* b=\[1,3\];
* c=\[2,3\];
* d=\[1,2,3,4\]

d should be reduced to \[4\] as it apparently cannot be anything else.

# Challenge

Provide a sniplet that compares *n* arrays. For every X, if only X numbers appear at least once in a set of X arrays, then all those X numbers should be removed from each array not in the set. The elements are *integer numbers* ranging *\[1, n\]*.

# Winning criterion

Lowest character count.

## "I'm too young to die" version

9 arrays at most, 9 elements at most.

# Test Cases

> \[1,2\]; \[2,3\]; \[1,3\]; \[1,2,3,4\]
> \[1,2,3\]; \[2,3,4\]; \[1,5,6\]; \[2,3\]; \[1,4\]; \[1,2,3,4,6\]
>
> ## Test outputs
>
> \[1,2\]; \[2,3\]; \[1,3\]; **\[4\]**
> \[1,2,3\]; \[2,3,4\]; **\[5\]**; \[2,3\]; \[1,4\]; **\[6\]**

# Answer
# Pyth: ~~37~~ ~~29~~ 28 bytes

```
um?d|-lHl{sHsmg{kdH-dsHGtyQQ

```

Input is a list of lists like `[[1,2], [2,3], [1,3], [1,2,3,4]]`. Try it online: Pyth Compiler/Executor

## Explanation:

```
um?d|-lHl{sHsmg{kdH-dsHGtyQQ
u                          Q  G = input array
u                       tyQQ  For each H in powerset(input):
 m                     G        G = [            ...        for d in G]
  ?d               -dsH             [d if ... else d-sum(H) for d in G]
     -lHl{sH                        len(H)-len(set(sum(H)))!=0
    |                                     or
            smg{kdH                 sum(d is subset of k for k in H)>0

```
> 2 votes

# Answer
# C# - 231 characters

```
static int[][] P(int[][]a){var m=a.GetUpperBound(0)+1;var j=0;for(var i=0;i<m;i++){var u=new List<int>();for(j=0;j<=i;j++)u=u.Union(a[j]).ToList();if(u.Count()==m)for(j=0;j<m;j++)if(i!=j)a[i]=a[i].Except(a[j]).ToArray();}return a;}

```

Ungolfed and harness

```
using System.Collections.Generic;
using System.Linq;

namespace ArrayCombCompar
{
    class Program
    {
        static void Main(string[] args)
        {
            var testArray1 = new int[][] {
                new int[] {1,2},
                new int[] {2,3},
                new int[] {1,3},
                new int[] {1,2,3,4}
            };
            var testArray2 = new int[][] {
                new int[] {1,2,3},
                new int[] {2,3,4},
                new int[] {1,5,6},
                new int[] {2,3},
                new int[] {1,4},
                new int[] {1,2,3,4,6}
            };
            var result1 = P(testArray1);
            var result2 = P(testArray2);
        } // Put breakpoint here to see results

        static int[][] P(int[][]a)
        {
            var m = a.GetUpperBound(0) + 1;
            var j = 0;
            for (var i = 0; i < m; i++)
            {
                var u = new List<int>();
                for (j = 0; j <= i; j++)
                    u = u.Union(a[j]).ToList();
                if (u.Count() == m)
                    for (j = 0; j < m; j++)
                        if (i != j) a[i] = a[i].Except(a[j]).ToArray();
            }
            return a;
        }

     }
}

```
> 0 votes

---
Tags: code-golf, combinatorics, array
---


title: String Equivalence: Counting Substrings

text:
# Question
Title: String Equivalence: Counting Substrings
# Background

Two strings `s` and `t` are called `k`-Abelian equivalent (shortened to `k`-equivalent in the following) for a positive integer `k` if the following conditions hold:

* The length-`k-1` prefixes of `s` and `t` are equal.
* The length-`k-1` suffixes of `s` and `t` are equal.
* The strings `s` and `t` have the same multisets of length-`k` contiguous substrings. In other words, every string of length `k` occurs an equal number of times in `s` and `t`. Overlapping occurrences are counted as distinct.

Note that `k`-equivalent strings are always `k-1`-equivalent if `k > 1`, and the third condition implies that `s` and `t` have the same length. It is also known, and possibly useful, that the three conditions above are equivalent to the following one:

* Every non-empty string of length `k` or `k-1` occurs an equal number of times in `s` and `t`.

# An Example

For example, consider the strings `s = "abbaaabb"` and `t = "aabbaabb"`. Because the strings have the same number of each character, 4 of `a` and 4 of `b`, they are `1`-equivalent. Consider then `2`-equivalence. Their first and last characters are the same (both strings begin with `a` and end with `b`), so the first two conditions are satisfied. The length-`2` substrings of `s` are `aa` (occurs twice), `ab` (twice), `ba` (once), and `bb` (twice), and those of `t` are exactly the same. This means that the strings are `2`-equivalent. However, since their second letters are different, the strings are not `3`-equivalent.

# Input

Two alphanumeric strings `s` and `t` of the same length `n > 0`.

# Output

The largest integer `k` between `1` and `n` (inclusive) such that `s` and `t` are `k`-equivalent. If no such `k` exists, the output is `0`. In the above example, the correct output would be `2`.

# Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Crashing on malformed input is perfectly fine.

# Test Cases

```
"abc" "def" -> 0
"abbaabbb" "aabbbaab" -> 0
"abbaaabb" "aabbbaab" -> 2
"abbaaabb" "aabbaabb" -> 2
"aaabbaabb" "aabbaaabb" -> 3
"aaabbaabb" "aaabbaabb" -> 9
"abbabaabbaababbabaababbaabbabaab" "abbabaabbaababbaabbabaababbabaab" -> 9
"yzxyxx" "yxyzxx" -> 2
"xxxxxyxxxx" "xxxxyxxxxx" -> 5

```

# Answer
> 1 votes
# Pyth: ~~26~~ 22 bytes

```
lfq_TTCmmSm<>dbhkldldQ

```

Input are two strings like `"abc","def"`. Try it online: Pyth Compiler/Executor

## Explanation:

Quite some complicated code. But I'll start easy.

First we want to create all substrings of length `k` of the string `d`.

```
Sm<>dbhkld
 m      ld      apply a function ... to all elements b
                in the list [0, 1, 2, ..., len(d)-1]
   >db              take the string d starting from the position b
  <   hk            but only hk = k + 1 characters
S               Sort the resulting list.

```

For the string `"acbde"` and `k = 3` this results in `['abc', 'bde', 'cbd', 'de', 'e']`. Notice, that `'de'` and `'e'` are part of this list. This will be quite important in a bit.

I want the substrings for each `k`, one map again.

```
mSm<>dbhkldld
m          ld   apply a function (create all substrings of lenght k) to
                all elements k in the list [0, 1, 2, ..., len(d)-1]

```

For the string `"acbd"` this results in `[['a', 'b', 'c', 'd'], ['ac', 'bd', 'cb', 'd'], ['acb', 'bd', 'cbd', 'd'], ['acbd', 'bd', 'cbd', 'd']]`.

I want this for both strings, another map.

```
mmSm<>dbhkldldQ
m             Q   apply the function (see above) for all d in input()

```

`[[['a', 'b', 'c'], ['ab', 'bc', 'c'], ['abc', 'bc', 'c']], [['d', 'e', 'f'], ['de', 'ef', 'f'], ['def', 'ef', 'f']]]` for the input `"abc","def"`, and after a zip `C`, this looks `[(['a', 'b', 'c'], ['d', 'e', 'f']), (['ab', 'bc', 'c'], ['de', 'ef', 'f']), (['abc', 'bc', 'c'], ['def', 'ef', 'f'])]`.

Now comes the exciting part: We are of course only interest in the `k`s, where the substrings of both words are the same.

```
lfq_TTCmmSm<>dbhkldldQ
 f                         I filter the list for elements T, where
  q_TT                         reversed(T) == T
                           (basically T[0] == T[1])
l                          print the lenght of the resulting list.
                           (= the number of times, where the substrings of length k
                              of string 1 are equal to the substrings of
                              length k of string 2)

```

Since we also have the suffixes of length \< k in Ts, this also checks, if the suffixes are equal.

The only thing, which I don't check is, if the prefixes are equal. But as it turns out, this isn't necessary. Lemma 2.3 (4\<=\>5) of the linked paper says: If the substrings of length `k` are the same, than `pref_{k-1}(string 1) = pref_{k-1}(string 2)` is equivalent to `suff_{k-1}(string 1) = suff_{k-1}(string 2)`. Since the suffixes are equal, the prefixes are also equal.

# Answer
> 1 votes
# CJam, ~~51 49 47 41~~ 34 bytes

```
WqN/:Q0=,,{Qf{_,,\f>\)f<$}~=},+W=)

```

Just to get something started. This can surely be golfed a lot. Looking at a different algorithm too.

Input goes as the two strings without quotes on separate lines.

Example:

```
aaabbaabb
aabbaaabb

```

Output:

```
3

```

Try it online here

---
Tags: code-golf, string
---