Сделайте BackFlip для ais523!

16

Эта задача является призом для ais523 за победу в категории « Новичок года » в номинации « Лучший из PPCG 2016 ». Поздравляем!


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

BackFlip это 2D-язык, как Befunge или > <>, где указатель инструкций пересекает сетку текста (программу), перемещаясь вверх, вниз, влево и вправо, изменяя направление в зависимости от символа, на котором он находится. Крайне важно, что сетка в программе BackFlip изменяется по мере прохождения, немного как муравей Лэнгтона .

Для этой задачи вы можете предположить, что программа BackFlip всегда представляет собой прямоугольную сетку текста (все строки одинаковой длины), размером не менее 1 × 1, содержащую только символы ./\<>^V. ( .используется для видимости, а не для пробела.) Семантически BackFlip, который мы здесь используем, идентичен оригинальной спецификации .

Указатель инструкций (IP) в BackFlip всегда начинается слева от верхнего левого угла программы, направляясь вправо. Есть три типа команд, с которыми он может столкнуться:

  1. .это неоперация. IP продолжается в том же направлении, в котором он шел. Без операции остается без операции.

  2. /и \являются зеркалами. Они отражают IP в направлении, указанном их углом, затем они превращаются в зеркало другого типа .

    • Например, если IP направляется в a \, он начинает двигаться вверх, а не влево, и \становится a /.
  3. <, >, ^, И Vявляются стрелки. Они перенаправляют IP-адрес в указанном направлении, а затем превращаются в стрелки, указывающие направление, в котором появился IP-адрес (в противоположном направлении от IP-адреса) .

    • Например, если IP направляется вниз >, он начинает двигаться вправо, а не вниз, и >становится ^так, потому что это направление, откуда пришел IP.

Программа BackFlip завершается, когда IP выходит за границы, то есть выходит из сетки. Оказывается, все программы BackFlip в конце концов заканчиваются, потому что бесконечные циклы невозможны. (Вы можете предположить, что это правда.)

Ваша задача в этой задаче состоит в том, чтобы написать программу или функцию, которая принимает программу BackFlip и выводит количество ходов, которые указатель инструкций совершил до завершения программы. То есть, сколько шагов IP делает в ходе работы программы? Это включает в себя начальный шаг в сетке и последний шаг от нее.

Например, указатель инструкции выполняет 5 шагов в тривиальной сетке ....:

 ....  <- empty 4×1 grid
012345 <- step number of the IP

Итак, вывод .... есть 5.

В более сложной сетке 4 × 2

\...
\.><

IP выходит из сетки на своем 9-м шаге, поэтому вывод 9:

step  grid  IP position (@)
0     \...  @....
      \.><   ....

1     \...   @...
      \.><   ....

2     /...   ....
      \.><   @...

3     /...   ....
      /.><   .@..

4     /...   ....
      /.><   ..@.

5     /...   ....
      /.<<   ...@

6     /...   ....
      /.<<   ..@.

7     /...   ....
      /.><   .@..

8     /...   ....
      /.><   @...

9     /...   ....
      \.><   ....
             @

Самый короткий код в байтах побеждает.

Вы можете принять ввод как массив строк или матрицу символов вместо многострочной строки, если хотите, но вы должны использовать символы ./\<>^V(не целочисленные коды операций). Вы можете использовать пространство вместо. если предпочитаете. Это хорошо, если такие символы, как например, \необходимо экранировать при вводе. Вывод всегда является целым числом больше одного.

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

....
5

\...
\.><
9

.
2

..
3

.
.
2

\
2

^
2

.^.
3

<.
2

\\
\/
7

>V
^<
6

>\
>/
6

\><
2

\><
\><
7

\><
\><
\><
12

\.V.
\.\<
5

\.V.
\./<
9

V./\
V./\
>./<
..\/
14

\V..
.^..
\/><
.V..
.^..
20

\.V.V.
\./.\<
.>\<..
..^.^.
31

\.V.V.V.
\./>/.\<
.>\>\<..
..^.^.^.
69

\.V.V.V.V.
\./>/>/.\<
.>\>\>\<..
..^.^.^.^.
145

