If someone facing north at point A in this grid wanted directions to follow the green path (as they can only follow gridlines) to point B you might tell them:

Go North, North, West, East, East, South, East, East.

or equivalently

Go Forward, Forward, Left, Back, Forward, Right, Left, Forward.
(Where a command of Right, Left, or Back implicitly means turn in that direction, then go forward.)

A to B path

Write a function with one argument that translates between these absolute and relative directions along the same path, not just to the same point. Assume the directed person always starts facing north.

If the argument is a string of the letters NSEW, return the equivalent relative directions.
e.g. f("NNWEESEE") returns the string FFLBFRLF.

If the argument is a string of the letters FBLR, return the equivalent absolute directions.
e.g. f("FFLBFRLF") returns the string NNWEESEE.

The empty string yields itself. Assume no other input cases.

If your language does not have functions or strings use whatever seems most appropriate.

The shortest code in bytes wins.

  • \$\begingroup\$ Do we assume that a person always start with his head facing North ? That way, in relative terms to go towards East, it would require him to Turn Right, rather than simply saying Forward \$\endgroup\$
    – Optimizer
    Commented Sep 27, 2014 at 13:45
  • \$\begingroup\$ @Optimizer Yes, north. And yes to your other point. R equals E at the start. \$\endgroup\$ Commented Sep 27, 2014 at 13:49
  • 1
    \$\begingroup\$ Yay! You changed your picture to confirm what I always thought! \$\endgroup\$
    – Justin
    Commented Sep 27, 2014 at 17:35
  • 4
    \$\begingroup\$ Are you hooked on PPCG again? ;) \$\endgroup\$ Commented Sep 27, 2014 at 21:20
  • 4
    \$\begingroup\$ @MartinBüttner Either that or I'm very good at disguising my homework problems. ;) \$\endgroup\$ Commented Sep 28, 2014 at 5:23

8 Answers 8


CJam, 57 53 49


Previous version






How it works

  "NESW""FRBL"             " Push the two strings. ";
  _3$0=#W>                 " Check if the first character is in FRBL. ";
  :Q                       " Assign the result to Q. ";
  {\}*                     " Swap the two strings if true. ";
  :R;                      " Assign the top string to R and discard it. ";
  f#                       " Find each character of the input in the string. ";
  0\                       " Push a 0 under the top of the stack. ";
  {                        " For each item (index of character): ";
    {                      " If Q: ";
      +0\                  " A B -> 0 (A+B) ";
    _@-                    " C D -> D (D-C) ";
    R=                     " E -> E-th character in R ";
    \                      " Swap the top two items. ";
  );                       " Discard the last item in the list. ";

JavaScript (E6) 84 86 88 92 104

Edit: using & instead of %, different operator precedence (less brackets) and works better with negative numbers
Edit2: | instead of +, op precedence again, -2. Thanks DocMax
Edit3: array comprehension is 2 chars shorter than map(), for strings

F=p=>[o+=c[d=n,n=c.search(i),n<4?4|n-d&3:n=n+d&3]for(i of n=o='',c='NESWFRBL',p)]&&o

Test In FireFox/FireBug console



  • \$\begingroup\$ @Optimizer no more. And hoping to shrink even more. \$\endgroup\$
    – edc65
    Commented Sep 27, 2014 at 17:02
  • \$\begingroup\$ What does && o at the end mean? \$\endgroup\$
    – bebe
    Commented Sep 27, 2014 at 18:18
  • 2
    \$\begingroup\$ @bebe the map function returns an array, inside it, as a side effect, I fill the o string that is what I need to return. array && value evalute to value as any array evaluate to truthy \$\endgroup\$
    – edc65
    Commented Sep 27, 2014 at 18:30
  • 1
    \$\begingroup\$ Finally! I have been staring at this one since it hit 88. Unless I am missing something, you can replace 4+(n-d&3) with 4|n-d&3 and save 2 chars. \$\endgroup\$
    – DocMax
    Commented Sep 30, 2014 at 1:04

C++, 99 97 94 bytes

−3 bytes thans to ceilingcat

The following is formatted as a lambda expression. It takes one char* argument and overwrites it.

[](char*s){for(int d=0,n=0,c=*s*9%37&4;*s;*s++="NESWFRBL"[c|n&3])d+=n=c?*s%11/3-d:n+*s%73%10;}

For those who are not familiar with this feature (like myself 1 hour ago), use it as follows:

#include <iostream>

int main()
    char s[] = "NNWEESEE";
    auto x = [](char*s){for(int d=0,n=0,c=*s*9%37&4;*s;d+=n)c?n=*s%11/3-d:n+=*s%73%10,*s++="NESWFRBL"[c|n&3];};

    x(s); // transform from absolute to relative
    std::cout << s << '\n';

    x(s); // transform from relative to absolute
    std::cout << s << '\n';

Some explanations:

  • When using code like flag ? (x = y) : (x += z), the second pair of parentheses is required in C. So I used C++ instead!
  • C++ requires specifying a return type for a function. Unless I use a lambda expression, that is! An added bonus is I don't need to waste 1 character on the name of the function.
  • The code *s*9%37&4 tests the first byte; the result is 4 if it's one of NESW; 0 otherwise
  • The code *s%11/3 converts the bytes NESW to 0, 1, 2, 3
  • The code *s%73%10 converts the bytes FRBL to 0, 9, 6, 3 (which is 0, 1, 2, 3 modulo 4)
  • When converting relative directions to absolute, I don't need the d variable. I tried rearranging code to eliminate it completely, but it seems impossible...
  • 1
    \$\begingroup\$ I like the way your convert the letters to numbers very much. :) \$\endgroup\$
    – Emil
    Commented Sep 29, 2014 at 5:23

