So, I’ve been thinking about this one for quite some time. @kwx piqued my interest in Bloom filters with his response, and I just kept returning to this thread every few weeks. I decided to take a break from Monopoly this weekend and take a deep dive on this.
I stumbled upon a great little write up on universal hash functions here,[1] which took me back to the original paper on them by Carter and Wegman.[2] Those two references gave me the information that I needed to give Bloom filters a try.
I wrote a C# program that ingests a word list and spits out a TypeScript array that I can copy-and-paste into MakeCode Arcade. I used the Game Words list by Dana Bell;[3] YAWL[4] would work just as well. This first pass worked just fine for words up to five characters in length. Beyond that, the numbers got too big to fit into TypeScript’s number
type. This was my motivation to port bigint
to MakeCode.
It works, too! The complete Game Words dictionary up to 12-letter words fits in ~400kB. Take a look!
I’ll come back to this again another time. I’ll write a proper interface to my C# program and put that in GitHub so that y’all can use it with any word list you like. I’ll also refine the TypeScript code a bit and put that up on GitHub for anyone who wants it. I could wrap this into an extension, but because of the size of the dictionary, it might not work on hardware. You will want to strip out the filters that you don’t need to make the code optimal.
I’ll be adding Countdown to my list of future projects. That and Lingo. 
I’m just stoked that it works! Have fun!
[1] Mount, Dave. (2019). CSMC 420 Lecture 10: Hashing - Basic Concepts and Hash Functions. https://www.cs.umd.edu/class/fall2019/cmsc420-0201/Lects/lect10-hash-basics.pdf
[2] Carter, Larry; Wegman, Mark N. (1979). “Universal Classes of Hash Functions.” Journal of Computer and System Sciences . 18 (2): 143–154. https://doi.org/10.1016/0022-0000(79)90044-8 Conference version in STOC’77.
[3] Bell, Dana. (2020). Game Words 2020 (provisional). https://www.tylerhosting.com/gamewords/
[4] Cooper, Mendel Leo. Yet Another Word List (YAWL). Republished by Aaron Bull Schaefer. https://github.com/elasticdog/yawl