Checking to see if array can be sorted using only one operation

Posted on

Problem

I’m doing this HackerRank problem, which asks whether an array of up to 100000 integers can be sorted in ascending order by exactly one of the following:

• swapping two elements
• reversing a subarray
• doing nothing (i.e. it is already sorted)

I’ve written this code and it passes all the tests, but it seems very convoluted. Is there any way I can streamline this code to make it more Pythonic?

``````n = int(raw_input())
ar = map(int, raw_input().strip().split())
ar.insert(0, -1)
ar.append(1000001)

ups = 0
downs = 0

for i in xrange(1, n+1):
if ar[i] < ar[i-1] and ar[i] < ar[i+1]:
downs += 1
later_index = i
elif ar[i] > ar[i-1] and ar[i] > ar[i+1]:
ups += 1
first_index = i

for i in xrange(n, 0, -1):
if ar[i] > ar[i-1] and ar[i] > ar[i+1]:
swap_i = i

if downs == ups == 2:
ar[swap_i], ar[later_index] = ar[later_index], ar[swap_i]
if all(ar[i] < ar[i+1] for i in xrange(1, n)):
print 'yes'
print 'swap %d %d' % (swap_i, later_index)
else:
print 'no'
elif downs == ups == 1:
if first_index == 1 or later_index == n:
ar[swap_i], ar[later_index] = ar[later_index], ar[swap_i]
if all(ar[i] < ar[i+1] for i in xrange(1, n)):
print 'yes'
print 'swap %d %d' % (swap_i, later_index)
else:
print 'no'
else:
if first_index - later_index == -1:
ar[first_index], ar[later_index] = ar[later_index], ar[first_index]
if all(ar[i] < ar[i+1] for i in xrange(1, n)):
print 'yes'
print 'swap %d %d' % (first_index, later_index)
else:
print 'no'
else:
ar = ar[:first_index:] + ar[later_index:first_index-1:-1] + ar[later_index+1::]
if all(ar[i] < ar[i+1] for i in xrange(1, n)):
print 'yes'
print 'reverse %d %d' % (first_index, later_index)
else:
print 'no'
elif ups ==1 and downs == 0:
print 'yes'
print 'reverse %d %d' % (first_index, later_index)
else:
print 'no'
``````

I feel there are far too many `if-else` blocks ruining the program structure.

Solution

You have to make some functions.

You can start off with `swap`, `reverse` and `is_sorted`.
These are simple one or two liners:

``````def swap(array, i, j):
array[i], array[j] = array[j], array[i]
return array

def reverse(array, i, j):
return array[:i] + array[j:i-1:-1] + array[j+1:]

def is_sorted(array, length):
return all(array[i] < array[i+1] for i in xrange(1, length))
``````

This keeps things nice and DRY.

Next you can do with a `get_indexs`.
This will use the loops you have at the moment, to make the code simpler, you can make two comprehensions.
This can be to get `up`s and `down`s.
And from this you can get `ups`, `downs`, `first_index`, `last_index` and `swap_i`.

Since you currently create `first_index` in a for loop, it’s not guaranteed to be created,
and so we’d have to create it before the loops too.
This can cause the following function:

``````def get_indexs(array, length):
first_index = None
later_index = None
swap_i = None
range_ = xrange(1, length + 1)
up = [i for i in range_ if array[i - 1] < array[i] > array[i + 1]]
down = [i for i in range_ if array[i - 1] > array[i] < array[i + 1]]

if up:
first_index = up[-1]
swap_i = up[0]
if down:
later_index = down[-1]

return (
len(up),
len(down),
first_index,
later_index,
swap_i,
)
``````

Next you’d want to change your massive if-else block.
You do a check if the output of the function is sorted, and you manually print everything.
Instead if you make a function that returns the three strings that you need, and you use these to test the array,
then you can significantly reduce the complexity of your program.
Take:

``````def get_command(array, length):
ups, downs, first_index, later_index, swap_i = get_indexs(array, length)
if downs == ups == 2:
return 'swap', swap_i, later_index
elif downs == ups == 1:
if first_index == 1 or later_index == length:
return 'swap', swap_i, later_index
else:
command = 'swap' if first_index - later_index == -1 else 'reverse'
return command, first_index, later_index
elif ups == 1 and downs == 0:
return 'reverse', first_index, later_index
return False
``````

The final function that you’d want to make is a main.
You’d want to move all your global declarations into it.
Such as `n = int(raw_input())`.
You’d then want to move the little section that you copied and pasted on all your previous if-else’s.
To be able to easily use the functions that you’d made above you’d want to add a single variable to the global scope too, it’s just a simple dictionary that will hold the functions.
This could result in the following simple function:

``````COMMANDS = {
'swap': swap,
'reverse': reverse
}

def main():
n = int(raw_input())
ar = map(int, raw_input().strip().split())
ar.insert(0, -1)
ar.append(1000001)

command = get_command(ar, n)
if command:
c, i, j = command
ar = COMMANDS[c](ar, i, j)
if is_sorted(ar, n):
print 'yes'
print '{} {} {}'.format(*command)
return None
print 'no'
``````

Your algorithm may be easy to improve, but I think that you have to improve the base of you program.
As you’ll end up coping and pasting lots of code all over the place, as you already have.
This code may not be the easiest to read, as optimized code normally isn’t,
and may lead to a horrible program, rather than quite a nice one.

Also you say:

• doing nothing (i.e. it is already sorted)

But it prints ‘no’, if I enter a sorted list.

``````5
1 2 3 4 5
no
``````

Should that not just be a ‘yes’ rather than a ‘no’?