CareerCup

You can use any kind of sorting since you can keep more than one person at a floor. However, there is a catch - minimum number of movements does not necessarily mean, minimum traveled distance, by the lift, so I would ask for that clarification.

Can you explain with an example? Initially all persons are at same floor or at random floors?

Selection and insertion sort will work for nsquare complexity.

Important question would be - do we know up front which floor has which person number?
In other words, does the lift find out who's person number is at the floor only once it visits this floor?

Start from floor 1 till ith floor until you find a person on the wrong
floor, take him to his respective floor
take the guy from that floor and take him to his respective floor do it
until you reach back to ith floor.
Keep a counter, if all the N persons have been moved you are done otherwise
repeat the procedure
starting from i+1 th floor.

This appears to be asking to implement sort functionality on a Turing machine.

The lift is either going up or coming down. We have to consider the direction, the ID of a person and the floor #.

While going up 
    if person ID > current floor number
        if the lift is empty 
             Add the current person to the lift. 
         else if the person ID in the lift < person ID on the floor OR the person ID in the lift equals current floor #
              Swap the person in the lift with the person on the floor.
 
While coming down 
    if person ID < current floor number
        if the lift is empty 
             Add the current person to the lift. 
         else if the person ID in the lift > person ID on the floor OR the person ID in the lift equals current floor #
              Swap the person in the lift with the person on the floor.

Each lift movement to the top puts at least one person in right position and each movement from the top to the bottom puts at least one person in the right position. The total number of movements will therefore be at most N to sort N persons into their places.

Eg: if the initial ordering of people was 3 2 1 for N=3 people, then the sort should work as below

Initial:   3  2  1

Step 1:     _  2  1 
           (3) [inside lift]

Step 2:     _  2  1 
               (3)

Step 3:     _  2  1 
                 (3)

Step 4:     _  2  3 
                  (1)

Step 5:     _  2  3 
              (1)

Step 6:     _  2  3 
            (1)

Step 6:     1  2  3 
           (_)

An upfront sorry about the long post below. I think we need to realize that for minimum number of lift movements, this problem involves traversing cycles in terms of how we move people.

Lets say the people are in the following order from floors 1 to 5: [ P4, P3, P1, P5, P2 ]
So, following are the lift movements [ P4->F4, P5 ->F5, P2->F2, P3->F3, P1->F1] .. after moving the last person we are back to where we started at floor 1 and this has minimum number of lift movements.

The above example has 1 cycle .. and moving ppl in one continuous cycle minimizes the number of lift movements.

The solution is more complex when we have multiple cycles .. since after completing 1 cycle, we have to process the next cycle ... and this inter-cycle movement causes extra lift movements. In the example given by "aka", there are multiple cycles:

floor person_tag
1 2
2 1
3 3
4 5
5 4

cycle 1: [(1 2), (2 1)]
cycle 2: [(3,3)]
cycle 3: [(4 5) (5 4)]

In this case, we can ignore all cycles that have a single element. so ignore cycle 2: [(3,3)].

Start cycle 1: move person 2 from floor 1 to floor 2. suspend Cycle1 ... floor 2 has persons 1 and 2

Move to floor 4 to start processing cycle 3: move person 4 to floor 5 and move person 5 to floor 4

move back to floor2 to resume cycle 1: move person 1 to floor 1.

In this solution, the extra lift movements are when moving from cycle 1 to cycle 3 and back.


Overall, the solution involves finding all cycles, ignore cycles with single elements. Then we need to find overlapping cycles and underlapping cycles. We need to move from 1 cycle to another by suspending the first cycle (put on stack) and moving to the second cycle anytime there is overlap or underlap. This could be recursive and so we would need a stack to keep track of where we suspended cycles and in which order.

The another idea, we can treat this problem as calculate the connected components of one graph.
For example:
1) if
floor[1] = person[2], floor[2] = person[3], floor[3] = person[4], floor[4] = person[1].
The connected component (or a circle) contains 4 elements, so we can do 4 lift movements to finish the operation to move person[i] to floor[i].
2) if floor[1] = person[1], under this situation, we do 0 lift movements to finish the operation.
We can DFS to find the number of connected components and the number of elements of each connected components.

