Interpreta qué carajo

Smallfuck es un lenguaje similar al brainfuck con celdas de 1 bit. Tiene las siguientes instrucciones:

> Increment the pointer
< Decrement the pointer
* Flip the current bit
[ If the current bit is not set, jump to the instruction after the matching ]
] If the current bit is set, jump to the instruction after the matching [ 
    ( or just jump unconditionally to matching [ )

Whatfuck agrega una instrucción más:

? Nondeterministically set the current bit to 0 or 1.

Un programa whatfuck no toma ninguna entrada. Puede dar lugar a una de 3 posibilidades: 1(aceptar), 0(rechazar) o puede que nunca se detenga.

El programa dará como resultado 1si existe una secuencia de bits elegidos para ?s que da como resultado que el programa termine 1como el bit actual.

El programa termina con 0si todas las opciones posibles terminan con el bit actual 0,

Si algunas opciones no terminan, y todas las opciones que terminan lo hacen 0, entonces el programa nunca terminará.

Su intérprete debe ejecutar todas las posibilidades simultáneamente. No puede intentar 0primero y luego intentar 1, porque algunos programas no terminarán cuando deberían. Por ejemplo, *[?*]*aceptará con la elección 1, pero nunca terminará si siempre elige 0.

Como ejemplo, aquí hay un intérprete de Python 2 que escribí, no golf

Reglas

• Su intérprete debe aceptar un programa whatfuck de stdin e imprimir su resultado.

• Puede suponer que el programa whatfuck solo contiene caracteres []<>*?

• La matriz de bits no tiene límites en ambos extremos.

• El código más corto gana.

Algunos casos de prueba

Esto fallará si su código siempre lo intenta 0primero

*[?*]*
1

¿Hay un subconjunto de {-7,-3, 5, 8}cuya suma es 3?

*<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
1

¿Hay un subconjunto de {-7,-3, 5, 8}cuya suma es 4?

*<<<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
0

¿Hay alguna manera de asignar valores booleanos a a, by ctal que

(a XOR b) AND (a XOR c) AND (b XOR c) ¿es verdad?

?[*>*>*<<]?[*>*>>*<<<]?[*>>*>*<<<]>[*>[*>[*>*<]<]<]>>>
0

Python, 305 caracteres

P=raw_input()+'$'
S=[(0,0,[])]
F={}
R={}
i=r=0
for c in P:
 if'['==c:S+=i,
 if']'==c:j=S.pop();F[j]=R[i]=i-j
 i+=1
while S*(1-r):p,t,B=S.pop(0);c=P[p];b=B.count(t)%2;p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b;t+=(c=='>')-(c=='<');B=B+[t]*(c=='*');r|=(c=='$')&b;S+=[(p,t,B)]*(c!='$')+[(p,t,B+[t])]*(c=='?')
print r

Realiza un seguimiento del conjunto de estados no deterministas S, cada uno con una posición de código p, una posición de cinta ty una lista de índices de cinta B. Un índice de cinta puede aparecer varias veces en la lista B, la cinta en ese índice es 1 si el índice aparece un número impar de veces B.

Cinta infinita ahoy!

Haskell, 516

i((p:l,r),(π,'<':φ))=[((l,p:r),('<':π,φ))]
i((l,p:r),(π,'>':φ))=[((p:l,r),('>':π,φ))]
i((l,p:r),(π,'*':φ))=[((l,1-p:r),('*':π,φ))]
i((l,_:r),(π,'?':φ))=[((l,b:r),('?':π,φ))|b<-[0,1]]
i(s@(l,0:r),(π,'[':φ))=[(s,m(']':π,φ)0)]
i(s,(π,'[':φ))=[(s,(']':π,φ))]
i(s,(π,']':φ))=[(s,ξ$m(']':φ,π)0)]
i _=[]
m(l,']':r)0=('[':l,r)
m(l,']':r)n=m('[':l,r)$n-1
m(l,'[':r)n=m(']':l,r)$n+1
m(l,c:r)n=m(c:l,r)n
ν=null;ο=0:ο
μ[]="0"
μ ω|ν[ψ|ψ@((_,b:_),_)<-ω,b>0,ν$i ψ]=μ$ω>>=i
μ _="1"
ξ(a,b)=(b,a)
main=interact$ \ζ->μ[((ο,ο),("",ζ))]

Pitón ( 405 399 379)

Toma la entrada en una línea, pero "puedo asumir que el programa whatfuck solo contiene caracteres []<>*?" y la nueva línea no está en esa lista: P

w, i, p, a = {}, 0, raw_input (), [(0,0, [], [])]
para c en p:
 si c == '[': a + = i,
 si c == ']': g = a.pop (); w [i], w [g] = g, i
 i + = 1
i, z = 0, lambda l: ly l.pop () o 0
mientras que a:
 n, c, l, r = a.pop (0)
 intente: o = p [n]
 excepto:
        si c: i = 1; descanso
        Seguir
 si o == '*': c = no c
 si o == '>': l + = c,; c = z (r)
 si o == '<': r + = c,; c = z (l)
 si o en '[]' y (']' == o) == c: n = w [n]
 si o == '?': a + = (n + 1, no c, l [:], r [:]),
 a + = (n + 1, c, l, r),
imprimir i