15
\$\begingroup\$

Based on an idea suggested by Zgarb.

A spaceship is moving around a regular 3D grid. The cells of the grid are indexed with integers in a right-handed coordinate system, xyz. The spaceship starts at the origin, pointing along the positive x axis, with the positive z axis pointing upwards.

The spaceship will fly along a trajectory defined by a non-empty sequence of movements. Each movement is either F(orward) which makes the spaceship move one cell in the direction its facing, or one of the six rotations UDLRlr. These corresponds to pitch, yaw and roll as follows:

PYR
Thanks to Zgarb for creating the diagram.

  • Up and Down change the pitch of the spaceship by 90 degrees (where the direction corresponds to the movement of the spaceship's nose).
  • Left and Right change the yaw of the spaceship by 90 degrees. They are just regular left and right turns.
  • left and right are 90 degree rolling movements, where the direction indicates which wing moves downwards.

Note that these should always be interpreted relative to the spaceship so the relevant axes rotate along with it.

In mathematical terms, the spaceship is initially at position (0, 0, 0), pointing along the (1, 0, 0) vector, with (0, 0, 1) pointing upwards. The rotations correspond to the following matrices applied to the coordinate system:

U = ( 0  0 -1     D = ( 0  0  1
      0  1  0           0  1  0
      1  0  0 )        -1  0  0 )

L = ( 0 -1  0     R = ( 0  1  0
      1  0  0          -1  0  0
      0  0  1 )         0  0  1 )

l = ( 1  0  0     r = ( 1  0  0
      0  0  1           0  0 -1
      0 -1  0 )         0  1  0 )

You should output the final position of the spaceship as three integers x, y, z. Output may be three separate integers or a list or string containing them. They may be in any consistent order as long as you specify it.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Standard rules apply.

Test Cases

F                                                   => (1, 0, 0)
FDDF                                                => (0, 0, 0)
FDDDF                                               => (1, 0, 1)
LrDDlURRrr                                          => (0, 0, 0)
UFLrRFLRLR                                          => (1, 0, 1)
FFrlFULULF                                          => (3, 0, -1)
LLFRLFDFFD                                          => (-2, 0, -2)
FrrLFLFrDLRFrLLFrFrRRFFFLRlFFLFFRFFLFlFFFlUFDFDrFF  => (1, 5, 7)
FUrRLDDlUDDlFlFFFDFrDrLrlUUrFlFFllRLlLlFFLrUFlRlFF  => (8, 2, 2)
FFLrlFLRFFFRFrFFFRFFRrFFFDDLFFURlrRFFFlrRFFlDlFFFU  => (1, 2, -2)
FLULFLFDURDUFFFLUlFlUFLFRrlDRFFFLFUFrFllFULUFFDRFF  => (-3, -2, -3)

Worked example

Here are the intermediate steps of the UFLrRFLRLR test case. Here, all intermediate coordinates and direction vectors are given in the initial, global coordinate system (as opposed to one local to the spaceship):

Cmd.  Position    Forward     Up
      ( 0, 0, 0)  ( 1, 0, 0)  ( 0, 0, 1)
U     ( 0, 0, 0)  ( 0, 0, 1)  (-1, 0, 0)
F     ( 0, 0, 1)  ( 0, 0, 1)  (-1, 0, 0)
L     ( 0, 0, 1)  ( 0, 1, 0)  (-1, 0, 0)
r     ( 0, 0, 1)  ( 0, 1, 0)  ( 0, 0, 1)
R     ( 0, 0, 1)  ( 1, 0, 0)  ( 0, 0, 1)
F     ( 1, 0, 1)  ( 1, 0, 0)  ( 0, 0, 1)
L     ( 1, 0, 1)  ( 0, 1, 0)  ( 0, 0, 1)
R     ( 1, 0, 1)  ( 1, 0, 0)  ( 0, 0, 1)
L     ( 1, 0, 1)  ( 0, 1, 0)  ( 0, 0, 1)
R     ( 1, 0, 1)  ( 1, 0, 0)  ( 0, 0, 1)
\$\endgroup\$
  • \$\begingroup\$ This challenge is a 3D generalization of this one, minus the intersection part. \$\endgroup\$ – orlp Feb 11 '16 at 22:13
  • \$\begingroup\$ Why does 2 != 2, 3 != -1, 4 != 0 != -4, 1 != -3 \$\endgroup\$ – username.ak Feb 12 '16 at 15:35
  • \$\begingroup\$ @username.ak I don't think I understand the question. What are you referring to? \$\endgroup\$ – Martin Ender Feb 12 '16 at 15:37
  • \$\begingroup\$ @Martin Büttner, I say why 180 degrees rotation is not the same as -180, 270 is not the same as -90 etc \$\endgroup\$ – username.ak Feb 12 '16 at 15:41
  • \$\begingroup\$ @username.ak is it not? \$\endgroup\$ – Martin Ender Feb 12 '16 at 15:42
3
\$\begingroup\$

MATL, 76 75 bytes

FFF!3Xyj"FFT_FTFv4BvtFT_YStTF_YS3:"3$y!]6$Xh@'ULlDRr'4#mt?X)Y*}xxt1Z)b+w]]x

This works in current version (12.1.1) of the language.

Edit (April 4, 2016): The behaviour of function v has changed in release 15.0.0 of the language. To make the above code run, remove the first v and replace the second 3$v. The following link includes this modification.

Try it online!

Explanation

