distance_relaxer returns a list of shortest moves in predecessors

GameState has an expected_position() method.

4 files changed, 77 insertions, 20 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
diff --git a/robots/game.py b/robots/game.py
index cb065ec..9b5c339 100644
--- a/robots/game.py
+++ b/robots/game.py
@@ -2,6 +2,8 @@ from collections import defaultdict, deque
 from contextlib import contextmanager
 from copy import deepcopy
 from random import random
+import time
+import traceback
 
 from robots.constants import Action, City, DIRECTIONS, Energy, ENERGY_BY_ACTION
 from robots.state import GameState
@@ -104,9 +106,10 @@ class Game:
                         'Got unexpected action %r' % (action,)
                     )
 
-            except Exception as e:
+            except Exception:
                 # TODO: log this exception
-                print(e)
+                traceback.print_exc()
+                time.sleep(1)
 
             else:
                 for bot, action in zip(my_robots, result):
@@ -128,15 +131,11 @@ class Game:
                     action = Action.NOTHING
 
             elif action != Action.NOTHING:
-                dx, dy = DIRECTIONS[action]
-                nx = (x + dx) % self.state.width
-                ny = (y + dy) % self.state.height
+                nx, ny = self.state.expected_position(x, y, action)
 
-                if self.state.cities[ny][nx] in City.traversable:
-                    x = nx
-                    y = ny
-                else:
+                if x == nx and y == ny:
                     action = Action.NOTHING
+                x, y = nx, ny
 
             energy -= ENERGY_BY_ACTION[action]
 
diff --git a/robots/state.py b/robots/state.py
index 5a1450d..8a47139 100644
--- a/robots/state.py
+++ b/robots/state.py
@@ -1,7 +1,7 @@
 from collections import defaultdict, Counter
 
-from robots.constants import City
-from robots.utils import ceil_div
+from robots.constants import City, DIRECTIONS
+from robots.utils import ceil_div#, immutable
 
 class GameState:
     """The state of a game at a point in time.
@@ -18,7 +18,8 @@ class GameState:
         self.robots_by_player = {}
 
     def __hash__(self):
-        return hash(self._authorative_state)
+        return id(self)
+#        return hash(immutable(self._authorative_state))
 
     def __eq__(self, other):
         if isinstance(other, GameState):
@@ -112,3 +113,20 @@ class GameState:
     def n_cities_to_win(self):
         """How many cities you need to pledge allegiance to you to win."""
         return ceil_div(self.n_allegiable_cities, self.n_alive_players)
+
+    def expected_position(self, x, y, action):
+        """
+        Return the expected position for a robot at (x, y) if it performs the
+        given action.
+        Of course, combat (and possibly other factors in the future) may
+        influence whether it actually ends up at the returned position.
+        """
+        dx, dy = DIRECTIONS[action]
+        nx = (x + dx) % self.width
+        ny = (y + dy) % self.height
+
+        if self.cities[ny][nx] in City.traversable:
+            x = nx
+            y = ny
+
+        return (x, y)
diff --git a/robots/utils.py b/robots/utils.py
index e269a02..5793a00 100644
--- a/robots/utils.py
+++ b/robots/utils.py
@@ -10,6 +10,19 @@ def ceil_div(a, b):
 def ilen(items):
     return sum(1 for _ in items)
 
+def immutable(value):
+    if isinstance(value, str):
+        return value
+    try:
+        return immutable(list(sorted(value.items())))
+    except AttributeError:
+        pass
+    try:
+        return tuple(immutable(v) for v in value)
+    except TypeError:
+        pass
+    return value
+
 def add_spawns(map_, n_spawns, city=None):
     available = []
     for x, y, cell in iter_board(map_):