Interpretar whatfuck

8

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
caixa de papelão
fonte

Respostas:

5

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.

Keith Randall
fonte
Economize 1 byte substituindo t+=(c=='>')-(c=='<');por t+=c=='>';t-=c=='<';, outro substituindo B=B+[t]*(c=='*')por B+=[t]*(c=='*')e um terceiro substituindo p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b;por p+=1+F.get(p,0)*-~-b-R.get(p,0)*b;. Ótima resposta! (Desculpe, eu sei que esta resposta é super velho!)
osuka_
5

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$ \ζ->μ[((ο,ο),("",ζ))]
deixou de girar contra-relógio
fonte
1
É notável a forma como muitas vezes respostas Haskell ter sucesso na obtenção top votos, mesmo se há outras respostas com objetivamente melhor pontuação em torno de ...
deixou de vez counterclockwis
μ :) ..............
luser droog
1

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

marinus
fonte
1
.append(item)-> +=[item], remova ke substitua todas as chamadas por a+=[...]para salvar alguns caracteres.
beary605
@ beary605: obrigado, no entanto, acabei usando o +=item,que é ainda mais curto.
Marinus