CareerCup

I think pkm made a unstated assumption that only the car adjacent to empty space can be moved, which is not stated in the problem. Problem actually says moving only one car at a time into the spot but does not say anything about adjacency.

So I would think that the parking lot can be represented using a simple array such as below:
Initial configuration: 1 5 7 3 9 _ 2 4 6 8
Expected configuration: 1 4 5 2 3 6 9 _ 7 8

Solution: 1 is already placed in appropriate position let us move to second position where 4 should be placed so move 5, from the second place in the initial configuration to empty space and bring 4 in the second place, which is the expected configuration. So you will be performing one comparison and two swapping operations for every car to reach its final configuration hence
Complexity is O(3n) = O(n)

Construct the following hash map: Car => index in original config.
Then apply quick sort algorithm to the source config.
As compare predicate use the following: (car1 < car2) <=> (map[car1] < map[car2]).
When swapping elements, use the empty place.

It would be simpler (O(n)) if you maintain two mapping: car -> lot and lot -> car. Pesudo code:

Reconfig(Car2Lot oldConfig, Car2Lot newConfig)
{
Lot2Car lot2Car //assuming we have built the mapping from lot -> car
for(int i = 0; i < old.Size(); i++) //assume we have perform check for size
{
int lot_old = oldConfig[i];
int lot_new = newConfig[i];
if(lot_old == lot_new) //no change for this car
continue;
lot2Car.Set(SPARE_LOT, lot2Car.Get(lot_new))
//swap two cars ...
oldConfig[i] = lot_new;
oldConfig.Set(lot2Car.Get(SPARE_LOT), lot_old);
// and update lot2Car
lot2Car.Set(lot_new, oldConfig[i].Key);
lot2Car.Set(lot_old, lot2Car.Get(SPARE_LOT));
}
}

at the end of the loop, oldConfig and newConfig should be exactly the same.

The problem is not clear to me. what is the data structure to represent the parking lot configuration? If we don't differentiate cars, can we use a vector<bool> to represent it? if vec[i] is true, then it is occupied. otherwise, it is empty?

Could anyone pls explain the problem a little more? I can't understand some part of the original description.
Thanks in advance.

Ya.. Can somebody please elaborate on the problem first ?

Let me try it in a simple scenario

1 2 3
4 . 5
6 7 8

Above is the configuration of a parking lot, we need to move car from position 3 to 6
The operation we can do is fill the dots with adjacent cars to make that position vacant.

Let me try it in a simple scenario

1 2 3
4 . 5
6 7 8

Above is the configuration of a parking lot, we need to move car from position 3 to 6
The operation we can do is fill the dots with adjacent cars to make that position vacant.

If the problem is same as what pkm mentioned then we may be able to solve this via Graphs or maybe a grid.

Using the same example as pkm:

1 2 3
4 6
7 8 9

Let's the sopt number 5 is empty and we want to take car at spot 3 to car at spot 7.
Now we can just rotate the sub matrix/square/rect and any shape formed corresponding the shortest closed shape bw 3 and 5. Rotate it such that 3 takes spot 5.

Now spot 5 is full with the car which was initially at spot 3 and spot 3 is empty. Do Now again rotate the spots forming the smallest path shape between spot#5 and spot 7.

At the end car kept at spot#7 initially now goes to the initial empty spot and car initially 3 is where we want it to be i.e. at spot#7

I agree with Mohan. We can use a hash map for each car and it's current position that can be used for an O(1) lookup.

Use A* search with the manhattan distance heuristic. The heuristic is the sum of all the manhattan distances of each element from its desired location. If you consider each configuration as a state in a tree graph, the manhattan distance heuristic used with A* search will give you the minimum "distance" in the search tree from the start state to the end state.

www . kantz . com / jason / writing/ 8-puzzle.htm

Initial configuration: 1 5 7 3 9 _ 2 4 6 8
Expected configuration: 1 4 5 2 3 6 9 _ 7 8
Step 1. If in the old config the spot is not the same as the new config (the case above), move the car "6" to the spot and generate a new spot.
Repeat step 1 until the spot is already in place.
Step 2. If the spot is already in place and there is still car not in place, move the car to the spot, repeat step 1.
So, in step 1, one move to make one car in place. Step 2 needs an extra move.
Total move will be number of step 1 and number of step 2. At most O(2n).

Does this problem become a NP-complete problem if I say find the minimum number of steps to convert one parking lot arrangement to other using 1 empty spot?

//assumption: empty position is marked by 0 in the array.
public static void carParkingLotProblem(int[] correctOrder, int[] currentOrder){

int totalSwaps =0;
int emptyPos = 0;
int swapPos = 0;
//find empty position.
for(int i= 0; i<currentOrder.length; i++){
if(currentOrder[i]==0)
emptyPos = i;
}

for(int i=0; i<correctOrder.length; i++){

int correctVal = correctOrder[i];

//first, see if the item is int he correct place
if(correctVal == currentOrder[i]){
//same so dont worry, move on
}else{
//let's find it's position
for(int j=0; j<currentOrder.length; j++){
if(currentOrder[j]==correctVal){
swapPos = j;

}
}

//well, we now want to swap the value in i with j, and use empty as a buffer
//but empty has to be used alwasys/
currentOrder[emptyPos] = currentOrder[i];
currentOrder[i] = currentOrder[swapPos];
emptyPos = swapPos;
currentOrder[emptyPos] = 0;
totalSwaps++;
}




}
System.out.println("Total Swaps: "+totalSwaps);
//newly swapped array...
System.out.println(Arrays.toString(correctOrder));
System.out.println(Arrays.toString(currentOrder));


}

//assumption: empty position is marked by 0 in the array.
	public static void carParkingLotProblem(int[] correctOrder, int[] currentOrder){
		
		int totalSwaps =0;
		int emptyPos = 0;
		int swapPos = 0;
		//find empty position.
		for(int i= 0; i<currentOrder.length; i++){
			if(currentOrder[i]==0)
				emptyPos = i;
		}
		
		for(int i=0; i<correctOrder.length; i++){
			
			int correctVal = correctOrder[i];
			
			//first, see if the item is int he correct place
			if(correctVal == currentOrder[i]){
				//same so dont worry, move on 
			}else{
				//let's find it's position
				for(int j=0; j<currentOrder.length; j++){
					if(currentOrder[j]==correctVal){
						swapPos = j;

					}
				}
				
				//well, we now want to swap the value in i with j, and use empty as a buffer
				//but empty has to be used alwasys/
				currentOrder[emptyPos] = currentOrder[i];
				currentOrder[i] = currentOrder[swapPos];
				emptyPos = swapPos;
				currentOrder[emptyPos] = 0;
				totalSwaps++;
			}
			
			
			
			
		}
		System.out.println("Total Swaps: "+totalSwaps);
		//newly swapped array...
		System.out.println(Arrays.toString(correctOrder));
		System.out.println(Arrays.toString(currentOrder));

		
	}