2
\$\begingroup\$

I've came up with solution to the Piling Up! problem on HackerRank. It passes all tests on HackerRank. How could I improve this code? Are there any cases outside those provided on HR that I've missed?

for _ in (range(int(input()))):
    no_of_cubes = int(input())
    side_lengths = list(map(int, input().strip().split()))
    result = "Yes"
    if max(side_lengths) not in (side_lengths[0], side_lengths[-1]):
        result = "No"
    print(result)
\$\endgroup\$
11
  • 1
    \$\begingroup\$ Tests as in the two test cases in the problem page, or tests as in the submission passes? \$\endgroup\$
    – vnp
    Jul 29 '17 at 1:02
  • 4
    \$\begingroup\$ Unless I overlooking something, your solution is wrong: It would not detect that 3 2 1 2 1 can not be piled. \$\endgroup\$
    – Martin R
    Jul 29 '17 at 6:19
  • \$\begingroup\$ @vnp all tests as in the submission passes. \$\endgroup\$
    – an0o0nym
    Jul 29 '17 at 10:14
  • \$\begingroup\$ @MartinR my question was to prove my solution wrong, and thank you for sharing that answer with me! Can anyone explain it to me why is the question put on hold, so I know it fo future reference? \$\endgroup\$
    – an0o0nym
    Jul 29 '17 at 10:14
  • \$\begingroup\$ I am asking for feedback on Correctness in unanticipated cases which seems to be under list of areas that are allowed by Code review Stack Exchange. \$\endgroup\$
    – an0o0nym
    Jul 29 '17 at 10:27
1
\$\begingroup\$

You asked:

Are there any cases outside those provided on HR that I've missed?

Indeed, there are, and the "simplest" one is 2 1 2 1: Your code checks that the maximum side length is equal to the first or last number in the array, and prints "Yes".

But actually this row can not be stacked: The first cube with side length 2 must be picked first, then the two cubes with length 1 in any order. That leaves us with a cube with length 2 which cannot be stacked on top of the others.

How can this be fixed? If the given side length are $$ a_1, a_2, \ldots , a_n $$ then your code checks if $$ \max_i a_i \in \{ a_1, a_n \} $$ which is a necessary condition, but not sufficient.

Let us first assume that the row of cubes can be stacked, and let \$ m \$ be the index of the cube which is chosen last (\$ 1 \le m \le n \$). Then it is clear that $$ \tag{*} a_1 \ge a_2 \ge \ldots \ge a_m \le a_{m+1} \le \ldots \le a_{n-1} \le a_n \, , $$ i.e. the side length are first decreasing, and then increasing.

So \$(*) \$ is a necessary condition for the row to be stackable. But it is also sufficent: If \$(*) \$ is satisfied then the two decreasing sequences $$ a_1 \ge a_2 \ge \ldots \ge a_m \\ a_n \ge a_{n-1} \ge \ldots \ge a_{m+1} $$ can be merged into a single decreasing sequence by choosing (and removing) the larger of the two front elements until both sequences are exhausted.

Therefore a row can be stacked exactly if the side length are of the form \$(*) \$, this can be checked with a single traversal of the list. I'll leave the implementation in Python up to you :)

\$\endgroup\$
5
  • \$\begingroup\$ Just one question, why there is an≥an−1≥…≥ am−1 ? \$\endgroup\$
    – an0o0nym
    Aug 2 '17 at 15:08
  • \$\begingroup\$ @an0o0nym: \$ a_{n-1} \$ is picked after \$ a_n \$, therefore \$ a_{n-1} \le a_n \$. \$\endgroup\$
    – Martin R
    Aug 2 '17 at 15:12
  • \$\begingroup\$ yes, I got that part, but I was talking about the am-1(not an-1) in last equation of your answer. \$\endgroup\$
    – an0o0nym
    Aug 2 '17 at 15:16
  • \$\begingroup\$ @an0o0nym: That was a typo, sorry! \$\endgroup\$
    – Martin R
    Aug 2 '17 at 15:53
  • \$\begingroup\$ That what I suspected, now it all makes sense. Many thanks! \$\endgroup\$
    – an0o0nym
    Aug 2 '17 at 16:08
4
\$\begingroup\$

That was a fun little challenge to code against, although my solution was very different from yours!

With those kinds of challenges, it can be tempting to just write throw-away code. I would suggest though, if you are serious about coding, to just try to write the most professional code you can, even if it's just to solve this one challenge.


In particular, I find your code is not very expressive. There's no functions/methods/classes, there's really not anything telling me (or future you) what this code is for at all, so I'm having to actually read the code from beginning to end to even get an idea what it's supposed to do (let alone if it's doing it correctly). This also makes it much less reusable.


We can start by organizing input handling separately from program logic. In fact, I think __main__ would be a perfect place to handle getting input. You'll notice my code is somewhat more verbose, I personally prefer to make it obvious when doing "breaky" things like reading raw text input.

if __name__ == "__main__":
    num_cases = int(input())
    for case in range(num_cases):
        no_of_cubes = int(input())
        side_lengths = list(map(int, input().strip().split()))

I don't think it would be unreasonable to create a function to handle text input, but that may be a bit much for this. So, we have our input, now we just need to handle it.


One data structure to consider, and for which it seems like this challenge was written, is the deque...

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). 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.

However, you found a shorter, less literal way to pass the test cases, which, in the end, is the goal. So if you wanted to keep it at that, I'd just move the logic into a function and return a bool, and call it a day.

def can_be_piled(no_of_cubes: int, side_lengths: List) -> bool:
    if max(side_lengths) not in (side_lengths[0], side_lengths[-1]):
        return False
    return True

I also made a few other utility functions, one to split up the side lengths, the other to display the output. Note that I used Python 3 type hints in each function signature, in case that looks unfamiliar.

from typing import List

def can_be_piled(no_of_cubes: int, side_lengths: List) -> bool:
    if max(side_lengths) not in (side_lengths[0], side_lengths[-1]):
        return False
    return True

def get_side_lengths(raw_input: str) -> List:
    return list(map(int, raw_input.strip().split()))

def display_output(truthy: bool) -> None:
    if truthy:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    num_cases = int(input())
    for case in range(num_cases):
        no_of_cubes = int(input())
        side_lengths = get_side_lengths(input())
        display_output(can_be_piled(no_of_cubes, side_lengths))
\$\endgroup\$
3
  • \$\begingroup\$ That was a lot of time and effor you put into that answer, I found it very helpful! Thank you for your review. \$\endgroup\$
    – an0o0nym
    Jul 29 '17 at 14:22
  • \$\begingroup\$ You can turn display_output function a one liner: print("Yes") if truthy else print("No"). \$\endgroup\$
    – Lukasz
    Jul 29 '17 at 18:29
  • \$\begingroup\$ Same for can_be_piled: return max(side_lengths) in (side_lengths[0], side_lengths[-1]). \$\endgroup\$
    – Graipher
    Jul 31 '17 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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