\.V.V.V.V.V.V.V.V.V.V.
\./>/>/>/>/>/>/>/>/.\<
.>\>\>\>\>\>\>\>\>\<..
..^.^.^.^.^.^.^.^.^.^.
9721
Кальвин Хобби
источник
1
Это такой позор, что вы не можете сделать решение BackFlip для этого ...
HyperNeutrino
Запутался насчет зеркал ... делает / переворачивает направления влево => вверх и вверх => влево?
officialaimm
1
@officialaimm Если направиться налево /, IP поднимется, а вверх /- IP, как если бы мяч отскакивал от стены. (Но помните, что /изменения коснулись после того, как IP коснулся его.)
Увлечения Calvin
почему '\\' <LF> '\ /' равно 7 вместо 6?
17

Ответы:

3

JavaScript (ES6), 158 байт

f=(a,x=0,y=0,d=3)=>a[x]&&(c=a[x][y])?(a[x][y]=c=='.'?c:c=='/'?(d^=3,'\\'):c=='\\'?(d^=1,'/'):'v>^<'[d][d='^<v>'.search(c),0],f(a,d<3?x+d-1:x,d?y+d-2:y,d)+1):1

Разработано независимо от ответа @ tsh, хотя поразительно похоже.

Сопоставление направлений ^<v>с целыми числами 0-3 определяется тем, что .search('^')возвращает 0, поскольку ^является метасимволом регулярного выражения.

Нил
источник
Я чувствую себя так обоснованно избитым. Я был совершенно смущен в конце, пока не понял, что x и y перевернуты по сравнению с тем, что я ожидал.
Орджан Йохансен,
@ ØrjanJohansen Это хороший момент; возможно, я должен поменять местами x с y, чтобы его было легче понять.
Нил
2

Хаскелл , 333 325 байт

РЕДАКТИРОВАТЬ:

  • -8 байт: сделано без fточек и объединено в b.

bберет список Strings и возвращает Integer.

data C a=C{c::a->(a,C a)}
b g=[0,0]#([0,1],map(maybe(C$m 1)C.(`lookup`zip"./^>V<"[n,m(-1),a[-1,0],a[0,1],a[1,0],a[0,-1]]))<$>g)
[y,x]#(d,g)|g&y||g!!0&x=1|n@([f,e],_)<-(($d).c)?x?y$g=1+[y+f,x+e]#n
l&i=i<0||i>=length l
(f?i)l|(p,a:r)<-splitAt i l=(p++).(:r)<$>f a
n d=(d,C n)
a v d=(v,C$a$(0-)<$>d)
m s[d,e]=([s*e,s*d],C$m(-s))

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

