CODEWITHSUNDEEP
algorithmoptimization
user3572917
user3572917

Reputation: 45

Algorithm to distribute n objects to n different locations with minimum moves

There are n rooms arranged in a circle and n objects. At the end of the process each room should only have 1 object in it. Initially, each room can have a random number of objects from 0 to n but the sum of all the objects in all rooms is n. What is an algorithm to move these objects so that each room only has 1 object with minimum moves, assuming that moving an object from one room to the one clockwise next to it counts as 1 move and no other movement is possible.

Example:
n = 5
Initial situation:
room 1 = 5
room 2: 0
room 3: 0
room 4: 0
room 5: 0
Solution: 1+2+3+4 = 10

Upvotes: 1

Views: 416

Answers (2)

chqrlie
chqrlie

Reputation: 144969

The algorithm seems pretty simple:

  • Iterate through all rooms in clockwise order.
  • For each room, move any excess objects to the next room.
  • Keep going until all rooms have 1 object, at most 2*number_of_rooms-1 steps may be necessary.

That's it.

The number of moves can be computed this way:

int n = 5;
int rooms[5] = { 5, 0, 0, 0, 0 };
int excess = 0;
int total = 0;

for (int i = 0; i < 2 * n - 1; i++) {
    excess = rooms[i % n] - 1;
    if (excess > 0) {
        total += excess;
        rooms[i % n] = 1;
        rooms[(i + 1) % n] += excess;
    }
}

Upvotes: 0

Shubhashis
Shubhashis

Reputation: 10631

I'm only giving an idea on how to solve this problem.

At first lets build a priority queue. The queue will sorted according to nearest distance.

At first you will need to find the nodes that have extra objects, meaning it has more than 1 object. Lets call that filledRooms.

Now find the empty rooms, meaning these rooms have 0 object. Call it emptyRooms.

And the other rooms(Rooms having only 1 object) stay unaffected and these rooms are not included in the calculation.

Now build the priority queue sorted according to distance from the rooms. So it will be,

filledRooms -- emptyRooms -- distance

Your example is very simple, So, lets give an example.

Room no 1->2->3->4->5
Room obj 2->0->0->3->0

So, filled Rooms are 1 and 4. Distance from 1 to 2 is 1, 1 to 3 is 2, 4 to 5 is 1, 4 to 2 is 2, 4 to 3 is 2 Lets sort this out,

1 2 1
4 5 1
1 3 2
4 2 2
4 3 3

Now lets fill out the rooms until we've exhausted the rooms objects(Meaning only 1 object is left).

So move 1 object from 1 to 2. (We've exhausted 1)
move 1 object from 1 to 3(Can't do that, we've exhausted Room 1)
move 1 object from 4 to 2
Move 1 object from 4 to 3

Add up the costs. This is your optimal answer. This will also work if clockwise and anticlockwise both movements are allowed.

Upvotes: 2

Related Questions