Nuts and Bolts It Is

Well, recently I stumbled upon Nuts and Bolts problem. Also, I learnt Java very recently and wanted to try out some features of it.

Problem statement: #

The nuts and bolts problem is defined as follows. You are given a collection of n bolts of different sizes, and n corresponding nuts. You can test whether a given nut and bolt fit together, from which you learn whether the nut is too large, too small, or an exact match for the bolt. The differences in size between pairs of nuts or bolts are too small to see by eye, so you cannot compare the sizes of two nuts or two bolts directly. You are to match each bolt to each nut. Assume that for every nut you have a matching bolt.

This problem is different from other problems because it has a constraint which says you cannot compare nut with a nut or bolt with a bolt. Had it been that, we can compare a nut with a nut or bolt with a bolt, we could’ve just sorted the array of bolts and array of nuts thereby finding an exact match. Since we are out of that option, we have to think of some other ways to do it.

Solution 1: #

For every nut, compare it with all the bolts and find the exact match. If we have n nuts, then the runtime complexity is O(n2). This is sub optimal. Can we do any better?

Solution 2: #

We can use a variant of quick sort to do this job in O(n log n).

Here are the steps

Here is the Java code for this.

import java.util.*;

public class NutsAndBolts{
public static class Component{
    int size;
    Component(int _size){
        size = _size;
    }
}
public static class Bolt extends Component{
    Bolt(int _size){
        super(_size);
    }
    @Override
    public String toString(){
        return "Bolt#"+size;
    }
}
public static class Nut extends Component{
    Nut(int _size){
        super(_size);
    }
    @Override
    public String toString(){
        return "Nut#"+size;
    }
}
//Using Generics to avoid code duplication
public static <N extends Component,B extends Component> int compareTo(N n, B b){
    if(n.size < b.size) return -1;
    if(n.size == b.size) return 0;
    return 1;

}

public static <T extends Component> void exch(T[] a, int i, int j){
    T temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
public static <N extends Component,B extends Component> int partition(N[] ns, int lo, int hi, B b){
    int i,j;
    for(i = j = lo; j < hi; j++){
        int cmp = compareTo(ns[j],b);
        if( cmp == -1){
            exch(ns,i,j);
            i++;
        } else if (cmp == 0){
            exch(ns,j,hi);
            j--;
        }
    }
    exch(ns,hi,i);
    return i;
}

public static<N extends Component, B extends Component> void sort(N[] ns, B[] bs, int lo, int hi){
    if(hi <= lo) return;
    Random rn = new Random();
    int ch = lo + rn.nextInt(hi - lo + 1);
    int part = partition(bs,lo,hi,ns[ch]);
    partition(ns,lo,hi,bs[part]);
    sort(ns,bs,lo,part-1);
    sort(ns,bs,part+1,hi);

}
public static <N extends Component, B extends Component> void sort(N[] ns, B[] bs, int n){
    sort(ns, bs,0, n-1);
}
public static void main(String[] args) {
    Nut[] ns = {new Nut(4),new Nut(9),new Nut(1),new Nut(6),new Nut(7),new Nut(19)};
    Bolt[] bs = {new Bolt(19),new Bolt(7),new Bolt(1),new Bolt(6),new Bolt(9),new Bolt(4)};
        sort(ns,bs,6);
        for(int i = 0; i < 6; i++){
        System.out.println("nut#:"+ns[i].size+" "+"bolt#:"+bs[i].size);
        }
    }
} 

Liked it? Follow me. Mail me.

 
42
Kudos
 
42
Kudos

Now read this

Sweet Love O’ Mine

Well, with the sun scorching outside and with no intention to doze off in this sultry afternoon, a persistent thought about my love and how she has conquered me from a long time kept coming to my mind. So, that made me write this blog!... Continue →