Maze Mapping problem in Test-Mode

Dear Friends!

Here is test-version of a problem, or rather a challenge:

Maze Mapping Robot

I feel it may be interesting since usually "maze-solving" algorithms suppose we know the whole map (or graph), but it is not like in real life.

Here program should be created which doesn't know the map of the maze (and should create such a map really).

Problem is in test mode now - even if you solve it correctly, there'll be verdict telling it's ok, but not accepted yet.

The matter is I consider assigning "challenge" to it. But it would be good to consult with you whether it is good idea. Options I have in mind are:

• let it be challenge, with score based on how few rooms were travelled
• let it be challenge, with score based on how few instructions are used (e.g. how small (eval-counter) is after finish)
• let it be plain problem, not a challenge.

First option is "logical" but scoring is "algorithmic" and may be potentially tie if maze size is small and similar algorithms are used.

Second option is more "implementational" and there are tons of ways to improve count (but not always this makes code better).

Third option may be nice since the problem itself is a bit tough to implement with the language unfamiliar, so even just solving should make one glad and not-wishing to do anything more with solution.

As soon as this is decided, we shall have problem switched to "normal" mode, so solutions could be accepted :)

P.S. Current implementation checks the solution against single variant of maze, though final variant, probably may check against several (say 3) variants.

P.P.S. Just finished my own solution today, after few days of trying to check it is possible - not that large, but it really takes some mind efforts :)

Hi Friends!

Thanks for investigating this and casting your vote :)

Let it be then "plain problem" - as this gives us option to check each one's code. (it become visible and ready!)

For N=5 (given test case), my solution uses ~ 500k cycles.

Well, I guess this should still fit. I reduced checker to trying two mazes (7*7 and 10*10). My solution spends about 250k and 700k cycles respectively, thus I guess yours should fit too.

I shall add these details to problem statement, thanks for suggestion!

I suspect an endless loop in my solution against checker.

The checker itself just feeds your solution some maze and then checks that output is a list of lists of correct size, and then compares it with the initial maze. I.e. it is hard to stuck in loop outside your code.

As about your code itself, I think it shouldn't stuck either, from logical point of view. The "bot" is free to go wherever it wants... So there seem to be no reason to walk in circles. If bot feels there is nothing more to explore, then either the whole maze is mapped, or there are some unreachable places in maze, or bot have stuck in some dead-end part (e.g. cell with no doors out). I tried to check the mazes are "all-reachable", so last two cases shouldn't happen. Though if you feel they happen - tell at once, I'll investigate better!

11 by 11 example, if it may help

3 3 6 2 7 5 7 3 6 7 6
10 12 15 15 9 12 4 8 5 6 14
2 4 15 11 10 11 7 11 11 13 10
10 12 14 9 9 7 15 3 10 13 14
9 13 15 2 6 13 4 12 14 11 12
1 13 4 14 13 15 15 9 13 6 12
10 7 13 5 10 7 3 15 12 10 14
10 15 15 10 1 2 8 7 5 15 12
1 5 7 1 14 11 2 12 7 9 4
10 15 7 5 9 2 12 11 13 9 6
9 12 9 13 13 9 13 1 12 1 12

As a matter of fact it is easy to generate sample mazes:

• fill grid with random numbers
• clean "doors" leading over the edges of the maze (manually or programmatically)
• try runing your bot, if not all maze is mapped, check where bot have stuck or which parts are not reachable, add some doors and repeat.

P.S. about efficiency, it should be noted that some functions may be not built-in, but defined through others in the init.scm (I believe R5RS standard called some of them "library functions"). Particularly

(list->vector (vector->list #(1 2 3 4 5 6 7 8 9 10)))

Takes over 200 evaluations. I can't find function for cloning (or something which could be effectively used for it) in R5RS standard, but it appears in R7RS. So probably it is a good thing to be added to our version of the interpreter (I'll try to see for it) but until this happened even manual cloning (make-vector and copy elements) may give slightly better results.