Programming question - Mars Rover Commands

From NoskeWiki
Jump to navigation Jump to search

About

This page is a child of: Programming questions and Python


I came across this question in a coding interview ~Oct 2023, and it was a fun one, made more interesting as a pair programming exercise with a focus on iterative testing. In this "test-first-and-iterate" approach you are only supposed to look at some of the requirements at a time and are not supposed to write any code unless you already have the test case for it. It's still a bit foreign to me, but I do understand the brilliance of this going slow method to make sure you think of good test cases and build up slowly. You can try the same - don't read too far ahead, and make test cases for the simplest thing first.

Programming banner mars bg 900w.jpg

I've summarized the problem I remember seeing into just the key points. In some places, it's slightly ambiguous, but I think that's part of the point!

PROBLEM: Mars Rover Commands

Develop the program that takes a list of commands for the Mars Rover and shows the result position and direction of the rover.

Requirements:

The input of the program is:

  • The rover's starting point (x, y) and the direction ("N", "S", "E" or "W") it is facing.
  • A list of commands to move and turn the rover: "f" to move forward, "l": to turn left (90 degrees), "r" to turn right (90 degrees), and "b" to move backward.

After the string of commands, the rover can report its new position and direction.

Extra requirements:

  1. Mars is full of obstacles mapped at certain x, y locations. If the rover is about to hit an obstacle it stops and reports its position and the obstacles position (the remaining commands are ignored).
  2. Mars is a planet (spherical), so the rover must wrap around its x and y coordinates at some logical point.


SOLUTION: In Python3

I was a little all over the place with my answer in the interview. I think I figured out the solution in my head, but it was hard to translate into one test case at a time. Probably I should have tested more scenarios like the rover rotating 360, but in my answer below I've added some extra use cases for that. I can't remember what exactly we typed in the interview - and honestly, I fell short of the extra requirements in time but here is a half-decent solution I programmed after the fact.

What is tricky is that you start off just thinking 2D grid, but then you get to the requirement reminding you that Mars is a sphere... so how realistic do you want to get? I think a geographic coordinate system make the most sense (think: lat, lng), meaning that as you approach the North or South pole, moving one "x distance" would get smaller. If you drive from location (20,89,'n') to the north pole location (20,90,'n') - then *technically* you are not facing any direction (longitude=NA, latitude = 90, direction=NA) - but if you drive forward ('f') once more then it makes sense that suddenly you are at (180,89,'s') on the opposing x-coordinate (longitude) that you just traveled on... and will flip the direction you are facing (now facing south).


Code file rover.py
:
# Direction structs:
DIRECTIONS = ['n', 'e', 's', 'w']  # Direction in clockwise order.
DIRECTION_MOVEMENTS = [
    [0,  1],  # n.
    [1,  0],  # e.
    [0, -1],  # s.
    [-1, 0]   # w.
]
DIRECTION_MAPPINGS = { 'n': 0, 'e': 1, 's': 2, 'w': 3 }

# Geographic coordinate limits:
X_MIN = -180  # Think 180 degrees west (latitude)
X_MAX = 180   # Think 180 degrees east (latitude)
Y_MIN = -90  # Think 90 degrees south (longitude)
Y_MAX = 90   # Think 90 degrees north (longitude)


class MarsMap:
  """Stores a map of known obstacles on mars."""
  def __init__(self, obstacles: list[tuple[int, int]] = []):
    self.obstacles = set(obstacles)  # Set of obstacles
  def add_obstacle(self, obstacle: tuple[int, int]):
    """We could add more obstacles if we bumped into them."""
    self.obstacles.add(obstacle)
  def is_obstacle_at_location(self, x: int, y: int) -> bool:
    return (x, y) in self.obstacles


class Rover:
  """A class for our rover, location and direction."""
  def __init__(self, x: int, y: int, direction: str, mars_map: MarsMap = None):
    self.x = x
    self.y = y
    self.direction_idx = DIRECTION_MAPPINGS[direction]
    # Mars stuff:
    self.mars = mars_map
    self.obstacle_hits = 0
    self.last_obstacle_hit_location = None

