Run Stackylogic

45

Stackylogic - это язык программирования, основанный на логике, который я создал, который принимает 0и вводит 1и выводит один 0или 1после завершения.

Программа Stackylogic состоит из строк, которые могут содержать только три символа, 01?а также ровно один <в конце одной из строк. Линии не могут быть пустыми и линия с <должна иметь по крайней мере один 0, 1, или ?перед ним.

Вот пример программы, которая (как я объясню) вычисляет NAND из двух битов:

1
?<
11
?
0

Каждая строка в программе Stackylogic считается стеком , с нижней частью слева и верхней справа. Неявно, есть пустой стек (пустая строка) перед первой строкой в ​​программе и после последней строки.

Элемент <, который мы назовем курсором , помечает стек для запуска при запуске программы Stackylogic. Выполнение программы Stackylogic происходит следующим образом:

  1. Удалите верхний символ из стека, на который в данный момент указывает курсор.

    • Если это символ ?, предложите пользователю ввести a 0или a 1и действуйте так, как если бы это был символ.
    • Если это символ 0, переместите курсор на одну стопку вверх (на строку выше текущей строки).
    • Если это символ 1, переместите курсор на одну стопку вниз (на строку ниже текущей строки).
  2. Если стек, в который перемещается курсор, пуст, выведите последнее значение, извлеченное из стека (всегда a 0или 1), и завершите программу.

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

Обратите внимание, что программы Stackylogic всегда заканчиваются, потому что они должны в конечном итоге исчерпать свои стеки.

Пример NAND

В программе NAND курсор начинается на ?:

1
?<
11
?
0

Мы будем предполагать, что пользователь вводит a 1после ?нажатия, что означает, что курсор будет перемещаться вниз, делая программу похожей на это:

1

11<
?
0

Теперь равнина 1находится на вершине стека курсора. Это правильно вытолкнуто, и курсор снова перемещается:

1

1
?<
0

Теперь предположим, что пользовательский ввод 0для ?, что означает, что курсор будет двигаться вверх:

1

1<

0

Опять же, a 1находится в стеке курсора, поэтому курсор появляется и перемещается вниз:

1


<
0

Наконец, стек курсоров пуст, поэтому 1выводится последнее значение , выводится, и программа завершается.

Это верно для ворот NAND, потому что 1 NAND 0есть 1. Это, конечно, работает для остальных трех двухбитных входов, если вы хотите проверить.

ИЛИ Пример

Эта программа Stackylogic имитирует ИЛИ ворота:

?
?<

Легко видеть, что начальный ввод 1толкает курсор к неявному пустому стеку ниже последней строки, заканчивая программу и выводя только 1что введенный.

С 00другой стороны, для ввода курсора он направляется к неявному пустому стеку вверху, заканчивая программу и выводя последний, который 0должен быть введен.

Вызов

Напишите программу или функцию, которая принимает программу Stackylogic в виде строки и запускает ее, печатая или возвращая полученный результат 0или 1.

После ?этого вы можете запросить у пользователя ввод 0или 1, или прочитать значение из предустановленной строки 0«и 1», которую вы также принимаете в качестве ввода. (Это может быть другая строка ввода для вашей программы / функции, или вы можете просто предположить, что первая или последняя строка строки программы будет входным потоком).

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

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

Больше примеров программ

ZERO
0<

ONE
1<

BUFFER
?<

NOT
1
?<
0

AND
?<
?

NAND
1
?<
11
?
0

OR
?
?<

NOR
1
?
00
?<
0

XOR(v1)
?
0
1?<
?
0

XOR(v2)
?
?<
11
?
0

XNOR(v1)
1
?
0?<
1
?

XNOR(v2)
1
?
00
?<
?

MEDIAN(v1)
1
???<
0

MEDIAN(v2)
?
1?<
??

Спасибо Мартину за медианные программы .

