## Roomba

### January 19, 2018

A robot can move any number of steps in the four cardinal directions. Given the robot’s initial position and a string of moves given as, for instance, N3E5S2W6 (any of the four cardinal directions, followed by any number of steps, as many commands as desired), determine the ending position of the robot.

Your task is to write a program to determine the ending position of a robot, given a starting position and a string of move commands. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Roomba”

1. This is where regex’s become useful…

```( \$x, \$y, \$_ ) = @ARGV;
while( s{([NESW])(\d+)}{} ) {
\$x+=\$2*( 'E' eq \$1 ? 1 : 'W' eq \$1 ? -1 : 0 );
\$y+=\$2*( 'N' eq \$1 ? 1 : 'S' eq \$1 ? -1 : 0 );
}
print "\$x \$y\n";
```
```> perl solution.pl 17 -3 W4S19W33N17E37N2
17 -3
> perl solution.pl 0 0 N3E5S2W6
-1 1
```
2. Zack said

Here is my take on this problem, using Julia and mapping everything on the Complex number plane:

global CP = [‘N’, ‘S’, ‘E’, ‘W’]

function Cardinal2Numeric(x::AbstractString)
x = uppercase(x)
d = x

``````if d in CP
z = parse(Int64, x[2:end])

if d == 'N'
return Complex(0, z)
elseif d == 'S'
return Complex(0, -z)
elseif d == 'E'
return Complex(z, 0)
else
return Complex(-z, 0)
end
else
println("Invalid cardinal notation!")
return NaN
end
``````

end

function Numeric2Cardinal(x::Complex)
y = “”
a = imag(x)
b = real(x)

``````if a != 0
if a > 0
y = string(y, CP, a)
else
y = string(y, CP, -a)
end
end

if b != 0
if b > 0
y = string(y, CP, b)
else
y = string(y, CP, -b)
end
end

if length(y) > 0
return y
else
return "Starting Position"
end
``````

end

function main(x::AbstractString)
x = uppercase(x)
z = Complex(0, 0)
c = 1
n = length(x)

``````while c < n
m1 = m2 = typemax(Int64)

for i = 1:4
ind = search(x, CP[i], c)
if (ind > 0) & (ind < m1); m1 = ind; end
end

for i = 1:4
ind = search(x, CP[i], m1 + 1)
if (ind > 0) & (ind < m2); m2 = ind; end
end

if m2 > n
m2 = n
else
m2 -= 1
end

c = m2
z += Cardinal2Numeric(x[m1:m2])
end

return Numeric2Cardinal(z)
``````

end

It could be done in a more simpler way, but I’ve never worked with Complex numbers in Julia and I’m always up for a challenge!

3. ```
(defun split-vector-on-indicator (vector indicator)
"
RETURN: a list of subvector of vector, the vector is splited between
elemtns a and b for which (indicator a b).
"
(loop
:with result := '()
:with start := 0
:for i :from 0 :below (1- (length vector))
:do (when (funcall indicator (aref vector i) (aref vector (1+ i)))
(push (subseq vector start (1+ i)) result)
(setf start (1+ i)))
:finally (return (nreverse (cons (subseq vector start) result)))))

(defun xor (a b)
"Return A ⊻ B"
(or (and a (not b)) (and (not a) b)))

;; with vectors:

(defun roomba (initial-position path)
(loop
:with position := (make-array 2 :initial-contents initial-position)
:for (direction steps)
:on (split-vector-on-indicator path (lambda (a b)
(xor (digit-char-p a)
(digit-char-p b))))
:by (function cddr)
:for distance := (parse-integer steps)
:do (map-into position
(lambda (x dx) (+ x (* dx distance)))
position
(ecase (intern direction)
(n #(0 +1))
(s #(0 -1))
(e #(+1 0))
(w #(-1 0))))
:finally (return position)))

(assert (equalp (roomba #(0 0) "N3E5S2W6") #(-1 1)))
(assert (equalp (roomba #(0 0) "N10E10S10W10") #(0 0)))

;; with complexes:

(defun roomba/c (initial-position path)
(loop
:for position := initial-position
:then (+ position (* distance
(ecase (intern direction)
(n #c(0 +1))
(s #c(0 -1))
(e #c(+1 0))
(w #c(-1 0)))))    :for (direction steps)
:on (split-vector-on-indicator path (lambda (a b)
(xor (digit-char-p a)
(digit-char-p b))))
:by (function cddr)
:for distance := (parse-integer steps)
:finally (return position)))

(assert (= (roomba/c #C(0 0) "N3E5S2W6")     #C(-1 1)))
(assert (= (roomba/c #C(0 0) "N10E10S10W10") #C(0 0)))

```
4. Paul said

