Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

After 20 years, the globally optimal Boggle board

danvk.org

Post reply on HN
Print view View original

21–25 of 25 posts

Re: After 20 years, the globally optimal Boggle board

#21

Post by danvk »

joefkelley wrote: post #20

This reminded me of one of my high school computer science assignments- simply to find all words in a single boggle board. And try to optimize your solution a bit. The point was to teach about recursion/backtracking and data structures. The intended solution was roughly: start at a square, check if your current prefix is a valid prefix, move to a neighbor recursively, and emit any words you find. Trying to optimize n…

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.

Re: After 20 years, the globally optimal Boggle board

#22

Post by LPisGood »

danvk wrote: post #21
joefkelley wrote: post #20

This reminded me of one of my high school computer science assignments- simply to find all words in a single boggle board. And try to optimize your solution a bit. The point was to teach about recursion/backtracking and data structures. The intended solution was roughly: start at a square, check if your current prefix is a valid prefix, move to a neighbor recursively, and emit any words you find. Trying to optimize n…

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.

I think GP mentioned it was on a _single_ boggle board.

Re: After 20 years, the globally optimal Boggle board

#23

Post by benrbray »

oliwary wrote: post #15

Fun, love word game computations! Reminds me a bit of the challenge to place the challenge to place all letters in the alphabet in as small a grid as possible, with valid words: https://gamepuzzles.com/alphabest.htm I made a word game based on a similar concept, featuring different letters every day: https://spaceword.org

Somewhat related, I used minisat.js to generate Boggle boards that contain a given list of words!

[0] https://benrbray.com/projects/unboggler

Re: After 20 years, the globally optimal Boggle board

#24

Post by danvk »

LPisGood wrote: post #22
danvk wrote: post #21

Earlier quoted context omitted.

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.

I think GP mentioned it was on a _single_ boggle board.

Your best bet in that case is to store the dictionary in a Trie or DAWG structure that can be mmapped directly from disk.
Post reply on HN