3 ms·

It's kind of interesting how we're discussing which solution is most pythonic, but nobody has managed to write a solution which actually works. This is partiall

It's kind of interesting how we're discussing which solution is most pythonic, but nobody has managed to write a solution which actually works. This is partially because the problem is slightly ambiguous, but even then nobody seems to have written a version that works for any of the possible interpretations of the problem. Most solutions suffer from a combination of any of the following problems: - Not using strict vs non-strict monotonicity consistently - Failing to identify the correct direction of a run (either not bothering at all or failing for any run starting with two equal values) - Assuming the first run is increasing (implicitly by comparing with negative infinity) There's also nobody who seems to have given thought on how to solve the ambiguity when you allow runs that are not strictly monotonic.

dec0dedab0de 5y ago
This is a really good point. I am very big on making code Pythonic, but I always tell junior developers to get the thing to work first. Once it works, we can re-write it with the advantage of hindsight. The hard part is getting people to tell the manager it's going to be a few days longer even though it's already working.
- contravariant 5y ago
  Yeah, though at this point it would help to be a bit more explicit about what we even want. The most consistent interpretation I can come up with as follows: - Partition the list into strictly monotonic runs (either increasing or decreasing) - Reverse the decreasing runs. But writing a version that is entirely bug free turns out to be surprisingly tricky. You also need to be careful about how you allow runs to be split up. You can't require each run to be maximally large because then [1,2,3,4,3,2,1] must be partitioned into overlapping runs. You also can't just require the list to be partition into any set of monotonic runs, because then [[1],[2],[3],[4]] is a valid partition of [1,2,3,4]. This is especially a problem when you allow runs that aren't strictly monotonic.

dec0dedab0de 5y ago

This is a really good point. I am very big on making code Pythonic, but I always tell junior developers to get the thing to work first. Once it works, we can re-write it with the advantage of hindsight. The hard part is getting people to tell the manager it's going to be a few days longer even though it's already working.

contravariant 5y ago
Yeah, though at this point it would help to be a bit more explicit about what we even want. The most consistent interpretation I can come up with as follows: - Partition the list into strictly monotonic runs (either increasing or decreasing) - Reverse the decreasing runs. But writing a version that is entirely bug free turns out to be surprisingly tricky. You also need to be careful about how you allow runs to be split up. You can't require each run to be maximally large because then [1,2,3,4,3,2,1] must be partitioned into overlapping runs. You also can't just require the list to be partition into any set of monotonic runs, because then [[1],[2],[3],[4]] is a valid partition of [1,2,3,4]. This is especially a problem when you allow runs that aren't strictly monotonic.