Question: https://codility.com/demo/take-sample-test/clocks
Question Name: lithium2013 or Clocks
At the very beginning, I found this task is very similar with the string rotation question in CTCI. And I did transfer this question into a string rotation one. The string rotation solution worked, and gave the right answer. But I could only get 95/100, because of the TIMEOUT ERROR in the large_constantSpace test set. This bad solution is show as below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def solution(A, P): columns = len(A[0]) same_after_rotation = {} for row_index in xrange(len(A)): A[row_index].sort() signature = "-".join([str((A[row_index][column_index] - A[row_index][column_index-1]) % P) for column_index in xrange(columns)]) for sig, count in same_after_rotation.items(): if signature in sig: same_after_rotation[sig] += 1 break else: same_after_rotation[signature+"-"+signature] = 1 same_pairs = sum([item*(item-1)/2 for item in same_after_rotation.values()]) return same_pairs |
Then, I tried to solve it by finding out the Lexicographically Minimal Rotation (LMR). At that time, I did not know the term “LMR” being a classic problem, and use a brute force method. Reasonably, I still did not get the 100/100 until google it. After reading couple of articles, with the improved algorithm to find LMR, the final solution gets the 100/100.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | def lexicographically_min(A): ''' Return the given array in a Lexicographically Minimal Rotation (LMR) ''' double_array = A + A array_len = len(A) start = 0 # The start point of the LMR so far testing = 1 # The start point of the next trying rotation offset = 0 # The offset in comparing two rotations while testing < array_len: if offset == array_len: # Pass all the test, the "start" begins the # lexicographically minimal array rotation break if double_array[start+offset] == double_array[testing+offset]: # So far, both rotations have the same lexicographically # value. So we move on to compare the next element. offset += 1 elif double_array[start+offset] < double_array[testing+offset]: # The current trying rotation is lexicographically larger # The start point of LMR could not in the range # [testing, testing + offset] testing += offset + 1 offset = 0 else: # The current trying rotation is lexicographically smaller # The start point of LMR could not in the range # [start, start + offset]. AND # all the points in [start+1, testing-1] have been tested # not to be the start point of LRM start = max( start+offset+1, testing ) testing = start + 1 offset = 0 return A[start:]+A[:start] def solution(A, P): columns = len(A[0]) same_after_rotation = [] # Compute the Lexicographically Minimal Rotation for the hands' # distance array. And use the LMR array as signature to identify # the same clocks for row_index in xrange(len(A)): A[row_index].sort() # Make the hands in order distance = [(A[row_index][column_index] - A[row_index][column_index-1]) % P for column_index in xrange(columns)] same_after_rotation.append( lexicographically_min(distance) ) # Sort the LMR array for better counting the same clocks same_after_rotation.sort() # Count the same clocks. Notice that all the same clocks must # appear consecutively. current = same_after_rotation[0] current_count = 1 same_pairs = 0 for clock in same_after_rotation[1:]: if clock == current: current_count += 1 else: same_pairs += current_count * ( current_count - 1 ) /2 current_count = 1 current = clock same_pairs += current_count * ( current_count - 1 ) /2 return same_pairs |