Stackylogic to język programowania oparte na logice wymyśliłem, że biorą w 0„s i 1” s dla wejścia i wyjścia jednego 0lub 1po zakończeniu.

Program Stackylogic składa się z wierszy, które mogą zawierać tylko trzy znaki, 01?a także dokładnie jeden <na końcu jednego z wierszy. Linie nie mogą być puste, a linia z <musi mieć co najmniej jednego 0, 1lub ?przed nim.

Oto przykładowy program, który (jak wyjaśnię) oblicza NAND dwóch bitów:

1
?<
11
?
0

Każda linia w programie Stackylogic jest uważana za stos , z dolną po lewej stronie i górną po prawej stronie. Domniemany jest pusty stos (pusta linia) przed pierwszą linią w programie i po ostatniej linii.

<, Które będziemy nazywać się kursor , znaki stos rozpocząć się, gdy program jest uruchamiany Stackylogic. Wykonanie programu Stackylogic przebiega następująco:

1. Usuń górną postać ze stosu, na który wskazuje obecnie kursor.

   • Jeśli znakiem jest ?, poproś użytkownika o znak a 0lub a 1i postępuj tak, jakby to był znak.
   • Jeśli znak jest 0, przesuń kursor o jeden stos w górę (do linii powyżej bieżącej linii).
   • Jeśli znak jest 1, przesuń kursor o jeden stos w dół (do linii poniżej bieżącej linii).

2. Jeśli stos, do którego przesuwa się kursor, jest pusty, wypisz ostatnią wartość, która została usunięta ze stosu (zawsze a 0lub 1) i zakończ program.

3. W przeciwnym razie, jeśli stos, na który przesuwa się kursor, nie jest pusty, wróć do kroku 1 i powtórz proces.

Zauważ, że programy Stackylogic zawsze kończą się, ponieważ ostatecznie muszą wyczerpać swoje stosy.

Przykład NAND

W programie NAND kursor zaczyna się od ?:

1
?<
11
?
0

Zakładamy, że dane wprowadzone przez użytkownika zostaną 1raz wyświetlone ?, co oznacza, że ​​kursor przesunie się w dół, dzięki czemu program będzie wyglądał następująco:

1

11<
?
0

Teraz równina 1znajduje się na górze stosu kursora. Jest należycie wysunięty, a kursor znów się porusza:

1

1
?<
0

Załóżmy teraz, że dane wejściowe użytkownika 0dla ?, co oznacza, że ​​kursor przesunie się w górę:

1

1<

0

Znów a 1znajduje się na stosie kursora, więc kursor wysuwa się i przesuwa w dół:

1


<
0

Na koniec stos kursorów jest pusty, więc wyświetlana jest ostatnia wartość, to 1, i program się kończy.

Jest to poprawne dla bramki NAND, ponieważ 1 NAND 0jest 1. To oczywiście działa na pozostałe trzy dwubitowe wejścia, jeśli chcesz to sprawdzić.

LUB Przykład

Ten program Stackylogic symuluje bramkę OR :

?
?<

Łatwo zauważyć, że początkowe wejście 1popchnie kursor do domyślnego pustego stosu poniżej ostatniego wiersza, kończąc program i wyprowadzając to, 1co właśnie zostało wprowadzone.

Z 00drugiej strony, kursor dojdzie do niejawnego pustego stosu u góry, kończąc program i wysyłając ostatni 0do wprowadzenia.

Wyzwanie

Napisz program lub funkcję, która pobiera program Stackylogic jako ciąg znaków i uruchamia go, drukując lub zwracając wynikowe 0lub 1.

Po ?, możesz poprosić użytkownika o wprowadzenie 0lub 1wejście, lub odczytać wartość ze wstępnie ustawionego ciągu 0„i 1”, który również bierzesz jako dane wejściowe. (Może to być kolejny ciąg znaków do twojego programu / funkcji lub możesz po prostu założyć, że pierwszy lub ostatni wiersz łańcucha programu będzie strumieniem wejściowym).

Możesz założyć, że program jest zawsze dobrze sformułowany. Opcjonalnie możesz założyć, że programy wejściowe mają pojedynczy znak nowej linii (pamiętaj jednak, że na końcu zawsze jest ukryty pusty stos).

Najkrótszy kod w bajtach wygrywa.

Więcej przykładowych programów

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?<
??