# Mutators:
  def move(self, command: str) -> bool:
    x = self.x
    y = self.y
    if command == 'f':
      x += DIRECTION_MOVEMENTS[self.direction_idx][0]
      y += DIRECTION_MOVEMENTS[self.direction_idx][1]
    elif command == 'b':
      x -= DIRECTION_MOVEMENTS[self.direction_idx][0]
      y -= DIRECTION_MOVEMENTS[self.direction_idx][1]
    else:
      raise ValueError(f'rotate("{command}") must be "f" or "b".')
    
    # If we just crossed over north or south pole:
    if y > Y_MAX:
      y = Y_MAX - (y - Y_MAX)  # 90 - (91 - 90) = -89
      x = x + 180
      self.direction_idx = (self.direction_idx + 2) % 4  # Flip direction.
    elif y < Y_MIN:
      y = Y_MIN - (y - Y_MIN)  # -90 - (-91 - -90) = -89
      x = x + 180
      self.direction_idx = (self.direction_idx + 2) % 4  # Flip direction.
    # If we just crossed over the -180/180 latitude line:
    if x > X_MAX:
      x = X_MIN + (x - X_MAX)  # 180 + (181 - 180) = -179
    elif x <= X_MIN:
      x = X_MAX - (x - X_MIN)  # 180 - (-181 - 180) = -89

    # Check obstacle collision at these coordinates:
    if self.mars and self.mars.is_obstacle_at_location(x, y):
      self.obstacle_hits += 1
      self.last_obstacle_hit_location = (x, y)
      print('WARNING: Hit obstacle trying to move from ' \
            f'({self.x}, {self.y}) to ({x}, {y})')
      return False

    self.x = x
    self.y = y
    return True

  def rotate(self, command: str) -> bool:
    if command == 'r':
      self.direction_idx = (self.direction_idx + 1) % 4
    elif command == 'l':
      self.direction_idx = (self.direction_idx - 1) % 4
    else:
      raise ValueError(f'rotate("{command}") must be "l" or "r".')
    return True

  def execute_commands(self, commands: list[str]) -> bool:
    """Execute a sequence of move and rotate commands.

    Exits early with false if we hit an obstacle on mars."""
    for i, command in enumerate(commands):
      if command in ['f', 'b']:
        if not self.move(command):
          return False  # Abandon the rest of the commands.
      elif command in ['l', 'r']:
        self.rotate(command)
    return True

  # Accessors:
  def get_location(self) -> (int, int):
    return (self.x, self.y)

  def get_direction(self) -> str:
    return DIRECTIONS[self.direction_idx]

  def __str__(self) -> str:
    direction = self.get_direction()
    return f'({self.x}, {self.y}) {direction}'

# Main for live testing:
if __name__ == '__main__':
  mars = MarsMap([(-2,2), (-1,2), (0,2), (1,2), (2,2)])  # Long wall.
  rover = Rover(0, 0, 'n', mars)
  success = rover.execute_commands([
    'f', 'f',  # We just hit an obstacle, so we've stopped here.
    'f', 'r', 'f', 'f', 'l'  # Everything else is irrelevant.
    ])
  print(rover)


Code file rover_test.py
: lots of testing
import pytest
from rover import Rover, MarsMap

# No commands:
def test_rover_no_commands():
  rover = Rover(0, 0, 'n')
  assert rover.get_location() == (0, 0)
  assert rover.get_direction() == 'n'

# Simple forwards/back:
def test_rover_drive_one_forwards():
  rover = Rover(0, 0, 'n')
  rover.move('f')
  assert rover.get_location() == (0, 1)
  assert rover.get_direction() == 'n'
def test_rover_drive_two_back():
  rover = Rover(0, 0, 'e')
  rover.move('b')
  rover.move('b')
  assert rover.get_location() == (-2, 0)
  assert rover.get_direction() == 'e'

# Simple left/right rotations:
def test_rover_rotate_right_once():
  rover = Rover(1, 1, 'e')
  rover.rotate('r')
  assert rover.get_location() == (1, 1)
  assert rover.get_direction() == 's'
def test_rover_rotate_left_twice():
  rover = Rover(1, 1, 'e')
  rover.rotate('l')
  rover.rotate('l')
  assert rover.get_location() == (1, 1)
  assert rover.get_direction() == 'w'
