[Down-n-Out]max board size 300x300 ?

Is this a reasonable max board size?

Starting with a simple script

It only finds the biggest block and processes it and loop until empty

It gives me the following timings

10x10 less then 1 second
15x15 1 second
20x20 3 seconds
25x25 8 seconds
30x30 15 seconds
35x35 28 seconds
40x40 exceed time limit

So every 5 more the time doubles

And this runs on a dual Intel Xeon 2Ghz

As I look to my code I think I could optimize a little but never get a board of 300x300

I would like to suggest an extra rule here

Something like
(Width x Height) < 1000

We will see how it plays out...If it is deemed impossible to work with a board that size, I will modify the board sizes.....

I am seriously considering lowering the max grid size. I will make a final decision within 12 hours....

I'll toss my opinion in too. I coded up a simple thing like marcel suggested and it too couldn't come close to 300x300. In fact, mine timed out much sooner than his, but this machine is a dog. p3-600 I think. 25x25 grid went over time on that one. 20x20 came in at under 14 seconds though.

Whatever you decide to do, I'd urge you not to make it too small as that could also eliminate some interesting scoring situations. How much can you get done in 30 seconds when there's no chance of finishing the whole board. It would almost certainly be a completely different approach than what you would take knowing that you could get the entire board completed. Who will be best at both things? Just my thoughts.



Andy

Now I'm confused...

I thought we had to clear the entire board... I guess not now...

Also, I would suggest having plenty of run-time for us to process quite a number of branches of boards... I would personally prefer a low max-size.

I haven't done any PHP yet for this contest, but I've thought of how I want to attack this, but my algorithm would definitely be in polynomial time... If we can't even be guaranteed to completely finish one board, then all of us will have to code at least some constant-time (or linear time?) algorithm for the huge boards. Besides that, the difficulty will be in knowing when to waste time to use this lean-n-mean back-up algorithm.

Actually, so you do get a small difference between linear and constant. If you really have NO time, then you pick a block and cut away from there. If you have time to find the biggest at this moment, then you pick that one. Actually, I'm not sure now that the difference would be constant and linear (linear in terms of the size of width*height of board).

So, I would definitely prefer being assured I can use my polynomial-time algorithms in all cases

I have updated to a 50x50 board.

As mentioned, you do not need to clear the board. If you can do so in the time alloted, great. If not go for as many points as you can before time runs out....

I was making some stats with random boards yesterday evening...

The mean size of groups of adjacent tiles is ~2.70 tiles when there are 3 types, ~1.30 when there are 8.

This is rather independent of grid size.

So for a 300x300 grid with 8 tile-types I had 67,000 initial groups. It took 5 seconds for my script to identify all those groups.

On a 30x20 grid, it took only 50msec to identify the ~450 groups.

I tried many random boards, and the stats where rather consistent.

So for a 50x50 grid and 8 tile-types (the worst case we have now) you can expect about 1,900 groups to start off. My script will identify them in less than 200msec.

I think the optimal solution is very likely to be obtained for grids up to 20x20.

For a 300x300 grid there was not a chance for the optimal, but you still can try to get a good score.

Thus a 300x300 max would force a double approach: to go for the best and to try a fast solution.

I wonder if it is achievable with a 50x50 grid... I give it a 50% chance...

A last consideration: 50x50 is far better than 300x300 when it comes to show the grid on a HTML TABLE, so I could stick (again) to pure (&boring) HTML.

Can you post some of the files you were testing (say 10-20 files) to have them as a reference for progress report, time compare etc?

http://dist.doticni.net/dno/dnoinputs.zip (408k)

There's a bunch of input files of all sizes, and also 100 input files with max difficulty (50x50, 8 types)

Line breaks are placed at random so you can also test if your parser works as it should

It seems you have once more done a methodic and carefull work to produce some excellent files for testing. the only "mistake" i see is that while files are named index_lines_cols_tiles.txt, inside the file you have the number of cols in the first line and the number of rows in the second. In the rules it says that the number of rows should be in the first line. So when you run the file input_20_50_5.txt you are getting a grid of 50 lines and 20 cols instead of 20 lines and 50 cols. Not that it matters much but i just thought to mention it. Thanks again for the files.

As for the size and the time it seems perfectly challenging for me. The only grids i am not able to complete are 50x50x8! I complete 50x45x8 in 25.9 secs, 45x50x8 in 25.4 and 50x50x7 in 29.3! I have an Athlon XP 1800+ and 256 memory. Awaiting other participants feedback ...

Well, actually input_20_50_5.txt DOES mean 20 cols and 50 lines. To me, it's more natural to have the x coordinate before y, even though that is not the case with this contest... But as you said, it's not very important anyway...

Still working on the code, though, so I can't post a progress report yet

>fractalbit:As for the size and the time it seems perfectly challenging for me. The only grids i am not able to complete are 50x50x8! I complete 50x45x8 in 25.9 secs, 45x50x8 in 25.4 and 50x50x7 in 29.3! I have an Athlon XP 1800+ and 256 memory.

Ok, I just tried the first version of my program, and it is able to finish the 50x50x8 in 17 seconds on my P4 2.4Ghz (it removes the longest possible chain of tiles at each move).
There are still plenty of time to save !

>gato:I think the optimal solution is very likely to be obtained for grids up to 20x20.

I doubt you'll ever solve 20x20, even with 1 hour !
One year ago, I wrote a solver in C for this kind of problems, but found better and better solutions after a long period of time !
Removing the longest chain of tiles is not the best heuristic.
Sometimes, you can remove a smaller set to get a longer chain after that.
Optimizing the solution is NP complete (this has been demonstrated !)

JC

if mcoder is right (and it seems that way, looking at fractalbit's times) i would vote on raising the 50*50 limit to at least 60*60 or 75*75, because with that board size, one algorithm should be made for "small" boards, and another for "big" ones, where small and big would vary on your "better-and-slower" algorithm.

it would be interesting to see algorithsm for boards that can't be cleared. i think it is a whole new algorithm, and will make things just more interesting

(and i think that there is time for it, since there is still 20+ more days..)

I'd agree, but...

but if i got the rules right, removing only random (or fixed) square would on a random grid get you probably around two removed squares per turn (on average), so 50*50 grid would get you around 50*50/2 (turns) * 2^2 (points)== 1250*4 == 5000 points.

but if you could do just 20 turns of 20 squares, that would be 8000 points...

i didn't get into details about moves yet, so i can't tell if it would be hard to get 20 turns of 20 squares on a random board, but in a "nice" board, it could be quite easy...