Motion on a hexagonal grid

Question

Given an input of a series of characters representing movements on a hexagonal grid, output the final coordinates of the "pointer."

Our hexagons will be numbered like so (imagine a rectangular grid with every odd-numbered column shifted downwards slightly):

  _____         _____         _____         _____
 /     \       /     \       /     \       /     \
/ -3,-2 \_____/ -1,-2 \_____/  1,-2 \_____/  3,-2 \
\       /     \       /     \       /     \       /
 \_____/ -2,-1 \_____/  0,-1 \_____/  2,-1 \_____/
 /     \       /     \       /     \       /     \
/ -3,-1 \_____/ -1,-1 \_____/  1,-1 \_____/  3,-1 \
\       /     \       /     \       /     \       /
 \_____/ -2,0  \_____/  0,0  \_____/  2,0  \_____/
 /     \       /     \       /     \       /     \
/ -3,0  \_____/ -1,0  \_____/  1,0  \_____/  3,0  \
\       /     \       /     \       /     \       /
 \_____/ -2,1  \_____/  0,1  \_____/  2,1  \_____/
 /     \       /     \       /     \       /     \
/ -3,1  \_____/ -1,1  \_____/  1,1  \_____/  3,1  \
\       /     \       /     \       /     \       /
 \_____/       \_____/       \_____/       \_____/

The pointer starts at (0, 0).

The instructions you must support are as follows:

• q: move up-left
• w: move up
• e: move up-right
• a: move down-left
• s: move down
• d: move down-right
• r: rotate grid clockwise
• R: rotate grid counterclockwise

The rotation commands rotate the entire grid while keeping the pointer at the same coordinates. (Why qweasd? They match up with the directions nicely on a QWERTY keyboard.)

To help visualize this, here's what the movement commands would do, assuming the pointer starts in the middle:

         _____
        /     \
  _____/   w   \_____
 /     \       /     \
/   q   \_____/   e   \
\       /     \       /
 \_____/       \_____/
 /     \       /     \
/   a   \_____/   d   \
\       /     \       /
 \_____/   s   \_____/
       \       /
        \_____/

After a clockwise rotation (r), the commands are remapped to (imagine it as rotating the entire hex grid but still keeping "w" as up, etc., which is equivalent to the following):

         _____
        /     \
  _____/   e   \_____
 /     \       /     \
/   w   \_____/   d   \
\       /     \       /
 \_____/       \_____/
 /     \       /     \
/   q   \_____/   s   \
\       /     \       /
 \_____/   a   \_____/
       \       /
        \_____/

Similarly, rotating counterclockwise (R) after that would return the grid to normal, and rotating counterclockwise again would "remap" qwedsa to aqweds.

Input must be given as a single string, and output can be either a single string joined by any non-numerical characters (ex. 1 2 or 3,4) or an array of integers.

Since this is code-golf, the shortest code in bytes will win.

Test cases:

In                         Out
---------------------------------
edeqaaaswwdqqs             -2, 0
dddddddddd                 10, 5
wswseaeadqdq               0, 0
<empty string>             0, 0
esaaqrweesrqrq             -1, 0
wrwrwrwrw                  -1, 0
RRssrrrs                   -1, -1
aRRRRwddrqrrqqq            -1, -4
rrrrrrrrrrrrRRRRRRrrrrrrq  -1, -1
rrRrRrrRrrrrRRrRrRR        0, 0

Answer 1

Pyth, 81 bytes

J_K1=Y"qwedsa"A,ZZFNz=kxYN ?<kZ=Y?<x\rNZ.>Y1.<Y1A,+G@[JZ1KZJ)k+H@[J_2JK2K)k;,G/H2

Output is a list of integers representing the coordinates.

My solution is actually really boring; it just looks up the inputted character in an array (the qwedsa), and then accesses two arrays that represent the respective changes in the coordinates. For example, if the input is w, then we get 1 (as it is the second character in the array). Then we add A[1] to x (where A is the array for the changes in x in respect to the different inputs) and B[1] to y (where B is the changes for y). r and R are achieved by just rotating the qwedsa array.

I'm sure someone can do much better using Pyth. I'll continue to try to golf my answer though!

You can try it out here.

Answer 2

Retina, 353 339 178 175 150 130 129 117 bytes

