text:
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.

What are the ways allowed to load these datas ?

You should download the word list from the dropbox link above, then process it with your program to generate the best answer you can.

Do accents matter? Also, what about words that are shorter than three letters?

Words shorter than 3 letters can't meet the 3 letter match rule, so are excluded. Letters must match including accents and upper/lower case.

Do apostrophes have to match?

Yes. Apostrophes are a letter so must match too (that of course makes these words mostly useless in this challenge).

@Sp3000 I though I agreed with you at first, but now I think it'll just take too long to find the longest path.

That is why I thought it would be a good challenge. It will take to long to find the perfect solution. I was hoping to see some clever heuristics and indexing that makes competitive solutions. My proof of concept solution sure takes a long time and only gives a mediocre answer.

I tried ignoring uncommon letters, but even ignoring words whose first three or last three letters contain the twenty least common letters, it still takes a really long time.

@KSFT Yeah I just realised knowing whether a Eulerian path exists and finding the longest path that repeats no edges are completely different things

Isn't that a Hamiltonian path?

Should it be case-sensitive?

Note: The file linked to is exactly the same as /usr/share/dict/words on Ubuntu 14.04 (verified via diff), so no need to download it if that's what you're running.

@KSFT yes, it is case-sensitive.

@Doorknob, I deliberately supplied my version of the file, as different Linux distros and OSX use different word lists. If you do use your local word list, please ensure it is the 99171 word version, so we keep the challenge fair.

If you provide the md5sum of the file, that would allow Linux users to easily check whether they already have it.

Good idea Peter. Added to question.

This is an NP-hard problem. I don't like problems where the solution is to throw your computer on the problem and wait.

The approach here is to come up with some clever code that creates a good result (not perfect) in a reasonable time. My test program makes 1400 word chains in a few seconds.

My analysis of the graph is that there's only one non-trivial strongly connected component, and the longest path in the compressed graph is of length 6. By considering the minimum for each three-letter sequence of words in the SCC with the sequence as a prefix and a suffix, I get an upper bound of 4655 on the longest chain of words, so there might still be a lot of room to improve on the current best of 1733.

The words file contains acronyms and proper nouns, which I think don't count as words?

I agree there are some odd 'words' in there, but all I really needed was a large set of strings to use in this puzzle. Just treat all these 'words' as strings to link.

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

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

I didn't think of randomly sampling the possibilities for the next word! I'm using that idea!

How long did this take to run?

I didn't time it, but I estimate about 15-20 minutes (I let it run over dinner).

My Python one is still building the dict (hash)...

Building the dictionary should be fast (a single iteration trough all words). Ruby reports 0.0996 seconds.

Ahhhh... That's what I was doing wrong! I was doing about fifty thousand iterations through all words.

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.

How long it takes to get your result ?

About an hour to generate the 1090 sequence, and another hour to do the local search.

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

I included the code from the Pastebin in your answer, then we don't have to rely on an external domain; in case Pastebin goes down, we can still see your code here.

Well, I was happy to have the winning answer for a short while at least.
Nice work Peter Taylor...

Oh, now I see that I shouldn't have added the list to your answer; I was a bit confused and I mixed up code and word list, and included the list in your answer. I'm sorry for that.

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

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

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

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

So your score is 90 ? While we already have 1700+ entries .. Anything I am missing ?

First of all I'm still working on it, but apart from that - It seemed like a good idea, I tried it, it failed. If anything, this will stop people from wasting time using the same approach

Heh :) Keep up the positive attitude :) Hope to see this get better results.