def test_rover_rotate_360():
  rover = Rover(1, 1, 'e')
  rover.rotate('l')
  rover.rotate('l')
  rover.rotate('l')
  rover.rotate('l')
  assert rover.get_location() == (1, 1)
  assert rover.get_direction() == 'e'

# Batch commands:
def test_rover_medium_winding_path():
  rover = Rover(0, 0, 's')
  rover.execute_commands(['f', 'f', 'l',      # (0, -2) e
                          'f', 'f', 'l',      # (2, -2) n
                          'b', 'b', 'b', 'r'  # (0, -5) e
                          ])
  assert rover.get_location() == (2, -5)
  assert rover.get_direction() == 'e'

# Drive over 180 latitude line:
def test_rover_drive_east_over_max_lat():
  rover = Rover(179, 0, 'e')
  rover.execute_commands(['f', 'f', 'f'])   # (182, 0) e
  assert rover.get_location() == (-178, 0)
  assert rover.get_direction() == 'e'

def test_rover_drive_west_over_max_lat():
  rover = Rover(-175, 5, 'w')
  rover.execute_commands(['f'] * 10)   # (182, 0) e
  assert rover.get_location() == (175, 5)
  assert rover.get_direction() == 'w'

# Drive over the north or south pole:
def test_rover_drive_north_onto_north_pole():
  rover = Rover(40, 89, 'n')
  assert rover.move('f') == True
  assert rover.get_location() == (40, 90)
  assert rover.get_direction() == 'n'  # Although technically, NA at this coordinate.

def test_rover_drive_backwards_onto_south_pole():
  rover = Rover(40, -80, 'n')
  rover.execute_commands(['b'] * 10)
  assert rover.get_location() == (40, -90)
  assert rover.get_direction() == 'n'  # Although technically, NA at this coordinate.

def test_rover_rotate_left_and_zero_move_east_at_north_pole():
  # NOTE: In the current set, if we are facing "east" or "west" at the north pole
  # each move will be zero distance, but move us onto a different N/S latitude
  # "track" in case we wanted to rotate north/south and move onto it.
  rover = Rover(40, 90, 'n')
  rover.rotate('r')
  rover.move('f')  # This move is actually zero distance travelled.
  assert rover.get_location() == (41, 90)
  assert rover.get_direction() == 'e'  # Although technically, NA at this coordinate.
  # TODO(noske): Another solution might be to stay 'n'
  # but increment 90 degrees left or right in x.

def test_rover_drive_north_over_north_pole():
  rover = Rover(40, 89, 'n')
  assert rover.move('f') == True
  assert rover.move('f') == True
  assert rover.move('f') == True
  assert rover.get_location() == (-140, 88)
  assert rover.get_direction() == 's'

def test_rover_drive_south_over_south_pole():
  rover = Rover(-140, -80, 's')
  rover.execute_commands(['f'] * 15)  # Move forwards 15 "squares".
  assert rover.get_location() == (40, -85)
  assert rover.get_direction() == 'n'

def test_rover_drive_backwards_over_south_pole():
  rover = Rover(45, -89, 'n')
  rover.execute_commands(['b', 'b', 'l',  # (-135, -89) e
                          'f', 'f', 'f', 'f', 'f', 'l',  # (-130, -89) n
                          'f', 'f', 'l', 'r'   # (-130, -87) n
                          ])
  assert rover.get_location() == (-130, -87)
  assert rover.get_direction() == 'n'

# ... and also I should have had a test for traveling around the whole planet
#     east, west, north and south using [f] * 360 to check that we end up
#     in the same coordinates, facing the same direction still.

# Test mars obstacles system:
def test_mars_map_empty_map():
  mars = MarsMap([])
  assert len(mars.obstacles) == 0
  assert mars.is_obstacle_at_location(0,0) == False

def test_mars_several_obstacles():
  mars = MarsMap([(1,1), (1,2), (1,3), (5,5), (-10,-10)])
  assert len(mars.obstacles) == 5
  assert mars.is_obstacle_at_location(0,0) == False
  assert mars.is_obstacle_at_location(1,1) == True
  assert mars.is_obstacle_at_location(-10,-10) == True

def test_mars_add_obstacles():
  mars = MarsMap()
  mars.add_obstacle((2,2))
  assert len(mars.obstacles) == 1
  assert mars.is_obstacle_at_location(2,2) == True

