Solution to #Codejam Qualification Round 2, Problem 2a

trouble_sort.py

def reader():
    """ Read input """
    N = int(input())
    tcs = []
    for i in range(N):
        input()
        lst =  [int(x) for x in input().split()]
        tcs.append(lst)
    return tcs

def troubleSort(L):
    """ Simulate the trouble sort algorithm. This is O(N^2) so will work only for the 2a """
    done = False
    while not done:
        done = True
        for i in range(len(L)-2):
            a, b, c = L[i:i+3]
            if c < a:
                done = False
                L[i] = c
                L[i+2] = a
    return L

def check_sort(L):
    """ Test if the resulting array is sorted or not """
    return sum(L[i]>L[i+1] for i in range(len(L)-1)) == 0

def wrong_index(L):
    """ Find the wrong index """
    for i in range(len(L)-1):
        if L[i]>L[i+1]:
            return i

def solver(L):
    """ Solver. It just runs trouble_sort, cheks result and if not ok, returns the index """
    TL = troubleSort(L)
    if check_sort(L):
        return "OK"
    else:
        return wrong_index(L)

import sys
for i, L in enumerate(reader()):
    print("Case #{}: {}".format(i+1, solver(L)))
    sys.stdout.flush()