Движение по гексагональной сетке

15

При вводе последовательности символов, представляющих движения в гексагональной сетке, выведите окончательные координаты «указателя».

Наши шестиугольники будут пронумерованы так (представьте прямоугольную сетку с каждым нечетным столбцом, слегка смещенным вниз):

  _____         _____         _____         _____
 /     \       /     \       /     \       /     \
/ -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  \
\       /     \       /     \       /     \       /
 \_____/       \_____/       \_____/       \_____/

Указатель начинается с (0, 0).

Инструкции, которые вы должны поддерживать, следующие:

  • q: двигаться вверх-влево
  • w: двигаться вверх
  • e: двигаться вверх-вправо
  • a: двигаться вниз-влево
  • s: двигаться вниз
  • d: двигаться вниз-вправо
  • r: вращать сетку по часовой стрелке
  • R: повернуть сетку против часовой стрелки

Команды вращения вращают всю сетку, сохраняя указатель в тех же координатах. (Почему qweasd? Они хорошо соответствуют направлениям на QWERTY-клавиатуре.)

Чтобы помочь визуализировать это, вот что будут делать команды перемещения, предполагая, что указатель начинается посередине:

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

После поворота по часовой стрелке ( r) команды переназначаются (представьте, что они вращают всю шестнадцатеричную сетку, но все еще сохраняют «w», как вверх, и т. Д., Что эквивалентно следующему):

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

Точно так же вращение против часовой стрелки ( R) после этого вернет сетку в нормальное состояние, а вращение против часовой стрелки снова «переназначит» qwedsaна aqweds.

Входные данные должны быть представлены в виде одной строки, а выходные данные могут быть либо одной строкой, объединенной любыми нечисловыми символами (например, 1 2или 3,4), либо массивом целых чисел.

Поскольку это , победит самый короткий код в байтах.

Тестовые случаи:

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
Дверная ручка
источник

Ответы:

2

Pyth, 81 байт

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

Выходные данные представляют собой список целых чисел, представляющих координаты.

Мое решение на самом деле очень скучно; он просто просматривает введенный символ в массиве (the qwedsa), а затем обращается к двум массивам, которые представляют соответствующие изменения в координатах. Например, если введено значение w, то мы получаем 1 (так как это второй символ в массиве). Затем мы добавляем A[1]к x(где Aмассив для изменений в xотношении различных входных данных) и B[1]к y(где Bизменения для y). rи Rдостигаются простым вращением qwedsaмассива.

Я уверен, что кто-то может сделать намного лучше, используя Pyth. Я продолжу пытаться сыграть в гольф мой ответ, хотя!

Вы можете попробовать это здесь .

Rhyzomatic
источник
12

Retina , 353 339 178 175 150 130 129 117 байт

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

Вывод в одинарных, разделенных двоеточием. Это означает, что вы действительно не увидите нули в выходных данных (хотя наличие двоеточия скажет вам, какая из двух координат равна нулю, если есть только одна).

Попробуйте онлайн!

Это было действительно весело и оказалось на удивление коротким. :)

объяснение

Сначала немного предыстории. Существует несколько систем координат для описания гексагональных сеток. Запрашиваемый использует координаты смещения. По сути это похоже на прямоугольные координаты сетки, за исключением того, что одна ось немного «качается». В частности, вопрос касается макета «odd-q», показанного на связанной странице. Эта система координат немного раздражает в работе, потому что то, как координаты меняются во время перемещения, зависит не только от направления движения, но и от текущей позиции.

Другая система координат использует осевые координаты. Это, по сути, представление гекс-сетки в виде диагонального среза через объем кубов и использование двух осей (например, x и z), чтобы найти положение на 2D-плоскости. На шестигранной сетке это означает, что две оси образуют угол 60 (или 120) градусов. Эта система немного менее интуитивна, но с ней гораздо проще работать, поскольку каждое направление соответствует фиксированному «дельта» вектору. (Для лучшего объяснения того, как прийти к этой системе координат, посмотрите ссылку и прекрасные схемы и анимации там.)