Как это устроено

  • C aэто тип данных, используемый потому, что Haskell не позволит типу быть рекурсивным, не объявив его явно. Cтакже является конструктором обёртывания и cего соответствующей функцией распаковки. Используется только с a=[Int].
    • Тип C [Int]представляет команду ячейки как функцию, которая принимает [Int]аргумент direction ( ) и возвращает пару нового направления и нового C [Int]значения.
  • bэто основная функция. Он преобразует каждый символ в Cзначение, а затем вызывает #.
    • g это сетка в виде списка строк.
    • Поскольку \необходимо экранировать и поэтому это самый длинный символ, который нужно упомянуть, его результат вместо этого используется в качестве значения по умолчанию для поиска в списке.
  • #запускает основное моделирование, проверяет границы &и генерирует новые сетки с ?. [y,x]текущая позиция, dтекущее направление и gтекущая сетка. [f,e]является следующим направлением и nявляется его парой и следующей сеткой.
  • l&iпроверяет, находится ли индекс iза пределами списка l. (Возвращается Trueза пределы, поскольку это позволяет избежать фиктивного состояния охраны в# .)
  • Когда f(l!!i)==(d,x), (f?i)l==(d,m)где mнаходится список lс iзамененным элементом th наx .
    • Технически (?i)это более общий объектив, фокусирующийся на i-м элементе списка, в данном случае используемый с (,) [Int]экземпляром функтора.
  • n это функция, представляющая точку.
  • a vэто функция , представляющая стрелу в направлении v.
  • m sявляется функцией, представляющей зеркало; s==1для \\и s==-1для /.
Орджан Йохансен
источник
1

JavaScript, 172 байта

f=(a,d=3,x=0,y=0,n=1)=>(p=a[y]||[],q=p[x])?(p[x]=~(t='^<V>'.indexOf(q))?'^<V>'[d^2]:q=='/'?(t=3-d,'\\'):q=='\\'?(t=d^1,'/'):(t=d,q),f(a,t,x+(t&1&&t-2),y+(~t&1&&t-1),n+1)):n

Но я не могу проверить последний тестовый пример, так как у меня переполнение стека на моей машине. (должен работать, если есть машина с большим оперативной памятью)

Мы используем номер для направления:

  • 0: ^
  • 1: <
  • 2: V
  • 3:>

Позвольте dбыть номером направления ...

  • если мы встретим '/', нам нужно d = 3 - d;
  • если мы встретим '\', нам нужно d = d ^ 1;
  • если мы встретим '^ <V>', нам нужно d = '^ <V>'. indexOf (примечание)

Пусть (x, y)будет текущее положение, следующее положение: x+(t&1&&t-2),y+(~t&1&&t-1)

Замечания:

Функция принимает один параметр в следующем формате:

[ [ '\\', '.', 'V', '.', 'V', '.', 'V', '.', 'V', '.' ],
  [ '\\', '.', '/', '>', '/', '>', '/', '.', '\\', '<' ],
  [ '.', '>', '\\', '>', '\\', '>', '\\', '<', '.', '.' ],
  [ '.', '.', '^', '.', '^', '.', '^', '.', '^', '.' ] ]

Проверьте это здесь

f=(a,d=3,x=0,y=0,n=1)=>(p=a[y]||[],q=p[x])?(p[x]=~(t='^<V>'.indexOf(q))?'^<V>'[d^2]:q=='/'?(t=3-d,'\\'):q=='\\'?(t=d^1,'/'):(t=d,q),f(a,t,x+(t&1&&t-2),y+(~t&1&&t-1),n+1)):n

    ;k=x=>x.split('\n').map(t=>t.split(''));
<textarea id=v>\.V.V.V.V.
\./>/>/.\<
.>\>\>\<..
..^.^.^.^.</textarea><br/><button onclick="r.textContent=f(k(v.value))">Solve</button>
<p>Result: <output id=r></output></p>

ТТГ
источник
Просто документально, я получаю Uncaught RangeError: Maximum call stack size exceededс 16 ГБ оперативной памяти.
Зеб Маккоркл
1
@ZebMcCorkle ага, просто узнайте, что «используйте строгий», и некоторые varобъявления заставляют его пройти последний
тестовый
1

C 232 221 байт

d,n,t,m[4]={1,-1};char*w="><^V/\\.",*P;main(o,v)char**v;{for(P=v[1],m[2]=-(m[3]=strchr(P,10)-P+1);P>=v[1]&&P<strchr(v[1],0)&&*P^10;++n)*P=w[((o=d,t=strchr(w,*P)-w)<4)?d=t,o^1:(t<6)?d^=t-2,9-t:6],P+=m[d];printf("%d",n+1);}

Принимает ввод в первом аргументе, печатает результат. Требуется, чтобы ввод содержал как минимум 1 символ новой строки (поэтому, если есть только 1 строка, он должен заканчиваться символом новой строки)

Пример использования:

./backflip '....
';

Сломать:

d,                                          // Direction
n,                                          // Step counter
t,
m[4]={1,-1};                                // Movement offsets
char*w="><^V/\\.",                          // Command lookup
*P;                                         // Cursor location
main(o,v)char**v;{
    for(P=v[1],                             // Begin at 0,0
        m[2]=-(m[3]=strchr(P,10)-P+1);      // Find width of grid
        P>=v[1]&&P<strchr(v[1],0)&&*P^10;   // While inside grid:
        ++n)                                //  Increment step
        *P=w[                               //  Update the current cell
            ((o=d,t=strchr(w,*P)-w)         //  (store current direction & command)
              <4)?d=t,o^1:                  //   If <>^V, write backflip & set dir
            (t<6)?d^=t-2,9-t:               //   If / or \, write flip & bounce
            6],                             //   If ., write unchanged & continue
        P+=m[d];                            //  Move
    printf("%d",n+1);                       // Print result
}
Дейв
источник
1

Python 3 , 286 байт

[f () принимает входные данные в виде {(0,0):'/',(0,1):'.'} поэтому я также написал функцию g () для преобразования массива строк в эту форму]

def f(r):
 x=y=0;d='>';s=1
 while 1:
  try:c=r[y,x];m='>^<V'.find(d)
  except:break
  if(c=="\\"):d='V<^>'[m];r[y,x]="/"
  elif(c=="/"):d='^>V<'[m];r[y,x]="\\"
  elif(c!="."):r[y,x]='<V>^'[m];d=c
  x+=1if(d=='>')else-1if(d=='<')else 0;y+=1if(d=='V')else-1if(d=='^')else 0;s+=1
 return s

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

officialaimm
источник