Raul Miller wrote: > On Dec 14, 2007 4:18 PM, metaperl.j <[EMAIL PROTECTED]> wrote: >> Raul's meteor contest entry failed to fit in memory. > > I would not decorate my sketches with the label "contest entry". > As you note, I never wrote anything that worked. > > But I believe John Randall put some real effort into this problem,
I did spend a while on the Meteor problem, and have a solution. My best version runs in about 50 seconds, and I could halve this by exploiting the board symmetry. I never submitted it because I did not want to show up J, since this is slow as compared to the other entries. This type of problem is tough for J. You have a tree to search with lots of small decisions. The problem is compounded since the recommended method for pruning the tree involves identifying "islands": connected components of the remaining empty cells whose size is not a multiple of 5. Most of the other solutions I could understand did this by flooding. Again this is slow in J. I tried some of the code for finding connected components of graphs that has been posted to the forum. This made things worse. I also tried caching bitmaps, etc. I ended up not looking for islands at all. I did prune the tree by adding pieces to only the first unoccupied cell. Finally, for this type of problem I prefer breadth first search. The rules prescribe depth first search, since you are required to be able to deliver fewer than the complete set of solutions. With breadth first you know them all as soon as you know any. This is a gripe, but immaterial compared with the problems above. My program's performance may be due to my ineptitude, and my code could be improved. However, I would be surprised if this problem can be solved quickly in J. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
