4 ms·
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
by credit_guy 2y ago
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)
- RodgerTheGreat 2y agoif you insist on verbose names, they're always an option in K: west_scan : |\ A east_scan : ||\| A water_level : west_scan & east_scan height_water_column : water_level - A max_height : |/ height_water_column total_water : +/ height_water_column
- chrispsn 2y agoAdding to RodgerTheGreat's comment: for me, k's power is its rich set of adverbs that are convenient to write. Notice that aside from reverse (monadic |), all verb symbols in the above code are in most other languages (max as |, min as &, plus as +, minus as -). Adverbs (such as / for reduce and \ for scan-reduce) make the symbols we already have more generally applicable. I think a language could go a long way with a small set of basic arithmetic symbols alongside a rich set of adverb symbols.
- RodgerTheGreat 2y agoAnd perhaps further worth noting, the reason K uses dyadic & and | for minimum and maximum (respectively) is because logical AND and logical OR are identical to minimum and maximum if the arguments happen to be boolean (0/1). The notation and selection of primitives illustrate a useful and memorable symmetry.
- cess11 2y agoYour Python solution is very deeply coupled with this specific problem, more than half of the code consists of names taken directly from the problem description. I don't think it is equivalent with the K solution. You could add names in a similar manner to it and they would be more equivalent. For me a nice thing about the Iverson languages is that idiomatic programs tend to be mathematically general and explain the problem in more general terms than a naive, immediate solution in a more popular scripting language.
- 1024core 2y agoThank you!
- rak1507 2y agoDoesn't work on empty arrays, whereas the K does and gives the reasonable result of 0 (for total water) and -inf for maximum height. Maybe it doesn't matter, but sensible defaults are a good thing! Edit: didn't look at the error closely enough to see that the only thing that breaks is the maximum height. That's not that bad, but still not ideal imo.
- credit_guy 2y agoI have to emphatically disagree here. The result may be reasonable, but this is just a fluke. Numpy complains that: "ValueError: zero-size array to reduction operation maximum which has no identity". This error makes sense. The only meaningful result for the maximum of an empty array would be minus infinity. It should not be zero. If it's zero, it means the programming language makes the silent assumption that the elements are non-negative. I very much prefer to have the code throw back a meaningful error at me than a reasonably looking result, and then fail silently in a different situation.
- rak1507 2y agoI agree that the maximum of an empty array should be -infinity. As does K! (numpy does not)
- maxbond 2y agoWould you agree with the statement, "the maximum of an array should be contained in that array?" That seems like a reasonable constraint that most languages uphold.
- rak1507 2y agoNo. I think the maximum of (x:xs) should be equal to max x (maximum xs). (Using haskell notation). Logically this implies maximum [] should be -infinity if it is defined. On finite lists, maximum is also the same as the supremum, and on infinite sets the supremum doesn't necessarily have to be contained in the set. So there's at least some precedent for not having the maximum in the list.