В духе Решить проблему остановки для Befinge , давайте определим еще один 2D-язык под названием Modilar SNISP . Modilar SNISP имеет следующие шесть инструкций:

• \ направляет указатель инструкции следующим образом:
  • если приблизиться сверху, идите направо;
  • если приблизиться справа, поднимитесь;
  • если приблизиться снизу, идите налево;
  • если подходить слева, спуститься вниз.
• / направляет указатель инструкции следующим образом:
  • если приблизиться сверху, идите налево;
  • если приблизиться слева, поднимитесь;
  • если приблизиться снизу, идите направо;
  • если приблизиться справа, спускайтесь вниз.
• ! пропускает следующую инструкцию
• @ выдвигает местоположение и направление IP на стек вызовов.
• #извлекает IP-адрес и направление из стека вызовов и восстанавливает их, затем пропускает следующую инструкцию. Если стек вызовов пуст, выполнение останавливается.
• . ничего не делает.

Указатель инструкций начинается в верхнем левом углу и идет вправо. Если он когда-либо покидает игровое поле, выполнение останавливается.

Modilar SNISP не может быть более мощным, чем КПК , потому что его единственным источником неограниченного хранилища является стек (стек вызовов) с конечным алфавитом (набор всех пар IP (местоположение, направление)). Проблема остановки решаема для КПК , поэтому эта задача всегда должна быть возможной.

Соревнование

Ваша цель - написать программу, которая принимает матрицу символов, представляющих программу Modilar SNISP, и возвращает один из двух отдельных выходных данных в зависимости от того, останавливается она или нет.

Это код-гольф , поэтому самая короткая действительная программа (измеряется в байтах выигрывает ).

Характеристики

