hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
useless pre-processing

Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle View previous topic
View next topic
useless pre-processing
Author Message

Joined: 19 Feb 2009
Posts: 10
Location: Germany

Post useless pre-processing Reply with quote
Hey guys, tried to do some pre-processing with the maze. but after i compared the running durations with and without clearing the maze, i got almost the same result.
the following example is level 141; the most unpleasant level for me, so far.

level141 pre-processed: RDDD********************************RRDD
solving time: 8216,9s

level141 normal: RDDD********************************RRDD
solving time: 8202,6s

Btw: The pre-processing itself needs just about a second. I am using a recursive BF-algo that recognizes and avoids the "walls".

Thx, wiz
Fri Mar 27, 2009 10:20 am View user's profile Send private message

Joined: 27 Mar 2008
Posts: 18

Post Reply with quote
Hey, try timing each path generation that results in a dead end (ie: a point where any legal move of the available two moves is impossible) in normal mode, then see how many are they and the total time it took you to generate them, if the result is consistent with the delta of the previous totals that you've pasted, then there should be three possibilities :

1. Your algorithm simply didn't go through many paths that resulted in a dead end in normal mode at that level compared to other levels, this could be detected by doing the same test on different levels and seeing if there is a significantly larger difference in the timing ratio, on average.
2. Your algorithm is not making full use of the preprocessed map, or not operating with the preprocessed map in mind at all, this could be easily detected by printing out dead ends (there shouldn't be any)
3. You algorithm is being delayed by some very time consuming operation in both cases, and this is dwarfing the timing advantage you're getting out of preprocessing .

ps. I'm assuming that the exact same algorithm is being used in both cases.

You like pink, don't you?
Sat Mar 28, 2009 9:22 am View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle All times are GMT
Page 1 of 1

Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.