Кальвин Хобби
источник
Если вы хотите добавить функцию в 3-входе, вот один из способов реализации медианы: ?\1?<\??. В качестве альтернативы, вот симметричная 5-строчная реализация:?\?0\?<\?1\?
Мартин Эндер
О, я нашел еще более аккуратную реализацию 1\???<\0.
Мартин Эндер
2
Более точная реализация @ 3-входной медианной функции MartinEnder (эквивалентно функции большинства правил) хорошо обобщается. Например, 7-функция входа мажоритарного правила является 111\???????<\000.
Грег Мартин
Пусть «bizarro» программы Stackylogic $ P $ будет программой $ BP $, сформированной путем изменения порядка строк исходных программ, изменения всех 1 на 0 и наоборот (но оставляя? S и <в покое). Похоже, что вывод $ BP $ на входах $ b_1, b_2, \ dots $ является НЕ выводом $ P $ на входах $! B_1,! B_2, \ dots $. Обратите внимание, что указанные реализации AND и OR таким образом связаны с причудой, как NAND и NOR, а также две версии XOR / XNOR. Некоторые программы являются их собственным bizarro (BUFFER, NOT, MEDIAN (v1)).
Грег Мартин
1
@GregMartin Да. Я считаю, что технический термин - это двойственность .
Увлечения Кэлвина

Ответы:

15

Retina , 79 78 73 68 66 65 63 62 55 44 байта

Число байтов предполагает кодировку ISO 8859-1.

+`(.)([^_]*)\?<|(¶.*)0<|1<(¶.+)
$2$1$4<$3
1<

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

Попробуйте онлайн! (Первые две строки включают набор тестов, где каждая строка представляет собой отдельный тестовый случай, /а не перевод строки.)

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

объяснение

Окончательная версия этого на самом деле оказалась довольно простой.

+`(.)([^_]*)\?<|(¶.*)0<|1<(¶.+)
$2$1$4<$3

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

  1. Обработка ?:

    (.)([^_]*)\?<
    $2$1<
    

    Это просто берет первый символ ввода, затем сопоставляет произвольные символы, пока не найдет ?<, и помещает этот первый символ перед <(удаляя ?).

  2. Обработка 0:

    (¶.*)0<
    <$1
    

    Это соответствует строке, предшествующей a, 0<и помещает ее после <, удаляя 0. (По сути, это просто удаляет 0и перемещает <одну строку вверх.)

  3. Обработка 1:

    1<(¶.+)
    $1<
    

    Практически то же самое, за исключением того, что мы перемещаем <одну строку вниз при удалении 1. Одна важная деталь, на которую следует обратить внимание, - это использование +вместо *, то есть мы требуем, чтобы следующая строка не была пустой.

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

Если символ перед <является ?единственным способом провала совпадения, это то, что перед ним нет символа без перевода строки, но этого не может быть, потому что мы гарантируем, что всегда достаточно ввода.

Если символ в передней части <IS 0, регулярное выражение будет всегда совпадать с , так как всегда есть другая линия над текущим (который может быть пустой , разделяющую линию ввода из исходного кода).

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

Наконец, есть также возможность, <которой не предшествует ни один из ?01. Оказывается, мы можем достичь этой ситуации, только нажав a 0и двигаясь вверх к пустой строке, так что <теперь ей предшествует перевод строки.

Таким образом, когда программа завершается на a 1, <после этого все равно будет 1. Но если программа завершается на a 0, она переместится на пустую строку. Мы можем легко превратить эту информацию в желаемый результат с помощью простого этапа сопоставления:

1<

Это просто подсчитывает совпадения 1<в строке. По рассмотренному выше рассуждению это будет, 1если программа завершилась на a 1, и 0если она завершилась на a 0.

Мартин Эндер
источник
3
Вы, сэр, волшебник.
GamrCorps
Такое Regex Mch Wow
Рохан Jhunjhunwala
12

