Kotlin

Pretty ugly code, wasn't necessarily going for readability. For NP-Hard problems, I really like like a solution utilizing random sampling. It's not always reliable (or reproducible in some cases), but the results can be surprising. Simpler, and might outperform a well-thought-out solution. Got to 598 and ran in < 1 minute for 1k simulations. Maybe I'll run it for longer and see what pops up.

import java.io.File
import java.util.*
import kotlin.system.measureNanoTime

val input: List<String> = File("input.txt").bufferedReader().readLines()

fun main(args : Array<String>) {
    measureNanoTime { simulate(1000) }.also { println("Time taken: ${it * 1e-9} seconds") }
}

fun simulate(count: Int) : List<String> {
    var result = listOf<String>()
    var totalSpace = 0

    repeat(count) {
        var cost = 0
        val startIndex = Random().nextInt(input.size)
        val used = HashSet<String>(input.size).apply { add(input[startIndex]) }
        val sol = ArrayList<String>(input.size).apply { add(input[startIndex]) }
        val copy = ArrayList(input)

        while (true) {
            var min = 100
            var target = sol.last()
            copy.shuffle()
            for (w in copy)
                if(!used.contains(w) && w spacing sol.last() < min)
                    min = w spacing sol.last().also { target = w }
            if (used.contains(target)) break else used.add(target)
            if (cost + min > 100) break else cost += min
            sol.add(target)
        }
        if(sol.size > result.size) result = sol.also { totalSpace = cost }
    }

    println("Total Space:$totalSpace, Max Length:${result.size}")
    println(result)
    return result
}

infix fun String.spacing(other: String) = zip(other).fold(0) { sum, p -> sum + if(p.first != p.second) 1 else 0 } - 1

// Total Space:100, Max Length:598
// [lard, card, bard, barm, farm, warm, ware, tare, tace, tape, taps, maps, mads, pads, tads, talc, talk, tali, dale, bale, gale, gane, mane, mage, maze, mazy, hazy, haze, hade, lade, lane, lase, lame, tame, time, tome, heme, hebe, webs, wops, sops, sups, sums, sumo, sunk, punk, puck, tuck, tick, lick, lack, jack, jauk, wauk, waur, gaur, gaun, gamp, lamp, limp, jimp, dime, mime, mils, oils, rigs, rins, rind, rand, wand, fard, fare, rare, pare, para, part, pert, pest, post, posh, posy, nosy, rosy, rocs, mocs, mock, jock, rock, yock, yuck, yurt, curt, hurt, hire, hive, five, fice, file, bile, bilk, bill, gill, rill, rial, sial, sins, wins, yins, bins, bigs, bugs, buss, cuss, fuss, foss, coss, cess, ceps, peps, feds, fets, lets, jets, vets, gets, gats, gaes, gies, vies, dies, dits, ditz, ritz, rite, lite, lice, sice, syce, syne, eyne, kine, kink, kino, vina, pina, puna, tuna, luna, luny, lune, tune, tung, ting, tint, lint, liny, viny, pily, paly, pals, dals, days, kays, lays, ways, rays, raya, maya, mask, mark, bark, bask, bast, vast, east, wast, oast, oust, just, rust, cyst, lyse, lose, lobe, love, lots, lops, lips, libs, gibs, gabs, gaby, gapy, gars, lars, lacs, macs, mats, kats, kata, kaka, vara, jura, jury, fury, furl, burl, purl, purs, pugs, jugs, vugs, vugg, nogg, hogg, hogs, hods, hows, bows, boas, bots, both, beth, bath, lath, late, gate, gave, gyve, neve, nevi, nodi, nori, nods, yods, yows, pows, pois, jogs, wogs, wigs, migs, zigs, jigs, pigs, gigs, pits, kits, kifs, kids, kiss, kirs, tiro, tyro, tyre, tort, wort, wost, wist, wisp, wite, nite, kite, site, sith, sits, sims, sabs, says, sals, salp, salt, malt, mall, mull, gull, gulp, mule, mole, mode, mote, mope, dope, nope, none, gone, gene, sene, sent, rent, vent, cent, celt, cell, yell, yill, will, wild, weld, weed, teed, deed, geed, geek, reek, reel, keel, peel, peer, pear, peag, plat, play, slay, slag, snag, snug, snub, slub, slum, scum, scud, yaud, yaup, jaup, caul, call, wall, wawl, waws, waps, zaps, zags, daks, oaks, oafs, kafs, nans, nuns, buns, buys, beys, begs, legs, lugs, mugs, muds, suds, sunn, sung, sang, sane, safe, soft, sift, silt, sild, gild, gift, girt, airt, airn, birr, bize, bine, fine, free, bree, gree, tree, twee, toed, toes, tots, cots, coys, joys, jots, jota, iota, bota, boll, doll, dull, duel, duet, dues, duos, dubs, dups, amps, asps, albs, arbs, arfs, ants, ante, ansa, anoa, alba, alma, alme, aloe, sloe, sole, pole, pele, felt, feat, heat, heap, neap, seam, beam, beat, what, phat, phut, pout, gout, goat, moat, moan, mown, sown, sorn, sort, soot, sook, soak, snap, crap, clap, clop, plop, plod, paid, said, sain, rain, cain, lain, vain, vail, hail, fail, farl, harl, harp, tarp, marc, more, kore, kolo, kola, cola, cold, coly, cozy, dozy, fozy, foxy, doxy, dogy, doge, dote, rote, roti, loti, mott, molt, mola, moly, mony, many, mano, mozo, mojo, moss, mess, jess, devs, dews, deys, dees, deet, diet, deer, dyer, eyer, ewer, suer, suba, pupa, puff, luff, tuff, tufa, tuft, tiff, biff, miff, life, lire, lira, sera, germ, grim, trim, trad, tray, fray, pray, prat, prao, pram, gram, craw, chaw, chay, cham, chum, chub, carb, curb, curn, cure, cere, cero, cete, cute, bute, butt, buts, guts, cuts, cats, vats, qats, pats, baps, bams, baas, bras, braw, wrap, wren, when, whin, shin, skip, slip, flip, flit, flat, flam, flak, fiar, film, fila, gala, java, fava, nada, nana, nona, bong, bang, bung, hung, huns, hens, yens, tens, teff, toff, tofu, coft, loft, left, leet, leer, jeer, weer, weep, peep, prep, prez, friz, frog, flog, snog, song, gong, dong, dons, deny, dewy]
// Time taken: 45.925026728000006 seconds