Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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
share|improve this question

3 Answers 3

Python, 305 chars

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.

share|improve this answer

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$ \ζ->μ[((ο,ο),("",ζ))]
share|improve this answer
1  
It's remarkable how often Haskell answers succeed in getting top votes even if there are other answers with objectively better score around... –  leftaroundabout Jan 6 '13 at 20:48
    
μ :) .............. –  luser droog Feb 24 '13 at 5:40

Python (405 399 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

share|improve this answer
1  
.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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.