Stackylogic est un langage de programmation basé sur la logique que j'ai composé et qui prend en charge 0les 1entrées et les sorties et en sort un seul 0ou 1à la fin.

Un programme Stackylogic est composé de lignes qui ne peuvent contenir que les trois caractères 01?, ainsi qu’un seul <à la fin de l’une des lignes. Les lignes ne peuvent pas être vide et la ligne avec le <doivent avoir au moins un 0, 1ou ?devant elle.

Voici un exemple de programme qui (comme je l'expliquerai) calcule la NAND de deux bits:

1
?<
11
?
0

Chaque ligne d'un programme Stackylogic est considérée comme une pile , avec le bas à gauche et le haut à droite. Implicitement, il y a une pile vide (ligne vide) avant la première ligne du programme et après la dernière ligne.

Le <, que nous appellerons le curseur , marque la pile à démarrer lorsqu'un programme Stackylogic est exécuté. L’exécution d’un programme Stackylogic se déroule comme suit:

1. Retirez le caractère du haut de la pile sur laquelle le curseur pointe actuellement.

   • Si le caractère est ?, demandez à l'utilisateur un 0ou un 1et agissez comme s'il s'agissait du caractère.
   • Si le caractère est 0défini, déplacez le curseur d'une pile vers le haut (sur la ligne située au-dessus de la ligne actuelle).
   • Si le caractère est 1défini, déplacez le curseur d'une pile vers le bas (sur la ligne située sous la ligne actuelle).

2. Si la pile sur laquelle le curseur se déplace est vide, affiche la dernière valeur extraite d'une pile (toujours un 0ou 1) et termine le programme.

3. Sinon, si la pile sur laquelle le curseur se déplace n'est pas vide, retournez à l'étape 1 et répétez le processus.

Notez que les programmes Stackylogic se terminent toujours car ils doivent éventuellement épuiser leurs piles.

Exemple NAND

Dans le programme NAND, le curseur commence sur un ?:

1
?<
11
?
0

Nous supposerons que l’utilisateur saisit une 1fois l’opération ?, ce qui signifie que le curseur se déplacera vers le bas, donnant au programme l’apparence suivante:

1

11<
?
0

Une plaine se 1trouve maintenant en haut de la pile de curseurs. Il est dûment sauté et le curseur se déplace à nouveau:

1

1
?<
0

Supposons maintenant que les entrées utilisateur 0pour le ?, ce qui signifie que le curseur se déplace vers le haut:

1

1<

0

Encore une fois, a 1est sur la pile du curseur pour que le curseur apparaisse et descende:

1


<
0

Enfin, la pile de curseurs est vide et la dernière valeur apparue, le 1, est sortie et le programme se termine.

Ceci est exact pour une porte NON - car 1 NAND 0est 1. Ceci fonctionne bien sûr pour les trois autres entrées à deux bits si vous voulez vérifier.

OU Exemple

Ce programme Stackylogic simule une porte OU :

?
?<

Il est facile de voir qu'une entrée initiale de 1déplacera le curseur sur la pile vide implicite située au-dessous de la dernière ligne, mettant ainsi fin au programme et produisant le résultat 1qui venait d'être entré.

Par 00contre, pour une entrée , le curseur se dirigera vers la pile vide implicite située en haut, mettant fin au programme et en sortie la dernière 0entrée.

Défi

Ecrire un programme ou une fonction qui prend dans un programme Stackylogic comme une chaîne et l' exécute, l' impression ou le retour résultant 0ou 1.

Upon ?, vous pouvez demander à l'utilisateur une entrée 0ou 1, ou lire la valeur d'une chaîne prédéfinie de 0'et de 1' que vous prenez également comme entrée. (Cela peut être une autre chaîne d'entrée dans votre programme / fonction ou vous pouvez simplement supposer que la première ou la dernière ligne de la chaîne de programme sera le flux d'entrée).

Vous pouvez supposer que le programme et les entrées sont toujours bien formés. Vous pouvez éventuellement supposer que les programmes d'entrée sont fournis avec une nouvelle ligne de fin (bien qu'il y ait toujours une pile implicite vide à la fin).

