Lars Yencken avatar Lars Yencken committed 9420122

Don't make conflicting future plans.

Comments (0)

Files changed (1)

 import heapq
 from functools import partial
 import random
+from collections import defaultdict
 
 from ants import Ants
 
         self.ants = ants
         self.game = game
         self.targets = {}
-        self.orders = {}
+        self.plans = defaultdict(set)
         self.needs_orders = set(ants.my_ants())
         self.frontier = self.build_frontier(self.game.unseen)
 
         # prevent stepping on own hill
-        for hill_loc in ants.my_hills():
-            self.orders[hill_loc] = None
+        self.plans[1].update(ants.my_hills())
 
     def do_move_direction(self, loc, direction):
         "Move in a given direction, handling conflicting orders."
         new_loc = self.ants.destination(loc, direction)
-        if (self.ants.unoccupied(new_loc) and new_loc not in self.orders):
+        if (self.ants.unoccupied(new_loc) and new_loc not in self.plans[1]):
             self.ants.issue_order((loc, direction))
-            self.orders[new_loc] = loc
+            assert new_loc not in self.plans[1]
+            self.plans[1].add(new_loc)
+            assert loc in self.needs_orders
             self.needs_orders.remove(loc)
             return True
         else:
             new_loc = p[0]
             d, = self.ants.direction(loc, new_loc)
             if self.do_move_direction(loc, d):
+                for i, l in enumerate(p):
+                    self.plans[i + 1].add(l)
                 self.targets[dest] = loc
                 return True
 
             l0 = p[-1]
             for direction in ('n', 's', 'e', 'w'):
                 l = self.ants.destination(l0, direction)
-                if l not in p and l not in self.orders and passable(l) \
+                if l not in p and l not in self.plans[len(p)] and passable(l) \
                         and (l not in unseen or l in frontier):
                     yield p + (l,)
 
 
             for p_next in expand(p):
                 l_next = p_next[-1]
-                if l_next not in visited:
+                step = len(p)
+                if l_next not in visited and l_next not in self.plans[step]:
                     visited.add(l_next)
                     push((f(p_next), p_next))
 
             if len(queue) > 100:
+                # randomly choose between the best options so far
+                push((cost, p))
+                p = random.choice([v for v in queue if v[0] ==
+                        cost])[1]
                 return p[1:]
 
     def find_food(self):
         distance = self.ants.distance
         for hill_loc in self.game.hills:
             for ant_loc in list(self.needs_orders):
-                if ant_loc not in self.orders.values():
-                    dist = distance(ant_loc, hill_loc)
-                    ant_dist.append((dist, ant_loc))
+                dist = distance(ant_loc, hill_loc)
+                ant_dist.append((dist, ant_loc))
         ant_dist.sort()
         for dist, ant_loc in ant_dist:
-            self.do_move_location(ant_loc, hill_loc)
+            if ant_loc in self.needs_orders:
+                self.do_move_location(ant_loc, hill_loc)
 
     def explore(self):
         # explore unseen areas
         distance = self.ants.distance
         for ant_loc in list(self.needs_orders):
+            if not self.have_time():
+                break
             unseen_dist = []
             for unseen_loc in self.frontier:
                 dist = distance(ant_loc, unseen_loc)
         self.game.print_map(self.frontier)
 
     def have_time(self):
-        return self.ants.time_remaining() > 300
+        return self.ants.time_remaining() > 200
 
     def random_walk(self):
         "Do a random walk with all remaining ants."
         turn.attack_hills()
         turn.explore()
         turn.random_walk()
-        print >> sys.stderr, ants.time_taken()
 
     def remember_seen(self, ants):
         visible = ants.visible
             print >> sys.stderr, l
 
 if __name__ == '__main__':
+    args = sys.argv[1:]
     # psyco will speed up python a little, but is not needed
     try:
         import psyco
         pass
     
     try:
-        Ants.run(MyBot())
+        if args:
+            Ants.run(MyBot(), open(args[0]))
+        else:
+            Ants.run(MyBot())
     except KeyboardInterrupt:
         print('ctrl-c, leaving ...')
 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.