How to reason about a live coding challenge

, ,

I recently had to solve the problem below during an interview. I thought I’d write down my thought process to resolve the problem, in hopes it might be useful or provide insights to other people.

The problem specification:

  • You have a lawnmower robot which needs to mow a rectangle lawn.
  • The robot can only move up, down, left or right, but it can be initially positioned anywhere on the lawn. The robot cannot move out of bounds.
  • The lawn contains some obstacles, and the robot cannot move over the obstacles, it has to go around.
  • Additionally, the robot should be able to identify if there are patches of grass walled off by obstacles.
  • And the robot knows nothing about the lawn initially.

My first thought is that the lawn is of a rectangular shape. That screams matrix (2 dimension array) to me. With obstacles placed in certain coordinates in the matrix. A graph seems too complex for this example, also graphs would have cycles to deal with. Stacks don’t make sense either. Nor would a tree. A simple 2-dimension array seems to be the simplest thing we can do. Then checking if a certain position is an obstacle is trivial, and so is checking if a certain position is out of bounds.

int width = 3;
int height = 3;
int[][] lawn = new int[width][height];
final int OBSTACLE_MARKER = 1;
boolean isObstacle(int x, int y) {
  return lawn[x][y] = OBSTACLE_MARKER;
}
boolean isWithinBounds(int x, int y) {
  return x >= 0 && x < width && y >= 0 && y < height;
}

I immediately noticed a couple of things:
* isObstacle and isWithinBounds are very tightly coupled to the lawn matrix. So it looks like we have a Lawn object.
* We are repeating x and y in many places, it seems we have another object in play here: Position. Let’s do that again.

record Position(int x, int y) {}

class Lawn {
  final int OBSTACLE_MARKER = 1;
  int[][] lawn;

  public Lawn(int width, int height, List<Position> obstacles) {
    if (width <= 0 || height <= 0) {
      throw new IllegalArgumentException("Invalid dimensions");
    }
    this.lawn = new int[width][height];
    this.width = width;
    this.height = height;

    for (Position obstacle : obstacles) {
      markObstacle(obstacle);
    }
  } 
  void markObstacle(Position position) {
    this.lawn[position.x()][position.y()] = OBSTACLE_MARKER;
  }
  boolean isWithinBounds(Position position) {
    return position.x() >= 0 && position.x() < width &&
           position.y() >= 0 && position.y() < height;
  }
  public boolean isObstacle(Position position) {
    return this.lawn[position.x()][position.y()] == OBSTACLE_MARKER;
  }
}

Ok, that’s a good start. But that was just the entrée. We still have to think about the Robot. How will the robot navigate that. We know how the lawn works, but the Robot does not.

Now let’s think about the Robot for a bit. We know the Robot knows nothing about the lawn other than that it’s a rectangle, and that it is placed somewhere in that rectangle. It also knows that there might be obstacles. And that it can only move up, down, left or right. Let’s encode some of that.

class Robot {
  List<Position> directions;
  public Robot() {
    Position up = new Position(0, -1);
    Position down = new Position(0, 1);
    Position left = new Position(-1, 0);
    Position right = new Position(1, 0);
    this.directions = List.of(up, down, left, right);
  }

  void mow(Lawn lawn, Position initialPosition) {
    // code goes here.
  }
}

So we are at the initial x and y coordinates/position, and the problem we have now is that we must go in all directions, up, down, left and right, in order to guarantee that we cover the entire lawn. It takes many minutes before I realize I’m looking at a recursion. Instinctively I realize it must go in all directions, not realizing initially that it’s supposed to go in all directions at once. Recursion allows for that.
It’s at a given position, it will call itself to all possible positions (up, down, left and right), and from those positions it will also call itself in all possible directions.
Whenever it finds the edge (out of bounds), or an obstacle, it stops, backtracks and goes in another direction.

That requires the Robot to keep some sort of State of progress, so that it can know which nodes were visited, which were obstacles, whenever it hit an edge.
It should probably also keep records of where the edges are, so that later it can infer if there are any positions hidden behind obstacles.

It’s kind of important that the Robot is separate from the lawn, so that we can reuse the Robot to mow multiple lawns. It’s also kind of important to separate the Robot from the State. The reason is that then the Robot can be given a state, and proceed from that. Meaning the Robot can pause and restart at any point. You could pause the work, serialize the state, then deserialize the state later and rebuild the Robot. Let’s have a look at the State, which will hold things like list of visited nodes, list of obstacles spotted, the edges of the lawn identified, and it should be able to compute whether it completed mowing the entire lawn, or if there are missing nodes hidden behind obstacles.

