Pythonic monotonic

Re:Pythonic monotonic by alecst on Friday August 13, 2021 @11:24AM (#28170057)

Gave it a try. I enjoy writing readable code but it's hard to judge one's own work. What do you all think?

  def monotonic(arr):
      """
      Turn an unordered list into a list of lists of monotone
      sequences. All sequences are converted to increasing.

      Start reading the list in chunks of two to decide if we're increasing or not.
      """

      if len(arr) <= 2: return sorted(arr)
  
      gen_arr = iter(arr)
      new_arr = []
      sub_arr = [next(gen_arr), next(gen_arr)]
      increasing = sub_arr[1] >= sub_arr[0]

      for m in gen_arr:
          if m >= sub_arr[-1] and increasing \
          or m <= sub_arr[-1] and not increasing:
              sub_arr.append(m)
          else:
              new_arr.append(sorted(sub_arr))   
              n = next(gen_arr, None)
              sub_arr, increasing = ([m, n], n >= m) if n else ([m], None)

      new_arr.append(sorted(sub_arr))

      return new_arr

Edit: thanks for the feedback. Changing `<` to `<=` has fixed some edge cases. Also swapped an if statement with a sort.

I think you could make it even more readable by traversing the list twice and keeping track of the runs.

[ Parent | on HN ]

Re:Pythonic monotonic by xorcist on Friday August 13, 2021 @11:43AM (#28170389)

This is the easiest one to read, thanks for that. If the intention of posting it was an invitation for review, here's a quick one.

Making the first entry a special case is probably a good idea, but it must also take into account when the first sub_arr is also the only:

  >>> monotonic([1, 2])
  []

There's also the fact that equality is considered a valid increase both not a valid decrease. One might expect that either it is valid as both or none. This is not necessarily wrong but may give surprising results:

  >>> monotonic([2, 1, 1, 1, 1, 2])
  [[1, 2], [1, 1], [1, 1], [1, 2]]

Otherwise a readable and straightforward implementation of a somewhat underspecified problem.

[ Parent | on HN ]

Re:Pythonic monotonic by alecst on Friday August 13, 2021 @12:26PM (#28171015)

Thanks. That was absolutely my intention and I'm grateful you replied. I amended this solution by changing strict > to >=, which seems to have fixed some of the problematic behavior.

[ Parent | on HN ]

Re:Pythonic monotonic by xorcist on Friday August 13, 2021 @01:45PM (#28172058)

Accepting equality is probably desirable, but as the test for ascending is first it will have precedence. If we accept both we probably need to defer the decision to find which it is. Otherwise there will be an inconsistency like:

  >>> monotonic([2, 2, 1])
  [[2, 2], [1]]

  >>> monotonic([1, 1, 2])
  [[1, 1, 2]]

As a separate detail, zeros are regarded false in Python:

  >>> monotonic([1, 2, 1, 0])
  [[1, 2], [1]]

[ Parent | on HN ]

Re:Pythonic monotonic by benburk on Friday August 13, 2021 @12:01PM (#28170657)

Fails for

  [1, 1, 2, 3, 3, 2, 1, 1] -> [[1, 1, 2, 3, 3], [1, 2], [1, 2], [1]]

[ Parent | on HN ]

Re:Pythonic monotonic by alecst on Friday August 13, 2021 @12:24PM (#28170981)

Thanks. I was inconsistent in my use of >= and >. Making them consistent has fixed this edge case.

[ Parent | on HN ]

Re:Pythonic monotonic by benburk on Friday August 13, 2021 @12:55PM (#28171451)

Also fails for

  [3, 3, 2, 2, 1, 1] -> [[3, 3], [2, 2], [1, 1]]

Here's my solution https://news.ycombinator.com/item?id=28170735

[ Parent | on HN ]

Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @01:18PM (#28171729)

And for [1]; the "return sorted(arr)" needs to be "return [sorted(arr)]".

[ Parent | on HN ]