# Test rover avoiding obstacles:
def test_rover_avoiding_obstacles():
  mars = MarsMap([(1,1), (1,2), (1,3), (5,5), (-10,-10)])
  rover = Rover(0, 0, 'n', mars)
  success = rover.execute_commands(
    ['f', 'f', 'l',  # (0, 2) w
     'f', 'f', 'f', 'f', 'f'  # (0, 2) w
     ])
  assert success == True
  assert rover.get_location() == (-5, 2)
  assert rover.get_direction() == 'w'
  assert rover.obstacle_hits == 0
  assert rover.last_obstacle_hit_location == None

def test_mars_hit_only_obstacles_on_second_move():
  mars = MarsMap()
  mars.add_obstacle((2, 0))
  rover = Rover(0, 0, 'e', mars)
  assert rover.move('f') == True
  assert rover.move('f') == False  # Hit.
  assert rover.move('f') == False  # Another hit.
  assert rover.obstacle_hits == 2
  assert rover.last_obstacle_hit_location == (2, 0)
  assert rover.get_location() == (1, 0)  # Didn't make it to 0,2.
  # Let's go around it now:
  rover.rotate('l')
  assert rover.move('f') == True
  rover.rotate('r')
  assert rover.move('f') == True
  assert rover.move('f') == True
  rover.rotate('r')
  assert rover.move('f') == True
  rover.rotate('l')
  assert rover.get_location() == (3, 0)  # Went around it.
  assert rover.get_direction() == 'e'

def test_mars_several_obstacles_and_hit_one_in_batch_commands():
  mars = MarsMap([(-2,2), (-1,2), (0,2), (1,2), (2,2)])  # Long wall.
  rover = Rover(0, 0, 'n', mars)
  success = rover.execute_commands([
    'f', 'f',  # We just hit an obstacle, so we've stopped here.
    'f', 'r', 'f', 'f', 'l'  # Everything else is irrelevant.
    ])
  assert success == False
  assert rover.obstacle_hits == 1
  assert rover.last_obstacle_hit_location == (0, 2)
  assert rover.get_location() == (0, 1)  # Didn't make it to 0,2.
  assert rover.get_direction() == 'n'

Afterthoughts

As you can see, when you add in all the relevant testing, what seems like a pretty small problem... well it's lots of testing code! Even now there might be useful scenarios I might have missed. I think something I've learned from these pair programming interviews. In strict pair programming I'm guessing 50/50 contribution and talking is idea, but because it's an interview where the other person typed, I felt like I had to do more talking, but probably not 100. I don't know a good ratio - but I probably should have explained certain parts better. Another way to solve this would be a large string of if statement in the form:

if "r":
  if direction == "N":
    direction = "E"
  if direction == "E":
    direction = "S"
  if direction == "S":
    direction = "W"
  if direction == "W"
     direction = "N"
elif "r":
  if direction == "N":
    direction = "W"
  if direction == "W":
    direction = "S"
  if direction == "S":
    direction = "E"
  if direction == "E"
     direction = "N"

But that just seems like a lot of code lines (and would be similar for the move function). With the array approach, you could also add "NE" later. It's these types of decisions I wish I'd spoken out loud, but hey - I still got most of the optimal solution - but just fell short of having time to code tests and rules for wrapping around the x and y coordinates. When you hear x and y it's easy to think of the coordinates as squares, but in reality, they are points... still: when you hit an obstacle at x,y are you at x,y or the previous point.... in reality, obstacles wouldn't be perfect squares, so you'd have to state your assumptions about obstacles in your sparse grid. Obviously a more realistic scenario the obstacles would be 2D or even 3D geometries/landscapes and mapped via and modified quadtree for indexing. Mars is a huge planet! How realistic do you want to go is the question! :)

I didn't get to this in the interview, but we typically think of forwards as walking straight. If you face east at the equator, you'll stay at the same longitude, but if you want to stay at the same longitude anywhere else you have to keep adjusting your direction to face east. If you are 10 meters from the south pole, walking east means you are walking in a circle (to stay 10 meters from the south pole)... so our definitions of "f" and "b" should have been spelled out. If we defined "f" as not adjusting to stay "E" or "W" as we walked then we'd have to return a floating point for our coordinates and apply some trigonometry.


See Also