-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathprepare-the-bunnies-escape.py
119 lines (92 loc) · 3.57 KB
/
prepare-the-bunnies-escape.py
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Step:
def __init__(self, x=None, y=None, steps=0, barrier=False):
self.x = x
self.y = y
self.barrier = barrier
self.steps = steps
def solution(map):
num_rows = len(map)
num_cols = len(map[0])
# cube with all possible locations, using barrier passed or not as dimension
# cube with [x][y][barriers]
cube = [[[Step(i, j) for k in range(2)] for j in range(num_cols)] for i in range(num_rows)]
max_x = num_rows - 1
max_y = num_cols - 1
paths = []
# init
paths.append(Step(0, 0, 1))
for minion in paths:
if minion.x == max_x and minion.y == max_y:
return minion.steps
if minion.x != max_x:
make_move(map, minion.x + 1, minion.y, minion, paths, cube)
if minion.x > 0:
make_move(map, minion.x - 1, minion.y, minion, paths, cube)
if minion.y != max_y:
make_move(map, minion.x, minion.y + 1, minion, paths, cube)
if minion.y > 0:
make_move(map, minion.x, minion.y - 1, minion, paths, cube)
def make_move(map, x, y, minion, paths, cube):
is_barrier = map[x][y] == 1
b = int(minion.barrier)
if cube[x][y][b].steps == 0 or cube[x][y][b].steps > minion.steps+1: # skip if we have passed over here with more steps
if minion.barrier is False or is_barrier is False: # no barrier passed o no barrier in destination
new_step = Step(x, y, minion.steps + 1, minion.barrier)
if is_barrier is True and minion.barrier is False: # first barrier passed, set to true + append
new_step.barrier = True
paths.append(new_step)
cube[x][y][1] = new_step
elif is_barrier is False: # not barrier, append
paths.append(new_step)
cube[x][y][int(new_step.barrier)] = new_step
# else: barrier + passed barrier = not append
print(solution(
[
[0, 1, 1, 0, 0, 0],
[1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 0],
[0, 1, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0]])) # should be 16
print(solution(
[[0, 1, 1, 0],
[0, 0, 0, 1],
[1, 1, 0, 0],
[1, 1, 1, 0]]))
print(solution(
[
[0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0]]))
print(solution(
[[0],
[0],
[0]]
))
print(solution(
[[0, 0, 0]]
))
print(solution(
[[0, 0],
[0, 0]]
))
print(solution(
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0]]))