In the programming course, we were given the task of minimizing number electrician's trips between the rooms.

Details:

• There is a building with two rooms connected by a thick cable.
• There are e.g. 30 (or rather in general n) coiled wires in the cable.
• The electrician can mark the ends of the individual wires in the cable, connect them and then disconnect them. He has a source and a light bulb to help measure whether they are in the same circuit or not.
• Electrician is allowed to connect even more wires together (2, 3, ...).

Goal:

• Advise the electrician on the procedure, which helps him to be able to identify the ends of the wires that belong to each other (the task is to pair the ends of the wires in the cable).
• Try to minimize the number of electrician trips between rooms.

One of the solutions:

I was thinking of brute-force solution where the guy can put label on one wire in the first room and n times keep trying for all in the second room if the bulb lights up. This leads to O(n^2) which is the worst scenario.

Is there any more efficient way how to minimize the number of electrician trips between rooms? I would appreciate any suggestion.

CodePudding user response：

If the complexity is measured by the number of trips the electrician has to make between the two rooms then your "brute force" solution has complexity O(n) not O(n^2), the electrician only has to travel once between the two rooms for each wire he needs to pair up the ends of, making the number of trips linearly proportional to the number of wires.

You can actually solve this by doing just 2 trips in total, here is my solution:

First in room A connect all wire ends together in pairs, ie. if the wire ends are: A1, A2, A3, A4.. connect A1 and A2 together, and connect A3 and A4 together etc.

In room B connect the source to wire end B1 (any of the wire ends in room B can be B1) and then measure all the other wire ends in room B, once you find the one that is connected to B1 mark it as B2. Now connect the source to B3 and start looking for B4 etc. continue this until you have found all the connected pairs of wire ends in room B. If N (the number of wires) is odd then there will be one wire which you did not pair up with another wire in room A, and which you did not find a connection for in room B either, so you already know which ends belong to this wire in both room A and room B.

So far we have made just one trip between the two rooms and we have not found all the matching wire ends between room A and room B yet but we have found all the pairs of matching wire ends between the two rooms, if that makes sense.

The next step is as follows: for each pair of wire ends that you found in room B pick one of them, lets say you pick the odd ones (B1, B3, B5 etc.) Now connect them all together and connect them to the source. Now after connecting all the odd wire ends in room B together and connecting them to the source go to room A.

In room A disconnect all the pairs one by one and for each pair measure which end is connected to the source in room B, which will tell you which of the ends are connected to the odd end in room B.

EDIT: As @greybeard pointed out in the comments you still need to match up each of the pairs between room A and room B, so A bit more work is needed:

After the two trips described above you have reduces the number of wire ends that you need to pair up down to floor(N/2), the next step is to recursively do the above steps (requiring two trips each time) on the pairs of wires until you are done.

The last step (requiring two trips) is when you are down to just 4 combinations of wires. So the number of trips that you end up doing this way is actually log2(N).