summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--robots/algorithms.pyx135
-rw-r--r--setup.py8
2 files changed, 143 insertions, 0 deletions
diff --git a/robots/algorithms.pyx b/robots/algorithms.pyx
new file mode 100644
index 0000000..620cfce
--- /dev/null
+++ b/robots/algorithms.pyx
@@ -0,0 +1,135 @@
+# cython: language_level=3
+
+cimport cython
+
+import numpy as np
+cimport numpy as np
+
+ITYPE = np.int32
+ctypedef np.int32_t ITYPE_t
+
+ctypedef cython.bint bool
+
+from robots.constants import DIRECTIONS
+
+INFINITY = float('inf')
+FAKE_INFINITY = 1<<31 - 1
+
+def distance_relaxer(distances, iterations=None):
+ width = len(distances[0])
+ height = len(distances)
+
+ predecessors = [
+ [None] * width
+ for _ in range(height)
+ ]
+
+ convert = {
+ INFINITY: FAKE_INFINITY,
+ None: -1,
+ }
+ unconvert = {
+ FAKE_INFINITY: INFINITY,
+ -1: None,
+ }
+ _distances = np.array(
+ [
+ [
+ convert.get(v, v)
+ for v in row
+ ]
+ for row in distances
+ ],
+ dtype=ITYPE,
+ order='c',
+ )
+
+ if iterations is None:
+ iterations = -1
+
+ _distance_relaxer(
+ _distances,
+ predecessors,
+ iterations,
+ width, height,
+ )
+
+ for y in range(height):
+ for x in range(width):
+ v = _distances[y, x]
+ distances[y][x] = unconvert.get(v, v)
+
+ return predecessors
+
+@cython.boundscheck(False)
+cdef void _distance_relaxer(
+ np.ndarray[ITYPE_t, ndim=2, mode='c'] distances,
+ predecessors,
+ int iterations,
+ Py_ssize_t width,
+ Py_ssize_t height,
+ DIRECTIONS=DIRECTIONS,
+):
+ cdef Py_ssize_t x, y
+ cdef Py_ssize_t nx, ny
+ cdef ITYPE_t distance, this_distance
+
+ cdef int i = 0
+ cdef bool updated
+
+ while i != iterations:
+ updated = False
+
+ for y from 0 <= y < height:
+ for x from 0 <= x < width:
+ distance = distances[y, x]
+ if distance == -1:
+ continue
+
+ nx = x
+ ny = (y - 1) % height
+ this_distance = distances[ny, nx]
+ if this_distance != -1:
+ if this_distance != FAKE_INFINITY:
+ this_distance += 1
+ if this_distance < distances[y, x]:
+ distances[y, x] = this_distance
+ predecessors[y][x] = 'U'
+ updated = True
+
+ nx = x
+ ny = (y + 1) % height
+ this_distance = distances[ny, nx]
+ if this_distance != -1:
+ if this_distance != FAKE_INFINITY:
+ this_distance += 1
+ if this_distance < distances[y, x]:
+ distances[y, x] = this_distance
+ predecessors[y][x] = 'D'
+ updated = True
+
+ nx = (x - 1) % width
+ ny = y
+ this_distance = distances[ny, nx]
+ if this_distance != -1:
+ if this_distance != FAKE_INFINITY:
+ this_distance += 1
+ if this_distance < distances[y, x]:
+ distances[y, x] = this_distance
+ predecessors[y][x] = 'L'
+ updated = True
+
+ nx = (x + 1) % width
+ ny = y
+ this_distance = distances[ny, nx]
+ if this_distance != -1:
+ if this_distance != FAKE_INFINITY:
+ this_distance += 1
+ if this_distance < distances[y, x]:
+ distances[y, x] = this_distance
+ predecessors[y][x] = 'R'
+ updated = True
+
+ if not updated:
+ break
+ i += 1
diff --git a/setup.py b/setup.py
new file mode 100644
index 0000000..77263a7
--- /dev/null
+++ b/setup.py
@@ -0,0 +1,8 @@
+from setuptools import find_packages, setup
+from Cython.Build import cythonize
+
+setup(
+ name='robots',
+ packages=find_packages(),
+ ext_modules = cythonize('robots/*.pyx')
+)