On Mon, Dec 22, 2008 at 4:54 PM, John Randall <[email protected]> wrote: > http://shootout.alioth.debian.org/gp4/benchmark.php?test=meteor&lang=all > > I have a working solution but with very poor performance compared to the > other entries. I am posting a simplified version here in the hopes I will > get some good suggestions for improvement. This solves the problem in both > depth first search (required for the contest) and breadth first search > (generally better for J). > > The part which sets up the game data is probably overcomplicated, but > correct. I am most interested in improving the code after "playing the > game". Unless I have missed it, looking for islands is not feasible.
I had a few moments to try your code, but unfortunately I only had a 32 bit machine, and you did not provide a copy of your definition for "ncap". So my comments here will be largely ignorant of what you have actually accomplished, and may go over ground that you have long since conquered. With those caveats, here are my thoughts: [1] Hypothetically speaking you do not need to deal with rotations and reflections in the placement of your first piece. These can be addressed through rotations and reflections of the solutions. (Trivial factor of four, here?) [2] Hypothetically speaking, you can deal with the pieces one at a time. Even in breadth first searching, you can do that with all possibilities for the first piece, all for the second, and so on. [3] Given a piece's placement on the board, only certain placements of any of the remaining pieces are possible. (Those that do not overlap.) [a] Once you have all the possibilities, you can "or" their bit masks to detect holes. If you have any holes which are not occupied in any pairing, the original piece position is useless. (Would this be and example of what you termed "islands"?) [b] Given placed pieces A, B, and C, only valid possible combinations of A+B, A+C, and B+C can be validly combined. [4] doing some breadth-first groundwork and then combining groupings in the resulting restricted spaces in a "depth-first" fashion might be fruitful? That is all I can think of at the moment. -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
