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.
‘Cause repeating your self is bad.
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 ups and downs.
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’?