0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What information do we get when comparing a pipe and a socket? Can we assume that we only know that it is bigger/smaller, but not the exact difference? $\endgroup$ – justhalf Oct 25 '16 at 1:44
  • $\begingroup$ yea you will only know if they are bigger or smaller or perfect fit and nothing else $\endgroup$ – Bibek Aryal Oct 25 '16 at 1:48
  • $\begingroup$ Also, why is this tagged enigmatic-puzzle? And how to quantify "efficiently"? $\endgroup$ – justhalf Oct 25 '16 at 2:52
  • 2
    $\begingroup$ "enigmatic-puzzle" means that the puzzle doesn't say explicitly what counts as an answer: part of the puzzle is to work out what the puzzle is. This isn't an enigmatic-puzzle in that sense. We know what counts as an answer: an algorithm for doing the matching that uses as few comparisons as possible. $\endgroup$ – Gareth McCaughan Oct 25 '16 at 15:50
  • 1
    $\begingroup$ I would argue that anything involving bigoh notation, abstract concepts like "time complexity" is not a puzzle, and therefore off-topic. I would suggest rewording the question in simple terms. $\endgroup$ – Matsmath Oct 26 '16 at 16:15
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 But just in case if it goes into worst case scenarios. :) $\endgroup$ – Techidiot Oct 25 '16 at 9:52
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 for the answer but to be honest, i am having problem following your answer line by line. i did google the term quadratic time and now i have edited the question where the solution needs to be in linear time or less. i hope you are among the ones who really like tough questions :D $\endgroup$ – Bibek Aryal Oct 26 '16 at 2:25
  • $\begingroup$ Given that it turns out you're trying to get us to do your homework for you, I'm not writing any more on this, sorry. $\endgroup$ – Gareth McCaughan Oct 26 '16 at 9:12
  • $\begingroup$ Its totally fine. All I wanted was the logic itself and not the complete work. And no its not exactly a homework $\endgroup$ – Bibek Aryal Oct 26 '16 at 14:26
  • $\begingroup$ So what did you mean by "I have to develop a working computer program for this puzzle"? $\endgroup$ – Gareth McCaughan Oct 26 '16 at 14:45
  • $\begingroup$ bumped into this question from a friend and this got me intrigued. thought that if i could figure out the logic i could turn it into a working computer program.im not sure if that places it outside this site's scope.if it does i will delete it $\endgroup$ – Bibek Aryal Oct 26 '16 at 14:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 'Divide the sockets into two groups by looking at their sizes' won't work. See 'Constraint: Comparison of a pipe to another pipe or a socket to another socket is not allowed'. $\endgroup$ – CiaPan Oct 25 '16 at 9:57
  • $\begingroup$ @CiaPan - Updated. Thanks. I thought comparison by just looking may work :) $\endgroup$ – Techidiot Oct 25 '16 at 9:59
  • $\begingroup$ by repeat above steps u mean 2 and 3 right? $\endgroup$ – Bibek Aryal Oct 25 '16 at 11:30
  • $\begingroup$ @BibekAryal - After step 3 we will be back with two groups. Hence, we need to regroup them and repeat the steps 2 and 3. $\endgroup$ – Techidiot Oct 25 '16 at 11:35
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm afraid your alleged average case can't possibly be the actual average case for any algorithm; this has to take more time than that on average, because you can reduce it to another problem that takes more time than that; see the start of my answer. $\endgroup$ – Gareth McCaughan Oct 25 '16 at 17:39
  • $\begingroup$ I updated my answer to say "best case" instead of average. Again, it's been a while since I've done summations like that. :) $\endgroup$ – jstnthms Oct 25 '16 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.