Locker Room Algorithm [closed]

Question

Note: Just to give a heads up, this is not an assignment for my school since I myself don't even know which school wrote this question. Hopefully no misunderstanding occurred.

I found this interesting questions about locker room:

The locker room of the Rec has N lockers that are labeled 1, 2, . . ., N .

Each locker is locked, but can be opened using its unique key.

Copies of the key to each locker are in its adjacent lockers; i.e. a copy of the key to locker i is placed in locker i + 1 and i − 1 (the key to locker 1 is only in locker 2 and the key to locker N is only in locker N − 1).

T tennis balls are inside T distinct lockers (and you know which of the lockers they are in). You are given keys to M of the lockers and your goal is to collect all of the tennis balls by opening the least number of lockers.

For pictures you can see it directly to the file here.

I have to give this questions to some freshman but I wanted to make sure first that I myself already have the correct answer beforehand.

What I'm thinking is that:

1. Need to check the ball one by one. So for each ball (ignore the other balls), each key have to visit by traversing to the designated ball. For each key, calculate the steps it takes to visit the ball. The smallest result is stored in an variable called "total steps".

2. Do this exact thing to the next ball and when I get the minimum steps for this current ball. I add this value to "total steps".

3. Special condition applied if there is a ball above the key, then key start traversing from i + 1 and i - 1.

My question is: am I right? I don't want to share the wrong algorithm to others since it's unprofessional. Looking forward to any comments, suggestions and inputs.

Answer 1

Your algorithm will not result in minimum number of steps. You can not consider balls independently. Lets consider the following case: You have only one key for locker number 1 and balls are in lockers 12, 10, 8, 6, 4, 2. If You consider the balls in the order I have given you will end up with total steps equal to 11 + 9 + 7 + 5 + 3 + 1, while you can solve the problem in a single pass of 11 steps. You should not ignore the boxes visited on the previous steps.

Answer 2

Here is a technique you can use:

Consider each locker (in which there is a ball, of which you have a key and which have none) to be a node in the graph. The nodes will be of two types:

A) Lockers having balls
B) Lockers of which you have keys.
C) Lockers which have none

Consider all lockers of type-A to be closed and type-B to be open.

From all open lockers, find paths to all closed lockers (from locker type-B) and open the locker in A with min path length. Also, open all lockers of type C which fall in this min-path and move them from category-C to B.

Repeat above step till all lockers in A are opened. Sum of all the min-path lengths that you have come across will be your answer.