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(n²) 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)