Le code le plus court en octets gagne.

Plus de programmes exemples

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

^{Merci Martin pour les programmes médians .}

Retina , 79 78 73 68 66 65 63 62 55 44 octets

Le nombre d'octets suppose un codage ISO 8859-1.

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

La saisie s'effectue via STDIN et devrait être la saisie de l'utilisateur séparée par deux sauts de ligne à partir du code source.

Essayez-le en ligne! (Les deux premières lignes permettent une suite de tests, où chaque ligne est un scénario de test séparé avec /des sauts de ligne.)

Je ne suis pas tout à fait sûr de ce qui s'est passé ici. Cela ressemble à une solution vraiment maladroite et ce n’est vraiment pas le genre de problème que Retina a été créé, mais il bat toutes les réponses actuelles pour une raison quelconque.

Explication

La version finale de ceci a finalement été assez simple.

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

La première étape est simplement une boucle (en raison de l' +option) qui interprète réellement la langue. La scène est une substitution de regex unique, mais en réalité, il s’agit de trois substitutions différentes qui s’inscrivent dans une même étape, en exploitant le fait que la capture de groupes à partir de branches inutilisées est simplement considérée comme vide lors de la substitution.

1. Traitement ?:

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

   Cela prend simplement le premier caractère de l'entrée, puis fait correspondre des caractères arbitraires jusqu'à ce qu'il trouve ?<et place ce premier caractère devant le <(suppression du ?).

2. Traitement 0:

   (¶.*)0<
   <$1
   

   Ceci correspond à la ligne précédant a 0<et la met après le <, en supprimant 0. (Effectivement, cela supprime simplement le 0et déplace la <ligne vers le haut.)

3. Traitement 1:

   1<(¶.+)
   $1<
   

   À peu près la même chose, sauf que nous déplaçons <une ligne tout en supprimant un 1. Un détail important à noter est l'utilisation de à la +place de *, c'est-à-dire que nous exigeons que la ligne suivante ne soit pas vide.

Ce qui est intéressant, c’est de comprendre pourquoi cela fonctionne et pourquoi nous n’avons pas besoin de garder trace de la dernière valeur apparue pour déterminer la sortie finale. Pour ce faire, nous devons examiner comment la boucle ci-dessus peut se terminer. Étant donné que chaque correspondance possible modifie la chaîne (puisqu'au moins un caractère en est supprimé), il suffit de prendre en compte les cas où la correspondance échoue complètement.

Si le personnage qui se trouve devant <est ?le seul moyen d’échouer le match, c’est qu’il n’y a pas de personnage qui ne saute pas de ligne, mais cela ne peut pas arriver car nous avons la garantie que l’entrée est toujours suffisante.

Si le caractère précédant <est 0, l'expression régulière correspondra toujours, car il y a toujours une autre ligne au-dessus de la ligne actuelle (qui peut être la ligne vide séparant l'entrée du code source).

Si le caractère en face de <est 1, la regex échouera si nous sommes sur la dernière ligne (puisque la correspondance ¶échoue) ou si la ligne suivante est vide (car la correspondance .+ne correspond pas). Notez que ces deux cas correspondent à l’arrêt du programme après le popping a 1.

Enfin, il y a aussi la possibilité que <rien ne soit précédé ?01. Il s'avère que nous ne pouvons atteindre cette situation qu'en sautant une ligne 0et en nous déplaçant jusqu'à une ligne vide, de sorte que la ligne <est maintenant précédée d'un saut de ligne.

Ainsi, lorsque le programme se termine le 1, le <sera toujours après 1. Mais si le programme se termine sur un 0, il aura été déplacé sur une ligne vide. Nous pouvons facilement transformer cette information en sortie souhaitée avec une simple étape de correspondance:

1<

Ceci compte simplement les correspondances de 1<dans la chaîne. Selon le raisonnement ci-dessus, ce sera 1si le programme s'est terminé le 1, et 0s'il s'est terminé le 0.

Convexe , 102 à 95 octets

Eh bien, un langage basé sur une liste de piles empilée s'est révélé assez difficile. Marquez mes mots: je vais obtenir cela à 100 octets ou moins! EDIT: succès!

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

Essayez-le en ligne!

La saisie du programme s'effectue via les arguments de ligne de commande. Les entrées 0s et 1s normalement (sur TIO, cela signifie séparé par une nouvelle ligne dans la case "entrée").

Explication:

Tout le code peut être divisé en trois parties:

N/S\+

Ce bit prend simplement le programme d'entrée et le convertit en un tableau de lignes, et ajoute également des " "lignes au début du tableau. Étant donné que les tableaux de Convex sont bouclés, le fait de ne disposer que d'une pile vide suffit.

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

Cette partie détermine la ligne (ou la pile) avec laquelle commencer l'exécution. Il recherche dans chaque ligne et place le numéro de pile correct dans la Mvariable.

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

C'est la partie amusante! Il boucle continuellement jusqu'à atteindre une ligne contenant uniquement un espace ( " ") (symbolisant une pile vide). Si la ligne n'est pas vide, il effectue les opérations suivantes:

1. Pop le dernier caractère de la pile.
2. Instruction de commutation:
   1. Si le caractère est un ?, saisissez-le et ajoutez-le à la ligne.
   2. Si le caractère est un 0, déplacez le pointeur de ligne vers le haut.
   3. Si le caractère est un 1, déplacez le pointeur de ligne vers le bas.
   4. Si le caractère est un (espace), imprimez le dernier élément sauté et terminez le programme.

Code machine x86 32 bits, 70 octets

En hex:

FC89E1565F31D28A07A8DF740B3C3C7511428D5C24FCEB0A5729142484C07405B20147EBE2578B3B8A17F6C2DF7414FF0B923C3F7501AC3C30750383C30883EB04EBE389CCC3

L'entrée est une chaîne multiligne à terminaison NULL (séparée par un saut de ligne) transmise via ESI. L'entrée utilisateur est supposée être la première ligne. Renvoie '0' / '1' dans AL.

Démontage:

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

En supposant un retour à la ligne dans le programme

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

Moins golfé

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

Tester

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 octets

2 octets sauvés grâce à Emigna ! Code:

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

Utilise le codage CP-1252 . Essayez-le en ligne! .

Python 3, 147 146 145 144 octets

1 octet grâce à @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 étant le programme, z étant entré. Oui, mes noms de variables sont insensés.

ES6, 190 octets

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
}