@aka, if we use the idea to find the connected components of one graph, we can get the result use DFS and a vector<int> (or some others) data structure, instead of doing many times search operation and to find the minimum lift movements.

Below is my code using calculating the connected components of one graph.

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int n = 10;
bool visit[n];

void dfs(int x, int seat[], vector<int>& rec)
{
    visit[x] = true;
    rec.push_back(x);
    if(!visit[seat[x]])
    {
        dfs(seat[x], seat, rec);
    }
}

int findMinLift(int seat[])
{
    int i = 0;
    int ret = 0;

    vector<int> list;
    memset(visit, false, sizeof(visit));
    while(true)
    {
        list.clear();
        for(i = 0; i < n; i++)
        {
            if(seat[i] != i && !visit[i])
            {
                dfs(i, seat, list);
                for(vector<int>::iterator it = list.begin(); it != list.end(); it++)
                {
                    cout << (*it) << " ";
                }
                cout << endl;

                if(list.size() > 1)
                {
                    ret += list.size();
                }
                break;
            }
        }
        if(i == n)
        {
            break;
        }
    }
    return ret;
}

int main()
{
    int seat[n] = {3, 8, 9, 4, 0, 1, 5, 2, 6, 7};

    int min = findMinLift(seat);

    cout << min;

    return 0;
}

Since the title told us
"While moving persons, at some point of time, we can keep more than one person at one floor."
So,
if the initial seat(person) is (3) (2) (1)
1st lift: () (2) (1,3)
2nd lift: (1) (2) (3)

Bubble sort complexity O(N^2)

void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b=tmp;
}
void bubbleSort(int arr[], int size)
{
	for(int i=size-1;i>0;i--)
		for(int j=0;j<i;j++)
		{
			if(arr[j]>arr[j+1])
				swap(arr[j],arr[j+1]);
		}
}

what does minimum number of lift movements mean? does it mean with respect to total number of trips or minimum number of stops ??? at any cost (in worst scenario) , lift has of stop in all n-1 floors ..

Is this algo correct-

// at the ends the lift has only one way
// whenever a person reaches his floor he is disposed of
// after each disposal the direction of motion is ascertained by the following rule. say lift is going down-
// sum(magnitude of shift for persons above the lift upwards) + sum(magnitude of shift for persons below the lift and on the lift downwards) >
// sum(magnitude of shift for persons above the lift downwards) + sum(magnitude of shift for persons below the lift and on the lift upwards) then lift goes down otherwise changes direction

I think a simple bubble sort would be pretty optimal; at each step you're doing your best to get someone closer to where they want to go.

The better-complexity searching algos (quicksort/mergesort) won't work properly because there is no 'swap' operation (for ordering around the pivot) and you can't create and merge lists (for merging).

Random thought ...I guess it is possible to modify Levenshtein distance for floor number as
floors:1234567
Men: 3426715 to get min distance

I have a Integer Linear Programming solution:

I give an example:
(6)(5)(4)(3)(2)(1)

first consider floor1: it has p6. so p6 must be moved to f6. Thus floor5~floor6 each must be passed by the lift from the bottom once. or for convenient, be passed by the lift from the left;

then consider the floor2. it has p5 so floor5~floor3 each be passed by from left once!

continue doing this until floor6: it has p1 so floor1~floor5 each be passed by from right once!

we let Xn be the times floorN be passed by from left
we let Yn be the times floorN be passed by from right;

thus we have the following equations:

* x1>=0 y1>=1;
* x2>=1 y2>=2
* x3>=2 y3>=3
* x4>=3 y4>=2
* x5>=2 y6>=1
* x6>=1 y6>=0

also notice that the lift must be moved continuely through the building: it must visit floor4 if
it go from floor3 to floor5.

