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.