# Interpret whatfuck

Smallfuck is a brainfuck-like language with 1-bit cells. It has the following instructions:

> 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 adds one more instruction:

? Nondeterministically set the current bit to 0 or 1.


A whatfuck program does not take any input. It can result in one of 3 possibilities: 1 (accept), 0 (reject) or it may never halt.

The program will result in 1 if there exists a sequence of bits chosen for ?s which results in the program terminating with 1 as the current bit.

The program terminates with 0 if all possible choices terminate with current bit 0,

If some choices don't terminate, and all choices which terminate do so with 0, then the program will never terminate.

Your interpreter should run all possibilities simultaneously. You can't try 0 first and then try 1, because some programs will not terminate when they should. For example, *[?*]* will accept with the choice 1, but never terminate if you always choose 0.

As an example, here is a python 2 interpreter I wrote, not golfed

## Rules

• Your interpreter must accept a whatfuck program from stdin and print its result.

• You may assume the whatfuck program only contains characters []<>*?

• The array of bits is unbounded on both ends.

• Shortest code wins.

## Some Test Cases

This will fail if your code always tries 0 first

*[?*]*
1


Is there a subset of {-7,-3, 5, 8} whose sum is 3?

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


Is there a subset of {-7,-3, 5, 8} whose sum is 4?

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


Is there a way to assign boolean values to a,b and c such that

(a XOR b) AND (a XOR c) AND (b XOR c) is true?

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


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  Keeps track of the nondeterministic set of states in S, each with a code position p, a tape position t, and a list of tape indexes B. A tape index can appear multiple times in the list B, the tape at that index is 1 if the index appears an odd number of times in B. • Save 1 byte by replacing t+=(c=='>')-(c=='<'); with t+=c=='>';t-=c=='<';, another by replacing B=B+[t]*(c=='*') with B+=[t]*(c=='*'), and a third by replacing p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b; with p+=1+F.get(p,0)*-~-b-R.get(p,0)*b;. Great answer! (Sorry, I know this answer's super old!) – osuka_ Jan 4 '18 at 5:03 Infinite tape 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\$ \ζ->μ[((ο,ο),("",ζ))]

• It's remarkable how often Haskell answers succeed in getting top votes even if there are other answers with objectively better score around... – ceased to turn counterclockwis Jan 6 '13 at 20:48
• μ :) .............. – luser droog Feb 24 '13 at 5:40

## Python (405399 379)

It takes the input on one line, but I "may assume the whatfuck program only contains characters []<>*?" and newline isn't on that list :P

w,i,p,a={},0,raw_input(),[(0,0,[],[])]
for c in p:
if c=='[':a+=i,
if c==']':g=a.pop();w[i],w[g]=g,i
i+=1
i,z=0,lambda l:l and l.pop()or 0
while a:
n,c,l,r=a.pop(0)
try:o=p[n]
except:
if c:i=1;break
continue
if o=='*':c=not c
if o=='>':l+=c,;c=z(r)
if o=='<':r+=c,;c=z(l)
if o in'[]'and(']'==o)==c:n=w[n]
if o=='?':a+=(n+1,not c,l[:],r[:]),
a+=(n+1,c,l,r),
print i


• .append(item) -> +=[item], remove k and replace all calls with a+=[...] to save a few characters. – beary605 Dec 27 '12 at 2:20
• @beary605: thanks, however I ended up using +=item, which is even shorter. – marinus Dec 27 '12 at 4:30