^{Dzięki Martin za medianę programów .}

Retina , 79 78 73 68 66 65 63 62 55 44 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

Dane wejściowe są przesyłane przez STDIN i oczekuje się, że będą to dane wejściowe użytkownika oddzielone dwoma wejściami liniowymi od kodu źródłowego.

Wypróbuj online! (Pierwsze dwa wiersze włączają zestaw testowy, gdzie każdy wiersz jest oddzielnym przypadkiem testowym /zamiast z wierszami).

Nie jestem do końca pewien, co się tutaj stało. To wydaje się być naprawdę niezręcznym rozwiązaniem i nie jest to naprawdę problem, dla którego stworzono Retinę, ale z jakiegoś powodu wciąż bije wszystkie aktualne odpowiedzi.

Wyjaśnienie

Ostateczna wersja tego faktycznie okazała się dość prosta.

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

Pierwszym etapem jest po prostu pętla (z powodu +opcji), która dokonuje faktycznej interpretacji języka. Etap jest pojedynczą substytucją wyrażenia regularnego, ale tak naprawdę są to trzy różne substytucje wciśnięte w jeden etap, wykorzystując fakt, że przechwytywanie grup z nieużywanych gałęzi jest po prostu uważane za puste podczas podstawienia.

1. Przetwarzanie ?:

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

   To po prostu bierze pierwszy znak wejścia, a następnie dopasowuje dowolne znaki, aż znajdzie ?<, i umieszcza ten pierwszy znak przed <(usuwanie ?).

2. Przetwarzanie 0:

   (¶.*)0<
   <$1
   

   Pasuje do linii poprzedzającej a 0<i umieszcza ją po <usunięciu 0. (W efekcie to po prostu usuwa 0i przesuwa <jedną linię w górę.)

3. Przetwarzanie 1:

   1<(¶.+)
   $1<
   

   Prawie to samo, z wyjątkiem tego, że przesuwamy <jedną linię w dół podczas usuwania a 1. Ważnym szczegółem, na który należy zwrócić uwagę, jest użycie +zamiast tego *, że wymagamy, aby następny wiersz nie był pusty.

Interesującą częścią jest ustalenie, dlaczego to działa i dlaczego nie musimy śledzić ostatniej wartości, którą podaliśmy, aby określić ostateczny wynik. Aby to zrobić, musimy rozważyć, w jaki sposób powyższa pętla może się zakończyć. Ponieważ każde możliwe dopasowanie zmienia ciąg (ponieważ co najmniej jeden znak jest z niego usuwany), musimy jedynie rozważyć przypadki, w których dopasowanie całkowicie się nie powiedzie.

Jeśli znak z przodu <jest ?jedynym sposobem na porażkę, to to, że nigdzie przed nim nie ma znaku nieciągłego, ale to nie może się zdarzyć, ponieważ mamy gwarancję, że zawsze jest wystarczająca ilość danych wejściowych.

Jeśli przed nim <jest znak 0, wyrażenie regularne zawsze będzie pasować, ponieważ zawsze jest inny wiersz nad bieżącym (którym może być pusty wiersz oddzielający dane wejściowe od kodu źródłowego).

Jeśli przed nim <znajduje się znak 1, wyrażenie regularne zakończy się niepowodzeniem, jeśli znajdziemy się w ostatnim wierszu (ponieważ ¶nie uda się dopasować) lub jeśli następny wiersz będzie pusty (ponieważ .+nie uda się dopasować). Zauważ, że oba te przypadki odpowiadają zakończeniu programu po kliknięciu na 1.

Wreszcie istnieje również możliwość, której <nie poprzedza żadna z nich ?01. Okazuje się, że możemy dojść do tej sytuacji tylko przez naciśnięcie przycisku 0i przejście do pustej linii, tak że <poprzedza ją teraz linia .

Tak więc, gdy program zakończy się na 1, <nadal będzie po nim 1. Ale jeśli program zakończy się na a 0, zostanie przeniesiony do pustej linii. Możemy łatwo przekształcić te informacje w pożądany wynik za pomocą prostego etapu dopasowania:

1<

To po prostu zlicza dopasowania 1<ciągu. Zgodnie z powyższym rozumowaniem będzie tak, 1jeśli program zakończy się na a 1, a 0jeśli zakończy na 0.

Wypukły , 102 95 bajtów