"those words can only be in the beginning or the end of the chain" is incorrect. The largest connected component in the graph includes words such as boutonnières which have an accented character, but not in the prefix or suffix. It only affects a dozen or so words, but one of them might be a key link.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Solve a 2x2 Eigensystem
For those with a little linear algebra background, the challenge is as simple as this: determine the eigenvalues and eigenvectors of a given complex 2x2 matrix. You may skip ahead to The Challenge for I/O details, etc. For those who need a little refresher on eigensystems, read on.
Background
The characteristic equation of a matrix \$A\$ is defined by
$$\det| A - λI | = 0$$
where \$λ\$ is a complex (scalar) parameter, \$I\$ is the identity matrix and \$\det|...|\$ is the determinant. The left-hand side evaluates to a polynomial in \$λ\$, the characteristic polynomial, which is quadratic in the case of 2x2 matrices. The solutions of this characteristic equation are the eigenvalues of \$A\$, which we will denote as \$λ_1\$ and \$λ_2\$.
Now the eigenvectors \$v_i\$ of \$A\$ satisfy
$$Av_i = λ_iv_i$$
For each \$λ_i\$, this gives you a system of two equations in two unknowns (the components of \$v_i\$), which can be solved quite easily. You will notice that the system is actually underspecified, and the magnitude of the eigenvectors are not determined by the equations. We will usually want the eigenvectors to be normalised, that is \$\sqrt{|x|^2 + |y|^2} = 1\$, where \$x\$ and \$y\$ are the vector components, \$|x|^2\$ is \$x\$ multiplied by its complex conjugate.
Note that the eigenvalues may be degenerate, i.e. \$λ_1 = λ_2\$. In this case, you may or may not be able to satisfy the single system of equations with two linearly independent eigenvectors.
The Challenge
Given a 2x2 matrix with complex elements, determine its two (possibly identical) eigenvalues and a normalised eigenvector for each eigenvalue. The resulting numbers must be accurate to at least 3 (decimal) significant digits. You may assume that the real and imaginary parts of any matrix element is in the range \$[-1,1]\$.
You may write a function or a program, taking input via STDIN, command-line argument, prompt or function argument. You may output the result to STDOUT, a dialog box or as the function return value.
You may use any convenient (but unambiguous) string or list format for input and output. You can also choose between pairs of floats or complex types to represent the individual numbers.
You must not use built-in functions for solving eigensystems (like Mathematica's Eigenvectors or Eigensystem) or equation solvers.
This is code golf, so the shortest answer (in bytes) wins.
Examples
Each example is three lines: the input, the eigenvalues and the corresponding eigenvectors in the same order. Note that the eigenvectors are only determined up to their phase, and that in the case of degenerate eigenvalues, the eigenvectors may actually be arbitrary (as in the first example).
[[1.0, 0.0], [0.0, 1.0]]
[1.0, 1.0]
[[1.0, 0.0], [0.0, 1.0]]

[[0.0, 0.4], [-0.1, -0.4]]
[-0.2, -0.2]
[[0.894427, -0.447214], [0.894427, -0.447214]]

[[0.3, 0.1], [0.4, -0.9]]
[-0.932456, 0.332456]
[[-0.0808731, 0.996724], [0.951158, 0.308703]]

[[0.5, -1.0], [0.8, -0.5]]
[0.74162i, - 0.74162i]
[[0.745356, 0.372678 - 0.552771i], [0.745356, 0.372678 + 0.552771i]]

[[-0.0539222 + 0.654836i, -0.016102 + 0.221334i], [0.739514 - 0.17735i, -0.0849216 + 0.77977i]]
[0.238781 + 0.984333i, -0.377625 + 0.450273i]
[[0.313668 + 0.322289i, 0.893164], [-0.236405 - 0.442194i, 0.865204]]

[[-0.703107 - 0.331792i, 0.286719 - 0.587305i], [-0.418476 + 0.396347i, -0.885934 + 0.50534i]]
[-1.13654 - 0.32678i, -0.4525 + 0.500329i]
[[0.833367, -0.248208 - 0.493855i], [-0.441133 - 0.408236i, 0.799215]]

[[-0.156312 + 0.788441i, 0.045056 - 0.579167i], [0.130741 - 0.97017i, 0.049183 - 0.590768i]]
[-0.181759 + 1.11738i, 0.0746298 - 0.919707i]
[[0.86955, -0.493846 + 0.000213145i], [0.318856 - 0.0181135i, 0.94763]]

MATLAB, 91
A standard technique to obtain a normalized vector and remove the useless degree of freedom is representing the elements of the vector as the cosine and sine of some angle.
I originally tried to code in Python, but its math handling proved to be too brain-damaged. Its math functions refused to accept complex values, and it does not understand that floating-point division by zero is OK.
function[]=f(a,b,c,d)
L=(a+d+[1,-1]*((a-d)^2+4*b*c)^.5)/2
t=atan((L-a)/b);v=[cos(t);sin(t)]

First the two eigenvalues are printed under the heading L =. Then two column vectors are printed under the corresponding values of L, under v =. The code may fail to give linearly independent vectors in cases where it is possible to do so (such a program normally would be considered broken), but Martin said it is not required.

Python 2, 198 bytes
a,b,c,d=input()
H=(a+d)/2
D=(H*H-a*d+b*c)**.5
X,Y=H+D,H-D
p,q,r,s=[[1,0,0,1],[b,X-a,b,Y-a],[X-d,c,Y-d,c]][2*(c!=0)or(b!=0)]
A=abs
V=A(A(p)+A(q)*1j)
W=A(A(r)+A(s)*1j)
print[X,Y],[[p/V,q/V],[r/W,s/W]]

Input is a flat list of 4 complex numbers via STDIN, e.g.
[0.0+0j, 0.4+0j, -0.1+0j, -0.4+0j]

Note that Python uses j instead of i for complex numbers.
Output is two lists, the first containing the eigenvalues and the second containing the eigenvectors, e.g.
[(-0.2+0j), (-0.2+0j)]
[[(0.8944271909999159+0j), (-0.4472135954999579+0j)], [(0.8944271909999159+0j), (-0.4472135954999579+0j)]]

(newline inserted for clarity)

APL (Dyalog Classic), 59 bytes
{a b c d←⍵⋄l,2 1∘.○¯3○b÷⍨a-⍨l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d}

Derivation of formula for eigenvalues:
$$
det|A-\lambda I|=0
\\
det\left|\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}-
\begin{pmatrix}
\lambda & 0 \\
0 & \lambda
\end{pmatrix}\right|=0
\\
det\left|\begin{pmatrix}
a-\lambda & b \\
c & d-\lambda
\end{pmatrix}\right|=0
\\
(a-\lambda)(d-\lambda)-bc=0
\\
\lambda^{2}-(a+d)\lambda+ad-bc=0
\\
\lambda=\frac{a+d\pm \sqrt{(a+d)^{2}-4(ad-bc)}}{2}
\\
\lambda=\frac{a+d\pm \sqrt{a^{2}+2ad+d^{2}-4ad+4bc}}{2}
\\
\lambda=\frac{a+d\pm \sqrt{a^{2}-2ad+d^{2}+4bc}}{2}
\\
\lambda=\frac{a+d\pm \sqrt{(a-d)^{2}+4bc}}{2}
$$
As for the eigenvectors... everything I tried myself was longer than the MATLAB answer that I don't really understand yet. May add another explanation here at some point.
The code is then a simple implementation of these formulae.
{a b c d←⍵⋄l,2 1∘.○¯3○b÷⍨a-⍨l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d}
 a b c d←⍵                                                    ⍝ assign variable names
                            l←2÷⍨a+d(+,-).5*⍨(4×b×c)+×⍨a-d    ⍝ formula for the eigenvalues
             2 1∘.○¯3○b÷⍨a-⍨l                                 ⍝ formula for the eigenvectors
           l,                                                 ⍝ append eigenvalues

