An APL Translation of 'Square Joy: Trapped Rainwater' J Posting

 I saw an interesting post entitled "Square Joy: Trapped Rainwater" on the mmapped blog, describing how to approach the problem of computing water levels in a 2D Flatland cityscape.

The configuration of bars with heights 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, and the water trapped by this configuration.

The author uses J, so I thought I'd take a quick look at converting the basic computation into its parent language, APL. Turns out it's quite simple (minus the graphic representation which I haven't yet looked at doing in GNU APL).

J has the  /\. adverb ('suffix'), here applied to the 'insert' (/) which it shares with APL. APL must simulate it via two applications of the reversal (⌽) function:

      H ← 0 1 0 2 1 0 1 3 2 1 2 1
      ⌈\H
0 1 1 2 2 2 2 3 3 3 3 3
      ⌽⌈\⌽H    ⍝ Note the use of 'reversal' here (⌽) with insert (/) to match J's 'suffix scan'
3 3 3 3 3 3 3 3 2 2 2 1
      (⌈\H) ⌊ (⌽⌈\⌽H)
0 1 1 2 2 2 2 3 2 2 2 1

Maybe later I'll try to create the visual renderings in GNU APL to match what the J solution does.

String Interpolation in APL -- Formatted string output ala printf()

This is not as sophisticated as C's printf() of course, but it's enough for many uses.

  ∇r ← s sInterp sv
⍝⍝ Interpolate items in sv into s (string field substitution)
⍝ s: string - format string, '∆' used for interpolation points
⍝ sv: vector - vector of items to interpolate into s
⍝ r: interpolated string
  s[('∆'=s)/⍳⍴s] ← ⊃¨(⍕¨sv)
  r ← ∊s
∇
      'Mary had a ∆ lamb, its fleece was ∆ as ∆.' sInterp 'little' 'black' 'night'
Mary had a little lamb, its fleece was black as night.
      'Mary had a ∆ lamb, its fleece was ∆ as ∆.' sInterp 'little' 'large' 42
Mary had a little lamb, its fleece was large as 42.

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 
+-+-+-+-+-+-+-+-+-+
|     |       |   |
+-+ + +-+-+ + +-+ +
|   |       |   | |
+ +-+-+-+-+-+-+ + +
|     |     | | | |
+-+-+ +-+ + + + + +
|   |   | |   |   |
+ + +-+-+ +-+-+-+ +
| | |   |       | |
+ +-+ + + +-+ +-+ +
| |   |   |   |   |
+ + +-+-+-+ + + +-+
| |   |   | | | | |
+ +-+ + +-+ +-+ + +
|   | | |   |   | |
+ +-+ + + +-+ +-+ +
|       |         |
+-+-+-+-+-+-+-+-+-+