diff options
Diffstat (limited to 'robots/algorithms.pyx')
| -rw-r--r-- | robots/algorithms.pyx | 43 |
1 files changed, 35 insertions, 8 deletions
diff --git a/robots/algorithms.pyx b/robots/algorithms.pyx index 620cfce..3bf6916 100644 --- a/robots/algorithms.pyx +++ b/robots/algorithms.pyx @@ -10,17 +10,31 @@ ctypedef np.int32_t ITYPE_t ctypedef cython.bint bool -from robots.constants import DIRECTIONS - INFINITY = float('inf') FAKE_INFINITY = 1<<31 - 1 +PREDECESSORS = {} +for i in range(16): + p = [] + if i & 1: + p.append('U') + if i & 2: + p.append('D') + if i & 4: + p.append('L') + if i & 8: + p.append('R') + PREDECESSORS[i] = p + def distance_relaxer(distances, iterations=None): width = len(distances[0]) height = len(distances) predecessors = [ - [None] * width + [ + [] + for _ in range(width) + ] for _ in range(height) ] @@ -68,7 +82,6 @@ cdef void _distance_relaxer( int iterations, Py_ssize_t width, Py_ssize_t height, - DIRECTIONS=DIRECTIONS, ): cdef Py_ssize_t x, y cdef Py_ssize_t nx, ny @@ -76,6 +89,7 @@ cdef void _distance_relaxer( cdef int i = 0 cdef bool updated + cdef int p while i != iterations: updated = False @@ -86,6 +100,8 @@ cdef void _distance_relaxer( if distance == -1: continue + p = 0 + nx = x ny = (y - 1) % height this_distance = distances[ny, nx] @@ -93,9 +109,11 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'U' updated = True + if this_distance == distances[y, x]: + p |= 1 nx = x ny = (y + 1) % height @@ -104,9 +122,11 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'D' updated = True + if this_distance == distances[y, x]: + p |= 2 nx = (x - 1) % width ny = y @@ -115,9 +135,11 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'L' updated = True + if this_distance == distances[y, x]: + p |= 4 nx = (x + 1) % width ny = y @@ -126,9 +148,14 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'R' updated = True + if this_distance == distances[y, x]: + p |= 8 + + if p: + predecessors[y][x] = PREDECESSORS[p] if not updated: break |