From 9aedbb911e1596f30229469a53e56cf5c1056c97 Mon Sep 17 00:00:00 2001
From: Peter Ward <peteraward@gmail.com>
Date: Thu, 2 Aug 2012 23:45:14 +1000
Subject: more sections

---
 docs/closest_apple.py | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)
 create mode 100644 docs/closest_apple.py

(limited to 'docs/closest_apple.py')

diff --git a/docs/closest_apple.py b/docs/closest_apple.py
new file mode 100644
index 0000000..8f8c560
--- /dev/null
+++ b/docs/closest_apple.py
@@ -0,0 +1,60 @@
+DIRECTIONS = {
+    'L': (-1, 0),
+    'U': (0, -1),
+    'R': (1, 0),
+    'D': (1, 0),
+}
+
+def closest_apple_bot(board, position):
+    x, y = position
+    height = len(board)
+    width = len(board[0])
+
+    # todo contains the squares we need to explore
+    todo = []
+    # done contains the squares we've already explored
+    done = set()
+
+    # for each initial direction
+    for direction in DIRECTIONS:
+        dx, dy = DIRECTIONS[direction]
+        # find the new position
+        nx = (x + dx) % width
+        ny = (y + dy) % height
+        # add to todo and done
+        todo.append((nx, ny, direction))
+        done.add((nx, ny))
+
+    while todo:
+        # take the first item in todo
+        x, y, direction = todo.pop(0)
+
+        cell = board[y][x]
+
+        # if we've reached an apple, we've found the shortest path
+        # and direction is the right way to go
+        if cell == '*':
+            return direction
+
+        # if we can't move into this cell, go to the next square to explore
+        if cell != '.':
+            continue
+
+        # at this square, we can go any direction,
+        # as long as it's not in our done set
+        for dx, dy in DIRECTIONS.values():
+            nx = (x + dx) % width
+            ny = (y + dy) % height
+
+            if (nx, ny) not in done:
+                # we haven't visited this square before,
+                # add it to our list of squares to visit
+                # note that the third item here is the direction we initially
+                # took to get to this square
+                todo.append((nx, ny, direction))
+                done.add((nx, ny))
+
+    # if we get here, there are no apples on the board,
+    # so we'll just move up.
+    return 'U'
+
-- 
cgit v1.2.3