R
5$*r
T`aq\we\ds`so`r.+
)`r(.*)
$1
^
:
a
sq
e
wd
+`(.+)q
w$1
+`(.+)d
s$1
+`sw

(.*)(\1w?):
$0$2
+`sw|ws

w+
-$0
\w
1

Output is in unary, separated by a colon. That means you won't really see zeroes in the output (although the presence of a colon will tell you which of the two coordinates is zero, if there is only one).

Try it online!

This was really fun and ended up being surprisingly short. :)

Explanation

Some background first. There are several coordinate systems to describe hexagonal grids. The one asked for uses offset coordinates. That's essentially like rectangular grid coordinates, except that one axis "wobbles" a bit. In particular, the question asks for the "odd-q" layout shown on the linked page. This coordinate system is a bit annoying to work with, because how the coordinates change during a move depends not only on the direction of the move but also on the current position.

Another coordinate system uses axial coordinates. That's essentially imagining the hexgrid as a diagonal slice through a volume of cubes, and using two of the axes (e.g. x and z) to find a position on the 2D plane. On the hex grid, that means that the two axes form an angle of 60 (or 120) degrees. This system is a bit less intuitive but much easier to work with, since every direction corresponds to a fixed "delta" vector. (For a better explanation of how to arrive at this coordinate system, check out the link and the lovely diagrams and animations there.)

So here's what we'll do: we compute the movement in axial coordinates (taking care of rotation as suggested in the challenge, by remapping the meaning of the commands), and when we're done we convert axial to to odd-q offset coordinates.

The six moves map to the following delta vectors in (x-z) axial coordinates:

q => (-1,  0)
w => ( 0, -1)
e => ( 1, -1)
d => ( 1,  0)
s => ( 0,  1)
a => (-1,  1)

Wait, this is Retina, we'll have to work with unary numbers. How do we work with negative unary numbers? The idea is to use two different digits. One represents +1 and the other represents -1. That means regardless of whether we want add or subtract 1 from the current position, we can always do so by adding a digit. When we're done we collapse the result into its magnitude (of the corresponding digit) by cancelling balanced digits. Then we figure out the sign based on the remaining digit, and replace all digits with 1.

The plan is to build up the axial x and z components to the left and right of a : (as a separator), in front of the input. w and s will add to the right-hand side. q and d will add to the left-hand side, and e and a will add to both sides. Since w and s are already on the correct side of the : (which will go in front), we will use those as the -1 and +1 digits, respectively.

Let's go through the code.

R
5$*r

We start by turning each R into five rs. Of course, one left turn is the same as five right turns on a hex grid, and by doing so we can a lot of duplication on the remapping step.

T`aq\we\ds`so`r.+

This is a transliteration stage which rotates the six commands, if they are found after the first r (thereby processing the first r). w and d need to be escaped to prevent them from expanding into character classes. The o inserts the source set into the target set which saves a bunch of bytes for these rotation tasks. The character mapping is therefore:

aqweds
saqweds

where the last s in the second row can simply be ignored.

)`r(.*)
$1

This removes the first r from the string, because it's been processed (I wish I had already implemented substitution limits...). The ) also tells Retina to run all stages up to this one in a loop until the string stops changing. On subsequent iterations, the first stage is a no-op because there are no more Rs and the second stage will apply another rotation as long as there are rs left in the string.

When we're done, we've mapped all commands to the direction they correspond to on the unrotated grid and can start processing those. Of course this movement is just a sum of those delta vectors, and sums are commutative, so it doesn't really matter in which order we process them now that rotations have been eliminated.

^
:

Insert the coordinate delimiter at the front.

Now we don't really need to process s and w. They are our +1 and -1 digits and they're already on the correct side of the : so they'll just drop out as required in the end. We can make another simplification: a is simply s + q and e is w + d. Let's do that:

a
sq
e
wd

Again, those s and w will just drop out. All we need to do is move those qs and ds to the front and turn them into ws and ss themselves. We do that with two separate loops:

+`(.+)q
w$1
+`(.+)d
s$1

So that's done. Time for the conversion from axial to offset coordinates. For that we need to collapse the digits. However, for now we only care about the left-hand side. Due to the way we've processed the qs and ds, we know that all the ss in the left-hand side will appear in front of any ws, so we only need to check one pair for collapsing the them:

