Rotate a string of integers to match index

Question

t is number of tests; each test contains two lines: n and sequence

n is number of integers

sequence is a sequence of integers from 1..n (e.g. '3 6 1 2 4 5' if n is 6)

Rotate sequence until you maximize the number of integers that match their position in the string. (e.g. '3 6 1 2 4 5' should output '1 2 4 5 3 6'). Print the answer sequence for each test.

Here is the working code. It seems to satisfy the conditions above.

Would be very grateful for any guidance to make it more efficient!

def rotate_left(seq):
 return seq[1:] + [seq[0]]
def is_in_position(seq):
 in_position = 0
 for idx, val in enumerate(seq, start=1):
 if int(val) == idx:
 in_position += 1
 return in_position
t = int(raw_input()) #number of tests
while t:
 n = int(raw_input()) #number of integers
 sequence = str(raw_input()).split() #sequence of integers from 1..n
 if not n:
 break
 max_score, answer_sequence = 0, 0
 for i in range(n):
 sequence = rotate_left(sequence)
 sequence_score = is_in_position(sequence)
 if max_score < sequence_score:
 max_score = sequence_score
 answer_sequence = sequence
 answer_sequence = ' '.join(answer_sequence)
 if max_score >= 0.5 * len(sequence):
 break
 if answer_sequence:
 print(answer_sequence)
 t -= 1

• peonicles: The program is supposed to make a best guess and terminate search at some point ? As opposed to running through all possible combinations and returning the best sequence ?
• SuperBiasedMan: @peonicles It runs through all possibilities but all it does is rotate them. It doesn't do a full re-order, so in many cases it can't put them in 100% correct order.

Answer 1

Variable name

If you were to give t a different name, you wouldn't need to comment number of tests. I suggest nb_tests.

Looping - the pythonic way

There are better ways to write :

nb_tests = int(raw_input())
while nb_tests:
 ...
 nb_tests -= 1

You could use a simple for loop.

nb_tests = int(raw_input()) 
for _ in range(nb_tests):

(I've used _ as a variable name because this is the convention for unused variables in Python).

Split the logic into smaller functions

At the moment, the logic related to input/output is mixed with the logic related to the actual algorithm. It would make things clearer to write proper functions to handle this properly.

def get_rotate_sequence_with_best_match(sequence):
 max_score, answer_sequence = 0, []
 n = len(sequence)
 for i in range(n):
 sequence = rotate_left(sequence)
 sequence_score = is_in_position(sequence)
 if max_score < sequence_score:
 max_score = sequence_score
 answer_sequence = sequence
 if max_score >= 0.5 * len(sequence):
 break
 return answer_sequence
nb_tests = int(raw_input())
for _ in range(nb_tests):
 n = int(raw_input())
 sequence = str(raw_input()).split()
 assert len(sequence) == n
 print(' '.join(get_rotate_sequence_with_best_match(sequence)))

See also : separation of concerns.

if __name__ == "__main__":

It is a good habit to use a if __name__ == "__main__": guard to separate your function definitions to what you actually run when you call your script. It is useful when you want to re-use your code via module import.

Tests

Now that you've re-organised a bit your code, it is much easier to write and run unit tests to ensure everything is working properly.

Based on the provided example, I have :

def run_test_on_stdin():
 nb_tests = int(raw_input())
 for _ in range(nb_tests):
 n = int(raw_input())
 sequence = str(raw_input()).split()
 assert len(sequence) == n
 print(' '.join(get_rotate_sequence_with_best_match(sequence)))
def run_unit_tests():
 seq = [3, 6, 1, 2, 4, 5]
 assert get_rotate_sequence_with_best_match(seq) == [1, 2, 4, 5, 3, 6]
if __name__ == "__main__":
 run_unit_tests()

Counting - the pythonic way

You could use sum(iterable[, start]) in is_in_position. Indeed, you could write :

def is_in_position(seq):
 return sum(int(val) == idx for idx, val in enumerate(seq, start=1))

Micro-optimisations

You don't need to always check if max_score >= 0.5 * len(sequence): : you just need to check it after updating max_score. Also, you could reuse n instead of calling len every time.

def get_rotate_sequence_with_best_match(sequence):
 max_score, answer_sequence = 0, []
 n = len(sequence)
 for i in range(n):
 sequence = rotate_left(sequence)
 sequence_score = is_in_position(sequence)
 if max_score < sequence_score:
 max_score, answer_sequence = sequence_score, sequence
 if max_score >= 0.5 * n:
 break
 return answer_sequence

Different algorithm

Generating n sequences and counting how many of the n elements are in the right position gives you an 0(n2) algorithm (at best).

A different strategy could be to look at the shift required for each number to be in the correct position. Because all numbers are in 1...n, you can compute the shift with a simple substraction and a modulus operation. Doing this for all numbers can be easily done :

print([(i - val) % n for i, val in enumerate(sequence, start=1)])

Then, you just need to see which elements occurs more often which can be done with collection.Counter.most_common.

from collections import Counter
def rotate_left(seq, shift=1):
 return seq[shift:] + seq[:shift]
def get_rotate_sequence_with_best_match(sequence):
 n = len(sequence)
 shifts = Counter([(i - val) % n for i, val in enumerate(sequence, start=1)])
 best_shift, nb_occur = shifts.most_common(1)[0]
 return rotate_left(sequence, best_shift)