Решить проблему остановки для Befinge

29

Давайте определим простой 2D-язык, который мы дадим невероятно оригинальному названию befinge . У Бефинге есть 5 инструкций:

  • <>^v, как и в большинстве двумерных esolangs, перенаправьте указатель инструкции в их соответствующих направлениях.
  • . это неоперация.

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

Приостановление:

>.v
..<

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

>....v
..v..<
..>v..
^..<..

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

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

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

Приостановление:

.

v>
>^

....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.

v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<

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

>..v
^..<

>v<
v<.
>v.
v<.
>.^

>.>.>.v
.><.<.<

Это , поэтому выигрывает самая короткая (в байтах) программа.

Esolanging Fruit
источник
А как насчет 아희 (Aheui) ?
JungHwan Мин
Подойдут некоторые тестовые случаи, когда не каждая стрелка будет нажата.
xnor
Тьюринг доказал, что проблема Остановки не разрешима ни для одного языка Turing-Complete, поэтому мне пришлось придумать поддельную проблему, не являющуюся полной по Тьюрингу. Язык, который всегда в конечном итоге останавливается, не является полным по Тьюрингу.
Esolanging Fruit
1
У нас также нет примеров, когда путь делает поворот не на 90 градусов, как >..>.или ><.
xnor
2
@PyRulez Потому что я хотел, чтобы обработка направленного движения была частью проблемы.
Esolanging Fruit

Ответы:

4

ES6 (JavaScript), 111101 байт

РЕДАКТИРОВАТЬ: изменил выходные значения на истину и ложь , вместо Y и N , чтобы сбрить еще 10 байтов

Golfed

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

Тест

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search`\n`+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0  

//Alphabet Map
tr={
'<':'h',
'>':'l',
'^':'k',
'v':'j',
'.':'q',
'\n':'\n'
};

//Test
T=(I,A)=>{
console.log({"Y":"#Halting","N":"#Non-Halting"}[A]);
console.log("I=\n",I,"\nF(I)=",O=F([...I].map(s=>tr[s]).join('')));
console.log('NY'[O*1] == A ? "OK !" : "NOT OK !");
}

//Halting
T(
`>.v
..<`
,'Y');

//Non-Halting
T(
`>....v
..v..<
..>v..
^..<..`
,'N');

//Halting
T(
`.`
,'Y')

//Halting
T(
`v>
>^`
,'Y');

//Halting
T(
`....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.`
,'Y');

//Halting
T(
`v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<`
,'Y');

//Non-Halting
T(
`>..v
^..<`
,'N');

//Non-Halting
T(
`>v<
v<.
>v.
v<.
>.^`
,'N');

//Non-Halting
T(
`>.>.>.v
.><.<.<`
,'N');

Пример вывода

#Halting
I=
>.v
..< 
F(I)= true
OK !    

#Non-Halting
I=
>....v
..v..<
..>v..
^..<.. 
F(I)= false
OK !

#Halting
I=
 . 
F(I)= true
OK !

#Halting
I=
v>
>^ 
F(I)= true
OK !

#Halting
I=
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<. 
F(I)= true
OK !

#Halting
I=
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^< 
F(I)= true
OK !

#Non-Halting
I=
>..v
^..< 
F(I)= false
OK !

#Non-Halting
I=
>v<
v<.
>v.
v<.
>.^ 
F(I)= false
OK !

#Non-Halting
I=
>.>.>.v
.><.<.< 
F(I)= false
OK !
дирижабль
источник
Вы не можете просто использовать Yи в Nкачестве вывода, как в JavaScript, они оба правдивы .
ბიმო
3

Python 2 , 116 105 байт

x=1
X=Y=y=0
H=[]
G=input()
while(X,Y,x,y)not in H:H+=[(X,Y,x,y)];C=ord(G[Y][X]);x=C%3-1;y=C%5-1;X+=x;Y+=y

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

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

> G
< B
v C
^ F
. L

Например, третий пример остановки превращается в ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. Вывод осуществляется через код завершения, 0 (успех) для отсутствия остановки и 1 (ошибка) для остановки. Любые советы или хитрости приветствуются.

nedla2004
источник
2

Befunge-98 (PyFunge) , 217 209 200 байт

#v10dpf1dp12dp3dpk
 >#v~:a-#v_$10dp1dg1+1dp >
v  >10dp;>0dg1dgp0dg1+0dp^;f1dp
>0dg1dgg:'^-#v_n1-v
^<v01_v#!->':<
  <   >:'<-#v_01-0>   v
