"Almost Sorted" coding challenge

Question

The "Almost Sorted" problem from HackerRank:

Given an array with \$n\$ elements, can you sort this array in ascending order using only one of the following operations?

1. Swap two elements.
2. Reverse one sub-segment.

Output format

1. If the array is already sorted, output yes on the first line. You do not need to output anything else.

2. If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:

   1. If you can sort the array by swapping \$d_l\$ and \$d_r\$, output swap l r in the second line. \$l\$ and \$r\$ are the indices of the elements to be swapped, assuming that the array is indexed from \$1\$ to \$n\$.

   2. Else if it is possible to sort the array by reversing the segment \$d[l\ldots r]\$, output reverse l r in the second line. \$l\$ and \$r\$ are the indices of the first and last elements of the subsequence to be reversed.

   If an array can be sorted by either swapping or reversing, stick to the swap-based method.

3. If you cannot sort the array in either of the above ways, output no in the first line.

I am trying to improve my Python so I would appreciate if somebody could review the following piece of code. I know it can be done with less code in Python, I am just not sure how.

import sys

def checkSorted(arr):
    return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))

def almostSorted(arr):
    if len(arr) == 1 or checkSorted(arr):
        print("yes")
        return

    # Find first item out of order from the left
    i = 0
    while i < len(arr) - 1 and arr[i] < arr[i+1]:
        i+=1
    first_ooo_left = i

    # Find first item out of order from the right
    i = len(arr) - 1
    while i > 0 and arr[i-1] < arr[i]:
        i-=1
    first_ooo_right = i

    # Same item?
    if (first_ooo_left == first_ooo_right):
        print("no")
        return

    l = first_ooo_left
    r = first_ooo_right
    swaps = 0
    while r-l > 0:
        if arr[l] > arr[r]: 
            arr[r], arr[l] = arr[l], arr[r]
            swaps += 1
        r-=1
        l+=1

    sorted = checkSorted(arr)

    if sorted:
        if swaps == 1:
            print("yes")
            print("swap " + str(first_ooo_left+1) + " " + str(first_ooo_right+1))
        elif swaps == (first_ooo_right-first_ooo_left+1)//2:
            print("yes")
            print("reverse " + str(first_ooo_left+1) + " " + str(first_ooo_right+1))
    else:
        print("no")

Answer 1

Some remarks from my side...

Most importantly, the function as provided doesn't just check the passed in list object, it also modifies it. This may surprise future users. You might want to do writing changes on copies of the input list. (For further reading: https://stackoverflow.com/q/986006/1025391)

Regarding the implementation:

• I would implement the check for sortedness by iterating the values, rather than indirectly via indexed access:

  def is_sorted(arr):
      return all(a <= b for a,b in zip(arr, arr[1:]))
  

• You should use string formatting ("yes\nswap {} {}".format(a,b)) instead of string concatenation ("yes\nswap "+str(a)+" "+str(b)) to build the output.

• In order to have testable code, you should split the algorithm from the output, i.e., return results from the function instead of print statements.
• For testability, you should also split logical parts of your algorithm to different functions. For example you could find the first out of order item from the left and from the right using the same function (with normal and reversed() iterators). Another function to count the swaps required, and so on... i.e., make the units you can test as small as possible.

Some general/PEP8-related comments:

• Functions are usually to be named snake_case() in Python (PEP8)
• Usually variables should have proper names. Single letter names are acceptable for variables with very limited scope, but as soon as it survives two or three lines it probably deserves a real name.
• Some letters are difficult to distinguish with certain fonts. The letters r and l are borderline in this case. Consider to use more distinctive letters instead, e.g., a and b.
• You should avoid shadowing standard library names, e.g., by naming a local variable sorted the built-in function sorted() is hidden.
• You seem to have an unused import sys.
• If you would want others to use your code, you would obviously add docstrings.

Regarding the lines of code in your solution: I don't think it can or should be done with much less code.

However I would have used another approach to implement this. I think something along the lines of the following is a bit easier to read/understand.

# removed the helper functions for reasons of brevity ;)

def almost_sorted(arr):
    # produce list of violations of ascending order
    idx = range(len(arr))
    out_of_order_idx = [lhs for lhs,rhs in zip(idx, idx[1:])
                        if arr[lhs] > arr[rhs]]
    # handle possible cases
    if not out_of_order_idx:
        # is already sorted
        return "yes"
    elif len(out_of_order_idx) <= 2:
        # can potentially be solved by swapping two items
        a, b = out_of_order_idx[0], out_of_order_idx[-1]+1
        if try_swap(arr, a, b):
            return "yes\nswap {} {}".format(a+1, b+1)
        else:
            # not solvable
            return "no"
    elif is_consecutive_out_of_order(out_of_order_idx):
        # can potentially be solved by reversing items
        a, b = out_of_order_idx[0], out_of_order_idx[-1]+1
        if try_reverse(arr, a, b):
            # reversible
            return "yes\nreverse {} {}".format(a+1, b+1)
        else:
            # not solvable
            return "no"
    else:
        # not solvable
        return "no"

