"Almost Sorted" coding challenge 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?
  
  
  Swap two elements.
  Reverse one sub-segment.
  
  
  Output format
  
  
  If the array is already sorted, output yes on the first line. You do not need to output anything else.
  If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:
  
  
  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\$.
  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.
  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] &lt;= 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 &lt; len(arr) - 1 and arr[i] &lt; arr[i+1]:
        i+=1
    first_ooo_left = i

    # Find first item out of order from the right
    i = len(arr) - 1
    while i &gt; 0 and arr[i-1] &lt; 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 &gt; 0:
        if arr[l] &gt; 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")
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]) == &quot;yes\nswap 1 2&quot;
assert almostSorted([3, 1, 2]) == &quot;no&quot;
assert almostSorted([1, 5, 4, 3, 2, 6]) == &quot;yes\nreverse 2 5&quot;
# Generate various small strings
for i in range(10):
    l_i = list(range(i))
    assert almostSorted(l_i) == &quot;no&quot;  # WRONG
    result_reversed = almostSorted(list(reversed(l_i)))
    if i &lt; 2:
        assert result_reversed == &quot;no&quot; # WRONG
    elif i &lt; 4:
        assert result_reversed == &quot;yes\nswap %d %d&quot; % (1, i)
    else:
        assert result_reversed == &quot;yes\nreverse %d %d&quot; % (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 == &quot;yes\nswap %d %d&quot; % (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 &gt;= 3:
                assert result_rev == &quot;yes\nreverse %d %d&quot; % (j+1, k+1)
            else:
                assert result_swap == &quot;yes\nswap %d %d&quot; % (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 &quot;issues&quot; 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) == &quot;yes&quot;
    l_i = list(range(i))
    assert almost_sorted(l_i) == &quot;yes&quot;
    result_reversed = almost_sorted(list(reversed(l_i)))
    if i &lt; 2:
        assert result_reversed == &quot;yes&quot;
    elif i &lt; 4:
        assert result_reversed == &quot;yes\nswap %d %d&quot; % (1, i)
    else:
        assert result_reversed == &quot;yes\nreverse %d %d&quot; % (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 &quot;yes&quot; 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] &gt; lst[i+1]:
        first_ooo_left = i
        break
else: # no break: sorted already
    return &quot;yes&quot;