+`sw

Now the actual conversion. Here is the pseudocode, taken from link above:

# convert cube to odd-q offset
col = x
row = z + (x - (x&1)) / 2

Right, so the left-hand side is already correct. The right-hand side needs the correction term (x - (x&1)) / 2 though. Taking &1 is the same as modulo 2. This basically parses as x/2, integer division, rounded towards minus infinity. So for positive x, we add half the number of digits (rounded down), and for negative x, we subtract half the number of digits (rounded up). This can be expressed surprisingly concisely in regex:

(.*)(\1w?):
$0$2

Due to the greediness, for even x, group 1 will match exactly half the digits, \1 the other half and we can ignore the w?. We insert that half after the : (which is x/2). If x is even, then we need to distinguish positive and negative. If x is positive, then w? will never match, so the two groups will still have to match the same number of digits. That's no problem if the first s is simply skipped, so we round down. If x is negative and odd, then the possible match is with \1 (half of x rounded down) and that optional w. Since both of those go into group 2, we will write x/2 with the magnitude rounded up (as required).

+`sw|ws

Now we collapse the digits on the right-hand side. This time, we don't know the order of the s and w, so we need to account for both pairs.

w+
-$0

Both parts are now reduced to a single repeated digit (or nothing). If that digit is w, we insert a minus sign in front.

\w
1

And finally we turn both into w and s into a single reasonable unary digit. (I suppose I could save a byte by using w or s as the unary digit, but that seems like a bit of a stretch.)

Answer 3

Python (3.5) 193 185 182 bytes

I also calcul in axial coordinates and convert at the end.

I add some optimisation according to @Martin Büttner solution : I replace R by r*5, it doesn't change the bytes count. But with this change we can replace the second test elif j=='r' by just else

The solution assume we can't have invalid characters in the input.

def f(i):
 x=y=0;u=-1,0,-1,1,0,1,1,0,1,-1,0,-1;v='dewqas'
 for j in i.replace('R','r'*5):
  w=v.find(j)*2
  if-1<w:x+=u[w];y+=u[w+1]
  else:u=u[2:]+u[:2]
 print(-x,-x-y+(x-(x%2))/2)

Ungolfed

def f(i):
  x=y=0
  u=-1,0,-1,1,0,1,1,0,1,-1,0,-1    # operations list xd,yd,xe,ye...
  v='dewqas'                       # letters list in clockwise order 
  i.replace('R','r'*5)             # replace 'R' by 5*'r'
  for j in i:
    w=v.find(j)*2                  # extract letter index
    if-1<w:
      x+=u[w]                      # apply operations
      y+=u[w+1]
    else:
      u=u[2:]+u[:2]                # rotate clockwise the operation string
  print(-x,-x-y+(x-(x%2))/2)       # convert coordinates axial to "odd-q"

Usage

>>> f('wrwrwrwrw')
-1 0.0
>>> f('dddddddddd')
10 5.0
>>> f('edeqaaaswwdqqs')
-2 0.0

Answer 4

05AB1E, 60 bytes