Try it online!

Lua, 462 455 431 427 bytes
There is no built-in complex math in Lua.  No vector operations either.  All had to be rolled by hand.
a,b,c,d,e,f,g,h=...x=math.sqrt z=print i=a-g j=b-h
k=(i^2-j^2)/2+2*(c*e-d*f)m=x(k^2+(i*j+2*(c*f+d*e))^2)n=x(m+k)o=x(m-k)i=(a+g+n)/2
j=(b+h+o)/2 k=(a+g-n)/2 l=(b+h-o)/2 z(i,j,k,l)q=c^2+d^2 r=e^2+f^2 s=q+r if s==0
then z(1,0,0,0,0,0,1,0)else if r==0 then m,n,o,p=c,d,c,d c,d=i-a,j-b e,f=k-a,l-b
u=x(q+c^2+d^2)v=x(q+e^2+f^2)else m,n=i-g,j-h o,p=k-g,l-h c,d=e,f
u=x(r+m^2+n^2)v=x(r+o^2+p^2)end z(m/u,n/u,o/v,p/v,c/u,d/u,e/v,f/v)end

Run from the command-line with the following arguments:
lua eigen.lua Re(a) Im(a) Re(b) Im(b) Re(c) Im(c) Re(d) Im(d)

Produces the following output:
Re(lambda1) Im(lambda1) Re(lambda2) Im(lambda2)
Re(v11) Im(v11) Re(v12) Im(v12) Re(v21) Im(v21) Re(v22) Im(v22)

...for a,b,c,d the 4 components of the input matrix, lambda1 and lambda2 the two eigenvalues, v11,v21 the first unit eigenvector, and v12,v22 the second unit eigenvector.
For example,
lua eigen.lua 1 0  1 0  1 0  0 0

