Piling Up with Python

Question

This is my solution for a Hackerrank problem. The problem was:

There is a horizontal row of cubes. The length of each cube is given. You need to create a new vertical pile of cubes. The new pile should follow these directions: if cube_i is on top of cube_j then sideLength_j >= sideLength_i.

When stacking the cubes, you can only pick up either the leftmost or the rightmost cube each time. Print "Yes" if it is possible to stack the cubes. Otherwise, print "No". Do not print the quotation marks.

Input Format

The first line contains a single integer T, the number of test cases. For each test case, there are 2 lines. The first line of each test case contains , the number of cubes. The second line contains space separated integers, denoting the sideLengths of each cube in that order.

Constraints

1 <= T <= 5
1 <= n <= 10**5
1 <= sideLength <= 2**31

Output Format

For each test case, output a single line containing either "Yes" or "No" without the quotes.

Sample Input

2
6
4 3 2 1 3 4
3
1 3 2

Sample Output

Yes
No

Explanation

In the first test case, pick in this order: left - 4, right - 4, left - 3, right - 3, left - 2, right - 1. In the second test case, no order gives an appropriate arrangement of vertical cubes. 3 will always come after either 1 or 2.

My code is actually rather short:

if __name__ == '__main__':
    num_tests = int(input().strip())

    for _ in range(num_tests):
        num_cubes = int(input().strip())
        cube_sidelengths = list(map(int, map(str.strip, input().strip().split())))


        i, j = 0, len(cube_sidelengths)-1
        pile = []

        while i != j:
            left, right = cube_sidelengths[i], cube_sidelengths[j]
            # In case there is nothing in the pile just add the bigger one
            if not pile:
                if left > right:
                    pile.append(left)
                    i += 1
                else:
                    pile.append(right)
                    j -= 1
            else:
                # Take the bigger of the left and right element and compare it
                # to the last item on the pile. If it's bigger we can't pile
                # it up, otherwise put it on the pile and continue
                if left > right:
                    if left > pile[-1]:
                        print('No')
                        break
                    else:
                        pile.append(left)
                        i += 1
                else:
                    if right > pile[-1]:
                        print('No')
                        break
                    else:
                        pile.append(right)
                        j -= 1
        else:
            print('Yes')

But I'm actually not very satisfied with the code. It passes all Hackerrank tests but I can't help feeling that it's missing something - but I can't put my finger on it.

An additional thing that has been bugging me was that it was part of the "Python collections" problems but I haven't used anything from the collections module. It would be possible to use a deque here but that felt like overkill - because pop and popLeft are O(1) but just keeping the indices and accessing a list is also O(1) so it wouldn't even provide better asymptotic behaviour. So as additional question: Is there anything that could be improved by using a deque?

Otherwise I would be very glad about any feedback how I could improve the code.

Answer 1

You don't need to build the pile

Why make the extra effort to "pop" and "append" where the only expected result is a boolean value (it is possible or not). Using your approach, all you need is a variable holding the last used cube to compare the next two to.

You'd better return than print

Instead of printing from your main part of the computation, return a meaningful result instead; and let the caller print something according to it. This "forces" you to build functions and make your code more reusable.

In the same vein, separate the input parsing part from the core of your computation.

---

Also incorporating @MrGrj advices, your code can look like:

def can_pile_cubes(cube_lengths):
    cube_on_top = None
    left_index = 0
    right_index = len(cube_lengths) - 1

    while left_index < right_index:  # Avoid corner case of `cube_lengths` being an empty list
        left_cube = cube_lengths[left_index]
        right_cube = cube_lengths[right_index]

        if cube_on_top is None:
            if left_cube > right_cube:
                cube_on_top = left_cube
                left_index += 1
            else:
                cube_on_top = right_cube
                right_index -= 1
        else:
            if left_cube > right_cube:
                if left_cube > cube_on_top:
                    return False
                cube_on_top = left_cube
                left_index += 1
            else:
                if right_cube > cube_on_top:
                    return False
                cube_on_top = right_cube
                right_index -= 1

    return True


def parse_test_case():
    input()  # Throw away number of cubes
    return [int(x) for x in input().split()]


if __name__ == '__main__':
    num_tests = int(input())
    for _ in range(num_tests):
        can_pile = can_pile_cubes(parse_test_case())
        print('Yes' if can_pile else 'No')

