; This program attempts to find the exit of a maze. If a path to exit is found,
; it stores a 1 in x4000, otherwise, it stores a 0 in x4000.

            .ORIG x3000
            LD  R6, STACK

            ; compute the address of the starting point
            LEA R0, MAZE
            LD  R1, START_IDX
            ADD R0, R0, R1    

            JSR FIND_EXIT
            STI R1, OUTPUT
            HALT

STACK       .FILL xFE00
OUTPUT      .FILL x4000
START_IDX   .FILL #9      ; the index of the starting location in the maze
                          ; Read comments above definition of MAZE for details

; Recursive subroutine that determines if there is a path from current cell
; to the exit point.
; input: R0, current cell address
; output: R1, Yes (1) or No (0)

FIND_EXIT   ; save modified registers into the stack.
            STR R2, R6, #-1
            STR R3, R6, #-2
            STR R4, R6, #-3
            STR R5, R6, #-4
            STR R7, R6, #-5
            ADD R6, R6, #-5
            
            ; Move cell address to R3, since we need to use R0 
            ; as the input to recursive subroutine calls.
            ADD R3, R0, #0        

            ; Put breadcrumb in the current cell.
            LDR R2, R0, #0
            LD  R7, BREADCRUMB
            ADD R2, R2, R7
            STR R2, R0, #0

            ; If the exit is in this cell, return yes
            LD  R7, EXIT_MASK
            AND R7, R2, R7
            BRnp DONE_YES

            AND R2, R2, #0     ; R2 is the loop counter
            LEA R4, OFFSETS    ; R4 is the pointer to correct offsets
            LD  R5, NORTH_MASK ; R5 is the bit mask 
            
AGAIN       LDR R7, R3, #0    ; Reload current cell information
            AND R7, R5, R7
            BRz SKIP          ; If the way is blocked, check next direction
            LDR R7, R4, #0
            ADD R7, R3, R7
            LDR R7, R7, #0
            BRn SKIP          ; If there is breadcrumb on the way, check next direction
            LDR R7, R4, #0
            ADD R0, R3, R7
            JSR FIND_EXIT
            ADD R1, R1, #0
            BRp DONE_YES
            
SKIP        ADD R2, R2, #1    ; Increment loop counter
            ADD R7, R2, #-4
            BRp DONE_NO       ; If finished checking all 4 direction, return no
            ADD R4, R4, #1    ; Increment offset pointer
            ADD R5, R5, R5    ; left shift bit mask to prepare for next direction
            BR  AGAIN

DONE_NO     AND R1, R1, #0
            BR  RESTORE
            
DONE_YES    AND R1, R1, #0
            ADD R1, R1, #1
            
RESTORE     ADD R0, R3, #0 ; restore R0 from R3
            ; restore the rest of the modified registers from the stack.
            LDR R7, R6, #0
            LDR R5, R6, #1
            LDR R4, R6, #2
            LDR R3, R6, #3
            LDR R2, R6, #4
            ADD R6, R6, #5
            RET

BREADCRUMB  .FILL x8000
EXIT_MASK   .FILL x0010
NORTH_MASK  .FILL x0001

            ; the next 4 locations hold offsets needed to get to north,
            ; east, west, and south respectively
OFFSETS     .FILL #-6
            .FILL #1
            .FILL #-1
            .FILL #6

; The data structure initialized below represents the 6x6 maze shown in the
; comments. Each location in memory stores information relevant for one cell.
; Bits 0, 1, 2, and 3 in each words are set to 1 if path towards north, east,
; west, and south exists. Bit 4 is set if the cell is an exit point. bit 15
; is initialized to zero and is used as a placeholder for breadcrumbs needed
; by the recursive algorithm.
;    _ _ _ _ _ _
;   |_|_ _  |_| |
;   | | |_|S|_| |
;   | |  _    | |
;   |_ _|_| | |_|
;   | |  _ _|_|_|
;   |_|E|_ _ _ _|

; The maze is stored in row major-order, meaning that the cells corresponding
; to each row are stored in sequential order. 
; first row : indices 0 to 5
MAZE        .FILL x0000
            .FILL x0002
            .FILL x0006
            .FILL x000C
            .FILL x0000
            .FILL x0008
; second row : indices 6 to 11
            .FILL x0008
            .FILL x0008
            .FILL x0000
            .FILL x0009
            .FILL x0000
            .FILL x0009
; third row : indices 12 to 17
            .FILL x0009
            .FILL x000B
            .FILL x0006
            .FILL x000F
            .FILL x000C
            .FILL x0009
; fourth row : indices 18 to 23
            .FILL x0003
            .FILL x0005
            .FILL x0000
            .FILL x0009
            .FILL x0009
            .FILL x0001
; fifth row : indices 24 to 29
            .FILL x0008
            .FILL x000A
            .FILL x0006
            .FILL x0005
            .FILL x0001
            .FILL x0000
; sixth row : indices 30 to 35 
            .FILL x0001
            .FILL x0019
            .FILL x0002
            .FILL x0006
            .FILL x0006
            .FILL x0004

            .END