Выпуклый , 102 95 байт

Что ж, язык на основе списка стеков, закодированный на языке стеков, оказался довольно сложным. Запомните мои слова: я получу это до 100 байтов или меньше! РЕДАКТИРОВАТЬ: успех!

N/S\+{s)_'<={R:M;}{R):R;+}?}%'<-M){(æ=)s_:Q;"?10 ""l+ M):M; M(:M; W:M;A~p"S/Ë~~_!S*+tM)Q:A;}h;;

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

Ввод программы осуществляется через аргументы командной строки. Входные данные 0с и 1ев нормально (на TIO, это означает символ новой строки , разделенных в поле «ввод»).


Объяснение:

Весь код можно разбить на три части:

N/S\+

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

{s)_'<={R:M;}{R):R;+}?}%'<-

Эта часть определяет, с какой строки (или стека) начать выполнение. Он просматривает каждую строку и помещает правильный номер стека в Mпеременную.

M){(æ=)s_:Q;"?10 ""l+ M):M; M(:M; W:M;A~p"S/Ë~~_!S*+tM)Q:A;}h;;

Это самое интересное! Он непрерывно зацикливается, пока не достигнет строки, на которой есть только пробел ( " ") (символизирующий пустой стек). Если строка не пуста, она делает следующее:

  1. Вытащите последний символ из стека.
  2. Переключатель заявление:
    1. Если это символ ?, возьмите ввод и добавьте этот символ в строку.
    2. Если символ a 0, переместите указатель строки вверх на один.
    3. Если символ a 1, переместите указатель строки вниз на один.
    4. Если символ является (пробел), распечатайте последний извлеченный элемент и завершите программу.
GamrCorps
источник
6

32-битный машинный код x86, 70 байт

В шестнадцатеричном виде:

FC89E1565F31D28A07A8DF740B3C3C7511428D5C24FCEB0A5729142484C07405B20147EBE2578B3B8A17F6C2DF7414FF0B923C3F7501AC3C30750383C30883EB04EBE389CCC3

Ввод - это многострочная строка с нулевым символом в конце (разделенная переводом строки), передаваемая через ESI. Пользовательский ввод считается первой строкой. Возвращает «0» / «1» в AL.

Разборка:

fc           cld
89 e1        mov    ecx,esp
56           push   esi
5f           pop    edi                  ;EDI=ESI
31 d2        xor    edx,edx              ;EDX=0
_loop0:
8a 07        mov    al,BYTE PTR [edi]    ;AL=*EDI
a8 df        test   al,0xf5              ;AL&~0x0a==0 => separator ('\n' or '\0')
74 0b        je     _stck
3c 3c        cmp    al,'<'
75 11        jne    _loop0end
42           inc    edx                  ;For "cursor" symbol adjust stack pointer offset
8d 5c 24 fc  lea    ebx,[esp-0x4]        ;and load EBX with the address where this pointer
eb 0a        jmp    _loop0end            ;is going to be stored in the next iteration
_stck:
57           push   edi                  ;Pointer to the separator
29 14 24     sub    DWORD PTR [esp],edx  ;adjusted to point to the top of the stack
84 c0        test   al,al                ;AL==0?
74 05        je     _loop0break          ;break
b2 01        mov    dl,0x1               ;EDX can be [0..2], resets to 1
_loop0end:
47           inc    edi                  ;++EDI
eb e2        jmp    _loop0
_loop0break:
57           push   edi                  ;*EDI==0, add lower implicit empty stack
_loop1:                                  ;The actual state machine code
8b 3b        mov    edi,DWORD PTR [ebx]  ;EDI=*EBX
8a 17        mov    dl,BYTE PTR [edi]    ;DL=*EDI
f6 c2 df     test   dl,0xf5              ;DL&~0x0a
74 14        je     _loop1break          ;ZF==1 => current stack is empty
ff 0b        dec    DWORD PTR [ebx]      ;--(*EBX): pop the stack
92           xchg   edx,eax              ;AL=DL
3c 3f        cmp    al,'?'
75 01        jne    _skplods             ;AL=='?' => substitute char from the input string
ac           lodsb
_skplods:
3c 30        cmp    al,'0'
75 03        jne    _0x31                ;EBX+=AL==0?4:-4
83 c3 08     add    ebx,0x8              ;But to avoid wasting 2 bytes for the jump after the 'add'
_0x31:                                   ;add 8 and fall through to subtract 4 back
83 eb 04     sub    ebx,0x4
eb e3        jmp    _loop1
_loop1break:
89 cc        mov    esp,ecx              ;Clear the stack
c3           ret                         ;Returns '0'/'1' in AL
Зорница
источник
5