---

Use efficient looping

Now looking at the code at hand, maintaining explicit indexes in a while loop does not feel very Pythonic. So let's take a closer look at the problem: checking that the biggest end of the two in the current state of the list is no bigger than the last poped item lead to the property that, if the list is pileable, its first part is in decreasing order up to a minimum and from this minimum onward the second part is in increasing order.

This property is easy to check if we can access items by pairs. This is exactly what the pairwise recipe from itertools allow us to do.

We thus just need to check that each pair in the list is in decreasing order and, once we found a pair that doesn't fit the condition, that all remaining pairs are in increasing order:

import itertools


def pairwise(iterable):
    first, second = itertools.tee(iterable)
    next(second, None)
    return zip(first, second)


def can_pile_cubes(cube_lengths):
    pairs = pairwise(cube_lengths)

    # First part of the list, check if decreasing order
    for first, second in pairs:
        if first < second:
            break

    # Second part of the list, check if increasing order
    for first, second in pairs:
        if first > second:
            return False

    return True


def parse_test_case():
    input()  # Throw away number of cubes
    return [int(x) for x in input().split()]


if __name__ == '__main__':
    num_tests = int(input())
    for _ in range(num_tests):
        can_pile = can_pile_cubes(parse_test_case())
        print('Yes' if can_pile else 'No')

Answer 2

The algorithm is actually pretty efficient, so congrats for that.

The first thing that I'd like to suggest is moving the logic outside the main check. In python, it's fairly common (and IMO more readable) to have your structure like this:

imports

def pile_algo(*args, **kwargs):
    """Docstring here"""
    # your code


def main():
    """Docstring here"""
    # process pile_algo

if __name__ == '__main__':
    main()

Of course, the main() is optional if you already have all the logic inside pile_algo().

Even if I said the algorithm is good, we can improve the way you're doing things.

You're not using num_cubes variable, so you can remove it (int(input().strip()) it's enough). Moving forward, neither use of strip() or list() or map() is necessary in your:

cube_sidelengths = list(map(int, map(str.strip, input().strip().split())))

You can rewrite that as:

cube_sidelengths = [int(x) for x in input().split()]

---

Apart from that, I don't have any other reasons to think about using deque. If it works, it works. And apparently works better enough to get over it.

Though, of course, I would also ask: Is it too slow right now? Most of the times, the aim of a programming challenge is both getting familiar with a specific library/module and improve your algorithms skills. You said:

It would be possible to use a deque here but that felt like overkill - because pop and popLeft are O(1) but just keeping the indices and accessing a list is also O(1) so it wouldn't even provide better asymptotic behavior.

Well, it would provide a worse asymptotic behavior? Just start writing a deque-based solution and see what improvements might that bring. I can think of a few right now:

• the code will be more comprehensive because of deque's already builtin methods which might do what you manually did (pop, etc..)
• talking about efficiency, Python lists are much better for random-access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists.

From the docs:

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

---

This might look more of a theory answer, and might not specifically answer your question, but I just wanted to highlight a couple of things out.

Answer 3

Make it lazy a pull pipeline, it's more fun. It should look either like

print(analyzed(loaded("tests.txt")))

which is the same as

gen = loaded("tests.txt")
gen = analyzed(gen)
print(gen)

To yield the separation of concerns, letting you change one bit without touching others.

from collections import deque
from sys import argv, stdin

def load():
    filenames = ('-',) if not argv[1:] else tuple(argv[1:])
    for filename in filenames:
        if filename == '-':
            yield stdin
        else:
            with open(filename, 'r') as f:
                yield f

def parse(inputs):
    for inp in inputs:
        n = int(inp.readline())
        for x in range(0, n):
            l = int(inp.readline())
            yield (int(_) for _ in inp.readline().split())

def analyze(inputs):
    buf = deque()
    last = None
    for inp in inputs:
        buf.extend(inp)
        while buf:
            if last and last < max(buf[0], buf[-1]):
                break
            else:
                if buf[-1] >= buf[0]:
                    last = buf.pop()
                else:
                    last = buf.popleft()

        yield 'No' if buf else 'Yes'
        buf.clear()

def report(inputs):
    for inp in inputs:
        print(inp)

def main():
    report(analyze(parse(load())))

if __name__ == "__main__":
    main()