Yes. You can give pickType a type in TS. Something like pickType<B extends boolean>(b: B): B extends true ? string : number.
I’d love to read a post explaining how TS conditional types are or are not a form of dependent types. Or, I’d like to understand dependent types well enough to write that post.
I asked GPT-5 about it before writing the above comment and got a pretty interesting answer about how, for example, you can’t write a function that takes a number as an argument and returns an array of that length (length enforced by the type system). You can partly get there with tuple types but you have to enumerate every length explicitly. And it only works if you pass a number literal to the function. If you pass a variable of type number, it can’t infer the particular number it is.
These bounds are pretty effective at finding the global max for 3x3 Boggle, but 4x4 is a lot bigger.
There is a mapping from Boggle optimization to ILP, but I’ve seen no evidence that this is an efficient way to solve it. I’ve been told that branch and cut is usually better than branch and bound, but I don’t know whether it’s applicable to Boggle.
I have been surprised that the Boggle code runs about 4x slower on the GCP machine than on my M2 MacBook. I don’t have enough experience running CPU- and RAM-intensive cloud jobs to know whether this is normal.
Similar experience at DigitalOcean where, in 2023, I rented a VPS with dedicated cores to compute on some decent-sized dataset and it turned out to be slower than the 2012 laptop CPU that I use as my main server! That laptop has an i7-3630qm iirc, not sure what DO claimed they give you but it was slower
The storage i/o speeds were also crap (quoting myself here from the notes I made at the time) compared to what I got soon after when I bought a 70€ TLC SSD as upgrade for the laptop-server. They claim it runs on SSDs but, if it does, they're the world's cheapest bulk data SSDs or they have a bottleneck in ferrying data between the SAN and the VPS host, even for sequential r/w (that it has higher iops latency, I could understand)
At work, we sometimes use AWS GPUs for password cracking (we do security audits and sometimes find hashes). The GPUs that employees have just to play some games are faster than these and cost a lot less to operate, but we can't put customer data on private systems
For occasional problems that can be parallelised, sure, rent a hundred temporary systems at a cloud farm for two days; but in general I just can't recommend it to anyone. It costs an arm and a leg compared to cheaper providers or buying hardware yourself (if you're into being the sysadmin). The "we have a fleet of systems on stand-by for you" (so you can scale on demand) is a big premium that most seem to be unaware of that they're paying implicitly
You can possibly do a lot better with dedicated servers (bare iron) than VPS. Particularly, "dedicated core" VPS are actually dedicated threads, so you get one real core per two vcores.
> “As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said.
For context, many people are interested in finding high-scoring Boggle boards, usually via simulated annealing, hillclimbing, or genetic algorithms. But so far as I can tell, I'm the only one interested in _proving_ that a particular board is best. Doing that was the new result here.
I once spent a little time writing code to find the longest possible boggle word and found there were a few candidates. Interesting things I noted that weren’t entirely obvious: the longest word is actually 17 characters, not 16, because of the “Qu” side, and there are actually lots of words that are impossible, because for example there is only one J and only one B and they are on the same die.
I don’t remember all the longest words but sesquicentennials was one of them.
Finding the highest-scoring board with a 16- or 17-letter word is a fun, but very different problem. There are few enough "Hamiltonian paths" through the all the letters on a 4x4 Boggle board (~68,000) and few enough 16 letter words (~2,000) that you can enumerate all pairs in an hour or two.
Depending on wordlist and whether you want a 16 or 17 letter word, you get "charitablenesses", "supernaturalised" (British spelling), "quadricentennials" or "quartermistresses". These boards all score considerably lower than the REPLASTERING board. Full results here:
https://github.com/danvk/hybrid-boggle/#highest-scoring-boar...
I hadn't realized until I did this "side quest" that most wordlists top out at 15 letter words. That makes sense for a Scrabble dictionary, but it's not great for Boggle.
Ok so English max is 3,625 points from 1,045 words (with ENABLE2K word list).
Why not compute the max possible Boggle board for other languages: French, Spanish, German, Italian, Portuguese, Czech... they each have a different set of 16 dice x 6 faces [], and of course totally different wordlists:
It's open source, take a crack at it! Or file an issue requesting it.
This analysis doesn't make use of the Boggle dice. It assumes that any cell can be any letter. In practice, all high-scoring boards can be rolled with the Boggle dice. My code does assume the letters are A-Z, though, so the Ñ die in Spanish Boggle would require some code changes.
Ok, but then a) we'd need to refine the issue to "enhance request to handle every non-ASCII character/digram that could occur in other Boggle languages":
- Spanish: ñ
- Czech: no extra characters (e.g. 'E' can be used in words as E, É and Ì)
- Danish/Norwegian: do Boggle dice use æ,å,ø ? I searched but couldn't find out.
- Filipino: ñ . And separately in some wordgames (e.g. Scrabble knockoffs), I see 'ng' treated as a single digraph. Apparently it's officially a separate digraph, so the Tagalog alphabet ('abakada') has 28 letters.
And b) if we have rare characters on a few dice (esp. the unofficial Bosnian one proposed), that imposes restrictions on your assumption that any cell can be any letter. So you'd have to postprocess to cull a few words that couldn't legally be made with that dice-set.
"Lone coder" here. I reached out to Ollie (the FT reporter) because he'd written a book (Seven Games) about computers and games, so I thought the Boggle story might interest him. It did!
Nice work! I love an "impossible" problem that falls to bounding estimates like this one does. There was a surprisingly lot of work done in protein folding that had similar sorts of techniques to eliminate structures that would either never happen or would self destruct if they did kinds of things.
Sorry, but this doesn’t pass the smell test. The article mentions 200,000 random 4x4 boards/second on a single core on an M2. That’s a ~4GHz chip. So ~20,000 ops/board. There are 200,000 words in the dictionary. You can’t possibly do something for every word in the dictionary, it would be too slow.
It sounds like your Trie implementation had a bug or inefficiency.
Annealing is mentioned a few times in the post but not discussed in any detail. I found that hill climbing with an expanded "pool" of boards and exhaustive search of neighbors was the most reliable way to get from a random starting point to the highest-scoring board: https://github.com/danvk/hybrid-boggle/blob/main/boggle/hill...
I tried Z3 and OR Tools. I didn't try Gurobi. But this was enough to make me think ILP was a dead end. (There were a lot of dead ends in this project.)
I don't know much about integer programming, though, and I'd love to be proven wrong.
I saw that! In my experience, problems that seem completely intractable using open source tools often get solved in seconds using state of the art commercial approaches.
One interesting thing about Boggle is that the number of variables (16 cells) is very small compared to the number of coefficients on how they combine (the number of possible words).
We built a visualization along these lines at Sidewalk Labs back in 2017. It's open source if you're interested in playing around with it: https://github.com/sidewalklabs/router
I particularly liked the multimodal comparison feature. It lets you answer questions like "where does the bus help me get to faster than the subway?" (Answer: basically nowhere.)
I’d love to read a post explaining how TS conditional types are or are not a form of dependent types. Or, I’d like to understand dependent types well enough to write that post.