v^pd1+gd3gd1[:'v-#v_01>3dp2dpndg1dgp
>0dg2dg+0dp ^ @.!;>:'.-#;_

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

Для того, чтобы остановить проблему, нужно найти решение. Возвращает 0 для правды и 1 для фальси. Помещает ввод в сетку, начиная с 1,15, а затем перемещается сверху, заменяя стрелки нулями. Как только мы достигаем нуля, мы знаем, что он зацикливается. Что-нибудь кроме> <^ v. и ноль считается для остановки программы, которая включает в себя границу пробелов, которую мы получаем вокруг программы, помещая ее в сетку с небольшим смещением.

Один из простых способов избавиться от нескольких укусов - использовать числа вместо> <^ v. но я не чувствую, что это того стоит.

Дэвид
источник
A befinge halting problem needs a befunge solution.Точно. +1
Draco18s
1

Turtlèd , 146 байт

!u[*.[ r+.]l[ l]dr_+]#*#[ u]d[ (.r)(>.r{.r}@>)(v.d{.d}@v)(<.l{.l}@<)(^.u{.u}@^)(*@0' )],@1(0@0)(v' d)(<' r)(>' l)(^' d)[ u]d[ l]r[ [ r]l[ ' l]dr],

Эта программа использует ввод-вывод по-разному: пожалуйста, завершите каждую строку пробелом, включая последнюю. Turtlèd не любит переводы строк, поскольку он использует сетку для второго измерения символов.

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

0 для циклов навсегда, 1 для остановок.

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

Он записывает входные данные в сетку, затем фактически следует пути, по которому стрелки делают вокруг сетки, заменяя каждую стрелку на *, сохраняя направление в char var. Если он встречает *, стрелку, которую он ударил ранее, программа не остановится, поэтому она устанавливает char var в значение 0, выход из цикла. В противном случае он достигнет конца сетки и выйдет из цикла. Он напишет символ вар. Если он достигает конца сетки, он использует направление, сохраненное в char var, чтобы вернуться к сетке, и устанавливает char var в значение 1, для остановок. Если char var был на самом деле 0, а не направление, ему не нужно возвращаться, так как он все еще там, и он устанавливает его обратно 0. Он очищает сетку, затем записывает char var, 1для остановок, иначе 0.

Разрушаемый Лимон
источник
1

JavaScript (ES6), 158 127 байт

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>c<'~'?(c>'.'&&(a[y][x]='~',d=(c=='>')-(c=='<'),e=(c=='v')-(c=='^')),f(a,x+d,y+e,d,e)):!c

Принимает ввод в виде двумерного символьного массива и возвращает trueдля остановки и falseбесконечного цикла. Работает, устанавливая символы посещенного направления в ~s, поскольку он рекурсивно обходит их. Редактировать: Сохраненные 31 байт путем обновления моего вектора направления перед повторением.

Злоупотребление инструкцией символов ( 1=^ 4=< 5=. 6=> 9=v) приводит меня к 101 байту:

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>+c?(c-5&&(a[y][x]='0',d=~-c%4,e=~-(c>>2)),f(a,x+d,y+e,d,e)):!c
Нил
источник
> Принимает ввод как двумерный символьный массив. Разрешен ли ввод в другом формате? (переход от плоской строки к массиву тоже занимает байты).
Цеппелин
@zeppelin Я верю, что это разрешено. См. Например, meta.codegolf.stackexchange.com/q/2214/17602 .
Нил
ReferenceError: f не определено
l4m2
@ l4m2 Бах, я сделал это снова, я включил f=в число байтов, но не код ...
Нил
1

SmileBASIC, 158 145 байт

Если одна и та же стрелка встречается более одного раза, программа никогда не остановится. Когда указатель инструкции пропускает стрелку, он заменяется другим символом, который заставит функцию возвращать 0, если она будет достигнута снова. Если IP выходит за пределы, он возвращает 1.

DEF H P@L
C=VAL(P[Y][X])IF C>8THEN?0RETURN
IF C THEN D=C-1P[Y][X]="9
X=X+!D-(D==1)Y=Y+(D==2)-(D>2)IF X+1&&Y+1&&Y-LEN(P)&&X-LEN(P[0])GOTO@L
?1
END

Принимает ввод как массив строк. <any non-digit chracter>, 1, 2, 3, 4= ., >, <, v,^

12Me21
источник
0

Python 2, 182 байта

m,v,d,x,y=input(),[],'>',0,0
try:
 while 1:
  if[x,y]in v:print 0;break
  c=m[y][x]
  if c!='.':d=c;v+=[[x,y]]
  if d in'><':x+=[-1,1][d=='>']
  else:y+=[-1,1][d=='v']
except:print 1

Принимает массив строк в качестве входных данных. Мне нужно больше играть в гольф, но сейчас настало время подчеркнуть выборы.

Ungolfed:

input = input()

visited = [  ] 

dir = ">"
x=0
y=0

try:
    while True:
        if[x,y]in visited:print False;break
        char=input[y][x]
        if char!=".":
            dir=char
            visited+=[[x,y]]

        if dir==">":
            x+=1
        if dir=="<":
            x-=1
        if dir=="v":
            y+=1
        if dir=="^":
            x-=1
except:
    print True
Даниил
источник
эй, что если вы взяли основную часть из попытки и поместили только c = m [y] [x] в попытку и исключение? это также позволит вам заменить разрыв на 1/0, а также уменьшить отступы.
Разрушаемый Лимон
1
[-1,1][d=='v'] -> 2*(d>'>')-1и [-1,1][d=='>'] -> 2*(d>'<')-1сохранить в общей сложности 6 байтов.
Каде
Неправильный ответ["<>"]
feersum
0

Clojure, 143 байта

#((fn[p v i s](if-let[v({\> 1\< -1\^(- s)\. v\v s}(get % p))](if(neg? i)1(recur(+ p v)v(dec i)s))))0 1 1e9(+(count(take-while(set"<>v^.")%))1))

Функция с 4 аргументами состояния: положение p, скорость v, индекс шага iи размер одной строки s. Возвращает, 1если мы не вышли за пределы в 10 ^ 9 шагов и nilиначе. На самом деле , сколько шагов мы должны проверить , чтобы убедиться, (count %)? Я думаю, что это больше, чем тот же NOP, который можно пройти по горизонтали и вертикали.

Может быть вызвано так (принимает нормальные строки в качестве аргументов, getвозвращает nilкогда выходит за пределы):

(def f #( ... ))
(f ">....v\n..v..<\n..>v..\n^..<..")
(f "v>\n>^")
(f "....v....\n....>...v\n.^..<....\n.......v<\n.......v.\n....^..<.")

Переходы состояний (+1, -1, + s, -s) кодируются в словаре {\> 1\< -1\^(- s)\. v\v s}.

NikoNyrh
источник
В четыре раза должно быть достаточно количества символов сетки: если указатель возвращается к одному и тому же символу с тем же входящим направлением, то он находится в бесконечном цикле.
Грег Мартин
0

Python 2/3, 201 192 байта

def f(x):
 X=Y=b=0;a=1;D={}
 while len(x)>Y>-1<X<len(x[Y]):
  try:
   a,b={'>':(1,0),'^':(0,-1),'<':(-1,0),'v':(0,1)}[x[Y][X]]
   if(X,Y)in D:return 0
  except:0
  D[X,Y]=0;X+=a;Y+=b
 return 1

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

Дает правильный ответ для ["<>"]

ceilingcat
источник
Я считаю, что вы можете сохранить несколько байтов, перейдя от функции к полной программе. Вы можете заменить def f(x):на x=input()0 байтовой разницей, затем удалить лишние отступы (-8 байт), а затем заменить return xна exit(x)(разрешено для каждого мета-консенсуса ) еще на 2 байта. В любом случае, хорошее решение!
Амфибологическое
0

Ява, 477

Я знаю, что это не выигрыш, n = и, вероятно, может быть больше в гольфе, но он подразумевает аналогичный метод относительно того, что используют другие ответы, но этот использует hashmap для выполнения поиска. В качестве входных данных используются символы> <^ v и все, что не указано для параметра no op. Ввод поступает через аргументы.

GOLFED

import java.util.*;interface B{static void main(String[]a){HashMap<String,Byte>h=new HashMap<>();int x,y=0;for(String s:a){x=0;for(char c:s.toCharArray()){if("><^v".indexOf(c)>-1)h.put(x+","+y,(byte)c);x++;}y++;}x=0;y=0;int d=0;int D=0;while(x>-1&&x<a[0].length()&&y<a.length&&y>-1){Byte v=h.get(x+","+y);if(v!=null){if(v==0){System.out.print(0);return;}d=(v<85)?"<>".indexOf(v)*2-1:0;D=(v>84)?"^v".indexOf(v)*2-1:0;}h.replace(x+","+y,(byte)0);x+=d;y+=D;}System.out.print(1);}}

UNGOLFED

импорт java.util. *;

interface B{
    static void main(String a[]) {
        HashMap<String, Byte> h = new HashMap<>();
        int x, y = 0;
        for(String s : a) {
            x = 0;
            for(char c : s.toCharArray()) {
                if ("><^v".indexOf(c) > -1) h.put(x + "," + y, (byte) c);
                x++;
            }
            y++;
        }
        x = 0;
        y = 0;
        int d = 0;
        int D = 0;
        while(x > -1 && x < a[0].length() && y < a.length && y > -1) {
            Byte v = h.get(x + "," + y);
            if(v != null) {
                if(v == 0) {System.out.print(0); return;}
                d = (v < 85) ? "<>".indexOf(v)*2-1 : 0;
                D = (v > 84) ? "^v".indexOf(v)*2-1 : 0;
            }
            h.replace(x + "," + y, (byte) 0);
            x += d;
            y += D;
        }
        System.out.print(1);
    }
}

Объяснение скоро!

KrystosTheOverlord
источник
Одна маленькая вещь: вы можете изменить , String a[]чтобы String[]aи опускать пробел.
Esolanging Fruit
Вы также можете использовать varво многих местах, если вы используете Java 10.
Esolanging Fruit
410 байт
floorcat