Roomba

January 19, 2018

The hard part of this exercise is parsing the command string, as the arithmetic of calculating the position after each move is easy. Here’s our parser, which makes natural use of several functions from the Standard Prelude:

(define (get-command cs)
  (call-with-values
    (lambda () (split 1 cs))
    (lambda (dir rest)
      (call-with-values
        (lambda () (split-while char-numeric? rest))
        (lambda (digits rest)
          (values (car dir) (string->number (apply string digits)) rest))))))

We are assuming the command string is properly formed; various errors will result if it isn’t. Then we calculate the position after each move command:

(define (roomba x y str)
  (let loop ((x x) (y y) (cs (string->list str)))
    (if (null? cs) (values x y)
      (call-with-values
        (lambda () (get-command cs))
        (lambda (dir steps rest)
          (case dir
          ((#\N #\n) (loop x (+ y steps) rest))
          ((#\E #\e) (loop (+ x steps) y rest))
          ((#\S #\s) (loop x (- y steps) rest))
          ((#\W #\w) (loop (- x steps) y rest))))))))

And that’s it. Here are two examples:

> (roomba 0 0 "N3E5S2W6")
-1
1
> (roomba 17 -3 "W4S19W33N17E37N2")
17
-3

You can run the program at https://ideone.com/3P3WAL.

Advertisements

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[1]

    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[1], a)
        else
            y = string(y, CP[2], -a)
        end
    end
    
    if b != 0
        if b > 0
            y = string(y, CP[3], b)
        else
            y = string(y, CP[4], -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[0]], int(move[1:])
            pos = (pos[0] + steps * direc[0], pos[1] + steps * direc[1])
        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[0];
        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.
    
    {-# LANGUAGE OverloadedStrings #-}
    
    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: