Mars Rover problem in J

Question

I've written an implementation of the "famous" Mars Rover simulation, (another question on this) whose problem statement is this:

The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.

The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover's position, and the second line is a series of instructions telling the rover how to explore the plateau.

The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover's orientation.

Each rover will be finished sequentially, which means that the second rover won't start to move until the first one has finished moving.

Output:

The output for each rover should be its final co-ordinates and heading.

Test Input:

5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM

Expected Output:

1 3 N
5 1 E

This is my working solution:

dirs =: 'NESW'

input =. _4]\ 2 }. '' cut (' ',LF) charsub fread '~/Desktop/marsrover.txt'

NB. State transitions are the directions rotated forward and backwards
st =. 0,."1~ (] ,. 1 |. ] ,.  _2 |. ]) i. # dirs

NB. R = 1, L = 2, anything else = 0
a =. ('R'=a.) + (2 * 'L'=a.)

NB. Run the state machine against the input, initial facing on left
facing =: dirs {~ 4 {"1 ] ;:~ 5 ; st; a; 0 _1 , _1 ,~ dirs i. [

NB. Detect motion in each direction
moves =: ] #~ 1 - 'M' i. [

simulate =: monad define "1
  'x0 y0 dir commands' =. y
  pos =. ". x0, ' ', y0
  f =. dir facing commands
  dest =. pos + (+/ (dirs i. commands moves f) { 4 2 $ 0 1   1 0   0 _1   _1 0)
  (": dest), ' ', {: f
)

echo simulate input
exit ''

My plan for this program was basically this:

1. Run a state machine with the current facing against the input to figure out what the facing is at the moment of each command. This is what facing calculates.
2. Get the facing corresponding to each M command
3. Take the sum of "move" vectors to get the total change in coordinates. N = 0 1, so three moves with facing N will be the sum of 0 1 + 0 1 + 0 1 = 0 3.
4. The solution is the sum of the total change in coordinates with the initial coordinate, plus the final facing state.

What I'd like review for, is to find out if this code is idiomatic J, if there are more direct ways to do what I'm trying to do here, and especially in the simulate verb, if there are better ways to handle taking apart the input and passing it through the other verbs. I am happy that I figured out how to use sequential machine, but overall this solution feels a bit gassy to me. But I haven't found another implementation to compare to.

Answer 1

I applaud any use sequential machine. A primitive that simulates a state machine... fruit only the tree of J could produce... why resist?

So while in that way ;: is quintessential J, state machines are, on the other hand, procedural in mindset. Idiomatic J, by contrast, tends to frame the problem as a whole -- to solve in a single leap, rather than step by step.

How can we do that in this case?

The big trick is to encode the directions as complex numbers. An L just multiplies the current direction by i, or 0j1 in J. And an R multiplies by 0j_1. Then your direction at any point in time is just the scan product */\ of your starting position and the sequence of encoded L and R. For this step, M is encoded as 1, since it doesn't alter the direction.

Making the above concrete, let's see how the first example looks. The encoded commands (top) and their scan product (bottom):

┌───┬───┬──┬────┬────┬───┬─┬───┬───┬───┐
│0j1│0j1│1 │0j1 │1   │0j1│1│0j1│1  │1  │
├───┼───┼──┼────┼────┼───┼─┼───┼───┼───┤
│0j1│_1 │_1│0j_1│0j_1│1  │1│0j1│0j1│0j1│
└───┴───┴──┴────┴────┴───┴─┴───┴───┴───┘

We end facing N, as desired.

Similarly, thinking of adding complex numbers as vector addition, the final position is just the sum of the initial position and every direction vector corresponding to an M. The latter sum is just the sum of the element-wise product of the bottom row above, and the boolean mask of Ms:

┌───┬──┬──┬────┬────┬─┬─┬───┬───┬───┐
│0j1│_1│_1│0j_1│0j_1│1│1│0j1│0j1│0j1│
├───┼──┼──┼────┼────┼─┼─┼───┼───┼───┤
│0  │0 │1 │0   │1   │0│1│0  │1  │1  │
└───┴──┴──┴────┴────┴─┴─┴───┴───┴───┘

Using your code for argument parsing, and putting this all together, we get:

NB. convert direction to complex number

j =: 0j1 ^ 'ENWS' i. ]                            

NB. full solution

final =. 3 : 0
  'a b dir cmds' =. y
  dirs=. */\ (j dir) , 0j1 ^ 'ML.R' i. cmds       NB. all directions
  pos =. (a j.&". b) + +/ dirs * 0 , 'M' = cmds   NB. all positions
  (+. pos) ; j inv {: dirs
)

and running it:

f=. 0 : 0
5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM
)

input =.  _4]\ 2 }. '' cut (' ',LF) charsub f

echo input
echo final"1 input

produces:

┌─┬─┬─┬──────────┐
│1│2│N│LMLMLMLMM │
├─┼─┼─┼──────────┤
│3│3│E│MMRMMRMRRM│
└─┴─┴─┴──────────┘
┌───┬─┐
│1 3│N│
├───┼─┤
│5 1│E│
└───┴─┘

Try it online!