Comment by jodrellblank
2 days ago
Someone posted their word game Cobble[1] on HN recently, the game gives some letters and the challenge is to find two English words which together use up all the given letters, and the combined two words to be as short as possible.
A naive brute-force solver takes the Cobble wordlist of 64k words and compares every word against every other word and does 64k x 64k = 4Bn loops and in the inner loop body, loops over the combined characters. If the combined words average 10 characters long, that's 40 billion operations just for the code structure, plus character testing and counting and data structures to store the counts. Seconds or Minutes of work for a puzzle that feels like any modern computer should solve it in microseconds.
It's always mildly intresting to me how a simple to explain problem, a tiny amount of data, and four lines of nested loop, can generate enough work to choke a modern CPU for minutes. Then considering how much work 3D games do in milliseconds. It highlights how impressive algorithmic research of the 1960s was to find ways to get early computers to do anything in a reasonable time, let alone find fast paths through complex problem patterns. Or perhaps, of all the zillions of possible problems which could exist, find any which can be approached by human minds and computers.
Of course finding the optimal solution to a Cobble puzzle does not actually require the computation you describe. We can in a single pass find a limited set of candidate words and work out a solution with those.
Sure; after Casey Muratori saying that people argue with him that no normal developer needs to worry about performance, computers are fast enough, performance is a niche concern, I'm just musing how little data it takes - 64k is nothing to a modern person - and how abruptly anyone who wants a fast answer has to switch to think about performance, pre-processing the list, sorting more promising candidates first, using a faster language, noticing that it's embarrassingly parallel, etc.