Answer to Question #292216 in Python for Anino

Question

Imagine a collection of nuts and bolts that are all together in one pile on a table. Describe, in pseudocode, how you would find all matching pairs of nuts and bolts. You need to find one solution for each of the problem-solving approaches given below. For each of your solution, determine how many comparisons of pairs of nuts and bolts you might have to make in the best- and worst- case scenario. You can assume that there are complete pairs, no single nuts or bolts, and that for each bolt, there is exactly one nut that fits. Describe a solution to the nuts and bolts problem (in pseudocode) using a Divide and Conquer Approach.

Answer 1

from typing import List

# Method used to print array
def printArray(arr: List[str]) -> None:
   for i in range(6):
      print(" {}".format(arr[i]), end=" ")
   print()

def partition(arr: List[str], low: int, high: int, pivot: str) -> int:
   i = low
   j = low
   while j < high:
      if (arr[j] < pivot):
         arr[i], arr[j] = arr[j], arr[i]
         i += 1
      elif (arr[j] == pivot):
         arr[j], arr[high] = arr[high], arr[j]
         j -= 1
      j += 1
   arr[i], arr[high] = arr[high], arr[i]
   return i

# this function is for sorting
def matchPairs(nuts: List[str], bolts: List[str], low: int, high: int) -> None:
   if (low < high):

      pivot = partition(nuts, low, high, bolts[high])

      partition(bolts, low, high, nuts[pivot])


      matchPairs(nuts, bolts, low, pivot - 1)
      matchPairs(nuts, bolts, pivot + 1, high)

# Driver code
if __name__ == "__main__":

   nuts = ['@', '#', '$', '%', '^', '&']
   bolts = ['$', '%', '&', '^', '@', '#']

   matchPairs(nuts, bolts, 0, 5)
   print("Matched nuts and bolts are : ")
   printArray(nuts)
   printArray(bolts)