I’m looking for a new job these days. I have had a set of interviews so far. One time, I faced an interesting practical task. In this post, I want to discuss a way how I’ve solved it.

The original text took two pages of A4 because of lots of unuseful details. Let me retell the task by memory.

Imagine you have a surface of Mars divided by cells. A robot moves on it. The robot knows its position represented by (x, y) coordinates and orientation (North, East, South, West, or just N, E, S, W). You may pass a command to the robot. A possible command might be to turn left (L), to turn right (R) and to move forward (F). When the robot rotates, it just changes its orientation without moving across the cell. When it moves forward, it changes the coordinates but keeps the orientation.

A robot will be lost when goes out of the surface. But before it has been lost, it marks the last cell it stands as “dangerous”. When another robot steps on a dangerous cell, it cannot be lost. Instead, it ignores all the commands that lead to being lost.

So you have a surfacers dimensions and a bunch of robots. For each robot, you know its initial position, orientation and a list of commands. Write a program that moves the robots in series. For each robot, print its final position and orientation. Also, if the robot has been lost, add “LOST” to that line.

Input sample (don’t pay attention at the comments):

5 3             # world's width and height
1 1 E           # x, y and orientation of the first robot
RFRFRFRF        # and its list of commands

3 2 N           # the second robot pos and orientation
FRRFLLFFRRFLL   # and its list of commands

0 3 W           # the third one
LLFFFLFLFL      # ...
                # etc...

Expected output:

1 1 E
3 3 N LOST
2 3 S

I know what are you thinking about. Let’s have a class World and a class Robot. Than I’ll make an instance of class Game and will move the robots across the world. But this way seems a bit weird to me because we start with the entities but not the process.

All these entities do not say how to organize them. We have a common “Paper and Pen” problem. How should I connect my entities: Pen.writeOn(Paper) or Paper.writeWith(Pen)? Which OOP pattern says directly what are the best practices? SOLID, Composition or whatever? Should I store an array of robots inside a World instance or just keep a reference to the world in each robot? What if a robot has been lost? Should I null that reference?

See, we’ve got lots of questions, but none of them move us to the solution.

Moreover, once you have solved the task using classical OOP, it would be difficult to port you code to such FP languages as Clojure or Haskell, because they do not have classes, just types. Even a Javascript programmer may face some problems because JS has its own OOP system that differs from Python/Java.

So let me provide a simple solution that do not use classes and tend to be functional. I will do it using Python, not Clojure to make it clean to everyone.

One famous programmer said: when somebody asks me on an error in their code, I always respond the following. Imagine your program is a black box. What data does it receive? What data does it return? Once you know the answers, it becomes easy to find a mistake in logic.

I’d like to follow this way. Let’s abstract from the entities and OOP patterns. We read parameters from the input, process them and print on a screen. So here is a scheme:

read_params() --> play_game() --> print_results()

Note that reading and writing functions do IO, so they are not pure. Instead, play_game accepts plain data structures and has no side effects. That makes it easy to test in both REPL and unit tests.

When we have basic knowledge of the task, it’s time to write some code. The following skeleton shows my decision as well:


def parse_input(source):
    ...


def play(params):
    ...


def compose_results(results):
    ...


def main():
    params = parse_input(sys.stdin)
    results = play(params)
    print compose_results(results)


if __name__ == "__main__":
    main()

On the next step we need to clarify what data exactly we expect inside play function. There should be world’s limits for each dimension first. And we also need robots’ data.

def play(w, h, routes):

Because parsing input stream is boring, let’s just return a sample data from parse_input for now:


def parse_input(source):
    return (10, 20, (
        (0, 0, "N", "LLLL"),
    ))

Now let’s look closer to the play function. It’ a black box for now, but we could imagine what is behind it. I believe, it should build the world at first. Then, we iterate on robots to process them in series. That is an outer cycle.

For each robot, we evaluate a bunch of commands: rotate left/right or move. That’s an inner cycle.

For each robot, we collect its final state with a special flag that indicates whether a robot has been lost.

Looks simple, let’s code that logic:

def play(w, h, routes):
    world = make_world(w, h)
    results = ()

    for (x, y, ori, steps) in routes:
        robot = make_robot(x, y, ori)
        for step in steps:
            ok, world, robot = update(world, robot, step)
            if not ok:
                break
        results += ((ok, robot), )

    return results

Now we have some undefined functions that we must populate before launch the code. What we should know about the world? Only width, height and what cells are marked as dangerous. So let the world will be a tuple something like (20, 30, ((2, 3), (15, 34))).

The following function returns a new world ready to play:

def make_world(w, h):
    return w, h, ()

Next, what data represent a robot on every turn? Both x and y coordinates plus orientation. In Python, let it be just a tuple like (1, 5, "N") or (10, 5, "S") for example.

The function below is to create a new robot:

def make_robot(x, y, ori):
    return (x, y, ori)

Our update function takes the world, the robot and a command to evaluate. It returns a tuple of three values. The first one is a boolean flag that indicates whether the robot is still on the surface. You see, if we get False, that will mean the robot has gone away from the world and there is no reason to continue evaluation for that robot.

The second and the third values are the new world and robot. The thing is I return new values instead of changing the previous ones. Avoiding state gives us more freedom in data manipulation. I’ll cover more on that a bit later.

Moving on to the update function. First, we need to distinguish the command whether it is to rotate or to move a robot. The case of rotate is really easy to handle:

def update(world, robot, step):

    if step in "LR":
        return True, world, rotate_robot(robot, step)

    # to be continued

The code above clearly shows we can rotate a robot without any limits. Notice I return a new rotated robot instead of changing the one I have in my function. The rotate function is simple:

def rotate_robot(robot, step):
    x, y, ori = robot

    rules = {
        ("N", "L"): "W",
        ("N", "R"): "E",

        ("E", "L"): "N",
        ("E", "R"): "S",

        ("S", "L"): "E",
        ("S", "R"): "W",

        ("W", "L"): "S",
        ("W", "R"): "N",
    }

    new_ori = rules[(ori, step)]
    return x, y, new_ori

Important thing is having a dict of rules is much better then a bunch of nested ifs. It’s possible to add new rotate rules at any times as well.

The movement forward command is a little bit trickier because of complicated logic. First of all, we need to know whether the robots stands on a dangerous cell. Wee also need to check whether the next turn will move the robot out from the surface.

Remember, if it’s a dangerous cell at the moment, the bad movement is just ignored. If it isn’t, move the robot. And if it has lost, mark that cell as dangerous. I’ve finished with the following code:

    # continues the `update` function

    if step == "F":

        robot_next = move_robot(robot)
        placed_next = is_placed(world, robot_next)

        if is_scent(world, robot):
            if placed_next:
                return True, world, robot_next
            else:
                return True, world, robot

        else:
            if placed_next:
                return True, world, robot_next
            else:
                return False, set_scent(world, robot), robot

A tree of nested ifs looks ugly to me and may be reduced. But it’s not so important at the moment. The key feature of the code above is kept in a line:

robot_next = move_robot(robot)

Remember, I spoke about immutable data structures. Instead of moving the robot, we’ve got a new one that stands on the next cell. You see? Dealing with immutable data gives us opportunity to have objects in the future. When I have a future state of a robot, I can easy check whether its state fits to the requirements. And if it does not, just return an old copy of a robot.

Now imagine I had a mutable object with x and y fields. To check that robot, I would move it forward, e.g. change its state, than check the conditions and rollback the state if they failed. Should I say that way is weird and tends to a buggy code?

Here is a code for the missing functions. To move a robot:

def move_robot(robot):
    x, y, ori = robot

    rules = {
        "N": (0, 1),
        "W": (-1, 0),
        "S": (0, -1),
        "E": (1, 0),
    }

    dx, dy = rules[ori]

    return (
        x + dx,
        y + dy,
        ori,
    )

To check if a robot is on the surface:

def is_placed(world, robot):
    w, h, _ = world
    x, y, _ = robot

    return (
        0 <= x <= w
        and 0 <= y <= h
    )

And to check whether a robot stands on the dangerous cell:

def is_scent(world, robot):
    _, _, scents = world
    x, y, _ = robot

    return (x, y) in scents

So we’ve done with the solution. What wee are missing for now are parsing input data and formatting the game result functions. I’m not sure they are so important to place them here. Check the Git repo if you are interested.

Let’s check the data sample given in the task. Say we have sample.txt file with the input:

5 3
1 1 E
RFRFRFRF

3 2 N
FRRFLLFFRRFLL

0 3 W
LLFFFLFLFL

We perform:

cat sample.txt | python mars.py
1 1 E
3 3 N LOST
2 3 S

Just as the expected results provided in the task.

To sum up, I’ll list the key points that I’ve got from that task.

  1. Try to think on the program like a black box, that accepts some data and produces the result. Your mission is to uncover that black box.

  2. Use plain data structures like hash-tables, lists or tuples rather than classes and objects. Just because it keeps you from all that OOP complexity.

  3. Keep data immutable while it is possible rather then modify them.

  4. Don’t be afraid of implementing you logic with undefined functions. Or functions that return hard-coded result. You may correct them later.

  5. Separate functions that don’t have side effects from those that have. They become really easier to test.

Find the whole code on Github. And by the way, it’s my first post written in English. I hope you enjoyed that reading.

Thanks!

← Хром

С вами. Говорит. Робот. →