Итак, вот что мы сделаем: мы вычисляем движение в осевых координатах (заботясь о вращении, как предложено в задаче, переназначая значение команд), а когда мы закончим, мы преобразуем осевое в смещение odd-q координаты.

Шесть перемещений отображаются на следующие дельта-векторы в (xz) осевых координатах:

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

Подождите, это Retina, нам придется работать с одинарными номерами. Как мы работаем с отрицательными одинарными числами? Идея состоит в том, чтобы использовать две разные цифры. Один представляет, +1а другой представляет -1. Это означает, что независимо от того, хотим ли мы добавить или вычесть 1из текущей позиции, мы всегда можем сделать это, добавив цифру. Когда мы закончим, мы свернем результат в его величину (соответствующей цифры), отменив сбалансированные цифры. Затем мы вычисляем знак на основе оставшейся цифры и заменяем все цифры на 1.

План состоит в том, чтобы построить осевые компоненты x и z слева и справа от a :(как разделитель), перед входом. wи sдобавит к правой стороне. qи dдобавит к левой стороне, и eи aдобавит к обеим сторонам. Так как wи sуже на правильной стороне :(которая будет идти впереди), мы будем использовать те, что -1и +1цифры соответственно.

Давайте пройдемся по коду.

R
5$*r

Мы начинаем с превращения каждого Rв пять rс. Конечно, один левый поворот такой же, как пять правых поворотов на шестигранной сетке, и, делая это, мы можем много дублировать на шаге переназначения.

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

Это этап транслитерации, который вращает шесть команд, если они найдены после первой r(тем самым обрабатывая первую r). wи dдолжны быть экранированы, чтобы предотвратить их расширение в классы персонажей. oВставляет набор источника в целевой набор , который экономит кучу байтов для выполнения этих задач вращения. Следовательно, отображение символов:

aqweds
saqweds

где последний sво втором ряду может быть просто проигнорирован.

)`r(.*)
$1

Это удаляет первое rиз строки, потому что оно было обработано (хотелось бы, чтобы уже были введены ограничения на подстановку ...). Кроме )того, Retina сообщает, что все этапы до этой стадии должны выполняться в цикле, пока строка не перестанет меняться. На последующих итерациях первый этап - это запрет, так как больше нет Rs, а второй этап будет применять другое вращение, пока rв строке осталось s.

Когда мы закончим, мы сопоставили все команды с направлением, которому они соответствуют в не повернутой сетке, и можем приступить к их обработке. Конечно, это движение является просто суммой этих дельта-векторов, и суммы являются коммутативными, поэтому не имеет значения, в каком порядке мы обрабатываем их сейчас, когда вращения были исключены.

^
:

Вставьте разделитель координат спереди.

Теперь нам не нужно обрабатывать sи w. Они наши +1и -1цифры, и они уже на правильной стороне, :поэтому они просто выпадут, как требуется в конце. Мы можем сделать еще одно упрощение: aпросто s + qи eесть w + d. Давайте сделаем это:

a
sq
e
wd

Опять те sи wпросто выпадут. Все, что нам нужно сделать, это переместить эти qs и ds вперед и превратить их в ws и ss сами. Мы делаем это с двумя отдельными циклами:

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

Итак, все готово. Время для перевода из осевых координат в смещение. Для этого нам нужно свернуть цифры. Однако сейчас нас интересует только левая сторона. Благодаря тому, как мы обработали qs и ds, мы знаем, что все ss в левой части будут отображаться перед любыми ws, поэтому нам нужно проверить только одну пару, чтобы свернуть их:

+`sw

Теперь актуальная конверсия. Вот псевдокод, взятый по ссылке выше:

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

Правильно, поэтому левая часть уже правильная. Правая сторона требует исправления, (x - (x&1)) / 2хотя. Взятие &1такое же, как по модулю 2. Это в основном разбирает как x/2целочисленное деление, округленное до минус бесконечности. Таким образом, для положительного x, мы добавляем половину количества цифр (округляется в меньшую сторону), а для отрицательного xмы вычитаем половину количества цифр (округляется в большую сторону). Это может быть удивительно кратко выражено в регулярном выражении:

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