.•F?äM•U2Å0IvXy'rQiÀUëy'RQiÁUëykÐ5α‚ßsD3%_s3›·+‚<+]Ć`DÉ-2÷+‚

Try it online or verify all test cases.

Explanation:

General explanation:

We start with a string "qwedsa" and a coordinate [0,0], and loop over the characters of the input.
If it's an "r" or "R" we rotate this string towards the left or right respectively.
If not, we get the 0-based index in this string, and map it as follows:

q → 0 → [-1,  0]
w → 1 → [ 0, -1]
e → 2 → [ 1, -1]
d → 3 → [ 1,  0]
s → 4 → [ 0,  1]
a → 5 → [-1,  1]

We'll need to convert the index-digits to the following \$x\$ and \$y\$ coordinates:

 x   indices     y   indices
-1 ← 0;5        -1 ← 1;2
 0 ← 1;4         0 ← 0;3
 1 ← 2;3         1 ← 4;5

We do this, by converting the index \$k\$ as follows:

\$x = min(k, abs(k-5))-1\$
\$y = (0\equiv k\pmod3) + 2(k\gt3) - 1\$

And after the entire loop, we have to fix the off-set of the \$y\$-coordinate based on the \$x\$-coordinate, which we do like this (\$x\$ remains the same):

\$y=y+\lfloor\frac{x-x\pmod2}{2}\rfloor\$

Code explanation:

.•F?äM•         # Push compressed string "qwedsa"
       U        # Pop and store it in variable `X`
2Å0             # Push list [0,0]
                # (many 3-byte alternatives for this: `00S`; `т¦S`; `0D‚`; `1¾‰`; etc.)
   Iv           # Loop over each character `y` of the input:
     X          #  Push string `X`
      y'rQi    '#  If `y` equals "r":
           À    #   Rotate string `X` once towards the left
            U   #   And pop and store it as new value for `X`
      ëy'RQi   '#  Else-if `y` equals "R":
            ÁU  #   Do the same, but rotate right instead
      ë         #  Else:
       yk       #   Get the 0-based index of `y` in the string `X`
         Ð      #   Triplicate this index
          5α    #   Take the absolute difference with 5
            ‚ß  #   Pair it with the original index, and pop and push the minimum
                #   (maps 0→[0,5]→0; 1→[1,4]→1; 2→[2,3]→2;
                #         3→[3,2]→2; 4→[4,1]→1; 5→[5,0]→0)
         sD     #   Swap to get the original index again, and duplicate it
           3%   #   Take modulo 3
             _  #   And check if it's equals to 0 (1 if truthy; 0 if falsey)
          s3›   #   Swap to take the index again, and check if it's larger than 
                #   (again, 1 if truthy; 0 if falsey)
             ·  #   Double this
          +     #   And add both checks together
                #   (maps 0→1+0→1; 1→0+0→0; 2→0+0→0;
                #         3→1+0→1; 4→0+2→2; 5→0+2→2)
         ‚      #   Pair both mapped values together
          <     #   Decrease both by 1, so it becomes: 0→-1; 1→0; 2→1
           +    #   And add it to the current coordinates
    ]           # After the loop with inner if-else statements:
     Ć          # Enclose the coordinate, appending its own head: [x,y] becomes [x,y,x]
      `         # Push all three values separated to the stack
       D        # Duplicate this x
        É       # Check if its odd (1 if truthy; 0 if falsey)
         -      # Subtract it from the duplicated x
          2÷    # Integer-divide it by 2
            +   # Add it to y
             ‚  # And pair it with the original x again
                # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress strings not part of the dictionary?) to understand why .•F?äM• is "qwedsa".

Answer 5

Batch, 708 636 586 569 bytes

I used doubled y-coordinates because it made the maths simpler. I'm not sure I took the rotation into account in the most ideal way, but it beats counting the number of rs.

Edit: Saved 72 bytes by improving on the handling of Rs. Saved 60 bytes by optimising my set/a statements. Saved 17 bytes with some minor optimisations.

@echo off
set m=%1
set/ay=x=0
set r=r
set g=goto l
:l
set/a"z=y>>1
if "%m%"=="" echo %x% %z%&exit/b
set c=%m:~0,1%
set m=%m:~1%
goto %r:rrrrrr=%%c%
:a
:rq
:rrw
:rrre
:rrrrd
:rrrrrs
set/ax-=2
:w
:re
:rrd
:rrrs
:rrrra
:rrrrrq
set/ax+=1,y-=1
%g%
:q
:rw
:rre
:rrrd
:rrrrs
:rrrrra
set/ay-=2
%g%
:s
:ra
:rrq
:rrrw
:rrrre
:rrrrrd
set/ax-=2
:e
:rd
:rrs
:rrra
:rrrrq
:rrrrrw
set/ax+=+1,y+=1
%g%
:d
:rs
:rra
:rrrq
:rrrrw
:rrrrre
set/ay+=2
%g%
:r
:rr
:rrr
:rrrr
:rrrrr
:rrrrrr
if %c%==R set c=rrrrr
set r=%c%%r%
%g%

Answer 6

Python 3, 227 bytes

def G(s):
 q='qwedsa'
 d=[-1,0,1,1,0,-1,-1,-2,-1,1,2,1]
 X=Y=0
 for c in s:
  if c in q:
   n = q.find(c)
   X += d[n]
   Y += d[n+6]
  if c == 'r':
   q = q[1:]+q[0]
  if c == 'R':
   q = q[5]+q[0:5]
 print(X, int((Y-X%2)/2))