I searched in the book for the passage the GP mentioned. It is on page 2, the 6th step in solving an interview problem. The steps are outlined in the book, and the code snippet for each listed. Here they are:
1- Scanning an array x and finding the running maximum is expressed by |\x (read “max scan of x”), the highest altitude to the West.
2- Reversing an array is achieved by inserting a | (“reverse”) before the array. ||\|x (“reverse max scan of reverse x”) will give us the highest altitude to the East.
3- Comparing two vectors element-wise is done with the & (“min”) operation, this is the water level.
4- The element-wise subtraction is -. Adding parentheses to ensure correct sequence of evaluation, and brackets to make it a function that takes an argument, results in {((|\x)&||\|x)-x}. This is a function that returns the height of the column of water at every point.
5- Using this function, we can easily get derived results, for example for the maximum height we can use |/ (“max over”), resulting in |/{((|\x)&||\|x)-x}.
6- For total water we can use +/ (“sum over”), resulting in +/{((|\x)&||\|x)-x}
Maybe you find this satisfying, I find it horrendous.
Here's the implementation in python/numpy:
west_scan = np.maximum.accumulate(A)
east_scan = np.maximum.accumulate(A[::-1])[::-1]
water_level = np.minimum(west_scan, east_scan)
height_water_column = water_level - A
max_height = np.max(height_water_column)
total_water = np.sum(height_water_column)
1- Scanning an array x and finding the running maximum is expressed by |\x (read “max scan of x”), the highest altitude to the West.
2- Reversing an array is achieved by inserting a | (“reverse”) before the array. ||\|x (“reverse max scan of reverse x”) will give us the highest altitude to the East. 3- Comparing two vectors element-wise is done with the & (“min”) operation, this is the water level.
4- The element-wise subtraction is -. Adding parentheses to ensure correct sequence of evaluation, and brackets to make it a function that takes an argument, results in {((|\x)&||\|x)-x}. This is a function that returns the height of the column of water at every point.
5- Using this function, we can easily get derived results, for example for the maximum height we can use |/ (“max over”), resulting in |/{((|\x)&||\|x)-x}.
6- For total water we can use +/ (“sum over”), resulting in +/{((|\x)&||\|x)-x}
Maybe you find this satisfying, I find it horrendous.
Here's the implementation in python/numpy: