3 ms·

> For total water we can use +/ (“sum over”), resulting in +/{((|\x)&||\|x)-x}. And they say Perl is bad.

by 1024core 2y ago

huhtenberg 2y ago
It's one of them "write-only" languages :)
RodgerTheGreat 2y ago
Perhaps you could grace us with your clearest alternative in a language you approve of?
- fifilura 2y ago
  Just for reference, and since I work with Trino these days. The benefit it gives me is that I almost never have to care about RAM or CPU. It just scales in all directions. The negative compared to vector languages is that order is not guaranteed (as can be seen) And the other negative of course is that it is not possible to write generalized functions. I am not saying it is better, but I'll leave it here. And yeah, it does not work with empty arrays. But this is my lunch break! WITH measurements AS ( SELECT index, m FROM UNNEST (ARRAY[3, 2, 5, 5, 3, 6, 5, 7, 2, 9, 2, 6, 1, 7, 2, 6, 9, 1, 1, 4, 2, 9, 2]) WITH ORDINALITY as t(m, index) ), tmp AS ( SELECT index, m, LEAST(MAX(m) OVER ( ORDER BY index), MAX(m) OVER( ORDER BY index DESC)) - m as water_level FROM measurements ) SELECT MAX(water_level) as max_level, SUM(water_level) as total_water FROM tmp
- 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 ago
    if 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 ago
      Adding 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 ago
        And 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 ago
    Your 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 ago
    Thank you!

> For total water we can use +/ (“sum over”), resulting in +/{((|\x)&||\|x)-x}. And they say Perl is bad.

huhtenberg 2y ago

It's one of them "write-only" languages :)

RodgerTheGreat 2y ago

Perhaps you could grace us with your clearest alternative in a language you approve of?

fifilura 2y ago
Just for reference, and since I work with Trino these days. The benefit it gives me is that I almost never have to care about RAM or CPU. It just scales in all directions. The negative compared to vector languages is that order is not guaranteed (as can be seen) And the other negative of course is that it is not possible to write generalized functions. I am not saying it is better, but I'll leave it here. And yeah, it does not work with empty arrays. But this is my lunch break! WITH measurements AS ( SELECT index, m FROM UNNEST (ARRAY[3, 2, 5, 5, 3, 6, 5, 7, 2, 9, 2, 6, 1, 7, 2, 6, 9, 1, 1, 4, 2, 9, 2]) WITH ORDINALITY as t(m, index) ), tmp AS ( SELECT index, m, LEAST(MAX(m) OVER ( ORDER BY index), MAX(m) OVER( ORDER BY index DESC)) - m as water_level FROM measurements ) SELECT MAX(water_level) as max_level, SUM(water_level) as total_water FROM tmp
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 ago
  if 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 ago
    Adding 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 ago
      And 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 ago
  Your 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 ago
  Thank you!