Rearrange parking lot


  • 0
    C

    There is a parking lot with only one empty spot. Given the initial state
    of the parking lot and the final state. Each step we are only allowed to move a car
    out of its place and move it into the empty spot. The goal is to find out the least movement needed to rearrange the parking lot from the initial state to the final state.

    Say the initial state is an array:

    [1,2,3,0,4], 
    

    where 1,2,3,4 are different cars, and 0 is the empty spot.

    And the final state is

    [0,3,2,1,4].
    

    We can swap 1 with 0 in the initial array to get [0,2,3,1,4] and so on. Each step swap with 0 only.


  • 0
    V

    swap the position of the initial car position with final car position ? Am I missing something ?


  • 0
    C

    @vbchekur Each step you can only swap the car position with the empty spot, not directly with another car position. So from [1,0,2] to [2,0,1], you can do

    [1,0,2] => [0,1,2] => [2,1,0] => [2,0,1]
    

    And you can't just do

    [1,0,2] => [2,0,1]

  • 0
    V

    @cqnkxy ahh.. Thanks it makes more sense to me now. But can we not do it like this:

    [1,2,3,0,4] => [1,0,3,2,4] => [1,3,0,2,4] => [1,3,2,0,4] => [0,3,2,1,4]
    ans: 4 steps

    Essentially it is the same thing I said before but with an intermediate step.


  • 0
    C

    @vbchekur Yes, but problem arises when 0 is already in the right place. Of course you can swap it randomly with one misplaced car, then start again. That is gonna take you one extra step. So is it optimal to just choose randomly when 0 is already in the right place?


  • 0
    V

    @cqnkxy I think it will not matter since everything will eventually be placed in the position it is supposed to go.

    [1,2,3,0,4] => [1,0,3,2,4] => [1,3,0,2,4] => [1,3,2,0,4] => [0,3,2,1,4]
    here answer is 4
    
    but if I would have gone the other route
    [1,2,3,0,4] => [0,2,3,1,4] => [2,0,3,1,4] => [2,3,0,1,4] => [0,3,2,1,4]
    the answer again comes out to be same i.e. 4
    

  • 0
    C

    @vbchekur I agree that they will end up with the right final positions. But I was wondering whether one route will have less states where 0 is already in the right place, which will conceptually give out less steps. Or if generally all routes are the same, can we prove it?


  • 0
    V

    @cqnkxy said in Rearrange parking lot:

    . But I was wondering whether one route will have less states where 0 is already in the right place, which will conceptually give out less steps. Or if generally all routes are the same, can we prove it?

    I think this will take the least steps mate. But it is just my thought though.


  • 0
    C

    @vbchekur Thanks! Appreciate your thoughts.


  • 0
    V

    @cqnkxy No problem man ! Lemme know if you can come up with a better solution.


  • 1
    C

    @vbchekur I think I may find a possible explanation.

    loops

    It's about the loops in a certain state. If some numbers are not in the right place, they will form a loop with your method. If 0 is in that loop, then those numbers in that loop can all be shifted to the right place, including 0. If 0 is not already in one loop, we have to move 0 into one loop first. How many times we need to move 0 out of its right place depends solely on the number of loops that don't include 0 in the first place.


  • 0
    V

    @cqnkxy yes you are correct.


  • 0
    A

    hi @cqnkxy ,Please check my code

    
        public int rearrangeCars(int[] initial , int[] end){
            int count=0;
            if(initial==null || end==null || initial.length<=0 || end.length<=0){
                return 0;
            }
            HashMap<Integer,Integer> initial_map = new HashMap<Integer, Integer>();
            HashMap<Integer,Integer> final_map = new HashMap<Integer, Integer>();
            for(int i=0;i<initial.length;i++){
                initial_map.put(initial[i],i);
                final_map.put(end[i],i);
            }
    
            for(int j : initial_map.keySet()){
                if(j==0){
                    continue;
                }
    
                int zero_pos = initial_map.get(0);
                int final_pos = final_map.get(j);
                int curr_Pos = initial_map.get(j);
                if(final_pos==curr_Pos){
                    continue;
                }
                //If the final position of the element has zero on it , then we need one swap
                if(final_pos==zero_pos){
                    swap(initial,zero_pos,curr_Pos);
                    initial_map.put(0,curr_Pos);
                    initial_map.put(j,final_pos);
                    count++;
                }else{
                    //if the final position of the element does not have zero on it , then we need 2 swaps
                    //Example Switch 2 to 2nd index  in this case => {0,2,3}=>{3,2,0}=>{3,0,2}
                    int element = initial[final_pos];//Element present in final position
                    swap(initial,final_pos,zero_pos);
                    initial_map.put(element,zero_pos);//update the map
                    swap(initial,curr_Pos,final_pos);
                    initial_map.put(0,curr_Pos);
                    initial_map.put(j,final_pos);
                    count += 2;
                }
    
            }
            return count;
        }
    
        public void swap(int[] a , int i , int j){
            int temp =a[i];
            a[i] =a[j];
            a[j] =temp;
    
        }

  • 0
    C

    @aman35 cool thanks.


  • 1
    P
    import java.util.*;
    import java.lang.*;
    import java.io.*;
    
    class Ideone {
    	public static void main (String[] args) throws java.lang.Exception {
    		int[] lot = {1,2,3,0,4};
    		int[] target = {0,3,2,1,4};
    		
    		System.out.print("Initial: [");
    		for (int i = 0; i < lot.length; i++) {
    			System.out.print(lot[i] + ",");
    		}
    		System.out.println("]");
    
    		int swaps = rearrange(lot, target);
    
    		System.out.print("Result: [");
    		for (int i = 0; i < lot.length; i++) {
    			System.out.print(lot[i] + ",");
    		}
    		System.out.println("]");
    		System.out.println("Swaps: " + swaps);
    	}
    
    	private static int rearrange(int[] lot, int[] target) {
    		Map<Integer, Integer> indices = new HashMap<>();	
    		for (int i = 0; i < lot.length; i++) {
    			indices.put(lot[i], i);
    		}
    
    		int count = 0;
    		for (int i = 0; i < target.length; i++) {
    			if (target[i] != 0 && target[i] != lot[i]) {
                                    // get index of the target element in the initial array
    				int index = indices.get(target[i]);
                                    // get index of empty lot
    				int empty = indices.get(0);
    
                                    // move current element to empty lot
    				lot[empty] = lot[i];
                                    // move target element to current lot
    				lot[i] = lot[index];
                                    // make the lot in which target element was present as empty lot
    				lot[index] = 0;
    				count += (i == empty) ? 1 : 2;   // if current lot was empty lot, 1 swap reduced
    
                                    // update the positons in the map
    				indices.put(lot[empty], empty);
    				indices.put(lot[i], i);
    				indices.put(0, index);
    			}
    		}
    
    		return count;
    	}
    }
    

  • 0
    L

    Hey guys, here's my python solution.

    I think this gives the least amount of moves. Let me know if you see a flaw.

    Thanks

    def Garage(beg, end):
    
        moves = 0
        i = 0
        while beg != end :
            if beg[i] != end[i] and beg[i] != 0:
                car = beg[i] #car that we will move
                free_space = beg.index(0)
                beg[beg.index(car)], beg[free_space] = beg[free_space], beg[beg.index(car)]
                moves += 1
                ## move car that's not in correct place into free space
                print(beg)
                if beg.index(car) != end.index(car):
                    # if the recently moved car is still not in its correct place
                    # then we want to move another car into the free space where
                    # it will be in its correct position
                    beg[beg.index(end[i])] = 0
                    beg[i] = end[i]
                    print(beg)
                    moves += 1
            i += 1 #move onto the next car, check again
            if i == len(beg):
                i = 0
    
        return moves
    
    

  • 0
    H

    Got minimum swaps for few test cases, prints intermediate steps too. Please comment
    http://ideone.com/Gx6OeI


  • 0
    P
    public static  int stepCount(int[] initialState,int[] finalState) {
    
        int result = 0;
    
        HashMap<Integer,Integer> finalNoToPos = new HashMap<>();
        HashMap<Integer,Integer> initialNoToPos = new HashMap<>();
    
    
        for (int i=0;i<finalState.length;i++) {
            finalNoToPos.put(finalState[i],i);
        }
    
        for (int i=0;i<initialState.length;i++) {
            initialNoToPos.put(initialState[i],i);
        }
    
        /*
    
        Just move the car to be parked in the empty positon.
        Then move the car that needs to be placed in the new empty postion.
        By this way you'll move only those cars need to be moved only once.
    
         */
        while (!initialNoToPos.get(0).equals(finalNoToPos.get(0))) {
            int zeroPos = initialNoToPos.get(0);
            int noToBePlaced = finalState[zeroPos];
            int posOfNoToPlaceInZeroPos = initialNoToPos.get(noToBePlaced);
            result++;
            initialNoToPos.put(noToBePlaced,zeroPos);
            initialNoToPos.put(0,posOfNoToPlaceInZeroPos);
        }
    
        int stillPlacedIncorrect = 0;
        /*
          Ones empty is at its current position, the total count required to place the remaining cars correctly is #cars+1
         */
        for (Integer key : initialNoToPos.keySet()) {
            if(!Objects.equals(initialNoToPos.get(key), finalNoToPos.get(key))) {
                stillPlacedIncorrect++;
            }
        }
    
        return result + stillPlacedIncorrect+1;
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.