Utiliser comme f(program, input)

Java, 256 255 231 219 215 213 octets

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

Démo sur Ideone.

Prend le programme et l'entrée en tant qu'arguments et renvoie le résultat sous forme d'entier.

PHP (<7.0), 195 192 octets

Prend le programme comme premier argument et chaque valeur comme argument supplémentaire.
Notez que j’ai testé cela avec des espaces asn séparés ("", ..) plutôt que des lignes, mais cela devrait quand même fonctionner.
Donne un avis obsolète si exécuté dans php> 5.3.
Donne également un avertissement si vous sortez du programme. Cependant, cela fonctionne toujours et fonctionne correctement, donc tout va bien.

<?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 ne fait pas si bien avec la manipulation des chaînes, mais c'est assez court.

Cela fonctionne en balayant la chaîne pour le curseur ( <), en reculant d’une place, en lisant la commande, en la remplaçant par un tabcaractère et en se déplaçant d’une ligne en avant ou en arrière. L'entrée se présente sous la forme d'un tableau de caractères C, par exemple char array[]="1\n?<\n11\n?\n0";result = f(array);, bien que les retours chariot soient également autorisés.

Bien que la chaîne d'entrée soit modifiée, la longueur n'est pas modifiée.

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

Programme de test

Exécutez ce programme avec chaque cas de test en tant que paramètre distinct, en utilisant une simple barre oblique inverse à la place des nouvelles lignes. Les cas de test seront séparés par une ligne vierge.

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