Finding 5 5-letter words to cover 25 letters under 1.5s via Linear Programming | Hacker News Reader

Finding 5 5-letter words to cover 25 letters under 1.5s via Linear Programming

partiallytyped.github.io

Hello everyone. I recently watched Matt Parker's video on the Jotto Problem, which basically asks to find 5 5-letter words such that they cover 25 characters.

It appears that there's a race to find the fastest solution / algorithm and I thought i'd give it a shot. As far as I know, this is the fastest solution.

I like your approach. It's a good way to find a single solution. Do you think it can be expanded to find all 538 unique solutions that are found within the words_alpha.txt file?

The competition that exists around Matt's original podcast, and later his YouTube video, has the following rules:

The full words_alpha.txt file must be read in The solution must be generic in that it will work on a supplied set of words The solution must be complete in that it finds, at least, all possible unique solutions from the input set.

The fastest solutions out there today are capable of reading in the file, and finding all 538 solutions from words_alpha.txt in around 0.002s for multiple threads, and around 0.010s for a single thread.

It can catch all solutions where one of the words is a permutation of another without any significant overhead by mapping a word to all of its permutations - which is more or less already there.

Besides that, we will have to rerun without one of the matched words to see other non-permutation solutions.

From what I have seen only by removing "m" there is a solution.

> The fastest solutions out there today are capable of reading in the file, and finding all 538 solutions from words_alpha.txt in around 0.002s for multiple threads, and around 0.010s for a single thread.

Language?

Edit:

If we have access to the solution and use the simplex method, we can actually find all combinations with no real overhead.

The simplex method essentially jumps from vertex to vertex in the polyhedra, when it can't produce a better solution, it will terminate. Thus, given one solution we have access to all of them since they are available on the same plane and all vertices have the same value. It's just that we will have to do discrete jumps which is not necessarily difficult to do.

The 538 possible solutions are not permutations, and are drawn from the set of 5977 unique non-anagram 5 letter words that can be extracted from words_alpha.txt. There are 536 solutions that include the letter "m".

https://docs.google.com/spreadsheets/d/11sUBkPSEhbGx2K8ah6Wb...

That's a spread-sheet of the various solutions as maintained by Benjamin Paassen, who was the author of the user-submitted solution featured in Matt's video. The times he presents are from being on his own system. Some of the solutions listed there have advanced since Benjamin ran them.

I wish you all the best! It's a fun little challenge to code for.

Reply on news.ycombinator.com