• Способ, которым вы берете матрицу символов, является гибким: допустимы строка, разделенная новой строкой, массив строк, массив массивов символов, двумерный массив символов, плоский массив символов с целым числом, представляющим ширину, и т. Д. Тестовые случаи выбирают первый из этих вариантов.
• Вы можете предположить, что входная матрица будет прямоугольной (поэтому вам не придется заполнять короткие строки) и будет иметь ненулевую длину и ширину.
• Вы можете выбрать любые два различных выхода, а не только правдивость / ложь.
• Можно предположить , что входная матрица будет состоять только из допустимых команд ( \, /, !, @, #, и. ).
• Когда команда говорит «пропустить следующую инструкцию», вы можете предположить, что будет следующая команда, которую нужно пропустить. В частности, его никогда не встретят в обстоятельствах, когда (1) он лежит на краю игрового поля и (2) IP движется перпендикулярно этому краю, так что «следующая инструкция» после него будет находиться за пределами игрового поля.

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

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

function htmlEscape(t){let i=document.createElement("span");return i.innerText=t,i.innerHTML}function tick(){snisp.tick(),snisp.update()}function run(){runButton.style.display="none",stopButton.style.display="",code.style.display="none",executionArea.style.display="",snisp.initialize(),intervalId=setInterval(tick,INTERVAL_MS)}function stop(){runButton.style.display="",stopButton.style.display="none",code.style.display="",executionArea.style.display="none",clearInterval(intervalId)}let TICKS_PER_SECOND=5,INTERVAL_MS=1e3/TICKS_PER_SECOND,runButton=document.getElementById("run-button"),stopButton=document.getElementById("stop-button"),code=document.getElementById("code"),executionArea=document.getElementById("execution-display"),intervalId,snisp={x:null,y:null,direction:null,callStack:null,stopped:null,playfield:null,padRows:function(){let t=Math.max(...this.playfield.map(t=>t.length));for(let i=0;i<this.playfield.length;i++)this.playfield[i]=this.playfield[i].padEnd(t,".")},initialize:function(){this.x=0,this.y=0,this.direction="right",this.callStack=[],this.stopped=!1,this.playfield=code.value.split("\n"),this.padRows(),this.update()},getCurrentChar:function(){let t=this.playfield[this.y];if(void 0!=t)return t[this.x]},backslashMirror:function(){let t={up:"left",right:"down",down:"right",left:"up"};this.direction=t[this.direction]},slashMirror:function(){let t={up:"right",right:"up",down:"left",left:"down"};this.direction=t[this.direction]},forward:function(){switch(this.direction){case"up":this.y-=1;break;case"down":this.y+=1;break;case"left":this.x-=1;break;case"right":this.x+=1;break;default:throw"direction is invalid"}},pushState:function(){this.callStack.push({x:this.x,y:this.y,direction:this.direction})},restoreState:function(){let t=this.callStack.pop();void 0!=t?(this.x=t.x,this.y=t.y,this.direction=t.direction):this.stopped=!0},tick:function(){if(this.stopped)return;let t=this.getCurrentChar();if(void 0!=t){switch(t){case"\\":this.backslashMirror();break;case"/":this.slashMirror();break;case"!":this.forward();break;case"@":this.pushState();break;case"#":this.restoreState(),this.forward()}this.forward()}else this.stopped=!0},generatePlayfieldHTML:function(t,i){let e=[];for(let n=0;n<this.playfield.length;n++){let s=[],l=this.playfield[n];for(let e=0;e<l.length;e++){let a=htmlEscape(l[e]);e==t&&n==i&&(a='<span class="highlight">'+a+"</span>"),s.push(a)}e.push(s.join(""))}return e.join("<br>")},update:function(){let t=[];for(let i=0;i<this.callStack.length;i++){let e=this.callStack[i];t.push(this.generatePlayfieldHTML(e.x,e.y))}t.push(this.generatePlayfieldHTML(this.x,this.y));let i=t.join("<br><br>");executionArea.innerHTML=i}};

#code{font-family:monospace;}#execution-display{font-family:monospace;white-space:pre;}.highlight{background-color:yellow;}

<b>Code:</b><br/><textarea id="code" width="300" height="300"></textarea><br/><button id="run-button" onclick="run()">Run</button><button id="stop-button" onclick="stop()" style="display: none;">Stop</button><br/><div id="execution-display"></div>

Негольфированную форму можно найти здесь .

запинающийся

.

Самая маленькая возможная программа. Выходит правильно

\\
\/

Обворачивается вокруг программы и выходит на вершину.

.\./.\
.\!/./

Идет в петле. Извилистая часть трассы в двух разных направлениях.

@\!/#
.\@/#

Использует все шесть команд.

@.@.@.@.@.@.@.@.@.#

Время выполнения этой программы экспоненциально по количеству повторений @., но оно все равно останавливается.

Non-Приостановление

!/\
.\/

Я считаю, что это самый короткий бесконечный цикл.

@!\\#/@\!\
//@//.#./.
.\#.!\./\.
#.\!@!\@//
/..@.@\/#!
\.@.#.\/@.

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

.!/@.@.@.@.@.\
/.@.@.@.@.@.@/
\@.@.@.@.@.@.\
/.@.@.@.@.@.@/
.@\@.@.@.@.@.\
\.@.@.@.@.@.@/

Создает стековые фреймы, но ни один из них не возвращается.

Python 3 , 639 байтов, 630 байтов, 593 байта

def e(I):
 m=[(0,-1),(0,1),(1,1),(1,-1)];a=lambda i:(tuple(i[0]),i[1]);b=lambda s,q:s.s==q.s and s.S&q.S==q.S
 class O():i=[[0,0],2];S=[];A={}
 def z():d=m[O.i[1]];O.i[0][d[0]]+=d[1]
 def y():O.i=O.S.pop();z()
 def x():O.i[1]=[3,2,1,0][O.i[1]]
 def w():O.i[1]=[2,3,0,1][O.i[1]]
 def v():O.S+=[[O.i[0][:],O.i[1]]]
 while 1:
  p=O();p.s=a(O.i);p.S={a(i)for i in O.S};l=O.A.setdefault(p.s,[]);c=any((b(p,s)for s in l));l+=[p];e=O.i[0];d=not((0<=e[0]<len(I))and(0<=e[1]<len(I[0])))or((x,w,z,v,lambda:len(O.S)==0 or y(),lambda:0)["\\/!@#.".find(I[e[0]][e[1]])]()==1);z()
  if d!=c:return not c or d

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

Я чувствую, что это скорее минимизированный источник, чем гольф ... Я уверен, что есть лучший способ добраться туда.

Программа работает как полный переводчик для языка. Останавливается либо когда:

1. Выходим из программы
2. Мы обнаруживаем, что находимся в цикле.

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

Редактировать 1 - благодаря Герману L за вырезание «паса». Также вырезать «Правда».

Редактировать 2 - лямбда-ified некоторые функции. Уменьшено количество возвратов. Возвращает «True» для завершения и «False» для не завершения. Использовать существующий O-класс в качестве объекта отслеживания, устраняя необходимость в N-классе.

JavaScript (ES6), 258 254 байта

p=>(d=>{for(x=y=r=k=1,s=[],v={};w=[--x,--y,d],c=1<<"\\!@/#".indexOf(q=(p[y]||0)[x]),q&&r&&(e=v[w]?v[w].some(u=>!s.some(t=>u+0==t+0)):1);x+=d>>2,y+=d&3)v[w]=[...s],k=k?c&9?d=c&1?d/4|4*d&12:(d+5)%10:c&4?s.push(w):c&16?(r=s.pop())&&!([x,y,d]=r):c-2:1})(9)|e

Ожидает непустую программу в виде массива строк, где каждый элемент представляет строку Modilar SNISP. Выводится, 1если данная программа останавливается, и в 0противном случае.

Та же логика, что и у @ machina.widmo . Несколько неудачных попыток альтернативных методов привели меня к выводу, что они все равно будут производить более длинный код!

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

объяснение

Подобно другому ответу, эта функция завершается с:

• 1 если программа останавливается (например, IP удаляется с сетки или появляется пустой стек)
• 0если IP-адрес достигает позиции, которую он уже посетил, движется в том же направлении и с расширенным набором стека, присутствовавшим в предыдущем посещении.

Почему в том же направлении?

 1
!\/

Вышеуказанная программа останавливается, но попадает в ту же позицию (символ 1), с идентичным стеком, но в другом направлении.

Почему суперсет, а не просто размер стека?

  ab4
!/@@.\
.\..#/

Это также останавливает, и IP четыре раза попадает в символ 4 с непротиворечивого направления со следующими состояниями стека ( *указывает на вершину стека):

• размер = 2 [a, b] *
• размер = 1 [а] *
• размер = 1 [б] *
• размер = 0 [] *

Как работает переводчик

Инструкции ( q) переводятся в двоичный ( c) следующим образом (со всеми другими символами .или иным образом, служа в качестве nops):

1 2 4 8 16
\ ! @ / #

Направление ( d) представляется в виде битового поля:

9 -> right : 1001
1 -> left  : 0001
6 -> down  : 0110
4 -> up    : 0100

Зеркала ( \/) изменяют направление:

\: 6-> 9 9-> 6 4-> 1 1-> 4

d/4 | 4*d&12

/: 1-> 6 6-> 1 4-> 9 9-> 4

(d+5) % 10

Новые направления трансформируют позицию:

x += d>>2 - 1

y += d&3 - 1

Другие глобальные переменные

• x, y: Позиция IP
• r: содержит значение, извлеченное из стека
• k: ложно, если пропущена следующая инструкция (например, из !#)
• s: stack
• v: кэширует посещенные позиции, направление, снимок стека
• w: [x, y, d]значение хранится в стеке и используется в качестве значения ключа дляv
• e: falsy, если программа не останавливается из-за совпадения кэша

Ungolfed

p => (d => {                                                  // set initial direction and avoid a verbose `return` statement
    for (
        x = y = r = k = 1,
        s = [],
        v = {};
        w = [--x, --y, d],                                    // decrement positions early so that x,y 
                                                              // do not require a separate assignment to 0
        c = 1 << "\\!@/#".indexOf(q = (p[y]||0)[x]),          // taking an index of undefined produces an error; using 0 does not
        q && r && (
            e = v[w]
                ? v[w].some(u => !s.some(t => u+0 == t+0))    // in order to compare two arrays, must coerce to strings
                : 1
        );
        x += d>>2,
        y += d&3
    )
        v[w] = [...s],                         // clone stack
        k = k
            ?
                c&9                            // if \ or /
                    ? d = c&1
                        ? d/4 | 4*d&12
                        : (d+5) % 10
                : c&4                          // if @
                    ? s.push(w)
                : c&16                         // if #
                    ? (r = s.pop())
                        && !([x, y, d] = r)    // destructure value in stack if any exists
                : c-2                          // 0 if !
            : 1
})(9) | e