Tuesday 26 May 2015

Learning Python (6) - Mars Rover

My next Kata was from a set of exercises that Amir Rajan describes, the mars rover. The idea is to model a planet as a grid, place a rover there, and send it instructions for moving about. The instructions are a limited set: forward, backwards, turn left, turn right. The planet is a sphere, so once the basics are working the grid needs to wrap around. And then, being Mars, it has rocks in the way. So sometimes the rover will stop and report where it has got to.

This is a nice problem for practising TDD. As I started it felt a lot like revising the skills I'd been developing already. This is a good thing: Katas are supposed to be about practising skills, and practise is really important for reenforcing learning. The tests flow naturally from unpicking the problem, and are a perfect fit to incrementally developing a function because the turns, moves and grid all offer at least two similar possibilities for each action.

Created on 24 May 2015

@author: Dan Chalmers 
import unittest
from mars_rover import Planet, Direction

class Test(unittest.TestCase):

    def setUp(self):
        self.grid = Planet(4)
        self.grid2 = Planet(4)
    def testPutRoverOnPlanet(self):
        self.assertEqual((1,1), self.grid.getLocation())
    def testMoveForwardNorth(self):
        (ok, position) = self.grid.move("f")
        self.assertEqual((True,(1,2)), (ok, position))

    def testTurnRightMoveForwardEast(self):
        (ok, position) = self.grid.move("rf")
        self.assertEqual((True,(2,1)), (ok, position))
    def testTurnR2MoveForwardSouth(self):
        (ok, position) = self.grid.move("rrf")
        self.assertEqual((True,(1,0)), (ok, position))

    #4 right turns wrap round to north again
    def testTurnR4MoveForwardSouth(self):
        (ok, position) = self.grid.move("rrrrf")
        self.assertEqual((True,(1,2)), (ok, position))
    def testMoveBackwardSouth(self):
        (ok, position) = self.grid.move("b")
        self.assertEqual((True,(1,0)), (ok, position))
    def testTurnLeftMoveForwardEast(self):
        (ok, position) = self.grid.move("lf")
        self.assertEqual((True,(0,1)), (ok, position))

    def testTurnLeftMoveBackwardWest(self):
        (ok, position) = self.grid.move("lb")
        self.assertEqual((True,(2,1)), (ok, position))
    def testWorldWrapsEast(self):
        (ok, position) = self.grid.move("rfff")
        self.assertEqual((True,(0,1)), (ok, position))

    def testWorldWrapsWest(self):
        (ok, position) = self.grid.move("lfff")
        self.assertEqual((True,(2,1)), (ok, position))

    #Poles wraps across the pole, not a jump to opposite end of the world!
    #Wrap over poles have an extra move after wrap to test direction swap
    def testWorldWrapsNorth(self):
        (ok, position) = self.grid.move("ffff")
        self.assertEqual((True,(3,2)), (ok, position))

    def testWorldWrapsSouth(self):
        (ok, position) = self.grid.move("rflbbb")
        self.assertEqual((True,(0,1)), (ok, position))
    def testBlockedByObstacle(self):
        (ok, position) = self.grid2.move("ff")
        self.assertEqual((False,(1,2)), (ok, position))

    #Written when debugging the not blocked, passed immediately
    def testWiggle(self):
        (ok, position) = self.grid.move("frflf")
        self.assertEqual((True,(2,3)), (ok, position))
    def testNotBlockedByObstacle(self):
        (ok, position) = self.grid2.move("frflf")
        self.assertEqual((True,(2,3)), (ok, position))

if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']

The code, similarly, flowed easily from the tests. Much of my earlier looking things up and use of explicit loops was being bypassed. I also found that this Kata led to a simple solution, that was fertile ground for refactoring. The similarity of the left / right, forward / backward, 2 poles, wrap around etc pairings naturally pushed me into eliminating duplication and separating little behaviours out. I was pleased that my tests described the behaviours in the spec, even as my code refactored into something much more subdivided.
Mars Rover Kata
Based on Kata defined at http://amirrajan.net/Blog/code-katas-mars-rover/
Created on 24 May 2015
@author: Dan Chalmers 

