Created
April 10, 2018 20:49
-
-
Save FirefoxMetzger/afe7d48a0ecf23b6a5565ac17c9d43a0 to your computer and use it in GitHub Desktop.
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