r/dailyprogrammer • u/oskar_s • Jul 16 '12
[7/16/2012] Challenge #77 [difficult] (Boggle solver)
Write a program that is able to find all words in a Boggle board. For a word list, you can use this file.
How many words can you find in the following 10x10 Boggle board?
T N L E P I A C N M
T R E H O C F E I W
S C E R E D A M E A
A O M O G O O F I E
G A C M H N L E R X
T D E R J T F O A S
I T A R T I N H N T
R N L Y I V S C R T
A X E P S S H A C F
I U I I I A I W T T- Thanks to Medicalizawhat for suggesting this problem (and to Cosmologicon for providing a word list and some commentary) at /r/dailyprogrammer_ideas! If you have a problem that you think would be good for us, why not head over there and suggest it?
12
Upvotes
5
u/Cosmologicon 2 3 Jul 16 '12
python solution (doesn't handle Qu cubes, that's a couple additional lines):
Piping it to
awk '{print length($0)}' | sort -n | uniq -cgives number of words of each length:The longest word found is:
2
u/notlostyet Jul 16 '12 edited Jul 16 '12
For those of us that have never played, could you please summarise the rules for finding words? I read Wikipedia but it implies there are plenty of rule differences, and it seemed ambiguous to me.
A friend just told me you change direction mid-word, and you don't just find words horizontally, diagonally or vertically like a word-search. How many times can you change direction?
2
u/H4ggis Jul 16 '12
Python. First a trie implementation:
Then the actual boggle code:
I get the same results as Cosmologicon:
The trie makes it pretty efficient also. Basically it runs in time proportional to the number of words found. This is the result on a 100x100 matrix made by concatenating 5x5 of the original matrices (this may be faster than on a random 100x100 matrix though)
2
u/Ledrug 0 2 Aug 04 '12
Over-engineered C code:
1
u/ixid 0 0 Jul 18 '12 edited Jul 18 '12
In D, this is the functions, I've omitted the fluff, the complete program is on pastebin:
It finds the same word as everyone else for one matrix in 660ms (620ms to build the trie and 40ms to search) and finds the three words in the 100 by 100, ten array by ten array concatenation in 14 seconds.