In this problem you are given a grid of numbers. This represents a map. Each number corresponds to the height of the ground at that grid point.
Part 1
Find all the low points in the grid add 1 to the value of each grid point and then sum those numbers. A low point is any point that is lower than any of its cardinal neighbors (up, down, left, right).
⎕←ex←↑(2 1 9 9 9 4 3 2 1 0) (3 9 8 7 8 9 4 9 2 1) (9 8 5 6 7 8 9 8 9 2) (8 7 6 7 8 9 6 7 8 9) (9 8 9 9 9 6 5 6 7 8)
┌→──────────────────┐
↓2 1 9 9 9 4 3 2 1 0│
│3 9 8 7 8 9 4 9 2 1│
│9 8 5 6 7 8 9 8 9 2│
│8 7 6 7 8 9 6 7 8 9│
│9 8 9 9 9 6 5 6 7 8│
└~──────────────────┘
⎕←b←¯1 ⊖ ¯1 ⌽(7 12 ↑ ex)+10×0=(⍳⍴ex)∊⍨⍳7 12 ⍝ add borders to the map
┌→──────────────────────────────────┐
↓10 10 10 10 10 10 10 10 10 10 10 10│
│10 2 1 9 9 9 4 3 2 1 0 10│
│10 3 9 8 7 8 9 4 9 2 1 10│
│10 9 8 5 6 7 8 9 8 9 2 10│
│10 8 7 6 7 8 9 6 7 8 9 10│
│10 9 8 9 9 9 6 5 6 7 8 10│
│10 10 10 10 10 10 10 10 10 10 10 10│
└~──────────────────────────────────┘
⍝ take the original bordered map and rotate it up down left right
{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌→────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ ┌→──────────────────────────────────┐ ┌→──────────────────────────────────┐ ┌→──────────────────────────────────┐ ┌→──────────────────────────────────┐ │
│ ↓10 2 1 9 9 9 4 3 2 1 0 10│ ↓10 10 10 10 10 10 10 10 10 10 10 10│ ↓10 10 10 10 10 10 10 10 10 10 10 10│ ↓10 10 10 10 10 10 10 10 10 10 10 10│ │
│ │10 3 9 8 7 8 9 4 9 2 1 10│ │10 10 10 10 10 10 10 10 10 10 10 10│ │ 2 1 9 9 9 4 3 2 1 0 10 10│ │10 10 2 1 9 9 9 4 3 2 1 0│ │
│ │10 9 8 5 6 7 8 9 8 9 2 10│ │10 2 1 9 9 9 4 3 2 1 0 10│ │ 3 9 8 7 8 9 4 9 2 1 10 10│ │10 10 3 9 8 7 8 9 4 9 2 1│ │
│ │10 8 7 6 7 8 9 6 7 8 9 10│ │10 3 9 8 7 8 9 4 9 2 1 10│ │ 9 8 5 6 7 8 9 8 9 2 10 10│ │10 10 9 8 5 6 7 8 9 8 9 2│ │
│ │10 9 8 9 9 9 6 5 6 7 8 10│ │10 9 8 5 6 7 8 9 8 9 2 10│ │ 8 7 6 7 8 9 6 7 8 9 10 10│ │10 10 8 7 6 7 8 9 6 7 8 9│ │
│ │10 10 10 10 10 10 10 10 10 10 10 10│ │10 8 7 6 7 8 9 6 7 8 9 10│ │ 9 8 9 9 9 6 5 6 7 8 10 10│ │10 10 9 8 9 9 9 6 5 6 7 8│ │
│ │10 10 10 10 10 10 10 10 10 10 10 10│ │10 9 8 9 9 9 6 5 6 7 8 10│ │10 10 10 10 10 10 10 10 10 10 10 10│ │10 10 10 10 10 10 10 10 10 10 10 10│ │
│ └~──────────────────────────────────┘ └~──────────────────────────────────┘ └~──────────────────────────────────┘ └~──────────────────────────────────┘ │
└∊────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
⍝ compare all the rotations with the original
(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌→────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ ┌→──────────────────────┐ ┌→──────────────────────┐ ┌→──────────────────────┐ ┌→──────────────────────┐ │
│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 1 1 0 0 0 1 1 1 1 1 0│ │0 1 1 1 1 1 1 1 1 1 1 0│ │0 0 1 0 0 0 0 0 0 0 1 0│ │0 1 1 0 0 0 1 1 1 1 1 0│ │
│ │0 1 0 0 0 0 0 1 0 1 1 0│ │0 0 0 1 1 1 0 0 0 0 0 0│ │0 1 0 0 1 1 0 1 0 0 1 0│ │0 1 0 1 1 0 0 1 0 1 1 0│ │
│ │0 0 0 1 1 1 1 0 0 0 1 0│ │0 0 1 1 1 1 1 0 1 0 0 0│ │0 0 0 1 1 1 1 0 1 0 1 0│ │0 1 1 1 0 0 0 0 1 0 1 0│ │
│ │0 1 1 1 1 1 0 0 0 0 0 0│ │0 1 1 0 0 0 0 1 1 1 0 0│ │0 0 0 1 1 1 0 1 1 1 1 0│ │0 1 1 1 0 0 0 1 0 0 0 0│ │
│ │0 1 1 1 1 1 1 1 1 1 1 0│ │0 0 0 0 0 0 1 1 1 1 1 0│ │0 0 1 0 0 0 0 1 1 1 1 0│ │0 1 1 0 0 0 1 1 0 0 0 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ └~──────────────────────┘ └~──────────────────────┘ └~──────────────────────┘ └~──────────────────────┘ │
└∊────────────────────────────────────────────────────────────────────────────────────────────────────────┘
⍝ sum up the comparison. Every 4 represents a low point.
+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌───────────────────────────┐
│ ┌→──────────────────────┐ │
│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 3 4 1 1 1 3 3 3 3 4 0│ │
│ │0 3 0 2 3 2 0 3 0 2 3 0│ │
│ │0 1 2 4 3 3 3 0 3 0 3 0│ │
│ │0 3 3 3 2 2 0 3 2 2 1 0│ │
│ │0 2 3 1 1 1 3 4 3 3 3 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ └~──────────────────────┘ │
└∊──────────────────────────┘
⍝ identify the low points
4=+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌───────────────────────────┐
│ ┌→──────────────────────┐ │
│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 0 1 0 0 0 0 0 0 0 1 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 0 0 1 0 0 0 0 0 0 0 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 0 0 0 0 0 0 1 0 0 0 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ └~──────────────────────┘ │
└∊──────────────────────────┘
⍝ mask for the low points
∊4=+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0│
└~──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
⍝ use the mask to pull the values out of the map
(,b)/⍨∊4=+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌→──────┐
│1 0 5 5│
└~──────┘
⍝ add one to the values as per the problem statement
1+(,b)/⍨∊4=+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌→──────┐
│2 1 6 6│
└~──────┘
⍝ sum the risk values
+/1+(,b)/⍨∊4=+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
15
Part 2
Find the 3 largest basins and multiply their sizes together. A basin is a set of points that all flow down to the same low point. Locations of height 9 are borders and dont count as basins.
⎕←mask←9≠¯1 ⊖ ¯1 ⌽(7 12 ↑ ex)+9×0=(⍳⍴ex)∊⍨⍳7 12 ⍝ everything not a wall
┌→──────────────────────┐
↓0 0 0 0 0 0 0 0 0 0 0 0│
│0 1 1 0 0 0 1 1 1 1 1 0│
│0 1 0 1 1 1 0 1 0 1 1 0│
│0 0 1 1 1 1 1 0 1 0 1 0│
│0 1 1 1 1 1 0 1 1 1 0 0│
│0 0 1 0 0 0 1 1 1 1 1 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
└~──────────────────────┘
From part 1 we already know the low points
⊃4=+/(⊂b)<{(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂b
┌→──────────────────────┐
↓0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 1 0 0 0 0 0 0 0 1 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 1 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 1 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
└~──────────────────────┘
⍝ set each low point id to its index location
7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→──────────────────────────┐
↓0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 15 0 0 0 0 0 0 0 23 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 40 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 68 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
└~──────────────────────────┘
⍝ apply rotations
{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ ┌→──────────────────────────┐ ┌→──────────────────────────┐ ┌→──────────────────────────┐ ┌→──────────────────────────┐ ┌→──────────────────────────┐ │
│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ ↓0 0 15 0 0 0 0 0 0 0 23 0│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ ↓0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 0 15 0 0 0 0 0 0 0 23 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 15 0 0 0 0 0 0 0 23 0 0│ │0 0 0 15 0 0 0 0 0 0 0 23│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 40 0 0 0 0 0 0 0 0│ │0 0 15 0 0 0 0 0 0 0 23 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 0 0 40 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 40 0 0 0 0 0 0 0 0 0│ │0 0 0 0 40 0 0 0 0 0 0 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 68 0 0 0 0│ │0 0 0 40 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ │0 0 0 0 0 0 0 68 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 68 0 0 0 0 0│ │0 0 0 0 0 0 0 0 68 0 0 0│ │
│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 68 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0 0 0│ │
│ └~──────────────────────────┘ └~──────────────────────────┘ └~──────────────────────────┘ └~──────────────────────────┘ └~──────────────────────────┘ │
└∊──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
⍝ combine up the rotations. low point ids have spread to neighbors
⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→────────────────────────────────┐
↓0 0 15 0 0 0 0 0 0 0 23 0│
│0 15 15 15 0 0 0 0 0 23 23 23│
│0 0 15 40 0 0 0 0 0 0 23 0│
│0 0 40 40 40 0 0 0 0 0 0 0│
│0 0 0 40 0 0 0 68 0 0 0 0│
│0 0 0 0 0 0 68 68 68 0 0 0│
│0 0 0 0 0 0 0 68 0 0 0 0│
└~────────────────────────────────┘
⍝ apply the border mask. this prevents the low points from corrupting any basin except their own
mask^⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→───────────────────────────────┐
↓0 0 0 0 0 0 0 0 0 0 0 0│
│0 15 15 0 0 0 0 0 0 23 23 0│
│0 0 0 40 0 0 0 0 0 0 23 0│
│0 0 40 40 40 0 0 0 0 0 0 0│
│0 0 0 40 0 0 0 68 0 0 0 0│
│0 0 0 0 0 0 68 68 68 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
└~───────────────────────────────┘
⍝ repeat until the basins have been fully filled by the low point id
({mask^⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂⍵}⍣50)7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→────────────────────────────────┐
↓0 0 0 0 0 0 0 0 0 0 0 0│
│0 15 15 0 0 0 23 23 23 23 23 0│
│0 15 0 40 40 40 0 23 0 23 23 0│
│0 0 40 40 40 40 40 0 68 0 23 0│
│0 40 40 40 40 40 0 68 68 68 0 0│
│0 0 40 0 0 0 68 68 68 68 68 0│
│0 0 0 0 0 0 0 0 0 0 0 0│
└~────────────────────────────────┘
⍝ pull out the unique ids
∪∊({mask^⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂⍵}⍣50)7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→────────────┐
│0 15 23 40 68│
└~────────────┘
⍝ each row is an indication of where that id is
{⍵∘.=⍨1↓∪⍵}∊({mask^⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂⍵}⍣50)7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
↓0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0│
└~──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
⍝ sum up the size of each basin and sort descending
{⍵[⍒⍵]}+/{⍵∘.=⍨1↓∪⍵}∊({mask^⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂⍵}⍣50)7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
┌→───────┐
│14 9 9 3│
└~───────┘
⍝ take the largest 3 and multiply the sizes
×/3↑{⍵[⍒⍵]}+/{⍵∘.=⍨1↓∪⍵}∊({mask^⊃∨/{(1↑⍵),(1 ¯1 ⊖¨⍵),(1 ¯1 ⌽¨⍵)} 2⍴⊂⍵}⍣50)7 12⍴{⍵∧⍳⍴⍵}∊⊃4=+/(⊂b)<{(1 ¯1⊖¨⍵),(1 ¯1⌽¨⍵)}2⍴⊂b
1134