Pipe and socket problem

Question

Given a set of n pipes of different sizes and n sockets of different sizes. There is a one to ­one mapping between pipes and sockets, meaning that a pipe can fit into only one socket. Match pipes and sockets correctly.

Constraint: Comparison of a pipe to another pipe or a socket to another socket is not allowed. It means pipe can only be compared with socket and socket can only be compared with pipe to see which one is bigger/smaller.

Answer 1

Here is the best I could come up with up for now with the little information we can get from each comparison.

Put all the sockets in a straight line.
Then take a random pipe to start with.
Then start testing with the socket in the middle.
If it is too small, test the left one next, if too big, test the right one next.
When you fail 2 times in a row at any given time, and that one was too big and the other was too small, change their position to make sure the small one is to the right and the big one to the left.
Once you find the good socket, you remove that socket from the line and get a new pipe and start from the middle again.
The socket line will become more and more reliable the more tests you make.
If at any point you reach the end of the line without finding the good socket, you go back in the middle and go the opposite way.

Answer 2

First of all, consider the following trivial algorithm.

Pick any pipe. Compare against all sockets until you find one that matches. Then move on to another pipe, and repeat until all are done.

If there are $n$ pipes and $n$ sockets then this takes at most

$n(n-1)/2$ comparisons.

So that gives us an upper bound on how long we can take in the worst case. For a lower bound,

suppose we are given some extra information at the outset: we are told the sizes of all the sockets. Our challenge is now to sort the pipes, and the only operation available to us is to compare a pipe's size with one of the numbers (let's say) from $1$ to $n$. There are $n!$ possible orderings and each comparison gives us one of at most 3 outcomes, so distinguishing all the outcomes takes at least $\log_3(n!)$ comparisons, which is of order $n\log n$.

If we are content with good average performance, we can do this:

Pick a random pipe. (Call it P.) Try it against all sockets until you find one it matches. (Call that S.) Then partition pipes into "smaller than S" and "larger than S", and sockets into "smaller than P" and "larger than P", after which we have two smaller subproblems. Solve those by the same method. (Once they get small enough you may actually do better to switch to the trivial algorithm above.)

This takes, on average,

time proportional to $n \log n$, with constant of proportionality not too wretched. (It's kinda like quicksort, except that the partitioning step is about twice as slow.)

I haven't yet thought of an algorithm that

does better than quadratic time in the worst case, but I bet there is one. I suspect we can manage time of order $n \log n$ at worst. One difficulty is that some partitioning schemes are much harder than for sorting. For instance, a natural idea is to look for something like mergesort, but that would require us to find $n/2$ matching pipes and sockets at the start.

Perhaps we can do it by

solving a harder problem. We have $n$ pipes and $n$ sockets that don't necessarily match; we have the same comparison-making ability as in the original problem; we want to sort them into an order so that we never have $a$ before $b$ when $a,b$ are of different types and $a$ is larger than $b$. Can we do this in time $O(n \log n)$?

The point here is that

the harder problem may make a better "induction hypothesis". So, let's begin by picking any $\lfloor n/2\rfloor$ pipes and any $\lfloor n/2\rfloor$ sockets. Sort these, and sort the remaining $\lceil n/2\rceil$ pipes and sockets. If we can now combine these in time $O(n)$ then we will have a solution to the original problem in time $O(n\log n)$. Unfortunately we can't. Suppose we happened to pick the $n/2$ biggest pipes and the $n/2$ smallest sockets; then to finish the job requires us to sort the pipes, which surely can't be done in time smaller than $O(n \log n)$. But it seems like something along these lines might be workable.

Answer 3

Another solution is -

Step 1 - Divide the sockets into two groups into two random groups A & B(Unmatched Pairs).

Step 2 - Now, compare a socket and a pipe from Group A. If they match we are good, if they don't, go for the next socket. If the socket doesn't match with any pipe, create a new group say Group C(Unmatched Socket).

Step 3- Now, compare a pipe and a socket from Group B. If they match we are good, if they don't, go for the next pipe. If the pipe doesn't match with any socket, create a new group say Group D(Unmatched Pipes)

Repeat the above process until all matched.

Answer 4

Even if you knew the order of the sockets, there would still be $n!$ possible combinations for the pipes. Each comparison tells you only "match", "lighter", or "heavier". Thus, any algorithm will require at least $O(n\ln n)$ comparisons, on average. There is no way to solve this puzzle using $O(n)$ comparisons.

That said, the puzzle said $O(n)$ time, and it did not say that we could only perform only one comparison at a time. If we line up all the sockets and all the pipes and perform $n$ comparisons at once, we may be able to solve the problem using only $O(n)$ sets of comparisons.

This may sound like cheating, but there is definitely no way to solve the problem in $O(n)$ time without performing multiple comparisons at once.

Answer 5

We can perform a sort of divide and conquer algorithm:

where we have "known" sockets with piles of sockets to the left/right of the "known" sockets. The piles are strictly smaller (left) or larger (right) than the "known" socket.

The algorithm:

1. while there are "known" sockets, compare the pipe to the middle-most known socket in the set; move to the left set if that socket is too big, and to the right set if that socket is too small
2. when we arrive at a set with no "known" sockets, compare the pipe to all those sockets, moving small sockets left, large sockets right, and keeping the matching socket with the pipe as a new "known" socket

I'm not well-versed in mathematical series but:

this algorithm should at best work out to something like the summation of N + N/2 + N/4 + N/8 + N/16, etc. which according to the internet is 2N-1. In the worst case, it would be N + (N-1) + (N-2) + (N-3), etc. which is (N*(N-1))/2 according to the internet

I gotta start reading all the answers in full. Another puzzle where I provide the same answer as someone else, haha