2
\$\begingroup\$

Consider a bucket array containing sorted and/or empty buckets, and the goal is to extract the longest possible sequence in sorted order, under the following conditions:

  1. Only one element in each bucket can be used per construction, and the same element cannot be reused if encountered in another bucket.

  2. Buckets cannot be rearranged, reordered, or repositioned, and must be treated incidentally in the provided order.

  3. Empty buckets can be skipped.

Further Insights

Sadly, the naive Dynamic Programming attempt (which is expected to walk from behind while assigning a max length of 1 to each element of the last bucket, and then buildup incrementally towards the first bucket) ultimately fails since no successful chain dependency can be established between all subproblems. This is because in a situation like in B3 for example (see second code block), there is no (efficient) way of telling B3[1][0] (which is 3) that it is greater than B3[6][0] (i.e. 2) without writing very nasty and inefficient loops.

I have decided to call this Longest Sorted Bucket Sequence/Subsequence as it can be considered a variant of the popular Leetcode problem: Longest Increasing Subsequence.

Below is my best attempt implemented in Python, however, I am stuck with devising a correct routine for processing B4 and B5. Is there a possibility of solving this without resorting to brute-force?

Current Progress

from collections import deque

# Longest Sorted Bucket Sequence
def LSBS(B):
    B = [deque(i) for i in B]
    PM = []
    pm = []
    for j in range(len(B)):
        if len(B[j]) == 0:
            continue
        else:
            if len(pm) > 0:
                prev = pm[len(pm)-1]
                matched = None
                for m in B[j]:
                    if m > prev:
                        pm.append(m)
                        matched = m
                        break
                if not matched:
                    PM.append(pm)
                    pm = []
            else:
                m = B[j].popleft()
                pm.append(m)

    PM.append(pm)
    return max(PM, key=len)

Test code

if __name__ == "__main__":
    # Output = [0, 1, 3, 4]; [0, 2, 3, 4] is also correct
    B1 = [
        [3], [0, 4], [2], [0, 4], [1], [3], [0, 4]
    ]

    # Output = [0, 3, 4, 5, 6, 9]; [1, 3, 6, 7, 9, 11] is also correct
    B2 = [
        [1, 8, 10], [3, 6, 7], [3, 6, 7], [0], [0], [3, 6, 7],
        [2, 4, 5, 9, 11], [2, 4, 5, 9, 11], [3, 6, 7], [2, 4, 5, 9, 11]
    ]

    # Output = [0, 3, 4, 5, 6]; [0, 3, 4, 5, 7] and [1, 3, 6, 7, 9] are also correct
    B3 = [
        [1, 8, 10], [3, 6, 7], [3, 6, 7], [0], [0],
        [3, 6, 7], [2, 4, 5, 9], [2, 4, 5, 9], [3, 6, 7]
    ]

    # Output = [0, 1, 2, 4]; code produces [1, 2, 4] instead
    B4 = [
        [3], [0], [1], [2], [4]
    ]

    # Output = [6, 7]; code produces [6] instead
    B5 = [
        [], [], [], [9], [6], [7], [0], [], [], []
    ]

    for b in B1,B2,B3,B4,B5:
        print(f"{b}\n{LSBS(b)}\n")
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

different concept? different name!

from collections.abc import Container
...
    B = [deque(i) for i in B]

You didn't annotate it, but B apparently came in with a type of B: Container[int]. And now it is of deque[int], something the subsequent code will depend upon (e.g. tuple lacks an .append() method).

Please use a new name for a new concept. Maybe the signature's parameter name could be buckets_in, which we immediately fix up with a list(map(deque, buckets_in)) expression.

docstring

# Longest Sorted Bucket Sequence
def LSBS(B):

Pep-8 asked you nicely to use def lsbs(b): names. Similarly B5 should be b5. I do thank you for commenting on how I should pronounce that tetragrammaton.

Using a single-letter identifier as part of your Public API is not appropriate here. Please spell out "buckets".

Also, the # comment was helpful, but it really belongs down in a """docstring""" for the function.

wrong name

    PM = []
    pm = []

Oh, my goodness! Now you're just deliberately trying to make it hard to reason about this code. Pick a new name for one of those, please. You didn't even tell me how to mentally pronounce it. I tried "plus minus", "previously matched", "post meridian", and got stuck there.

idiomatic looping

    for j in range(len(B)):

Prefer to iterate over enumerate(B) here. Then you won't need all those [j] subscripts. Oh, wait, then you won't need j at all! So for bucket in buckets: would suffice, of even for b in buckets:.

            if len(pm) > 0:

Also, you might shorten such expressions down to just if pm:.

algorithm

That \$O(n)\$ linear scan seems inconvenient. Should we maybe prefer binary search instead?

If you're willing to depend on sortedcontainers, you can let its methods do some of the work for you. Or you might import bisect.

test suite

Thank you for providing one.

if __name__ == "__main__":
    # Output = [0, 1, 3, 4]

That's crazy. You're asking me to visually compare stdout and the source code. But the code already knows the right answer! Tell the code to do the comparison and display a Green bar:

import unittest

class LongestSortedBucketSequenceTest(unittest.TestCase):

    def test_lsbs(self) -> None:
        b1 = [
            [3], [0, 4], [2], [0, 4], [1], [3], [0, 4]
        ]
        self.assertEqual([0, 1, 3, 4], lsbs(b1))
        b2 = ...

Invoke with $ python -m unittest *.py. Or use pytest if you prefer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.