makispaiktis

DCP35 - RGB

Sep 21st, 2020
1,080
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. This problem was asked by Google.
  3. Given an array of strictly the characters 'R', 'G', and 'B', segregate the values of the array so that all the Rs come first,
  4. the Gs come second, and the Bs come last. You can only swap elements of the array.
  5. Do this in linear time and in-place.
  6. For example, given the array ['G', 'B', 'R', 'R', 'B', 'R', 'G'], it should become ['R', 'R', 'R', 'G', 'G', 'B', 'B'].
  7. '''
  8. from random import randrange
  9.  
  10. def generateRGB(desiredLength):
  11.     result = list()
  12.     for i in range(desiredLength):
  13.         r = randrange(3)
  14.         if r == 0:
  15.             result.append('R')
  16.         elif r == 1:
  17.             result.append('G')
  18.         else:
  19.             result.append('B')
  20.     return result
  21.  
  22. def sortRGB(rgb):
  23.     # First, I have to sort "R"s, I will use the bubllesort method
  24.     for i in range(len(rgb)-1):
  25.         for j in range(i+1, len(rgb)):
  26.             if rgb[i] != 'R' and rgb[j] == 'R':
  27.                 # SWAP
  28.                 rgb[i], rgb[j] = rgb[j], rgb[i]
  29.                 break
  30.     # Now, all the "R"s are in the beginning of the list
  31.     # Then, I do the same thing for "G"s
  32.     for i in range(len(rgb)-1):
  33.         if rgb[i] == 'R':
  34.             continue
  35.             # If rgb[i] == 'R', the list is sorted until this spot, so I continue
  36.         for j in range(i+1, len(rgb)):
  37.             if rgb[i] != 'G' and rgb[j] == 'G':
  38.                 # SWAP
  39.                 rgb[i], rgb[j] = rgb[j], rgb[i]
  40.                 break
  41.     return rgb
  42.  
  43. def prettyPrintRGB(desiredLength):
  44.     rgb = generateRGB(desiredLength)
  45.     RGB = rgb.copy()
  46.     result = sortRGB(rgb)
  47.     print(str(desiredLength) + " elements: " + str(RGB) + " ----> " + str(result))
  48.  
  49. # MAIN FUNCTION
  50. desiredLengths = list(range(5, 11))
  51. for desiredLength in desiredLengths:
  52.     prettyPrintRGB(desiredLength)
RAW Paste Data