When you want to tune it for performance however, you might reach at something similar to your approach, but replacing some 2-3 passes through the array by intelligent conditionals...

Answer 2

Before anything else: add tests

To be on the safe side before any review of an algorithmic problem, I tend to ensure the code is testable and tested. On that point, the problem is nice for three reasons:

• for a given well defined input (a list), it returns a clear output (a string)
• it is easy to generate test cases for the different cases
• a few example are provided

You should start by rewriting your function so that it returns things instead of printing them. Then, you can write automated tests.

For instance, you can write the following tests:

# From the problem
assert almostSorted([4, 2]) == "yes\nswap 1 2"
assert almostSorted([3, 1, 2]) == "no"
assert almostSorted([1, 5, 4, 3, 2, 6]) == "yes\nreverse 2 5"
# Generate various small strings
for i in range(10):
    l_i = list(range(i))
    assert almostSorted(l_i) == "no"  # WRONG
    result_reversed = almostSorted(list(reversed(l_i)))
    if i < 2:
        assert result_reversed == "no" # WRONG
    elif i < 4:
        assert result_reversed == "yes\nswap %d %d" % (1, i)
    else:
        assert result_reversed == "yes\nreverse %d %d" % (1, i)
    for j in range(i):
        for k in range(j+1, i):
            l_swap = list(range(i))
            l_swap[j], l_swap[k] = l_swap[k], l_swap[j]
            result_swap = almostSorted(l_swap)
            assert result_swap == "yes\nswap %d %d" % (j+1, k+1)
            l_rev = list(range(i))
            l_rev[j:k+1] = l_rev[j:k+1][::-1]
            result_rev = almostSorted(l_rev)
            if k - j >= 3:
                assert result_rev == "yes\nreverse %d %d" % (j+1, k+1)
            else:
                assert result_swap == "yes\nswap %d %d" % (j+1, k+1)

You could also use a proper testing framework but this is the first step.

It is enough to see an issue spotted by Martin. R in the comment. This is enough easy to fix and I'll let you deal with this. Except for that, your code seems to be working fine which is a great news even if the test suite is far from perfect.

Spoiler alert: more issues are found later.

Style

There is an official standard Python style guide called PEP 8. This is highly recommended reading. It gives guidelines to help writing code that is both readable and consistent. The Python community tries to follow these guidelines, more or less strictly (a key aspect of PEP 8 is that it provides guidelines and not strict rules to follow blindly).

It deals with various aspects of the code style: naming conventions, indentation convention, etc.

You'll find various tools to try to check whether your code is PEP 8 compliant and if is it not, to try and fix this:

• pycodestyle package (formerly known as pep8) to check you code

• pep8online to check your code with an online tool

• autopep8 package to fix your code automatically

• Also, this is also checked by various linters: pylint, pyflakes, flake8, etc.

In your case, the naming convention of the function seems to be off:

• checkSorted should be check_sorted or even better is_sorted.

• almostSorted should be almost_sorted (or is_almost_sorted ?)

Regarding the naming, 2 other details could be improved:

• arrays are usually called list in the Python universe. Thus, lst may be a better argument name than arr.

• sorted is the name of a builtin. Thus, having a local variable named the same way could lead to issues in more complex code. In your case, you don't even need that variable in the first place...

  (There are other PEP8 "issues" about spacing but nothing very interesting to me).

Same logic but different

The logic to check is the list is sorted and the logic to find first item out of order from the left look the same but shaped in a different way.

Actually, a closer look shows that the logic itself is different in a subtle way: identical consecutive values are not handled the same way in both places. This can be shown by writing more tests with equal values:

for i in range(10):
    l_equal = [42] * i
    assert almost_sorted(l_equal) == "yes"
    l_i = list(range(i))
    assert almost_sorted(l_i) == "yes"
    result_reversed = almost_sorted(list(reversed(l_i)))
    if i < 2:
        assert result_reversed == "yes"
    elif i < 4:
        assert result_reversed == "yes\nswap %d %d" % (1, i)
    else:
        assert result_reversed == "yes\nreverse %d %d" % (1, i)
    for j in range(i):
        for new_val in (0, 42):
            l_almost_equal = [42] * i
            l_almost_equal[j] = new_val
            assert "yes" in almost_sorted(l_almost_equal)

I'll stop the review here to let you deal with the issue found.

Before finding the problem, I was about to suggest something along the lines of:

• instead of checking is the list is sorted first, you could try to find the first out of order value and if you do not find it, then the array is sorted.

• the for loop in is_sorted is clearer that the while loop, I reckon you should use the former rather than the later.

For instance, you could write something like:

# Find first item out of order from the left
for i in range(len(lst)-1):
    if lst[i] > lst[i+1]:
        first_ooo_left = i
        break
else: # no break: sorted already
    return "yes"