Run Stackylogic

Question

Stackylogic is a logic-based programming language I made up that take in 0's and 1's for input and outputs a single 0 or 1 upon completion.

A Stackylogic program consists of lines that can only contain the three characters 01? as well as exactly one < at the end of one of the lines. Lines may not be empty and the line with the < must have at least one 0, 1, or ? before it.

Here's a sample program that (as I'll explain) computes the NAND of two bits:

1
?<
11
?
0

Every line in a Stackylogic program is considered a stack, with the bottom on the left and the top on the right. Implicitly, there is an empty stack (empty line) before the first line in a program and after the last line.

The <, which we'll call the cursor, marks the stack to start on when a Stackylogic program is run. Execution of a Stackylogic program proceeds as follows:

1. Pop the top character off the stack the cursor is currently pointing to.

   • If the character is ?, prompt the user for a 0 or a 1 and act as if that was the character.
   • If the character is 0, move the cursor one stack up (to the line above the current line).
   • If the character is 1, move the cursor one stack down (to the line below the current line).

2. If the stack the cursor moves to is empty, output the last value that was popped off a stack (always a 0 or 1), and end the program.

3. Else, if the stack the cursor moves to is not empty, go back to step 1 and repeat the process.

Notice that Stackylogic programs always end because they must eventually deplete their stacks.

NAND Example

In the NAND program the cursor starts on a ?:

1
?<
11
?
0

We'll assume the user inputs a 1 once the ? is popped, which means the cursor will move down, making the program look like this:

1

11<
?
0

Now a plain 1 is at the top of the cursor stack. It is duly popped and the cursor moves again:

1

1
?<
0

Now assume the user inputs 0 for the ?, which means the cursor will move up:

1

1<

0

Again, a 1 is on the cursor stack so the cursor pops and moves down:

1


<
0

Finally the cursor stack is empty, so the last value popped, the 1, is output and the program ends.

This is accurate for a NAND gate because 1 NAND 0 is 1. This of course works for the other three two-bit inputs if you care to check.

OR Example

This Stackylogic program simulates an OR gate:

?
?<

It's easy to see that an initial input of 1 will push the cursor to the implicit empty stack below the last line, ending the program and outputting the 1 that was just input.

For an input of 00 on the other hand, the cursor will make its way to the implicit empty stack at the top, ending the program and outputting the last 0 to be input.

Challenge

Write a program or function that takes in a Stackylogic program as a string and runs it, printing or returning the resulting 0 or 1.

Upon ?'s, you may prompt the user for a 0 or 1 input, or read the value from a preset string of 0's and 1's that you also take as input. (This could be another string input to your program/function or you could just assume the first or last line of the program string will be the input stream).

You may assume the program and the input are always well formed. You may optionally assume input programs come with a single trailing newline (though remember there is always an implicit empty stack at the end).

The shortest code in bytes wins.

More Sample Programs

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

^{Thanks Martin for the median programs.}

Answer 1

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

Byte count assumes ISO 8859-1 encoding.

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

Input is via STDIN and is expected to be the user input separated by two linefeeds from the source code.

Try it online! (The first two lines enable a test suite, where each line is a separate test case with / instead of linefeeds.)

I'm not entirely sure what happened here. This feels like a really clunky solution and this is really not the kind of problem Retina was made for but it still beats all the current answers for some reason.

Explanation

The final version of this actually ended up being fairly simple.

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

The first stage is simply a loop (due to the + option) which does the actual interpreting of the language. The stage is a single regex substitution, but in fact it's really three different substitutions squeezed into one stage, by making use of the fact that capturing groups from unused branches are simply considered empty during the substitution.

1. Processing ?:

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

   This simply takes the first character of the input, then matches arbitrary characters until it finds ?<, and puts that first character in front of the < (deleting the ?).

2. Processing 0:

   (¶.*)0<
   <$1
   

   This matches the line preceding a 0< and puts it after the <, removing 0. (Effectively, this just deletes the 0 and moves the < one line upwards.)

3. Processing 1:

   1<(¶.+)
   $1<
   

   Pretty much the same thing, except that we move < one line down while deleting a 1. One important detail to notice is the use of + instead of *, that is, we require the next line not to be empty.

