-
Notifications
You must be signed in to change notification settings - Fork 4
/
gap.py
92 lines (91 loc) · 5.59 KB
/
gap.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
# autogenerated by bellmaniac
import sys
plus = min
zero = sys.maxint
DIM = 128
MIN = 0
MAX = 1000
from numpy import *
def g(T, oi, oj):
for i0 in xrange(0,(n + 1)):
for j0 in xrange(0,(n + 1)):
i = i0
j = j0
assert (((((0 <= i) and (i <= n)) and (0 <= j)) and (j <= n)) and (n > 0))
T[(i + oi), (j + oj)] = (w2 if ((i == 0) and (j == 0)) else (w[0, j] if ((i == 0) and (j > 0)) else (w1[i, 0] if ((i > 0) and (j == 0)) else reduce(plus, [(T[(i + oi), (q + oj)] + w[q, j]) for q in xrange(0, j)] + [(T[(p + oi), (j + oj)] + w1[i, p]) for p in xrange(0, i)] + [(T[((i - 1) + oi), ((j - 1) + oj)] + s[i, j])] + [r[i, j]], zero))))
r = empty((DIM, DIM), int)
r.fill(zero)
s = random.randint(MIN, MAX, size=(DIM, DIM))
w2 = 0
w1 = random.randint(MIN, MAX, size=(DIM, DIM))
w = random.randint(MIN, MAX, size=(DIM, DIM))
n = 64
def c1(T, oi, oj, n, w1, t, r, w1_0, w1_1, t_0, t_1, r_0, r_1):
if (n < 4):
c(T, oi, oj, n, w1, t, r, w1_0, w1_1, t_0, t_1, r_0, r_1)
return
# partition
c1(T, oi, oj, n/2, w1, t, r, w1_0, (n/2 + w1_1), (n/2 + t_0), t_1, r_0, r_1)
c1(T, oi, oj, n/2, w1, t, T, w1_0, w1_1, t_0, t_1, oi, oj)
# partition
c1(T, oi, (oj + n/2), n/2, w1, t, r, w1_0, (n/2 + w1_1), (n/2 + t_0), (n/2 + t_1), r_0, (n/2 + r_1))
c1(T, oi, (oj + n/2), n/2, w1, t, T, w1_0, w1_1, t_0, (n/2 + t_1), oi, (oj + n/2))
# partition
c1(T, (oi + n/2), oj, n/2, w1, t, r, (n/2 + w1_0), (n/2 + w1_1), (n/2 + t_0), t_1, (n/2 + r_0), r_1)
c1(T, (oi + n/2), oj, n/2, w1, t, T, (n/2 + w1_0), w1_1, t_0, t_1, (oi + n/2), oj)
# partition
c1(T, (oi + n/2), (oj + n/2), n/2, w1, t, r, (n/2 + w1_0), (n/2 + w1_1), (n/2 + t_0), (n/2 + t_1), (n/2 + r_0), (n/2 + r_1))
c1(T, (oi + n/2), (oj + n/2), n/2, w1, t, T, (n/2 + w1_0), w1_1, t_0, (n/2 + t_1), (oi + n/2), (oj + n/2))
def b1(T, oi, oj, n, w, t, r, w_0, w_1, t_0, t_1, r_0, r_1):
if (n < 4):
b(T, oi, oj, n, w, t, r, w_0, w_1, t_0, t_1, r_0, r_1)
return
# partition
b1(T, oi, oj, n/2, w, t, r, (n/2 + w_0), w_1, t_0, (n/2 + t_1), r_0, r_1)
b1(T, oi, oj, n/2, w, t, T, w_0, w_1, t_0, t_1, oi, oj)
# partition
b1(T, oi, (oj + n/2), n/2, w, t, r, (n/2 + w_0), (n/2 + w_1), t_0, (n/2 + t_1), r_0, (n/2 + r_1))
b1(T, oi, (oj + n/2), n/2, w, t, T, w_0, (n/2 + w_1), t_0, t_1, oi, (oj + n/2))
# partition
b1(T, (oi + n/2), oj, n/2, w, t, r, (n/2 + w_0), w_1, (n/2 + t_0), (n/2 + t_1), (n/2 + r_0), r_1)
b1(T, (oi + n/2), oj, n/2, w, t, T, w_0, w_1, (n/2 + t_0), t_1, (oi + n/2), oj)
# partition
b1(T, (oi + n/2), (oj + n/2), n/2, w, t, r, (n/2 + w_0), (n/2 + w_1), (n/2 + t_0), (n/2 + t_1), (n/2 + r_0), (n/2 + r_1))
b1(T, (oi + n/2), (oj + n/2), n/2, w, t, T, w_0, (n/2 + w_1), (n/2 + t_0), t_1, (oi + n/2), (oj + n/2))
def g1(T, oi, oj, v, v1, n, w, w1, w2, s, r, v_0, v_1, v1_0, v1_1, w_0, w_1, w1_0, w1_1, s_0, s_1, r_0, r_1):
if (n < 4):
g0(T, oi, oj, v, v1, n, w, w1, w2, s, r, v_0, v_1, v1_0, v1_1, w_0, w_1, w1_0, w1_1, s_0, s_1, r_0, r_1)
return
# partition
g1(T, oi, oj, v, v1, n/2, w, w1, w2, s, r, v_0, v_1, v1_0, v1_1, w_0, w_1, w1_0, w1_1, s_0, s_1, r_0, r_1)
# partition
b1(T, oi, (oj + n/2), n/2, w, T, r, w_0, (n/2 + w_1), oi, oj, r_0, (n/2 + r_1))
g1(T, oi, (oj + n/2), v, T, n/2, w, w1, v[(0 + v_0), (n/2 + v_1)], s, T, v_0, (n/2 + v_1), oi, (n/2 + oj), (n/2 + w_0), (n/2 + w_1), w1_0, w1_1, s_0, (n/2 + s_1), oi, (oj + n/2))
# partition
c1(T, (oi + n/2), oj, n/2, w1, T, r, (n/2 + w1_0), w1_1, oi, oj, (n/2 + r_0), r_1)
g1(T, (oi + n/2), oj, T, v1, n/2, w, w1, v1[(n/2 + v1_0), (0 + v1_1)], s, T, (n/2 + oi), oj, (n/2 + v1_0), v1_1, w_0, w_1, (n/2 + w1_0), (n/2 + w1_1), (n/2 + s_0), s_1, (oi + n/2), oj)
# partition
b1(T, (oi + n/2), (oj + n/2), n/2, w, T, r, w_0, (n/2 + w_1), (oi + n/2), oj, (n/2 + r_0), (n/2 + r_1))
c1(T, (oi + n/2), (oj + n/2), n/2, w1, T, T, (n/2 + w1_0), w1_1, oi, (oj + n/2), (oi + n/2), (oj + n/2))
g1(T, (oi + n/2), (oj + n/2), T, T, n/2, w, w1, g1[n/2, n/2, v, v1, n/2, w, w1, w2, s, r, v_0, v_1, v1_0, v1_1, w_0, w_1, w1_0, w1_1, s_0, s_1, r_0, r_1], s, T, (n/2 + oi), (oj + n/2), (oi + n/2), (n/2 + oj), (n/2 + w_0), (n/2 + w_1), (n/2 + w1_0), (n/2 + w1_1), (n/2 + s_0), (n/2 + s_1), (oi + n/2), (oj + n/2))
def g0(T, oi, oj, v, v1, n, w, w1, w2, s, r, v_0, v_1, v1_0, v1_1, w_0, w_1, w1_0, w1_1, s_0, s_1, r_0, r_1):
for i0 in xrange(0,(n + 1)):
for j0 in xrange(0,(n + 1)):
i = i0
j = j0
assert (((((0 <= i) and (i <= n)) and (0 <= j)) and (j <= n)) and (n > 0))
T[(i + oi), (j + oj)] = (w2 if ((i == 0) and (j == 0)) else (v[(0 + v_0), (j + v_1)] if ((i == 0) and (j > 0)) else (v1[(i + v1_0), (0 + v1_1)] if ((i > 0) and (j == 0)) else reduce(plus, [(T[(i + oi), (q + oj)] + w[(q + w_0), (j + w_1)]) for q in xrange(0, j)] + [(T[(p + oi), (j + oj)] + w1[(i + w1_0), (p + w1_1)]) for p in xrange(0, i)] + [(T[((i - 1) + oi), ((j - 1) + oj)] + s[(i + s_0), (j + s_1)])] + [r[(i + r_0), (j + r_1)]], zero))))
def b(T, oi, oj, n, w, t, r, w_0, w_1, t_0, t_1, r_0, r_1):
for i0 in xrange(0,(n + 1)):
for j0 in xrange(0,(n + 1)):
i = i0
j = j0
assert (((((0 <= i) and (i <= n)) and (0 <= j)) and (j <= n)) and (n > 0))
T[(i + oi), (j + oj)] = plus(reduce(plus, [(t[(i + t_0), (q + t_1)] + w[(q + w_0), (j + w_1)]) for q in xrange(0, n)], zero), r[(i + r_0), (j + r_1)])
def c(T, oi, oj, n, w1, t, r, w1_0, w1_1, t_0, t_1, r_0, r_1):
for i0 in xrange(0,(n + 1)):
for j0 in xrange(0,(n + 1)):
i = i0
j = j0
assert (((((0 <= i) and (i <= n)) and (0 <= j)) and (j <= n)) and (n > 0))
T[(i + oi), (j + oj)] = plus(reduce(plus, [(t[(p + t_0), (j + t_1)] + w1[(i + w1_0), (p + w1_1)]) for p in xrange(0, n)], zero), r[(i + r_0), (j + r_1)])