A Recursive Depth-First Maze Generator in GNU APL

Rosettacode.org is a great place to grab little ideas and apply them to learning a new language; especially if there isn't a solution there yet in the language you're learning! This past week I took some spare time in the evenings to implement the classic maze generator problem, in GNU APL.

Takeaways:

• Sometimes just manipulating the string representation of a maze is easier than trying to come up with a clever binary representation (I started with the idea that each maze cell's walls could be a 4-bit field, eg. nsew = [3210], but the shared walls between cells made it too messy);
• GNU APL's ? (shuffle) operator appears to have a static seed and the docs don't clearly state how to seed it: the ⎕RL system variable has the shuffle op's internal state so assigning to it will seed the PRNG, eg:

⎕RL ← +/ ⎕TS ⍝⍝ Seed ⎕RL (?) PRNG with sum of timestamp Y, M, D, H, M, S, ms

#!/usr/local/bin/apl --script --
 ⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝
⍝                                                                    ⍝
⍝ mazeGen.apl                          2022-01-07  19:47:35 (GMT-8)  ⍝
⍝                                                                    ⍝
 ⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝

∇initPRNG
  ⍝⍝ Seed the internal PRNG used by APL ? operator
  ⎕RL ← +/ ⎕TS   ⍝⍝ Not great... but good enough
∇

∇offs ← cellTo dir
  ⍝⍝ Return the offset (row col) to cell which lies in compass (dir)
  offs ← ∊((¯1 0)(0 1)(1 0)(0 ¯1))[('nesw'⍳dir)]
∇

∇doMaze rc
  ⍝⍝ Main function
  0 0 mazeGen rc      ⍝⍝ Do the maze gen
  m                   ⍝⍝ output result
∇

∇b ← m isVisited coord;mr;mc
  →( ∨/ (coord[1] < 1) (coord[2] < 1) )/yes
  →( ∨/ (coord > ⌊(⍴m)÷2) )/yes
  b ← ' ' ∊ m[2×coord[1];2×coord[2]]
  →0
yes:
  b←1
∇

∇c mazeGen sz ;dirs;c;dir;cell;next
  →(c≠(0 0))/gen
init:
  c ← ?sz[1],?sz[2]
  m ← mazeInit sz
gen:
  cell ← c
  dirs ← 'nesw'[4?4]
  m[2×c[1];2×c[2]] ← ' '  ⍝ mark cell as visited
dir1:
  dir ← dirs[1]
  next ← cell + cellTo dir
  →(m isVisited next)/dir2
  m ← m openWall cell dir
  next mazeGen sz
dir2:
  dir ← dirs[2]
  next ← cell + cellTo dir
  →(m isVisited next)/dir3
  m ← m openWall cell dir
  next mazeGen sz
dir3:
  dir ← dirs[3]
  next ← cell + cellTo dir
  →(m isVisited next)/dir4
  m ← m openWall cell dir
  next mazeGen sz
dir4:
  dir ← dirs[4]
  next ← cell + cellTo dir
  →(m isVisited next)/done
  m ← m openWall cell dir
  next mazeGen sz
done:
∇

∇m ← mazeInit sz;rows;cols;r
  ⍝⍝ Init an ASCII grid of size (rows cols) which
  ⍝⍝ has all closed and unvisited cells:
  ⍝⍝
  ⍝⍝  +-+
  ⍝⍝  |.|
  ⍝⍝  +-+
  ⍝⍝
  ⍝⍝ @param sz - tuple (rows cols)
  ⍝⍝ @return m - a (rows × cols) ASCII matrix
  ⍝⍝⍝⍝

  initPRNG
  (rows cols) ← sz
  r ← ∊ (cols ⍴ ⊂"+-" ),"+"
  r ← r,∊ (cols ⍴ ⊂"|." ),"|"
  r ← (rows,(⍴r))⍴r
  r ← ((2×rows),(1+2×cols))⍴r
  r ← r⍪ (∊ (cols ⍴ ⊂"+-" ),"+")
  m ← r
∇

∇r ← m openWall cellAndDir ;ri;ci;rw;cw;row;col;dir
  (row col dir) ← ∊cellAndDir
  ri ← 2×row
  ci ← 2×col
  (rw cw) ← (ri ci) + cellTo dir
  m[rw;cw] ← ' '   ⍝ open wall in (dir)
  r ← m
∇

⎕IO←1

doMaze 9 9
)OFF

russtopia@rlm-devuan:~/GNUAPL$ workspaces/mazeGen.apl 
+-+-+-+-+-+-+-+-+-+
|     |       |   |
+-+ + +-+-+ + +-+ +
|   |       |   | |
+ +-+-+-+-+-+-+ + +
|     |     | | | |
+-+-+ +-+ + + + + +
|   |   | |   |   |
+ + +-+-+ +-+-+-+ +
| | |   |       | |
+ +-+ + + +-+ +-+ +
| |   |   |   |   |
+ + +-+-+-+ + + +-+
| |   |   | | | | |
+ +-+ + +-+ +-+ + +
|   | | |   |   | |
+ +-+ + + +-+ +-+ +
|       |         |
+-+-+-+-+-+-+-+-+-+