class Planet( object ):
  def __init__(self, size):
    self.size = size
    self.obstacles =  [[False for _ in range(size)] for _ in range(size)]  #not the same as [[False]*3]*3]
  def landRover(self,x,y,direction):
    self.x = x
    self.y = y
    self.direction = direction
  def getLocation(self):
    return (self.x, self.y)
  def move(self, instructions):
    for i in instructions:
      ok = self._moveStep_(i)
      if not ok: break # Hit an obstacle, so stop
    return (ok,self.getLocation())
  def _moveStep_(self, instruction):
    ok = True
    (dx,dy) = Direction.getMove(self.direction)
    if instruction == 'f': ok = self._moveForward_(dx,dy)
    if instruction == 'b': ok = self._moveBackward_(dx,dy)
    if instruction == 'r': self.direction = Direction.turnRight(self.direction)
    if instruction == 'l': self.direction = Direction.turnLeft(self.direction)
    return ok
  def _testAndMove_(self,x,y):
    (x,y, direction) = self._checkCoordinatesWrap_(x,y)
    if self.obstacles[x][y]: return False
    self.x = x
    self.y = y
    self.direction = direction
    return True
  def _moveForward_(self,dx,dy):
    x = self.x + dx
    y = self.y + dy
    return self._testAndMove_(x,y)

  def _moveBackward_(self,dx,dy):
    x = self.x - dx
    y = self.y - dy
    return self._testAndMove_(x,y)
  def _checkCoordinatesWrap_(self,x,y):
    # Because y coordinate wrap may affect X, checkY has to go first
    (x,y,direction) = self._checkYCoordinateWrap_(x,y)  
    return (self._checkXCoordinateWrap_(x), y, direction)
  def _checkXCoordinateWrap_(self,c):
    return c % self.size
  def _checkYCoordinateWrap_(self, x, y):
    if y == self.size or y == -1: #Over a pole
      y = self._yOverPole_(y)
      x = (x + self.size/2)%self.size
      direction = Direction.swapDirection(self.direction)
      direction = self.direction
    return (x, y, direction)

  def _yOverPole_(self, y):
      if y == self.size: y = self.size-1
      elif y == -1: y = 0
      return y
  def setObstacle(self,x,y):
    self.obstacles[x][y] = True
#Enumeration of directions, with a number behind it allows simple changes    
class Direction:
  NORTH = 0
  EAST = 1
  SOUTH = 2
  WEST = 3
  def turnRight(direction):
    return (direction+1)%4

  def turnLeft(direction):
    return (direction-1)%4
  def swapDirection(direction):
    return (direction+2)%4

  #Get the delta a move forward makes given a direction the rover faces
  def getMove(direction):
    if direction == Direction.NORTH: return (0,1)
    if direction == Direction.EAST: return (1,0)
    if direction == Direction.SOUTH: return (0,-1)
    if direction == Direction.WEST: return (-1,0)

Although the focus was on practise, I did do some exploring, and found three things of note:
The first was the Direction class. Coming from a Java background this felt like an enum. However, in 2.7 Python doesn't have a built in enum. So the labels approach was the next best fit. In the end this facilitated the turn, get move delta, and swap direction methods.
The second was the use of @staticmethod.
The third was that
[[False for _ in range(3)] for _ in range(3)]
build subtly different things. When used to create the obstacles map this difference matters: setObstacle is broken for the first, as shown below.

>>> obstacles = [[False]*3]*3
>>> obstacles
[[False, False, False], [False, False, False], [False, False, False]]
>>> obstacles[1][2] = True
>>> obstacles
[[False, False, True], [False, False, True], [False, False, True]]

>>> obstacles2 = [[False for _ in range(3)] for _ in range(3)]
>>> obstacles2
[[False, False, False], [False, False, False], [False, False, False]]
>>> obstacles2[1][2] = True
>>> obstacles2
[[False, False, False], [False, False, True], [False, False, False]]

No comments:

Post a Comment