Boggle solver

[james]

Hey!

As a learning exercise I wrote a simple boggle solver in clojure.
I'm sure there is lots of room for improvement to make it more
idiomatic and perform better so I would be grateful if anyone would
care to cast their eye over it.

http://wiki.github.com/phraemer/Boggle-Solver

thanks,

James

[william douglas]

Very nice, I had actually been implementing a boggle solver for my
optimal boggle grid generator (5x5 with no limits on number of letters
on dice). I hadn't discovered the wonders of assoc-in though which
makes things look much nicer when creating nested maps. I really like
the layout of your code in general too though I'm a beginner with
clojure myself.

Mind if I fork your solution into mine for the grid creation as your
solver has very nice performance?

-William

[jng27]

C and Common Lisp versions here --> http://code.google.com/p/boggle-solvers/
Both use the same algorithm and data structures as far as possible.
The C version can solve a 1000x1000 board in about 40 seconds. The CL
version solves a 1000x1000 board in about 65 seconds on a dual core
laptop.

Haven't yet implemented a Clojure version. That would be interesting
for comparison ...

[james]

Please, do as you will with my code!
It's free for all to play with.
TBH, I'm delighted that someone else can find use for it.
I'd love to see what improvements you could make.

I've also now posted up on the wiki page some plots of the performance
using Incanter

http://wiki.github.com/phraemer/Boggle-Solver

I tested this against a friends very neat (but not optimised) c++
implimentation and it's only slightly faster as far as I can tell.

I suspect that some clever people on here could easily get better
performance out of my version and yet keep it idiomatic. (Come on you
guys and gals ;))

What I do love is that it would be trivial to parallelise this in
Clojure with no risk of locking, but still the most interesting thing
right now is tackling the single threaded performance.

On Nov 10, 10:53 am, william douglas <william.r.doug...@gmail.com>
wrote:

[james]

Nice. As soon as I get a chance I'll modify it to be able to solve
arbitrary sized boards.
Should be a perfect example to explore and demonstrate clojure's
concurrency capabilities.

[james]

I've changed it to allow variable board sizes.
Finding it difficult to profile Clojure code though for performance
tuning.
Using the -Xprof switch seems to indicate java.lang.Character.hashCode
is called a lot and i guess that's to do with the nested maps that
represent the trie.

Using jvisualvm doesn't help much either as it's not giving me a call
graph.
Just self counts for each function, so it's difficult to see how it
related to the clojure code.

On Nov 7, 7:11 pm, james <ja...@3dengineer.com> wrote:
> Hey!
>

> As a learning exercise I wrote a simplebogglesolver in clojure.

[Alex Osborne]

james <ja...@3dengineer.com> writes:

> Using the -Xprof switch seems to indicate java.lang.Character.hashCode
> is called a lot and i guess that's to do with the nested maps that
> represent the trie.
>
> Using jvisualvm doesn't help much either as it's not giving me a call
> graph.
> Just self counts for each function, so it's difficult to see how it
> related to the clojure code.

Try using this instead of -Xprof:

-agentlib:hprof=cpu=samples,depth=6,force=n

That'll write a file java.hprof.$pid.txt to the current directory. Look
at the end of the file and there'll be a "CPU SAMPLES" section which
shows the profiler output. You can search the start of the file for the
number in the "trace" column to find a stack trace for that function.
If the stack trace isn't long enough, adjust the "depth" option.