...produces...
1.6180339887499 0   -0.61803398874989   0
0.85065080835204    0   -0.52573111211913   0   0.52573111211913    0   0.85065080835204    0

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Trucks in a parking lot
There are P parking spaces in a parking lot, though some spaces are occupied by cars represented by octothorpes # while the free spaces are dots .. Soon there arrive T trucks, each of which will take up exactly L consecutive spaces. The trucks don't have to be parked next to each other.
Your task is to create a program that will find the smallest number of cars that need to be removed in order to park all of the trucks. There will always be enough spaces to fit all of the trucks, meaning T*L<P
Input
In the first row there will be three integers, P, T and L separated by spaces. In the second row there will be a string of P characters representing the parking lot in its initial state.
Output
In the first and only line your program should print out the smallest number of cars that need to be removed in order to park all of the trucks.
Test cases
Input:
6 1 3
#.#.##
Output: 1
Input:
9 2 3
.##..#..#
Output: 2
Input:
15 2 5
.#.....#.#####.
Output: 3
Shortest code wins. (Note: I'm particularly interested in a pyth implementation, if one is possible)

Python 2, 154 bytes
I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
print D[T*L]

A straightforward DP approach. A fair chunk of the program is just reading input.
Explanation
We calculate a 2D dynamic programming table where each row corresponds to the first n parking spots, and each column corresponds to the number of trucks (or parts of a truck) placed so far. In particular, column k means that we've placed k//L full trucks so far, and we're k%L along the way for a new truck. Each cell is then the minimal number of cars to clear to reach the state (n,k), and our target state is (P, L*T).
The idea behind the DP recurrence is the following:

If we're k%L > 0 spaces along for a new truck, then our only option is to have come from being k%L-1 spaces along for a new truck
Otherwise if k%L == 0 then we have either just finished a new truck, or we'd already finished the last truck and have since skipped a few parking spots. We take the minimum of the two options.

If k > n, i.e. we've placed more truck squares than there are parking spots, then we put ∞ for state (n,k). But for the purposes of golfing, we put k since this is the worst case of removing every car, and also serves as an upper bound.
This was quite a mouthful, so let's have an example, say:
5 1 3
..##.

The last two rows of the table are
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]

The entry at index 2 of the second last row is 2, because to reach a state of 2//3 = 0 full trucks placed and being 2%3 = 2 spaces along for a new truck, this is the only option:
  TT
..XX

But the entry at index 3 of the second last row is 1, because to reach a state of 3//3 = 1 full trucks placed and being 3%3 = 0 spaces along for a new truck, the optimal is
TTT
..X#

The entry at index 3 of the last row looks at the above two cells as options — do we take the case where we are 2 spaces along for a new truck and finish it off, or do we take the case where we have a full truck already finished?
  TTT            TTT
..XX.     vs     ..X#.

Clearly the latter is better, so we put down a 1.
Pyth, 70 bytes
JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ

Basically a port of the above code. Not very well golfed yet. Try it online
Expanded
Jmvdczd              J = map(eval, input().split(" "))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
>                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]=="#")
>%hT@J2Z                                                           (T+1)%J[2]>0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Now, if only Pyth had multiple assignment to >2 variables...

I was doing something completely different, I think.. but if you have the time, you can tell me where I can cut down on the code (honestly I'd love a one line solution with just a print statement.. dreams dreams...)
P,K,L=map(int,input().split())
Q=list(input()) l=[(L,0)]*K for j in range(len(Q)-L):     if Q[j:j+L].count('#')<l[i][0]:         l[i]=Q[j:j+L].count('#'),j del Q[l[i][1]:l[i][1]+L] print(sum([x[0]for x in l]))

@EtaoinShrdlu Might be easier if you put the code up somewhere like Pastebin so the indentation's correct. From what I can see though that looks like Python 3, and an  immediate saving is Q=list(input()) -> *Q,=input()

yeah, I tried to make this cooperate, but it just didn't want to. didn't really think of pastebin though heh

here it is http://pastebin.com/ugv4zujB

@EtaoinShrdlu I'm not sure how your logic works, but some other things you can do are 1) Store Q[j:j+L].count('#') as a variable, 2) x=l[i][1];del Q[x:x+L],

Haskell, 196 characters
import Data.List
f=filter
m=map
q[_,t,l]=f((>=t).sum.m((`div`l).length).f(>"-").group).sequence.m(:".")
k[a,p]=minimum.m(sum.m fromEnum.zipWith(/=)p)$q(m read$words a)p
main=interact$show.k.lines

Runs all examples
& (echo 6 1 3 ; echo "#.#.##" )  | runhaskell 44946-Trucks.hs
1

& (echo 9 2 3 ; echo ".##..#..#" )  | runhaskell 44946-Trucks.hs
2

& (echo 15 2 5 ; echo ".#.....#.#####." )  | runhaskell 44946-Trucks.hs
3

Somewhat slow: O(2^P) were P is the size of the lot.
Probably plenty left to golf here.