Clickmaze test cases

Clickmaze test cases

Hi All,

I have attached test files which, I hope, are the same problems as on the clickmaze web site.
Hope these can be of use to people.

FYI:
1) The first one is the same as the example in the problem definition.
2) These where made under linux so the line ending might be a bit short. i.e. not \\r and \\n.

10 帖子 / 0 全新
最新文章
如需更全面地了解编译器优化,请参阅优化注意事项

Thanks! Being able to validate by playing the fields on the website sure comes in handy!

Here's the shortest solutions I could come up with

test-example-1.txt 384535
test-example-2.txt 344301100305
test-example-3.txt 5026146555
test-example-4.txt 42630706775
test-example-5.txt 0000425157555

Is anyone willing to share their performance stats on these puzzles ?

As a complete set of shortest solutions I get the bellow values. These will be useful when the concurrency finds the results in different orders:

test-example-1.txt
384535
584353

test-example-2.txt
34482513402
34482513414

test-example-3.txt
5026146555
5084164555

test-example-4.txt
42630706775
82610506557

test-example-5.txt
0000425157555
0000426663556
0000684447554
0000685153555

All of these files, using single threaded code, yeild results in less than 10ms.
When I make a 'nasty' input file I will post it.

Thank you for taking the time to upload these, Duncan. Have you come up with a big test yet?

- Rick

Thank you for the test cases, lazydodo. Disclaimer noted. One can validate medium-sized solutions on clickmazes by bringing up a sample grid, clicking on the cells to toggle their initial state, and clicking 'Play'. This canvas is fairly large.

Here's a deceptively difficult test case:

7 7
6 6
2 2
1 1 1 2 2 1 6 5 6 6
6 7 0 0

The correct solution is: "No solution". A blinker sits on the goal, thumbing its nose at the intellgent cell who is stuck in a block out of reach. I'm sure many programs would go into an infinte loop trying to find a solution.

- Rick

Thank you all for the test cases. The DoDo_150x150-223533-55.txt test case and the "no solution" case are very interesting.

I have implemented my solution with a loop detection so that It doesn't hang in these sort of tests, but I think that a bigger test case like this could be a real problem even when you are aware of loops.

About the 150x150 test case, I think that it is interesting because, at least my implementation, takes a lot of time in solve the puzzle. My single threaded code:

Machine : Intel Core 2 Duo E7400 2.80Ghz
Time for DoDo_150x150-223533-55.txt : 180ms

Miguel

Given I used a slightly tweaked version of my solve code to generate the puzzle i suspect it's slightly biassed in my favour. (But it is indeed still taking alot longer then most other puzzles posted here)

Here are the min/max/avg times (of 500 runs) for each puzzle (single threaded on the intel many core windows box), the reported time is in milliseconds and includes parsing of the input file everytime.

test-example-1.txt 0.7948 / 2.5801 / 0.9830
test-example-2.txt 0.0538 / 0.0860 / 0.0552
test-example-3.txt 0.0692 / 0.2187 / 0.0754
test-example-4.txt 0.0706 / 0.2070 / 0.0721
test-example-5.txt 0.1272 / 0.2898 / 0.1367
nosolution.txt 0.0584 / 0.0761 / 0.0595
DoDo_14x14-9385-19.txt 0.8944 / 1.2853 / 0.9218
DoDo_25x25-63474-39.txt 0.4746 / 0.7205 / 0.4815
DoDo_150x150-223533-55.txt 37.3906 / 41.9716 / 38.7780
DoDo_300x300-373546-15.txt 62.7861 / 72.8158 / 64.8766

By the sounds of it you are having an easier time with the 300x300 puzzle then the 150x150?

Incase anyone is interested here is my benchmark code (Given GetTickCount wasn't up to the job anymore)

double TimeRun(char* fn, bool print)
{
LARGE_INTEGER liStart;
LARGE_INTEGER liStop;
LARGE_INTEGER liFreq;

QueryPerformanceFrequency(&liFreq);
QueryPerformanceCounter(&liStart);

Solve(fn,print);

QueryPerformanceCounter(&liStop);
LONGLONG llTimeDiff = liStop.QuadPart - liStart.QuadPart;
double elapsedTime = (double)llTimeDiff*1000.0/(double)liFreq.QuadPart; // in millisec
return elapsedTime;
}

double bench(char* fn)
{
double avg =0;
double min = 99999;
double max = -1;
int loops = 500;
for (int i=0; i<="" min)="" min="t;"> max)
max = t;
}
avg/=loops;
printf("%25.25s %.4f / %.4f / %.4f \n",fn, min,max,avg);
return avg;
}

Hi,

Thanks for the performance information. In my previous post, the 180ms was the average time for a single threaded version of my solution, still under work. The point is that the 150x150 puzzle was taking more time than the 300x300. Today I finished the optimization of the single threaded version, and my code still needs more time to solve the 150x150 puzzle.

My average times for 200 runs on the intel manycore linux box:

test-example-1 : 0.199775 ms
test-example-2 : 0.332585 ms
test-example-3 : 0.349705 ms
test-example-4 : 0.393440 ms
test-example-5 : 0.218940 ms
DoDo_14x14-9385-19 : 0.466640 ms
DoDo_25x25-63474-39 : 0.947110 ms
DoDo_150x150-223533-55 : 36.069920 ms
DoDo_300x300-373546-15 : 31.880110 ms

I am seeing the same behaviour with the 150 and 300 grids.
My algo at present takes 1281 iteration to finda solution for 150 grid and 760 iteration for the 300 grid.

发表评论

登录添加评论。还不是成员?立即加入