JavaScript (ES6), 136 138

Предполагая завершающий перевод строки в программе

(p,i,j=0)=>eval("for(p=`\n${p}`.split`\n`.map((x,i)=>((c=(x=[...x]).pop())=='<'?k=i:x.push(c),x));a=p[k].pop();k-=1-c-c)c=1/a?a:i[j++]")

Меньше гольфа

(p, i, j=0)=>{
  p=`\n${p}`
     .split`\n`
     .map(
       (x,i)=>
       (
         x = [...x],
         c = x.pop(),
         c == '<' ? k=i : x.push(c),
         x
       )
     )
  for(; a = p[k].pop(); k -= 1-c-c)
    c = 1/a ? a : i[j++];
  return c;
}

Контрольная работа

F=(p,i,j=0)=>eval("for(p=`\n${p}`.split`\n`.map((x,i)=>((c=(x=[...x]).pop())=='<'?k=i:x.push(c),x));a=p[k].pop();k-=1-c-c)c=1/a?a:i[j++]")

function run() {
  var pgm=P.value+'\n'
  var i=I.value
  O.textContent = F(pgm,i)
}

run()
#P { width:60%; height: 6em }
#I { width:50%;  }
Program<br>
<textarea id=P>1
?&lt;
11
?
0</textarea><br>
Input<br>
<input id=I value=01>
<button onclick='run()'>Run</button>
<br>Output
<pre id=O></pre>

edc65
источник
5

05AB1E , 58 56 55 53 51 50 46 байтов

Сэкономили 2 байта благодаря Emigna ! Код:

õ|`õ)[¤'<å#À]`¨[¬V¨Y'?QiI«ëYi1U)À`ëY_i0U)Á`ëXq

Использует кодировку CP-1252 . Попробуйте онлайн! ,

Аднан
источник
2

Python 3, 147 146 145 144 байта

1 байт благодаря @Lynn.

def f(p):
 i=p[:p.find("<")].count("\n");p=p.split()
 try:
  while 1:*p[i],c=p[i];c=c>"<"and input()or c;i+=c<"<"and int(c)*2-1
 except:return c
PurkkaKoodari
источник
1

Питон 3, 318

def s(f,z):
 p=b="";g=0;a=[];n=a.append;n(p)
 for i in f:
  if i=="\n":n(p);p=''
  else:p+=i
 n(p);p=b;n(p)
 while g<len(a):
  if'<'in a[g]:q=g;a[q]=a[q][:-1]
  g+=1
 while 1:
  v=a[q]
  if v=='':print(b);break
  if v[-1]=='1':a[q]=v[:-1];q+=1;b=1
  elif v[-1]=="0":a[q]=v[:-1];q-=1;b=0
  else:a[q]=v[:-1]+z[0];z=z[1:]

F - программа, z - ввод. Да, мои имена переменных безумны.

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

ES6, 190 байт

f=(p,i)=>{
n=p.split`<`[0].split`\n`.length-1
p=p.split`\n`.map(o=>o.split``)
i=i.split``
p[n].pop()
while(p[n]&&p[n].length){
c=p[n].pop()
v=c=='?'?i.shift():Number(c)
n+=v*2-1
}
return v
}

Используйте как f(program, input)

ASCII-только
источник
2
Пара общих советов по игре в гольф (где-то есть их список): используйте [...o]вместо o.split``и используйте forвместо while, поскольку это позволяет вам переместить два выражения в forдва байта сохранения. Пара конкретных советов: я думаю, что ваше Numberприведение не является необходимым, поскольку приведение *2будет для вас, и я бы просто прочитал, iиспользуя j=0и i[j++]который, я думаю, экономит 11 байтов.
Нил
1
Вам не нужны f=анонимные функции.
gcampbell
0

Java, 256 255 231 219 215 213 байт

int f(char[][]p,char[]I){int l=p.length,d=0,j=-1,c=0,k=0,i[]=new int[l];while(++j<l)if(p[j][i[j]=p[j].length-1]==60)i[k=j]--;try{for(;;k+=c>48?1:-1)c=(c=p[k][i[k]--])>49?I[d++]:c;}catch(Throwable t){}return c-48;}

Демо на Ideone.

Принимает программу и ввод в качестве аргументов и возвращает результат в виде целого числа.

PurkkaKoodari
источник
@LeakyNun Изменен на forцикл, но что означает ваш первый комментарий?
PurkkaKoodari
@ Pietu1998 LeakyNun означает, что это может быть, int f(String[]I)...и вы можете избежатьString[]p=I.split("\n");
кошка
Это означает, что вы можете объявить функцию какint f(String[]P)
Leaky Nun
1
@cat ninja'd на 7 секунд: /
Leaky Nun
Кроме того, если вы согласитесь на Java 8, вы можете иметь лямбда-подобие (я думаю)->(String[]I){...
кошка
0

PHP (<7,0), 195 192 байта

Принимает программу в качестве первого аргумента и каждое значение в качестве дополнительного аргумента.
Обратите внимание, что я проверял это с разделителями ("", ..) asn пробелами, а не с символами новой строки, но это должно работать в любом случае.
Выдает устаревшее уведомление, если работает в PHP> 5.3.
Также выдает предупреждение, если вы выходите из верхней части программы. Однако он все еще работает и выводит правильно, так что все в порядке.

<?php foreach(split("\n",$argv[++$t])as$l)$p[]=str_split($l);for($i=-1;end($p[++$i])!='<';);array_pop($p[$i]);for(;($v=array_pop($p[$i]))!==null;$i+=$n?:-1)($n=$v)=='?'&&$n=$argv[++$t];echo$n;
user55641
источник
0

С 264 249 244 242

C не очень хорошо справляется с манипулированием строками, но это довольно коротко.

Он работает путем сканирования строки для курсора ( <), перемещения на 1 позицию назад, чтения команды, замены ее tabсимволом и перемещения вперед или назад на одну строку. Ввод осуществляется в виде массива C char, например char array[]="1\n?<\n11\n?\n0";result = f(array);, возврат каретки также разрешен.

Хотя входная строка изменена, длина не изменяется.

t;f(char*n){char*p=strchr(n,60);for(*p--=9;;){if(*p==63)scanf("%d",&t),*p=t+48;if(*p^49){for(*p--=9;p>n&&*p^10;--p);for(--p;p>n&&*p==9;--p);if(p<n||*p==10)return 0;}else{for(*p++=9;*p&&*p^10;++p);for(p+=!!*p;*p>10;++p);if(*--p<11)return 1;}}}

Тестовая программа

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

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, const char **argv)
{
    while (*++argv)
    {
        char *input=malloc(strlen(*argv)+1),*p;
        strcpy(input,*argv);
        printf("testing %s\n",input);
        for (p=input;*p;++p)
            if (*p=='\\')
                *p=10;
        printf("result: %d\n\n",f(input));
        free(input);
    }
    return 0;
}
owacoder
источник