Cóż, język oparty na liście stosów zakodowany w języku opartym na stosie okazał się dość trudny. Zaznacz moje słowa: otrzymam to do 100 bajtów lub mniej! EDYCJA: Sukces!

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;;

Wypróbuj online!

Wprowadzanie programu odbywa się za pomocą argumentów wiersza poleceń. Wejścia 0si 1normalnie (w TIO oznacza to separację nowej linii w polu „input”).

Wyjaśnienie:

Cały kod można podzielić na trzy części:

N/S\+

Ten bit po prostu pobiera program wejściowy i przekształca go w tablicę linii, a także dodaje " "linie na początku tablicy. Ponieważ tablice wypukłe się zawijają, wystarczy mieć tylko pusty stos na początku.

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

Ta część określa, od której linii (lub stosu) rozpocząć wykonywanie. Przeszukuje każdą linię i umieszcza poprawny numer stosu w Mzmiennej.

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

To jest trochę zabawy! Ciągle zapętla się, aż osiągnie linię ze spacją ( " ") (symbolizującą pusty stos). Jeśli linia nie jest pusta, wykonuje następujące czynności:

1. Usuń ostatnią postać ze stosu.
2. Instrukcja zamiany:
   1. Jeśli znakiem jest a ?, wprowadź dane wejściowe i dodaj ten znak do wiersza.
   2. Jeśli znakiem jest a 0, przesuń wskaźnik linii w górę o jeden.
   3. Jeśli znakiem jest a 1, przesuń wskaźnik linii w dół o jeden.
   4. Jeśli znakiem jest (spacja), wydrukuj ostatnio wyskakujący element i zakończ program.

32-bitowy kod maszynowy x86, 70 bajtów

W hex:

FC89E1565F31D28A07A8DF740B3C3C7511428D5C24FCEB0A5729142484C07405B20147EBE2578B3B8A17F6C2DF7414FF0B923C3F7501AC3C30750383C30883EB04EBE389CCC3

Dane wejściowe to wielowierszowy łańcuch zakończony znakiem NULL (oddzielony od linii) przekazywany przez ESI. Zakłada się, że dane wejściowe użytkownika są pierwszym wierszem. Zwraca „0” / „1” w AL.

Demontaż:

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

JavaScript (ES6), 136 138

Zakładając zakończenie nowej linii w programie

(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++]")

Mniej golfa

(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;
}

Test

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>

05AB1E , 58 56 55 53 51 50 46 bajtów

Zaoszczędź 2 bajty dzięki Emignie ! Kod:

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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Python 3, 147 146 145 144 bajtów

1 bajt dzięki @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

Python 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 oznacza program, z jest wprowadzany. Tak, moje zmienne nazwy są szalone.

ES6, 190 bajtów

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
}

Użyj jak f(program, input)

Java, 256 255 231 219 215 213 bajtów

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;}

Demo na Ideone.

Bierze program i dane wejściowe jako argumenty i zwraca wynik jako liczbę całkowitą.

PHP (<7.0), 195 192 bajtów

Traktuje program jako pierwszy argument, a każdą wartość jako dodatkowy argument.
Zauważ, że przetestowałem to ze spacjami („”,…) asn zamiast spacjami, ale i tak powinno to działać.
Daje przestarzałe powiadomienie, jeśli działa w php> 5.3.
Daje również ostrzeżenie, jeśli wyjdziesz z górnej części programu. Jednak nadal działa i działa poprawnie, więc jest w porządku.

<?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;

C 264 249 244 242

C nie radzi sobie tak dobrze z manipulowaniem łańcuchami, ale jest to dość krótkie.

Działa poprzez skanowanie łańcucha w celu znalezienia kursora ( <), przesunięcie wstecz o 1 miejsce, odczytanie polecenia, zastąpienie go tabznakiem i przejście o jedną linię do przodu lub do tyłu. Dane wejściowe mają postać tablicy znaków C, na przykład char array[]="1\n?<\n11\n?\n0";result = f(array);, chociaż dozwolone są również powrotu karetki.

Chociaż łańcuch wejściowy jest zmodyfikowany, długość nie jest zmieniana.

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;}}}

Program testowy

Uruchom ten program dla każdego przypadku testowego jako osobnego parametru, używając pojedynczego ukośnika odwrotnego zamiast znaków nowej linii. Przypadki testowe zostaną oddzielone pustą linią.

#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;
}