Building a long chain of words (PPCG code golf challenge)

result.txt

["Del", "Delmar", "mar", "mariachi", "chickpea", "pea", "peahen", "henpecking", "ingraining", "ingratiated", "tedious", "ousters", "ersatzes", "zest", "estranging", "ingenuously", "sly", "slyness", "essayist", "isthmus", "mushing", "ingredient", "entertainment", "entryway", "waywardness", "essences", "cession", "ion", "ionization", "ionizer", "zeros", "roses", "sesame", "amelioration", "ionosphere", "erection", "ionospheres", "resale", "alerted", "tediously", "slyest", "establishment", "entrenchment", "entombed", "bedevilment", "entailing", "inglorious", "ousting", "ingested", "tediousness", "essay", "saying", "ingrown", "ownership", "hippie", "piercingly", "glycerin", "ringing", "ingrains", "insurgent", "entertainingly", "glycerol", "rolling", "ingenuousness", "essaying", "ingenuous", "ouster", "terracing", "ingesting", "ingratiating", "ingestion", "ionizing", "ingot", "got", "gotten", "tensing", "ingrates", "testable", "blest", "estimations", "onshore", "ore", "ores", "restructure", "urea", "rears", "arsenic", "nicking", "ingest", "esteemed", "meditations", "onset", "setback", "acknowledgement", "enterprising", "ingratiatingly", "glycogen", "generalissimos", "mosses", "sesames", "mescal", "calorific", "fiche", "checkering", "ingresses", "session", "ionizes", "zestful", "fulcrum", "rumbas", "baste", "stewed", "wedges", "gesundheit", "either", "herbal", "ballerina", "inapt", "aptitudes", "destitute", "utensil", "silences", "cesareans", "answer", "were", "ere", "erecting", "ingratiates", "testicles", "lesbians", "answered", "redder", "derringer", "germicidal", "dale", "ales", "lest", "established", "hedges", "gesticulates", "testiest", "estrangement", "entrenched", "hedonistic", "tic", "tickle", "kleptomania", "niacin", "cinctures", "resonator", "torpid", "pidgin", "gingham", "hamstrung", "ungrateful", "fulminates", "testates", "testes", "test", "estimator", "torus", "russet", "settlement", "entrenches", "hesitatingly", "glycerine", "inexorable", "bleeder", "dermis", "misbegotten", "tenet", "nethermost", "osteoporosis", "sisterhood", "oodles", "lessen", "sent", "entangled", "ledges", "gestures", "resemble", "bled", "led", "ledger", "geriatric", "riced", "cedilla", "llanos", "nosiest", "estimable", "blent", "entirety", "etymological", "calisthenic", "nick", "ickiest", "estimates", "testosterone", "oneself", "elf", "elfin", "finagle", "gleans", "answerable", "blew", "lewdest", "estates", "testament", "entertains", "inspector", "torment", "entreaty", "atypical", "callipered", "redistribute", "uterus", "rushed", "hedgerow", "rowdiest", "estrogen", "gentlest", "esthetes", "testicle", "clearest", "establishes", "hesitant", "antihistamine", "inequitable", "bleaches", "hesitates", "testy", "sty", "stylus", "lustful", "fulfill", "illustrator", "tornados", "dosed", "sedatest", "estranges", "gestates", "testis", "tissue", "suede", "edema", "emancipator", "tor", "tortured", "redeemable", "blend", "endured", "redid", "did", "didactic", "tickles", "lessens", "ensure", "urethras", "rashest", "ester", "terrace", "acerbic", "bicep", "cephalic", "licenced", "ceded", "dedicates", "tester", "terraced", "cedes", "deserves", "vesicles", "lessee", "seethed", "hedgehog", "hogwash", "ashram", "ramp", "ample", "pledges", "gestured", "redraw", "rawer", "werewolves", "vessel", "seltzer", "zero", "erotic", "ticket", "kettledrum", "rumored", "redressed", "sedan", "danker", "kerosine", "ineducable", "bleariest", "esthetic", "ticker", "keratin", "tin", "tinctured", "redcoat", "oath", "atherosclerosis", "sisal", "salamander", "derailment", "enticed", "cedillas", "lasagna", "gnash", "ashy", "shyster", "terrains", "installment", "entrapment", "entrap", "rapes", "pestles", "lessor", "sorrowful", "fulfilment", "entanglement", "entourage", "agendas", "dash", "ashtray", "ray", "rayon", "yon", "yonder", "derides", "destine", "inestimable", "blended", "deduced", "cedars", "arson", "son", "sonatas", "taste", "steins", "insectivores", "reschedules", "lesser", "servicewomen", "men", "menage", "agent", "entice", "iceberg", "erg", "ergonomic", "microcosm", "osmosis", "sis", "sister", "terrible", "blender", "derivable", "bleat", "eatables", "lesson", "songster", "terrapin", "pins", "insides", "deserter", "terser", "serapes", "pesky", "skyscraper", "peroxided", "deducible", "bleacher", "hermaphrodite", "iterator", "tortoiseshell", "elliptical", "calculus", "lusher", "heroins", "inscribes", "bespoken", "kens", "enslavement", "entrapped", "pedigree", "reenter", "terminological", "calf", "alfresco", "scoffed", "fedora", "orangutang", "angoras", "rasped", "pedicured", "redolent", "entreat", "eat", "eatable", "bleach", "achiever", "verdigris", "risky", "skydives", "vesicle", "cleric", "ricochet", "heterodoxy", "oxyacetylene", "enemas", "masseuse", "useable", "bleeps", "epsilon", "longhair", "aircraft", "aftershave", "avenger", "germane", "anemic", "microscope", "operable", "bleaker", "kerchieves", "vesper", "permit", "mitten", "tenpins", "insures", "resounded", "deductible", "blessed", "sedatives", "vestment", "entertainer", "nerves", "vestry", "tryout", "outrider", "derail", "ailment", "enthronement", "entrepreneur", "euros", "roster", "terminator", "torpor", "pored", "redcap", "caprice", "iced", "cedar", "dare", "area", "rearmost", "ostensible", "bleeped", "pedagogue", "guessed", "sediment", "entered", "redden", "denizens", "ensured", "rediscovered", "redevelopment", "enthuse", "use", "used", "seducer", "cervical", "calliope", "opera", "eras", "rasher", "herbivores", "resound", "undermost", "osteopathy", "thymus", "muslin", "linchpins", "insider", "derrières", "restructures", "restore", "oregano", "anorak", "rakes", "kestrel", "relinquishment", "enticement", "enthusiast", "astronaut", "autobiographical", "calibrator", "tormenter", "term", "ermine", "inexpedient", "entangle", "gleeful", "fulfillment", "entrant", "antlered", "redeploys", "oyster", "terrapins", "inscribed", "bedsides", "descender", "derangement", "entombment", "enthrall", "allowed", "wedder", "deride", "ideogram", "rampart", "art", "artisan", "sandman", "manslaughter", "termini", "initiator", "tortures", "restful", "fulcra", "craven", "venom", "nominee", "needful", "fulsome", "omen", "menopause", "user", "serpentine", "inertia", "tiaras", "raster", "terabit", "bitmap", "map", "mapped", "pedant", "antigen", "genome", "omegas", "gastronomical", "calipered", "redeployment", "enthused", "sedater", "termed", "medieval", "valet", "lettered", "redevelop", "lopped", "pedometer", "termite", "item", "temper", "perspired", "redskin", "kingpin", "pineapple", "plentiful", "fulfil", "filter", "termagant", "antelopes", "pesticides", "despoil", "oilskin", "kinship", "hip", "hippopotami", "amid", "midpoint", "intrinsic", "sickbed", "bedraggle", "glen", "lenient", "entomb", "ombudsmen", "mend", "endeared", "redeemed", "mediocre", "credit", "dithered", "redefine", "inexact", "act", "actor", "torturer", "reran", "ransom", "sombreros", "rosins", "instant", "antigens", "enslave", "averred", "redrew", "rewires", "resonant", "antebellum", "lumbered", "redraft", "aftercare", "areas", "eastward", "ardor", "dormant", "anthropological", "caloric", "rickshas", "hasp", "aspens", "ensures", "reset", "settee", "teeth", "ether", "heraldic", "dice", "icecap", "caped", "pedlar", "larval", "valor", "lordship", "hippos", "posher", "hereupon", "pondered", "red", "reddens", "ensign", "ignorant", "antique", "queens", "ensnared", "redesign", "ignores", "result", "ultra", "transcribed", "bedside", "ideograph", "aphid", "hidden", "dentine", "inefficient", "entitlement", "entomological", "call", "allured", "rediscover", "vertical", "callow", "lowland", "androgen", "generator", "tortillas", "lass", "asset", "set", "setups", "upstart", "artifice", "icebound", "underscored", "redundant", "antidepressant", "antipasto", "stooped", "pederast", "astringent", "entwine", "inelegant", "antiparticle", "clergywomen", "menace", "ace", "acetaminophen", "hen", "henchmen", "menthol", "holdups", "upshot", "hot", "hotbed", "bedtimes", "messenger", "gerbil", "billfold", "old", "olden", "denim", "nimbus", "busboy", "boyfriend", "endeavor", "vortex", "text", "extravagant", "anticlimax", "maxima", "imam", "mammography", "physical", "calendar", "dared", "redeveloped", "pediatric", "rickshaw", "hawser", "serape", "aped", "pedagogical", "calliper", "persecutor", "toreador", "dormer", "merchantmen", "menhadens", "ensnares", "restaurant", "antipastos", "tossups", "upside", "ides", "desires", "reside", "identical", "caliber", "bereave", "aver", "verandah", "dahlia", "liaison", "sonar", "narc", "arc", "archbishop", "hopped", "pederasty", "stymie", "miens", "ensnare", "ares", "resides", "describes", "bestow", "township", "hipped", "pedestal", "talon", "longshoreman", "mandarins", "insured", "redeemer", "merchantman", "manufactured", "redound", "underarm", "armlet", "letterbox", "boxcar", "carpel", "pellagra", "grammar", "marmot", "motorcar", "carpet", "pet", "petrochemical", "callus", "lush", "ushered", "redskins", "insulator", "tortilla", "llamas", "mason", "sonnet", "nether", "herald", "alderwoman", "mane", "anew", "newborn", "ornamental", "tall", "allegros", "rosin", "sinecures", "resumes", "mesas", "sash", "ashcan", "canton", "tonic", "nicer", "cervix", "vixen", "xenophobic", "bicuspid", "pidgins", "inspired", "redbreast", "astound", "undershot", "hotshot", "hotel", "telegraphic", "hiccuped", "pedagog", "goggle", "glee", "leech", "echelon", "lonesome", "omelet", "letups", "ups", "upsides", "descant", "antiwar", "war", "wardrobes", "besom", "sombrero", "erodes", "despair", "airplane", "anemia", "miasma", "small", "all", "allover", "vertebra", "bragger", "germicide", "ideas", "easel", "selector", "torrid", "rid", "ride", "idea", "dealership", "hipper", "pericardia", "diarrhea", "heaven", "vendettas", "tasty", "styes", "yes", "yeshivoth", "other", "heroin", "oink", "inkblot", "lot", "lotus", "tussle", "slenderer", "reruns", "unstrung", "ungrammatical", "calicos", "cosign", "ignoramus", "musical", "calico", "icon", "conniver", "verandas", "dashikis", "kismet", "meteoric", "rice", "icebox", "boxer", "xerography", "phylum", "lumber", "beret", "retriever", "vertex", "textures", "rescind", "indicator", "torque", "queerer", "rerun", "runway", "wayside", "ideological", "calk", "alkalis", "lissom", "somehow", "howsoever", "verbenas", "nasal", "salsas", "sass", "assemblyman", "manic", "nicknamed", "medulla", "llano", "anon", "nonsensical", "calabash", "ashen", "henchman", "maniacal", "calmed", "medic", "dickey", "key", "keyword", "ordains", "inspires", "resin", "sin", "sins", "insecticides", "described", "bedbug", "bug", "bugle", "gleamed", "mediator", "tort", "orthodontia", "tiara", "arabesque", "queasy", "asymmetrical", "calculator", "tornado", "adores", "resort", "orthodoxy", "oxygen", "generic", "richer", "heretical", "calm", "almanac", "nachos", "hospital", "talisman", "mannequins", "install", "allow", "low", "lowbrow", "row", "rowel", "welcomed", "medullas", "last", "astrological", "calligraphy", "physiological", "calif", "lifer", "fer", "fervid", "videotape", "ape", "apertures", "resultant", "anthem", "hem", "hemispherical", "calligrapher", "heros", "rosebud", "bud", "budget", "get", "getaway", "waylaid", "aides", "desktop", "topple", "pleas", "easy", "asymmetric", "ricksha", "shares", "resend", "end", "endear", "earthenware", "arena", "enamel", "melon", "longboat", "oat", "oaten", "tenant", "anther", "herbicides", "descend", "endemic", "microfilmed", "media", "diadem", "demographer", "herpes", "pesetas", "tassel", "selectman", "mankind", "indignant", "antipasti", "still", "ill", "illegal", "gala", "alas", "laser", "server", "vernacular", "larger", "germicides", "despot", "potpie", "pie", "piebald", "alderwomen", "menswear", "earwax", "waxen", "xenophobia", "biathlon", "longshoremen", "menhaden", "denatures", "resistant", "antitoxins", "insignificant", "antihero", "erode", "odes", "descendant", "antiperspirant", "antipodes", "descry", "crystal", "talc", "alcoholic", "licensee", "seesaw", "sawmill", "illicit", "citrus", "rustproofed", "fed", "fedoras", "rash", "ash", "ashamed", "mediaeval", "valiant", "anthropomorphic", "hiccup", "cupolas", "lassie", "sierras", "raspy", "spy", "spyglass", "assures", "restart", "arthropod", "pod", "podia", "dialectal", "tallyhos", "hostel", "telescopic", "picnic", "nickname", "amebic", "bicycle", "clef", "leftover", "versus", "sushi", "shit", "hither", "heraldry", "drywall", "alludes", "desideratum", "tumid", "midshipmen", "mendicant", "antithetical", "calmer", "merman", "manager", "gerund", "undercover", "vertebras", "rasp", "asp", "aspirins", "insouciant", "antiaircraft", "aft", "aftertaste", "steeper", "perfidy", "idyllic", "licit", "citronella", "llama", "amalgam", "gamesmanship", "hippopotamus", "mushroomed", "medical", "caliper", "perjures", "restraint", "interstellar", "larkspur", "pursuant", "ant", "anthill", "illogical", "calfskin", "kind", "inductee", "tee", "teethe", "thermal", "malt", "altar", "taro", "around", "underwear", "ear", "earlobes", "bestowal", "walkout", "outclass", "assemblymen", "menu", "enures", "resins", "insulin", "lintel", "telephotos", "tossup", "superabundant", "antelope", "open", "penicillin", "linemen", "menopausal", "salespeople", "plectrum", "rumor", "mortgagor", "gores", "reshuffle", "flee", "lee", "leeway", "waylay", "lay", "laywoman", "mandolins", "insofar", "far", "farther", "hereabout", "outgrew", "rewritten", "tensor", "sorbet", "bet", "betrothal", "halos", "loser", "sermon", "mongrel", "relabel", "bellhop", "hopper", "pertains", "insane", "anecdotal", "talk", "alkali", "alit", "lithographer", "herdsman", "manufactures", "respires", "restrains", "insular", "larvas", "vast", "astrakhan", "handmaiden", "den", "dentin", "tint", "intercessor", "sorghum", "humid", "midyear", "earldom", "dominos", "nosedove", "overgrew", "rewound", "undeveloped", "pedicures", "resolver", "vermin", "minaret", "retrodden", "denser", "servicewoman", "manor", "northbound", "underwritten", "tend", "endorser", "serviceman", "mangos", "gossamer", "meringue", "guesser", "sera", "eraser", "serum", "rumple", "plea", "lea", "leach", "ache", "checkout", "outlay", "layoff", "offal", "falcon", "con", "concoct", "octet", "tetrahedra", "drachmai", "maintains", "insult", "ultrasonic", "niche", "cheddar", "dart", "artificer", "cerebra", "brass", "assault", "ultraviolet", "let", "lethal", "hall", "allegro", "grotesque", "questionnaires", "restores", "resold", "oldie", "die", "diesel", "selfsame", "amebas", "basil", "silencer", "ceramic", "microprocessor", "sort", "orthopedic", "dictum", "tumult", "ultrasound", "underclassman", "mannikins", "instep", "tepee", "peeper", "persimmon", "monocle", "cleaver", "verbena", "enamor", "mortar", "tar", "tarmac", "macroscopic", "picayune", "uneaten", "tenor", "normal", "mall", "allay", "laypeople", "pleat", "eaten", "tenpin", "pinkeye", "eyeball", "allergen", "gentleman", "mangrove", "overachiever", "verbal", "ballpoint", "interloper", "periodic", "dickie", "kielbasas", "sashay", "hay", "hayloft", "oft", "often", "tenon", "nonbeliever", "verbatim", "timbre", "brethren", "renewal", "wallpaper", "performer", "merinos", "nostrum", "rum", "rumpus", "pussycat", "catamaran", "rang", "angstrom", "romper", "per", "persuades", "desperado", "adopt", "opt", "optimum", "mum", "mummer", "merino", "inopportune", "unethical", "calliopes", "peso", "esophagus", "gusto", "stovepipe", "ipecac", "cache", "checkpoint", "intercom", "compound", "underplay", "layman", "mantel", "telecast", "astronomic", "microfiche", "chessman", "mandolin", "linear", "earwig", "wigwam", "wampum", "pummel", "melanin", "ninjas", "jasper", "perusal", "saltpetre", "trend", "endow", "downplay", "layout", "outwit", "wit", "withdrawal", "walleye", "eye", "eyes", "yesterday", "day", "daybed", "bed", "bedpan", "pandemic", "microbes", "bestir", "tiro", "ironclad", "ladybug", "bugaboo", "boo", "bootstrap", "rapper", "perturb", "urban", "ban", "banana", "anaemia", "miasmas", "mascot", "cot", "cotyledon", "don", "donut", "nutmeg", "meg", "megalopolis", "listen", "tendon", "donor", "northeast", "astir", "tiros", "rostra", "transom", "sombre", "breathe", "theatre", "treetop", "topic", "pickerel", "relieve", "even", "ventricle", "clergywoman", "manatee", "teepee", "peewee", "weeper", "periwig", "wig", "wigwag", "wag", "wagon", "gonorrhea", "hearten", "ten", "tentacle", "clear", "earache", "cheapen", "pencil", "cilantro", "trowel", "welkin", "kin", "kinswoman", "manikin", "kinsman", "manifesto", "stop", "top", "topknot", "not", "notepaper", "perturbed", "bedlam", "lam", "lamb", "ambassador", "dorsal", "salmon", "monsignori", "origin", "gin", "ginkgos", "gospel", "pelvic", "victim", "timpani", "ani", "animus", "musky", "sky", "skydove", "overlap", "lapel", "pelican", "can", "cancan", "cannibal", "balsam", "sampan", "panoramic", "micra", "crag", "ragout", "outruns", "unsheathe", "thereabout", "outbid", "bidet", "detach", "achoo", "hoodlum", "lumberman", "man", "mantra", "tramp", "amphitheatre", "tremor", "morsel", "sellout", "outrun", "runaround", "undersea", "sea", "seas", "eastbound", "undertow", "tow", "towel", "wellington", "ton", "tonsil", "silicon", "confound", "underpin", "pin", "pinpoint", "interwove", "overpass", "assassin", "sinew", "newsprint", "intagli", "glib", "lib", "libel", "belabor", "borsch", "schwas", "was", "washout", "outran", "ran", "rancor", "corncob", "cob", "cobra", "brag", "rag", "ragas", "gas", "gasp", "asphalt", "altho", "tho", "thou", "hound", "undergrad", "radio", "diocesan", "sanserif", "riffraff", "affair", "air", "airstrip", "ripen", "pen", "pennon", "non", "nonverbal", "ballyhoo", "hoodoo", "doormat", "matriarchal", "halibut", "but", "butterfat", "fat", "fathom", "homespun", "pun", "puns", "unsnap", "nap", "naphtha", "thalamus", "muscat", "cat", "catalpas", "pas", "pastiche", "cherubim", "bimbos", "bosun", "sun", "sunlit", "lit", "litchi", "chi", "chichi", "chimp", "imprimatur", "turnout", "outfox", "fox", "foxglove", "overrun", "run", "runabout", "outstrip", "rip", "riposte", "stem", "tempos", "possum", "sum", "sumac", "macro", "crocus", "custom", "tom", "tomcat", "catastrophe", "phenomenon", "noncom", "complaint", "interurban", "bantam", "tam", "tamp", "amp", "ampul", "pulsar", "sari", "aristocrat", "rat", "rattan", "tan", "tang", "angora", "oracular", "largos", "gossip", "sip", "siphon", "honeybee", "bee", "beech", "echo", "choicer", "cerebellum", "lumbar", "barman", "mannikin", "kindergarten", "tenser", "serfdom", "domains", "instil", "tildes", "descriptor", "tormentor", "torn", "ornament", "enthrone", "one", "ones", "nest", "esteeming", "ingratiate", "ate", "ateliers", "ersatz's"]

script.rb

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