In Python.

```import re
prog = re.compile(r"([E|W|N|S]\d+)")
D = {"E": (1, 0), "W": (-1, 0), "N": (0, 1), "S": (0, -1)}

def move_robot(posEW, posNS, move_string):
pos = (posEW, posNS)
for move in prog.findall(move_string):
direc, steps = D[move], int(move[1:])
pos = (pos + steps * direc, pos + steps * direc)
return pos

for mstr in  ("N3E5S2W6", "W4S19W33N17E37N2"):
print(move_robot(0, 0, mstr))
```
5. Daniel said

Here’s a solution in C.

```/* roomba.c */

#include <stdio.h>
#include <stdlib.h>

void move(char* moves, long* x, long* y) {
while (1) {
char move = moves;
if (move == '\0') break;
long distance = strtol(moves + 1, &moves, 10);
switch(move) {
case 'N':
*y += distance;
break;
case 'E':
*x += distance;
break;
case 'S':
*y -= distance;
break;
case 'W':
*x -= distance;
break;
}
}
}

int main(void) {
long x;
long y;
char* moves;

moves = "N3E5S2W6";
x = 0;
y = 0;
move(moves, &x, &y);
printf("%ld,%ld\n", x, y);

moves = "W4S19W33N17E37N2";
x = 17;
y = -3;
move(moves, &x, &y);
printf("%ld,%ld\n", x, y);

return 0;
}
```

Output:

```-1,1
17,-3
```
6. Globules said

Here’s a Haskell version. It uses the attoparsec library for parsing a sequence of moves and the linear library for the two-dimensional vectors that represent those moves. Upon parsing, a direction is replaced by a unit vector in the appropriate direction, multiplied by the number of steps. The vectors are then added to form a single vector representing the sequence of moves. That result is added to a starting location to give a final location.

```-- Given a starting location and a sequence of moves, show the final location of
-- a robotic vacuum cleaner.
--
-- Moves and directions are represented by two-dimensional vectors, where the
-- first component is the east/west axis and the second is the north/south axis.
-- North and east are positive numbers; south and west are negative.

import Control.Applicative ((<|>))
import Data.Attoparsec.ByteString.Char8
import Data.ByteString.Char8 hiding (elem, putStrLn)
import Linear (V2(V2), (^*), sumV)

type Direction = V2 Integer
type Move      = V2 Integer

direction :: Parser Direction
direction = dir 'N' (V2   0    1)  <|>
dir 'S' (V2   0  (-1)) <|>
dir 'E' (V2   1    0)  <|>
dir 'W' (V2 (-1)   0)  <|>
mempty
where dir c d = char c >> return d

move :: Parser Move
move = (^*) <\$> direction <*> decimal

collapse :: ByteString -> Maybe [Move]
collapse = either (const Nothing) Just <\$> parseOnly (many' move <* endOfInput)

roomba :: Move -> ByteString -> Maybe Move
roomba start = fmap ((start +) . sumV) . collapse

printMove :: Maybe Move -> IO ()
printMove = maybe (putStrLn "Invalid move.") print

main :: IO ()
main = do
printMove \$ roomba (V2  0   0 ) "N3E5S2X4W6" -- invalid: has a direction 'X'
printMove \$ roomba (V2  0   0 ) "N3E5S2W6"
printMove \$ roomba (V2 17 (-3)) "W4S19W33N17E37N2"
```
```\$ ./roomba
Invalid move.
V2 (-1) 1
V2 17 (-3)
```