The state of the ship can be described in terms of two variables:

  • position: 3x1 vector
  • orientation: 3x3 matrix with the accumulated rotation, where "accumulated" means repeated matrix product.

A third variable would be the direction in which the ship is facing, but that's not needed, because it can be obtained as the initial direction (column vector [1;0;0]) times the current orientation; that is, the first column of the orientation.

These two state variables are kept on the stack, and are updated with each letter. Each of the letters ULlDRr multiplies the orientation matrix by one of the six rotation matrices to update the orientation. Letter F adds the current position plus the first column of the orientation matrix.

The six rotation matrices are created as follows: first is introduced directly; second and third are circular shifts of the previous one; and the remaining three are transposed versions of the others.

FFF!             % 3x1 vector [0;0;0]: initial position
3Xy              % 3x3 identity matrix: initial orientation
j                % input string
"                % for-each character in that string
  FFT_FTFv4Bv    %   rotation matrix for U: defined directly
  tFT_YS         %   rotation matrix for L: U circularly shifted to the left
  tTF_YS         %   rotation matrix for l: L circularly shifted down
  3:"            %   repeat three times
    3$y!         %     copy third matrix from top and transpose
  ]              %   end loop. This creates rotation matrices for D, R, r
  6$Xh           %   pack the 6 matrices in a cell array
  @              %   push current character from the input string
  'ULlDRr'4#m    %   this gives an index 0 for F, 1 for U, 2 for L, ..., 6 for r
  t?             %   if non-zero: update orientation
    X)           %     pick corresponding rotation matrix
    Y*           %     matrix product
  }              %   else: update position
    xx           %     delete twice (index and rotation matrix are not used here)
    t1Z)         %     duplicate orientation matrix and take its first column
    b+           %     move position vector to top and add
    w            %     swap the two top-most elements in stack
  ]              %   end if
]                % end for-each
x                % delete orientation matrix
                 % implicitly display position vector
\$\endgroup\$
1
\$\begingroup\$

Octave, 175 bytes

function p=s(i)m.U=[0,0,-1;0,1,0;1,0,0];m.D=m.U';m.L=[0,-1,0;1,0,0;0,0,1];m.R=m.L';m.l=flip(flip(m.L),2);m.r=m.l';a=m.F=eye(3);p=[0;0;0];for c=i p+=(a*=m.(c))*[c=='F';0;0];end

Readable version:

function p=s(i)
  m.U=[0,0,-1;0,1,0;1,0,0];
  m.D=m.U';
  m.L=[0,-1,0;1,0,0;0,0,1];
  m.R=m.L';
  m.l=flip(flip(m.L),2);
  m.r=m.l';
  a=m.F=eye(3);
  p=[0;0;0];
  for c=i p+=(a*=m.(c))*[c=='F';0;0];
end
\$\endgroup\$
  • \$\begingroup\$ Nice use of dynamic field names! \$\endgroup\$ – Luis Mendo Feb 12 '16 at 0:12
  • 2
    \$\begingroup\$ "Readable version [citation needed]" ;) \$\endgroup\$ – trichoplax Feb 12 '16 at 3:54
0
\$\begingroup\$

ES6, 265 259 bytes

s=>[...s.replace(/F/g,"f$`s")].reverse().map(e=>d={U:(x,y,z)=>[-z,y,x],D:(x,y,z)=>[z,y,-x],L:(x,y,z)=>[-y,x,z],R:(x,y,z)=>[y,-x,z],r:(x,y,z)=>[x,-z,y],l:(x,y,z)=>[x,z,-y],F:(...d)=>d,f:(x,y,z)=>[a+=x,b+=y,c+=z]),s:_=>[1,0,0]}[e](...d),d=[1,0,a=b=c=0])&&[a,b,c]

Explanation: Normally to calculate the direction of the spaceship you would compose all the rotations together, and then for each move you would compose the result to the unit vector F = (1, 0, 0) (or more simply extract the first column of the matrix). For instance, FFrlFULULF => F + F + r⋅l⋅F + r⋅l⋅U⋅L⋅L⋅L⋅F. Since matrix multiplication is associative, languages with built-in matrix multiplication can obviously compute the partial product r⋅l⋅U⋅L⋅L⋅L as they go along, multiplying by F as necessary to produce the terms that are then added together. Unfortunately I don't have that luxury, so the cheapest option is to compute each term in the above expression separately, starting with F and working back. For that, I need a list for each of the occurrences of F of all the rotations up to that point. I do this using replace with $` so I also need to mark the start and end of each term in the list so that I can ignore the rest of the string. Slightly ungolfed:

s=>[... // split the string into separate operations
    s.replace(/F/g,"f$`s")] // For each 'F', wrap the operations up to that point
  .reverse() // Play all the operations in reverse order
  .map(e=>d= // Update the direction for each operation
    { // set of operations
      U:(x,y,z)=>[-z,y,x], // Up
      D:(x,y,z)=>[z,y,-x], // Down
      L:(x,y,z)=>[-y,x,z], // Left turn
      R:(x,y,z)=>[y,-x,z], // Right turn
      r:(x,y,z)=>[x,-z,y], // right roll
      l:(x,y,z)=>[x,z,-y], // left roll
      F:(...d)=>d, // does nothing, `s` and `f` do the work now
      f:(x,y,z)=>[a+=x,b+=y,c+=z], // do the move
      s:_=>[1,0,0] // back to start
    }[e](...d), // apply the operation to the current direction
    d=[1,0,a=b=c=0] // initialise variables
  )&&[a,b,c] // return result
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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