class State {
  final List<Position> validNodesVisited = new ArrayList<>();
  final List<Position> obstaclesSpotted = new ArrayList<>();

  int minX = Integer.MAX_VALUE;
  int maxX = Integer.MIN_VALUE;
  int minY = Integer.MAX_VALUE;
  int maxY = Integer.MIN_VALUE;

  public void addValidNode(Position position) {
    this.validNodesVisited.add(position);
  }
  public void addObstacle(Position position) {
    this.obstaclesSpotted.add(position);
  }
// getters and setters for min and max fields
  boolean isComplete() {
    int width = maxX - minX + 1;
    int height = maxY - minY + 1;
    int area = width * height;
    int visitedCount = validNodesVisited.size() + obstaclesSpotted.size();
    return area == visitedCount;
  }
  // spot nodes hidden behind obstacles
  List<Position> missedNodes() {
    List<Position> ret = new ArrayList<>();
    for (int i = minX; i <= maxX; i++) {
      for (int j = minY; j <= maxY; j++) {
        Position pos = new Position(i, j);
        if (!validNodesVisited.contains(pos) && !obstaclesSpotted.contains(pos)) {
          ret.add(pos);
        }
      }
    }
    return ret;
  }
  boolean wasVisited(Position position) {
    return validNodesVisited.contains(position);
  }
}

Ok, but what about the Robot? Now that we have our infrastructure, if you will, in place, we can implement the Robot. Let’s start by looking at how the Robot can recursively work to visit all possible positions.

class Robot {
  final List<Position> directions;
  public Robot() {
    Position up = new Position(0, -1);
    Position down = new Position(0, 1);
    Position left = new Position(-1, 0);
    Position right = new Position(1, 0);
    this.directions = List.of(up, down, left, right);
  }

  void mow(
    Lawn lawn, 
    Position initialPosition, 
    State initialState) {
    // Visit all possible positions, recursively
    mowFromPosition(lawn, initialPosition, initialState);

    // spot the missed nodes behind obstacles
    List<Position> missedNodes = initialState.missedNodes();
    // Place the robot at each one of them
    // and recursively visit all possible nodes from there
    for (Position missed : missedNodes) {
      mow(lawn, missed, initialState);
    }
  }

  void mowFromPosition(
    Lawn lawn, 
    Position position, 
    State state) {
    // If out of bounds, do nothing.
    if (lawn.isWithinBounds(position)) {
      state.setMinX(position.x());
      state.setMaxX(position.x());
      state.setMinY(position.y());
      state.setMaxY(position.y());
      if (lawn.isObstacle(position)) {
        state.addObstacle(position);
      } else if (!state.wasVisited(position)) {
        state.addValidNode(position);
        // Visit nodes in all possible directions
        for (Position direction : directions) {
          int newX = position.x() + direction.x();
          int newY = position.y() + direction.y();
          mowFromPosition(
            lawn, 
            new Position(newX, newY), 
            state
          );
        }
      }
    }
  }
}

Ok, but there was one last thing bugging me. What if there’s a wall of obstacles, either vertical or horizontal. This would impact the min or max X and Y values, leaving many nodes hidden behind this wall.

So far, I was only able to come up with one possible way of going after them, and it’s kind of a brute force attack. It pretty much tries to place the lawnmower Robot in every physically possible position, assuming the range of valid positions is within the bounds of an integer type. I know some of you might be thinking that a negative position makes no sense, but the Robot cannot be sure of that. There are no guarantees that the positions can only be positive.

// Find anything hidden by an obstacle wall to the left or up
for (int i = Integer.MIN_VALUE; i < initialState.minX(); i++) {
  for (int j = Integer.MIN_VALUE; i < initialState.minY(); j++) {
    mowFromPosition(
      lawn, 
      new Position(i, j), 
      initialState
    );
  }
}
// Find anything hidden by an obstacle wall to the right or down
int i = initialState.maxX() + 1;
while (true) {
  int j = initialState.maxY() + 1;
  while (true) {
    mowFromPosition(
      lawn, 
      new Position(i, j), 
      initialState
    );
    if (j == Integer.MAX_VALUE) {
      break;
    }
    j++;
  }
  if (i == Integer.MAX_VALUE) {
    break;
  }
  i++;
}

Anyway, that was an interesting puzzle. This might sound weird but I really enjoy working on these puzzles!

Leave a comment