Google Code Jam 2018: Trouble Sort

Link to the exercise.

The second problem in this years Code Jam was Trouble Sort. This problem was substantially easier then the first one. At least for the small test.

The idea is that one performs bubble sort with three elements at a time and, if the last element in the triplet bigger then the first, one reverses the entire 3-element sub-list. Pseudo-code for this algorithm was given. The goal of the exercise was to, given a list, sort that list using above strategy and then asserting that it was ordered. If it was one should print “OK” otherwise one should print the index of the (0-indexed) first element of non-increasing order (e.g. [3,9,7] should return 1).

	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))

view raw

trouble_sort.py

hosted with ❤ by GitHub

The problem with passing the big test was that lists could have up to `10^8` many elements and above trouble sort implementation has `O(n^2)`. This means using the naive implementation will quickly run into the timeout.

The “trick” is to see that trouble sort is equivalent to splitting the unsorted list into elements with even and odd index, sorting them and then concatenating those sorted lists. Since this sort can use a reasonably fast algorithm (e.g. pythons native one) it can happen in O(n*log(n)) which will be significantly faster and work on the second, big set of tests. (I know this because I read it in the analysis).

The way I got that intuition was thinking about the fact that reversing a three element list is the same as swapping elements i-1 and i+1 . So we swap with a “distance” of two which made me wonder if it would be possible to swap the second and third element in the list in some way. The only swaps that involve the third element are when the “cursor” is at position two and four and that would swap with the first or fifth element respectively which are both uneven numbers. This trend continues for all numbers (even swap with even, odd with odd) and suddenly you begin to see a pattern.

Unfortunately I failed this challenge completely. My logic is correct, however if you look carefully at the last line, you will see that it outputs something like “Case 1:” however it should output “Case #1:”. I spent over 2 hours trying to find the mistake…

Sometimes it’s the small things that catch you. This probably won’t happen to me again … ever.