# Commits

committed d7dfef8

more sections

• Participants
• Parent commits 3edd13e
• Branches default

# File docs/closest_apple.py

+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'
+

# File docs/closest_apple.tex

+\section{Closest apple}
+
+One interesting bot we can write is one which always moves towards the closest
+apple. Both the idea and the coding are a little tricky, but see if you can
+handle it. In order to find the closest apple, we actually want to know
+the \emph{shortest path} to the apple, and when we know that, the first step in
+that path is the direction we need to move in.
+
+To find the shortest path, we need to use an algorithm called
+\emph{breadth first search} (BFS).
+% TODO: description of the algorithm
+
+\pythonfile{closest_apple.py}

+\section{Look ahead}
+
+By now you’re probably itching to try out some of your own ideas about how to
+make a good bot. Now’s a great time to take a break from following my detailed
+instructions and just play around with some ideas.
+Here’s an idea to get you started: our \texttt{random\_avoid\_bot} only looked
+one square ahead, try making a bot which looks two squares ahead and chooses the
+direction with the most free space.
+

# File docs/random_avoid.py

+from random import choice
+
+def random_avoid_bot(board, position):
+    x, y = position
+    height = len(board)
+    width = len(board[0])
+
+    valid_moves = []
+
+    left = board[y][(x - 1) % width]
+    if left == '.' or left == '*':
+        valid_moves.append('L')
+
+    right = board[y][(x + 1) % width]
+    if right == '.' or right == '*':
+        valid_moves.append('R')
+
+    up = board[(y - 1) % height][x]
+    if up == '.' or up == '*':
+        valid_moves.append('U')
+
+    down = board[(y + 1) % height][x]
+    if down == '.' or down == '*':
+        valid_moves.append('D')
+
+    return choice(valid_moves)

# File docs/random_avoid.tex

+%%- from "macros.tex" import make_board -%%
+
 \section{Random Avoid Bot}
 \fasttrack{Choose a direction at random, but not one which will lead to immediate death.}

 Well, the answer is that we need to look at each of the squares surrounding our
 snake’s head, to see if we’ll die if we move into them or not.

+Let’s have a look at the square to the right of our snake’s head.
+First, we need to know its coordinates: looking at
+Board~\ref{brd:right-square:normal},
+we see that if our snake is at position $(x, y)$,
+then the square on the right will be at position $(x + 1, y)$.
+
+But this isn’t the whole story: Board~\ref{brd:right-square:wrapping}
+shows that if the snake is on the rightmost column, the square on the right
+is going to wrap around to be on the leftmost column.
+
+\begin{board}
+\begin{subfigure}{.45\linewidth}
+    \begin{tabular}{l|l|l|l|l}
+      … & $x-1$ & $x$              & $x + 1$            & … \\\hline
+  $y-1$ &       &                  &                    &   \\\hline
+  $y$   &       & $\mathbf{(x,y)}$ & $\mathbf{(x+1,y)}$ &   \\\hline
+  $y+1$ &       &                  &                    &   \\\hline
+      … &       &                  &                    & … \\
+    \end{tabular}
+\caption{Coordinate of the square to the right (ignoring wrapping).}
+\label{brd:right-square:normal}
+\end{subfigure}
+\hfill
+%
+\begin{subfigure}{.45\linewidth}
+< make_board([
+    '.....',
+    '*...A',
+    '.....',
+]) >
+\caption{%
+    The board wraps around,
+    so the square to the right of our snake $(4, 1)$
+    is the apple $(0, 1)$.
+}
+\label{brd:right-square:wrapping}
+\end{subfigure}
+
+\caption{Finding the square to the right.}
+\label{brd:right-square}
+\end{board}
+
+Fortunately for us, there’s an easy way of ‘wrapping’ around in Python,
+which is the modulo operator (\%). The modulo operator returns the
+\emph{remainder} when you divide two numbers.
+\begin{minted}{pycon}
+>>> 3 % 8
+3
+>>> 7 % 8
+7
+>>> 8 % 8
+0
+>>> 9 % 8
+1
+>>> for i in range(20):
+...   print i % 8,
+...
+0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3
+\end{minted}
+
+\newcommand\mod{\,\%\,}
+
+% TODO: how do we get the width and height of the board?
+
+Looking back at Board~\ref{brd:right-square:wrapping}, we need to wrap the x
+coordinate back to $0$ when $x + 1 = width$,
+so we need $(x + 1) \mod width$.
+Taking this to a more general level, imagine we need to get the cell where
+the x coordinate is shifted by $dx$
+and the y coordinate is shifted by $dy$.
+For example, we might want to get the cell diagonally adjacent on the bottom
+left: it’s one square to the left, $dx = -1$ and one square down $dy = 1$.
+Don’t forget that moving right or down means adding
+and moving left or upwards means subtracting!
+Back to our general case, our new cell is going to be at the position
+$((x + dx) \mod width, (y + dy) \mod height)$.
+
+Don’t worry if you didn’t follow the general case there, you just need to
+remember that the cell to the right is at $((x + 1) \mod width, y)$.
+We then need to look \emph{in the board} at that position to see what’s in that
+cell.
+Remember that our board is a list of rows (stacked vertically),
+and each row is a list of cells (stacked horizontally).
+So we need to first find the right row, which we will do by using the y
+coordinate: \pyinline|board[y]|.
+Then we need to find the right cell in the row, using the x coordinate:
+\pyinline|board[y][(x + 1) % width]|.
+
+We’re almost at the end: all we need to do is build up a list of each cell we
+can move into. We know that we can move into cells which are
+empty (represented by a full stop)
+or have an apple (represented by an asterisk) in them,
+so we’ll test for that.
+Take a moment to write out the code we’ve managed to build so far, hopefully
+you’ll end up with something very close to what I’ve got below.
+Then you just need to add the other directions (left, up and down), and you’re
+done.
+
+\begin{pythoncode}
+from random import choice
+
+def bot(board, position):
+    x, y = position
+    height = len(board)
+    width = len(board[0])
+
+    valid_moves = []
+
+    right = board[y][(x + 1) % width]
+    if right == '.' or right == '*':
+        valid_moves.append('R')
+
+    return choice(valid_moves)
+\end{pythoncode}
+
+If you’re really stuck, or want to check your solution, here’s my solution:
+\pythonfile{random_avoid.py}
+

# File docs/tutorial.tex

 \DeclareCaptionSubType{board}

 \usepackage{minted}
+\usemintedstyle{tango}

 \newmint[pyinline]{python}{}
+\newminted{python}{}
 \newmintedfile{python}{}
-\usemintedstyle{tango}

 \setmainfont{Linux Libertine O}
+\setmonofont[AutoFakeBold]{Inconsolata}

 \setlength\parskip{2ex}
 \setlength\parindent{0mm}

 \input{introduction.tex}

-%\pagebreak
 \input{firstbot.tex}

 \input{random_simple.tex}

+% this section is rather long,
+% perhaps take an intermission to explain the board
+% and getting width, height
+% and modulo properly?
 \input{random_avoid.tex}

+\input{look_ahead.tex}
+
+\input{closest_apple.tex}
+
 \end{document}