Motion on a hexagonal grid
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 r
s. 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 R
s and the second stage will apply another rotation as long as there are r
s 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 q
s and d
s to the front and turn them into w
s and s
s 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 q
s and d
s, we know that all the s
s in the left-hand side will appear in front of any w
s, 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.)
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.