I now have a working solution in J to the Meteor problem. Unfortunately it is very slow (200+ seconds). While I do not expect to get close to the C++ solutions, I would like to get it to the same level as other interpreted languages.
While my solution is not ready to submit to the Shootout, or even to post here, I thought I would recount my experience for anyone else who is working on the problem. I am using the idea I posted earlier: using a length 50 bitmap to represent occupied cells. Since I have a 64-bit machine, this will fit into a single integer. I may have to adapt the solution for 32-bit. For each piece, I generate every placement on the board. This is done using a coordinate system rather than the linked approach in the Java article. It is much shorter than piece generation in the other approaches, and shows some of the features of J. All the approaches I have seen now search a tree of possible boards by adding one piece at a time. The trick is to prune the trees as much as possible to prevent exponential growth. The approach suggested in the Java article is island detection. An island is a connected component of the graph where the vertices are empty cells and the edges join neighboring cells. If the size of each connected component is not a multiple of 5, there is no solution obtainable from the current configuration. To generate solutions, I use the approach of the Scala program by Isaac Gouy (who has also contributed to the Wiki). The idea is to have at each stage a configuration which covers an initial run of cells. It is extended by finding pieces whose first cell is the first empty cell. This limits branching quite significantly, and creates few islands. In fact, I found that pruning through island detection had little effect on the runtime. Ironically, despite trying to open up the Shootout, the organizers are still presupposing an implementation: depth-first search. For this type of problem (if memory permits, which it does in this case), I prefer breadth-first search: solution=:f^:10 init where init is the empty board, and f adds all possible single pieces to a solution. The problem with this is that you have no solutions until the last step, when you suddenly have all solutions. The problem requires that you can produce N solutions in a time which increases with N, thereby precluding this approach. However, I am in no position to complain until I have a competitive solution. I'll post some code when it is cleaned up and it is working a bit faster. In the meantime, I would welcome any suggestions or comments. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
