Thursday, May 1, 2014

Nut and Bolt Problem (OR Key and Lock Problem) - Matching Nuts and Bolts when nuts cannot be compared with nuts and bolts with bolts

 Problem

You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut.
Compute time complexity of your algorithm.

Solution

Method 1 - Brute force

Since we can’t compare a nut with other nuts and a bolt with other bolts, we can’t sort them. So current best possibility seems to pick nuts one-by-one and find matching bolts for them. In this manner, we will match all the pairs in O(n^2) time complexity.
Can we do better?
Method 2 - Partition similar to quicksort

This problem can also be solved in a quick sort kind of technique. We can’t compare a nut with other nuts and so for bolts, we can compare a nut with bolts and vice-versa. Also keep in mind that if a Nut(N) is smaller than a Bolt(B) than N is fit only for bolts smaller than B. Similarly if a Bolt(B’) is smaller than a Nut(N’) than N is fit only for bolts smaller than B’. So we can go like following in solving this problem.
  • Take a nut from the nuts pile
  • Divide bolts around it in 2 parts, which are smaller and larger than this.
  • Find a matching bolt to this nut.
  • Divide nuts in 2 parts, which are smaller and larger than matching bolt.
Now we have 2 subsets of Nuts and Bolts. If we pick a nut from small size nuts pile, we will get a corresponding bolt in smaller size bolts pile and similarly for large size piles. At every step, we will be able to divide these piles in 2 halves and reduce complexity by a factor of 2 in average case. In this case time complexity will be O(nlogn).

In worst case we might have choose the smallest/largest nut/bolt as reference and our one pile will have zero nut/bolt and another pile will have all the remaining. In this case time complexity will be O(n^2), as it is with quicksort.
Algorithm:
Take a nut; partition the bolts with respect to this nut. We will find the matching bolt for this nut. Now take the bolt; partition the nuts.
In this manner, we have divided the Original problems into 2 sub-problems.

private static void matchPairs(char[] nuts, char[] bolts, int low,
                                                          int high)
{
    if (low < high)
    {
        // Choose last character of bolts array for nuts partition.
        int pivot = partition(nuts, low, high, bolts[high]);

        // Now using the partition of nuts choose that for bolts
        // partition.
        partition(bolts, low, high, nuts[pivot]);

        // Recur for [low...pivot-1] & [pivot+1...high] for nuts and
        // bolts array.
        matchPairs(nuts, bolts, low, pivot-1);
        matchPairs(nuts, bolts, pivot+1, high);
    }
}

T(n) = T( i ) + T(n-i ) + O(n)
Where we have chosen the ith largest nut from a particular pile.
Average time complexity = O(nlogn).
Worst time complexity = O(n^2).
 References

0 comments:

Post a Comment