Interpretar whatfuck

Smallfuck é uma linguagem semelhante ao cérebro com células de 1 bit. Possui as seguintes instruções:

> 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 acrescenta mais uma instrução:

? Nondeterministically set the current bit to 0 or 1.

Um programa whatfuck não recebe nenhuma entrada. Pode resultar em uma das três possibilidades: 1(aceitar), 0(rejeitar) ou nunca pode parar.

O programa resultará 1se existir uma sequência de bits escolhida para ?s, o que resultará no término do programa 1como o bit atual.

O programa termina com 0se todas as opções possíveis terminarem com o bit atual 0,

Se algumas opções não terminarem e todas as opções terminarem 0, o programa nunca terminará.

Seu intérprete deve executar todas as possibilidades simultaneamente. Você não pode tentar 0primeiro e depois tentar 1, porque alguns programas não terminam quando deveriam. Por exemplo, *[?*]*aceitará com a escolha 1, mas nunca será encerrada se você sempre escolher 0.

Como exemplo, aqui está um intérprete de python 2 que escrevi, não joguei golfe

Regras

• Seu intérprete deve aceitar um programa whatfuck da stdin e imprimir seu resultado.

• Você pode assumir que o programa whatfuck contém apenas caracteres []<>*?

• A matriz de bits é ilimitada nas duas extremidades.

• O menor código vence.

Alguns casos de teste

Isso falhará se seu código sempre tentar 0primeiro

*[?*]*
1

Existe um subconjunto {-7,-3, 5, 8}cuja soma é 3?

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

Existe um subconjunto {-7,-3, 5, 8}cuja soma é 4?

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

Existe uma maneira de atribuir valores booleanos a a, be cde tal forma que

(a XOR b) AND (a XOR c) AND (b XOR c) é verdade?

?[*>*>*<<]?[*>*>>*<<<]?[*>>*>*<<<]>[*>[*>[*>*<]<]<]>>>
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

Mantém o controle do conjunto não determinístico de estados S, cada um com uma posição de código p, uma posição de fita te uma lista de índices de fita B. Um índice de fita pode aparecer várias vezes na lista B; a fita nesse índice é 1 se o índice aparecer um número ímpar de vezes B.

Fita 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$ \ζ->μ[((ο,ο),("",ζ))]

Python ( 405 399 379)

Leva a entrada em uma linha, mas "posso assumir que o programa whatfuck contém apenas caracteres []<>*?" e a nova linha não está nessa lista: P

w, i, p, a = {}, 0, raw_input (), [(0,0, [], [])]
para c em p:
 se c == '[': a + = i,
 se c == ']': g = a.pop (); w [i], w [g] = g, i
 i + = 1
i, z = 0, lambda l: le l.pop () ou 0
enquanto um:
 n, c, l, r = a.pop (0)
 tente: o = p [n]
 exceto:
        se c: i = 1; quebra
        continuar
 se o == '*': c = não c
 Se o == '>': l + = c,; c = z (r)
 Se o == '<': r + = c,; c = z (l)
 se o em '[]' e (']' == o) == c: n = w [n]
 se o == '?': a + = (n + 1, não c, l [:], r [:]),
 a + = (n + 1, c, l, r),
imprimir i