how to restrict that? for a certain floor, the difference of its left passed number and right passed number should not be more than one ! Thus |Xn-Yn|<=1 for every n;

and our propose is to minimize the total lift distance. notice that if a floor is passed by either from left or right, it means the lift move One floor distance. so our goal is to

min(X1+....X6+Y1+....Y6)

you solve this ILP problem and you get the optimal solution.

I give my Matlab Code to solve this problem. Matlab has linprog function to solve LP
You can also use other LP solver to solve this problem. Don't try to write your own!!

Also notice that we have restriction that all Xn and Yn must be Integer which turn this problem from a LP to ILP.

ILP is a NPC problem. You're not supposed to have polynomial time solution !! Otherwise rearrange your desk for the Turing Award.

c=[1;1;1;1;1;1;1;1;1;1;1;1];
A=[ -1 0 0 0 0 0 0 0 0 0 0 0 ;
    0 -1 0 0 0 0 0 0 0 0 0 0;
    1 -1 0 0 0 0 0 0 0 0 0 0 ;
    -1 1 0 0 0 0 0 0 0 0 0 0 ;
    0 0 -1 0 0 0 0 0 0 0 0 0;
    0 0 0 -1 0 0 0 0 0 0 0 0;
    0 0 1 -1 0 0 0 0 0 0 0 0 ;
    0 0 -1 1 0 0 0 0 0 0 0 0;
    0 0 0 0 -1 0 0 0 0 0 0 0;
    0 0 0 0 0 -1 0 0 0 0 0 0 ;
    0 0 0 0 1 -1 0 0 0 0 0 0 ;
    0 0 0 0 -1 1 0 0 0 0 0 0 ;
    0 0 0 0 0 0 -1 0 0 0 0 0;
    0 0 0 0 0 0 0 -1 0 0 0 0 ;
    0 0 0 0 0 0 1 -1 0 0 0 0 ;
    0 0 0 0 0 0 -1 1 0 0 0 0;
    0 0 0 0 0 0 0 0 -1 0 0 0;
    0 0 0 0 0 0 0 0 0 -1 0 0 ;
    0 0 0 0 0 0 0 0 1 -1 0 0 ;
    0 0 0 0 0 0 0 0 -1 1 0 0;
    0 0 0 0 0 0 0 0 0 0 -1 0;
    0 0 0 0 0 0 0 0 0 0 0 -1 ; 
    0 0 0 0 0 0 0 0 0 0 1 -1  ;
    0 0 0 0 0 0 0 0 0 0 -1 1 ;
    ];
b=[0;-1;1;1;-1;-2;1;1;-2;-3;1;1;-3;-2;1;1;-2;-1;1;1;0;-1;1;1];
[x,fval]=linprog(c,A,b,[],[],[]);

x=18.0 for this case.

correct me if i solved this problem wrong

DP？

A sorting algorithm which takes minimum seeks.
How about bubble sort which will take about 2N seeks in every step(maximum)

Another approach: If minimizing the travel distance is concern, I would suggest the following:
1. Take the difference between the current and the desired floor of each person -> O(n)
2. Sort these distances in ascending order and reflect the swapping in the main arrays as well -> O(nlogn)
3. Start moving people around as per new sorted distances. -> O(n).
Example:
p1 assigned to 1st floor but in 3rd floor.
p2 assigned to 5th floor but in 2nd floor.
p3 assigned to 3rd but in 1st floor.

based on above ordering: (2+2)+(1+3)+(4+2)=14
based on sorting: (0+2)+(1+3)+(2+2) = 10
based on brute-force (0+3)+(0+2)+(1+4) = 10

So sorting and brute-force result in same shortest distance travel. However, complexity-wise the brute-force is better.

We can treat this problem as sorting an array.
From any point i which contains the person j (!= i), doing sorting algorithm and recording the swap times (and the lift movements == swap times * 2).
Then we do the same operation from other point ii which contains the person jj (!= ii).
At the end, we keep track the minimum value of swap times, and it is the result we want.