I recently watched a video by Matt Parker, who you might have seen a lot on the Numberphile Channel.
He shared an interesting problem in the video, which has attracted many coders to come up with faster solutions for the same or you can say speedrun?
He also made another video detailing the problem. Here's the podcast for the same.
For those of you lazy enough to go through the videos, here is the text version.
Problem:
Example:
I would like to see how the CP Community tackles this. As for the accepted wordlist, you can use any famous ones you can find such as this one.
Feel free to discuss approaches, and share your codes/times.
Bitmask DP :P
UPD: Wait, do you mean valid english words? We might like some heuristics to get it faster in this case.
This is debatable. But for the sake of the problem let's say a word that is defined on the following dictionary.
edit: seems like the word list is fixed. so the best solution is to use some heuristics. for example, you know a 5-tuple of word only works if it appears in your precomputed solution list.
As the heuristics, I believe we could use some pruning, to prevent searching words with impossible substrings such as "ghj" and "zwx".