APL, 72


If the interpreter configurations can be changed without penalty, then score is 66, by changing ⎕IO to 0:


Python, 171 139

No way near as short as the other solutions, but I guess it should be relatively good for what can be done with Python:

def f(i):a,b='NWSE','FLBR';I=map(a.find,'N'+i);return''.join((b[I[k+1]-I[k]],a[sum(map(b.find,i)[:k+1])%4])[-1in I]for k in range(len(i)))

Expanded version for slightly better readability:

def f(i):
    a, b = 'NWSE', 'FLBR'
    I = map(a.find,'N'+i)     # translate to numbers assuming abs. directions
    J = map(b.index,i)        # translate to numbers assuming rel. directions
    if not -1 in I:
        o = [b[I[k+1]-I[k]] for k in range(len(i))]    # rel. dir. is differences of abs. dir.
        o = [a[sum(J[:k+1])%4] for k in range(len(i))] # abs. dir. is sum of all rel. dir. so far
    return ''.join(o)

Go, 201

type q string;func F(s q)q{d,z:=byte(0),make([]byte,len(s));for i,c:=range[]byte(s){if(c^4)*167%3<2{c=c*156%5;z[i],d="LBRF"[(d-c)%4],c-1;}else{c=(c^43)*3%7-1;d=(d+c)%4;z[i]="NESW"[d];};};return q(z);}

Readable version:

func F(s string) string {
    d, z, R, A := 0, make([]byte, len(s)), "LBRFLBR", "NESW"
    for i, c := range []byte(s) {
        switch c {
        case 'N': c = R[d+3]; d = 0
        case 'E': c = R[d+2]; d = 1
        case 'S': c = R[d+1]; d = 2
        case 'W': c = R[d]; d = 3
        case 'F': c = A[d]
        case 'R': d = (d + 1) % 4; c = A[d]
        case 'B': d = (d + 2) % 4; c = A[d]
        case 'L': d = (d + 3) % 4; c = A[d]
        z[i] = c
    return string(z)


GNU sed, 356 bytes

The challenge calls for a simple transformation on a stream of characters. sed, the stream editor is the obvious choice of language ;-)

/[FRBL]/bx                                     # Jump to label x if relative
:y                                             # label y (start of abs->rel loop)
/[FRBL]$/q                                     # quit if string ends in rel char
s/(^|[FRBL])N/\1F/;ty                          # Substitute next abs char with
s/(^|[FRBL])E/\1R/;tr                          #     rel char, then jump to
s/(^|[FRBL])S/\1B/;tb                          #     relevant rotation label if
s/(^|[FRBL])W/\1L/;tl                          #     a match was found
by                                             # loop back to y
:r;y/NESW/WNES/;by                             # Rotation labels: transform then
:b;y/NESW/SWNE/;by                             #     loop back to y
:x                                             # label x (start of rel->abs loop)
/^[NESW]/q                                     # quit if string starts w/ abs char
/F([NESW]|$)/s/F([NESW]|$)/N\1/                # Matches for each direction:
/R([NESW]|$)/y/NESW/ESWN/;s/R([NESW]|$)/E\1/   #     rotate, then substitute
bx                                             # loop back to x

(Comments and spaces stripped for the purposes of golf score calculation)


$ sed -rf absrel.sed <<< NNWEESEE
$ sed -rf absrel.sed <<< FFLBFRLF


The idea here is that when we change the frame of reference, there is always a direct mapping between {N, E, S, W} and {F, R, B, L}.

In the case of absolute to relative, we work fowards through the string. For each character we map {N, E, S, W} to {F, R, B, L}, then rotate the remaining [NESW] characters according to the character we just mapped, then move onto the next character.

For the case of relative to absolute we do the reverse. We work backwards through the string, rotating all following [NESW] characters according to the character immediately in front. Then we map that character {N, E, S, W} to {F, R, B, L}, until we get to the start of the string.


Haskell, 224

import Data.Function
f s@(x:_)|elem x a=map((r!!).(`mod`4).(4-))$zipWith((-)`on`(i a))('N':s)(s)|True=tail$map((a!!).(`mod`4)).scanl(+)(0)$map(i r) s

This assigns rotation numbers to the relative directions, and orientation numbers to the absolute directions, then either finds the rotations between successive orientations or the orientations after successive rotations. The i function finds the index within the two legends.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.