Mars Rovers II: The Design

1. This validation can be made in isolation, map by map.
   

   That is, once we have each rover’s sequence of maps, each map’s validation does not depend on any other map. Each map has all the information necessary to verify those bounds. A map’s :x or :y being invalid is sufficient to reject that map.
   

2. I’ll assume that producing maps is cheap.
   

   So I’ll first produce all maps as if they were all valid and going to be used — and then verify if any one of them is, in isolation, invalid.
   

   If producing maps were found to be expensive for some reason, the validation could be done early, and the map-generating process interrupted until that was fixed.
   

   But not only this sort of calculation should be extremely cheap, mapping them all also has the advantage of possibly identifying many problems at once, so that we can also tell rover-input–producing folks about all these problems at once, so that they can fix them all at once, too. The alternative would be to send one problem, then they fix it, then they send it back, and then “oh, there’s another problem here”, and then they fix it, and...
   

3. Might as well validate the other variables.
   

   Now, we’re complicating our first solution to test for this because here, we assume, the rover-input–generating folks haven’t triple-checked their data before sending us. But if the rover may wander off-grid even when the data includes grid limits, what else may be wrong there? Maybe they sent us some bogus command (“Z”)? Or a nonexistent heading (“Q”)? We might as well validate those, too.
   

4. Might as well validate all maps.
   

   In theory, those extra checks (heading and command) could happen just in the first map, because if all our functions are good they won’t introduce errors in subsequent maps. But I’ll assume that this check is cheap enough, and therefore go ahead and test every single map: it could catch an error somewhere — of the program itself, for example, rather than from the received input data.
   

All right, but there’s still something we aren’t checking here.

Suppose we have seven rovers there. Rover #3 is about to move. What positions do we need?

• Rovers #1 and #2 have already moved, so they are at their respective final positions. We have to look at their last map.
  
• Rovers #4 to #7 haven’t moved yet, so they are at their respective initial positions. We have to look at their initial map.
  
• Rover #3 is about to move and may collide with any one of these rovers along the way. We have to look at all of its maps.
  

Let’s call “moving-rover” a rover that is about to start moving.

And let’s say that a moving-rover is collision-free if none of the final positions of the previous rovers and none of the initial positions of the following rovers are on its path.

If all moving rovers are collision-free, we have no rover collisions.

For Solution 2, a map’s validation does not depend on any other map. But here, to declare a moving-rover collision-free, we need all its maps, plus maps of all other rovers, some of which (the previous) must have had their paths calculated (for us to check their respective last maps). It’s a harder problem: the whole thing is entangled, and the lists of previous positions and following positions change for each rover.

One implication is that we cannot use map (the function): map only knows about the thing it’s currently looking at; it doesn’t know where it’s been or where it’s going.

An alternative is to deploy map-indexed, and use the index to reconstruct the left and right parts of the sequence. Something like this:

(let [x '[1 2 3 4 5 6 7]]
  (map-indexed (fn [i it]
                 (list (take i x) it (drop (inc i) x)))
               x))
=> ((()            1 (2 3 4 5 6 7))
    ((1)           2 (3 4 5 6 7))
    ((1 2)         3 (4 5 6 7))
    ((1 2 3)       4 (5 6 7))
    ((1 2 3 4)     5 (6 7))
    ((1 2 3 4 5)   6 (7))
    ((1 2 3 4 5 6) 7 ()))

so that an assert-no-collisions function would:

• for each number (rover) on the left triangle, check its last map;
  
• for each number (rover) on the right triangle, check its first map;
  
• for the middle number, check its whole path;
  

and then check if there’s an intersection.

Then we’d have something like this:

(defn ensure-no-collisions
  [coll]
  (let [partition  #(list (take % coll) %2 (drop (inc %) coll))
        partitions (map-indexed partition coll)]
    (doseq [[l n r] partitions]
      (assert-no-collisions l n r))
    coll))

So, yes, we could use map-indexed — but I thought this problem was begging for something else: zippers. And Clojure has those. So zipper it was.

Although they’re particularly useful for “non-destructively updating” a data structure, my idea here was to use them for running that assertion at each element. Why? Because, conveniently, the left and right lists are already given by the zipper. In the end, the solution size was about the same as the above.

Two other things crossed my mind.

First, could it be that the rover entries did not map one-to-one to individual rovers? After all, we could imagine a case where we have two rovers and six entries: each rover alternates rovering, and each rover’s next initial position and heading would match that of its last map. Interleaved rovering. Think about it: it would be implicit from the initial positions and paths. And it would complicate things, because we’d have to exclude these not-really-collisions, and subtract rovers.

But this removes the ambiguity:

Each rover has two lines of input.

Second, could it be that we always have only two rovers? The solutions could then be a bit simpler. For example, to verify collision, we’d only need to check whether the first rover’s final position is in the second rover’s path. No zipping or map-indexing or partitioning needed.

But the first sentence removes the ambiguity:

A squad of robotic rovers…

A “squad” could be, but not necessarily is, just “two”. In fact, it suggests a good half a dozen or more.

So n rovers it is — rovers that could run off-grid, or run into each other.