The interesting part is figuring out why this works and why we don't need to keep track of the last value we popped to determine the final output. To do that, we need to consider how the above loop can terminate. Since every possible match changes the string (since at least one character is dropped from it), we only need to consider cases where the match fails altogether.

If the character in front of < is ? the only way for the match to fail is that there isn't non-linefeed character anywhere in front of it, but that can't happen because we're guaranteed that there's always enough input.

If the character in front of < is 0, the regex will always match, since there's always another line above the current one (which may be the empty line separating input from source code).

If the character in front of < is 1, the regex will fail if either we're on the last line (since the ¶ will fail to match) or if the next line is empty (since the .+ will fail to match). Note that both of those cases correspond to terminating the program after popping a 1.

Finally, there's also the possibility that < isn't preceded by any of ?01. It turns out we can only reach this situation by popping a 0 and moving up to an empty line, so that the < is now preceded by a linefeed.

So, when the program terminates on a 1, the < will still be after that 1. But if the program terminates on a 0, it will have moved to an empty line. We can easily turn this information into the desired output with a simple match stage:

1<

This simply counts the matches of 1< in the string. By the above reasoning this will be 1 if the program terminated on a 1, and 0 if it terminated on a 0.

Answer 2

Convex, 102 95 bytes

Well, a list-of-stacks-based language coded in a stack-based language turned out to be quite difficult. Mark my words: I will get this to 100 bytes or less! EDIT: Success!

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

Try it online!

Program input is via command-line args. Input 0s and 1s normally (on TIO, this means newline-separated in the "input" box).

---

Explanation:

All of the code can be split into three pieces:

N/S\+

This bit simply takes the input program and converts it into an array of lines, and also adds " " lines to the beginning of the array. Since Convex's arrays wrap, having only an empty stack at the beggining will do.

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

This part determines what line (or stack) to start execution with. It searches through each line and puts the correct stack number into the M variable.

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

This is the fun bit! It continually loops until it reaches a line with only a space (" ") on it (symbolizing an empty stack). If the line is not empty it does the following:

1. Pop the last character off the stack.
2. Switch statement:
   1. If the character is a ?, take input and append that character to the line.
   2. If the character is a 0, move the line pointer up one.
   3. If the character is a 1, move the line pointer down one.
   4. If the character is a (space), print the most-recently popped item and end program.

Answer 3

32-bit x86 machine code, 70 bytes

In hex:

FC89E1565F31D28A07A8DF740B3C3C7511428D5C24FCEB0A5729142484C07405B20147EBE2578B3B8A17F6C2DF7414FF0B923C3F7501AC3C30750383C30883EB04EBE389CCC3

Input is a NULL-terminated multi-line string (linefeed-separated) passed via ESI. User input is assumed to be the first line. Returns '0'/'1' in AL.

Disassembly:

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

Answer 4

JavaScript (ES6), 136 138

Assuming a terminating newline in the program

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

Less golfed

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

Answer 5

05AB1E, 58 56 55 53 51 50 46 bytes

Saved 2 bytes thanks to Emigna! Code:

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

Uses the CP-1252 encoding. Try it online!.

Answer 6

Python 3, 147 146 145 144 bytes

1 byte thanks to @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

Answer 7

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 being the program, z being input. Yes, my variable names are insane.

Answer 8

ES6, 190 bytes

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
}

Use like f(program, input)

Answer 9

Java, 256 255 231 219 215 213 bytes

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 on Ideone.

Takes the program and input as arguments and returns the result as an integer.

Answer 10

PHP (<7.0), 195 192 bytes

Takes the program as first argument and each value as an additional argument.
Note that I tested this with split(" ",..) asn spaces rather than newlines but it should work anyway.
Gives a deprecated notice if run in php >5.3.
Also gives a warning if you go off the top of the program. However it still works and outputs correctly so it's fine.

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

Answer 11

C, 264 249 244 242

C doesn't do so well with manipulating strings, but this is pretty short.

It works by scanning the string for the cursor (<), moving back 1 place, reading the command, replacing it with a tab character, and moving either forward or backward one line. Input is in the form of a C char array, like char array[]="1\n?<\n11\n?\n0";result = f(array);, although carriage returns are permitted as well.

Although the input string is modified, the length is not changed.

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

Test program

Run this program with each test case as a separate parameter, using a single backslash in place of newlines. Test cases will be separated by a blank line.

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