Maze Mapping Robot

In this problem code for maze-crawling robot should be written in Scheme language. Please refer to earlier problems by tag scheme if you are not acquainted with details yet.

Young programmer Gill Bates have fallen in love with the beautiful daugther of local Raja. When he came to court and was introduced to majestic father, Raja asked to explain what is "programmer" at all. Unsuspicious fellow started explaining, and gave example of maze-solving algorithms.

"Har-har-har!!! Then I have a challenge for you!" - laughed Raja viciously...

There is an ancient maze under the Royal Palace, much older than the Palace itself. Numerous adventurers were offered good reward to investigate it - and many tried - never to be seen again!

Young man was thrown into dungeon and told to create complete map of the maze. Once this is accomplished, guards will fetch him back with ropes - but should he fail, he may just sit and wait there to die of starvation or more horrible evils lurking underneath.

Problem Statement

Maze is square, N by N rooms. Each room may have door to any of 4 adjacent ones, but not always. Some doors may be opened from both sides (e.g. they are "bi-directional"), while others are "one-way" (suppose they have no handle on the other side). At last there are walls without doors.

We need to create an algorithm to investigate all the rooms, in the form of Scheme function:

(define (explore n) ...)

As a parameter, the size of the maze is passed. The algorithm can call two pre-existing methods:

(look) returns value in range 1..15 describing exits in the current room (see below)
(move dir) instructs system to go to adjacent cell in the given direction (fails if there is no door)

Directions are integers in range 0..3:

         3 - north
2 - west           0 - east
         1 - south

Looking around with look function returns 4-bit value, where bits from 0 to 3 tell about existence of the door in the corresponding direction. E.g. 13 (or binary 1101) means there are three exits - in all walls except south (0-th is least significant, rightmost bit).

When explore function finishes, it should return the map of the maze, in a list-of-lists form. First sub-list corresponding to northernmost rooms, and first element in every sub-list corresponding to westernmost room in a row.

Input / Output

Consider the following sketch program, which defines some maze along with look and move functions:

(define maze (list
  (list #b0011 #b0110 #b0100 #b0010 #b0110)
  (list #b0011 #b0101 #b1111 #b0101 #b1110)
  (list #b0010 #b0011 #b1101 #b0111 #b1100)
  (list #b1010 #b1111 #b0011 #b0010 #b1010)
  (list #b1001 #b1000 #b0101 #b0101 #b1000)
))

(define *x 2)
(define *y 2)

(define (bit-set? v b)
    (> (modulo (quotient v (expt 2 b)) 2) 0))

(define (look)
    (list-ref (list-ref maze *y) *x))

(define (move d)
    (let ((v (look)))
        (if (or (< d 0) (> d 3) (not (bit-set? v d)))
            #f
            (begin (cond
                ((= d 0) (set! *x (+ 1 *x)))
                ((= d 1) (set! *y (+ 1 *y)))
                ((= d 2) (set! *x (- *x 1)))
                ((= d 3) (set! *y (- *y 1)))) #t))))

You can play with it, entering all these definitions and then executing interactively chain of (look) and (move ..) functions. E.g.

(look)      ; says 13
(move 3)    ; says #t
(look)      ; says 15
(move 1)    ; says #t
(move 1)    ; says #f

Here we initially are in the center room, make one step north, then back, then try go south and this fails as there are no door. However note, young man wasn't necessarily dropped in the center.

In this case, our implementation of explore function should return list like this:

((3 6 4 2 6) (3 5 15 5 14) (2 3 13 7 12) (10 15 3 2 10) (9 8 5 5 8))

(i.e. we need to figure out the content of secret maze variable).

P.S. with compiled version of interpreter you may save the code above into some file (say, maze.scm) and run the command like this

tinyscheme.exe maze.scm -       # windows version

./tinyscheme maze.scm -         # *nix version

In both cases the spare "-" in the end means to proceed interactively after loading the preceeding files.

Note: your function will be tested against two mazes, smaller (7*7) and larger (10*10) one. Make sure you reinitialize variables if necessary! Verdicts for smaller maze are bit more detailed. Larger is not tested if smaller fails.