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

Doing some testing i discovered that collapsing the grid takes almost 90% of the total time! I really have to code a better collapsing function :-

Through a more proper if coding i am now able to complete 50x50x8 in 22 secs

Now a question. I have the grid in a multidimension table of the form grid[$i][$j] = $tile. If i recode the whole script to work with a singe string, will i see a significant improvment in the speed?

>Now a question. I have the grid in a multidimension table of the form grid[$i][$j] = $tile. If i recode the whole script to work with a singe string, will i see a significant improvment in the speed?

Multidimensional arrays are VERY SLOW in PHP !
Try something else.

JC

Hmmmm, i converted only the collpasing function to work with a single string and to my surprise it is a little SLOWER than working with the multidimensional grid! I wonder why some people say that arrays are slow?

I didn't say arrays are slow.
I said MULTIDIMENSIONAL arrays are slow !

BTW, I optimized my programme a little bit more, and get 14 seconds for a 50*50 grid on my 2.4Ghz (with the dumb heuristic of removing the longest set of tiles every move).

JC

Are you implying that $grid[$i][$j] is not a multidimensional array?

Also, 50x50 and how many tile types? 3, 5, 8? It makes a lot of difference.

>Are you implying that $grid[$i][$j] is not a multidimensional array?

Replace your multidimensional array grid[x][y] by grid[y*XMAX+x], and you should notice a difference !
PHP handles multi-dimensional arrays in a strange way (just print_r your array).

>Also, 50x50 and how many tile types? 3, 5, 8? It makes a lot of difference.

8 colors, and I'm now below 10s.
But it seems that marcel's program performs a lot better than mine (around 15% faster) :-(((

I guess at least 5 or 6 guys will be able to write very fast programs (50*50*8 in less than 30 seconds). It's just a matter of time, and the contest will finish in 3 weeks.
This gives us plenty of time to write a good heuristic.

JC

It seems i misunderstood you earlier. I converted the multidimensional grid in a grid of type grid[x] = line_contents. The good thing is that i can access this type the same way i did with the previous grid. So without making any other change i now get 13.6 for 45x45x8 and 19.8 for 50x50x8. Previously i got 14 and 22.5 respectively. As it is obvious, the improvement increases more as the grid size increases.

I am happy to report that through some more optimizations, i am able to complete a 50x50x8 grid in 11.5secs! That is less than 13.6 that i get with the code that matt posted. So it seems that i am within the time limt for all grids