Из-за жадности, для четной xгруппы 1 будет совпадать ровно с половиной цифр, \1с другой половиной, и мы можем игнорировать w?. Мы вставляем эту половину после :(что есть x/2). Если xчёт, то нужно различать положительное и отрицательное. Если xположительный, то w?никогда не будет совпадать, поэтому две группы все равно должны будут совпадать с одинаковым количеством цифр. Это не проблема, если первый sпросто пропущен, поэтому мы округляемся. Если xон отрицательный и нечетный, то возможное совпадение с \1(половина xокругленного вниз) и это необязательно w. Так как оба из них идут в группу 2, мы будем писать x/2с округленной величиной (как требуется).

+`sw|ws

Теперь мы свернем цифры на правой стороне. На этот раз мы не знаем порядок sи w, поэтому нам нужно учесть обе пары.

w+
-$0

Обе части теперь уменьшены до одной повторяющейся цифры (или ничего). Если это цифра w, мы вставляем знак минус впереди.

\w
1

И, наконец, мы превращаем wи sв одну разумную унарную цифру. (Я полагаю, что я мог бы сохранить байт, используя wили sв качестве унарной цифры, но это кажется немного натянутым.)

Мартин Эндер
источник
10
(Я единственный, кто видел этот ответ пришел на главной странице сайта и дорого надеялся , что это было написано в hexagony?)
Addison Крамп
9
@FlagAsSpam Требования этого сообщества серьезно возрастают, когда можно разочаровать 8 человек (и считать), решая задачу с целыми числами со знаком и гексагональными сетками на языке, который может обрабатывать ввод только через регулярные выражения. ;)
Мартин Эндер
1

Python (3,5) 193 185 182 байта

Я также исчисляю осевые координаты и конвертирую в конце.

Я добавляю некоторую оптимизацию в соответствии с решением @Martin Büttner: я заменяю R на r * 5, это не меняет количество байтов. Но с этим изменением мы можем заменить второй тест elif j=='r'простоelse

Решение предполагает, что у нас не может быть недопустимых символов на входе.

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"

использование

>>> f('wrwrwrwrw')
-1 0.0
>>> f('dddddddddd')
10 5.0
>>> f('edeqaaaswwdqqs')
-2 0.0
Эрвана
источник
0

Пакетный, 708 636 586 569 байт

Я использовал двойные y-координаты, потому что это упрощало математику. Я не уверен, что учел вращение самым идеальным образом, но это лучше, чем подсчет числа rs.

Редактировать: Сохранено 72 байта за счет улучшения обработки Rs. Экономия 60 байтов за счет оптимизации моих set/aутверждений. Сохранено 17 байт с небольшими оптимизациями.

@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%
Нил
источник
0

05AB1E , 60 байтов

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

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

Общее объяснение:

Мы начинаем со строки "qwedsa"и координаты [0,0]и зацикливаем символы ввода.
Если это «r» или «R», мы поворачиваем эту строку влево или вправо соответственно.
Если нет, мы получаем индекс на основе 0 в этой строке и отображаем его следующим образом:

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

xy

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

k

x=min(k,abs(k5))1
y=(0k(mod3))+2(k>3)1

yxx

y=y+xx(mod2)2

Объяснение кода:

.•FM         # 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)

Посмотрите эту подсказку 05AB1E (раздел Как сжимать строки, не являющуюся частью словаря? ), Чтобы понять, почему .•F?äM•это так "qwedsa".

Кевин Круйссен
источник
-1

Python 3, 227 байт

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))
Остин Гастингс
источник
Я использую Python 3.5.0b3на MacOS, и хотя я получил ошибку в 5 и 6, из-за округления, остальные были правильными. (Так как исправлено с помощью Edit). Какую версию Python вы используете?
Остин Гастингс
1
@AustinHastings Я на Python 3, на нестабильной версии Debian.
Ручка двери