FilesExpand file tree

 master

/

garage.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (43 loc) · 1.51 KB

 master

/

garage.py

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (43 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

# 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.

#Edited by cyberking-saga

def garage(beg, end):

i = 0

moves = 0

while beg != end:

if beg[i] != 0 and beg[i] != end[i]:

car = beg[i]

empty = beg.index(0)

final_pos = end.index(beg[i])

if empty != final_pos:

beg[final_pos], beg[empty] = beg[empty], beg[final_pos]

print beg

empty = beg.index(0)

beg[beg.index(car)], beg[empty] = beg[empty], beg[beg.index(car)]

print beg

moves += 2

else:

beg[beg.index(car)], beg[empty] = beg[empty], beg[beg.index(car)]

print beg

moves += 1

i += 1

if i == len(beg):

i = 0

return moves

if __name__ == "__main__":

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

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

print("initial:", initial)

print("final:", final)

print(garage(initial, final))