My answer to the second problem of the Code Jam. It has a small error: Instead of printing "Case #1:" it's printing "Case 1:" ... small things :D
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
def trouble_sort(L): | |
# in place sorting | |
done = False | |
while not done: | |
done = True | |
for idx in range(len(L) - 2): | |
if L[idx] > L[idx + 2]: | |
done = False | |
L[idx],L[idx+1], L[idx + 2] = L[idx + 2], L[idx+1], L[idx] | |
def assert_list(sorted): | |
# there is a bug, but I don't see it | |
idx = 0 | |
while idx < len(sorted) - 1: | |
if sorted[idx] <= sorted[idx+1]: | |
idx += 1 | |
else: | |
return str(idx) | |
return "OK" | |
def fast_sort(unsorted): | |
list1 = unsorted[0::2] | |
list2 = unsorted[1::2] | |
list1.sort() | |
list2.sort() | |
# concatenate the list | |
unsorted[0::2] = list1 | |
unsorted[1::2] = list2 | |
def next_case(file): | |
test_cases = list() | |
num_cases = int(file.readline()) | |
for case_idx in range(num_cases): | |
N = int(file.readline()) | |
read_list = [int(elem) for elem in file.readline().split(" ")] | |
assert len(read_list) == N | |
test_cases.append((N,read_list)) | |
return test_cases | |
if __name__ == "__main__": | |
test_cases = next_case(sys.stdin) | |
for idx, case in enumerate(test_cases): | |
N, test_list = case | |
fast_sort(test_list) | |
result = assert_list(test_list) | |
print("Case %d: %s" % (idx+1,result)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment