whatfuck.py

class State:
    def __init__(self,arr=[0],arr_i=0,code_i=0):
        self.arr = arr
        self.arr_i = arr_i
        self.code_i = code_i
    def copy(self):
        return State(self.arr[:],self.arr_i,self.code_i)
    def __str__(self):
        a = '['+''.join(map(str,self.arr))+']'
        p = ' '*(self.arr_i) + ' ^' + ' '*(len(self.arr) - self.arr_i + self.code_i) + ' ^'
        return a + ' ' + code + '\n' + p
    def __repr__(self):
        return 'State('+`self.arr`+','+`self.arr_i`+','+`self.code_i`

#instructions
#Return a new state if one is created, otherwise return None
def while_open(state):
    if state.arr[state.arr_i]:
        state.code_i += 1
    else:
        state.code_i = brackets[state.code_i]+1

def while_close(state):
    state.code_i = brackets[state.code_i]

def flip(state):
    state.arr[state.arr_i] = 1 - state.arr[state.arr_i]
    state.code_i += 1

def right(state):
    state.arr_i += 1
    if state.arr_i >= len(state.arr):
        state.arr.append(0)
    state.code_i += 1

def left(state):
    if state.arr_i:
        state.arr_i -= 1
    else:
        state.arr.insert(0,0)
    state.code_i += 1

def nd_choose(state):
    state.code_i += 1
    c = state.copy()
    state.arr[state.arr_i] = 0
    c.arr[c.arr_i] = 1
    return c

instructions = {
    '[':while_open,
    ']':while_close,
    '*':flip,
    '>':right,
    '<':left,
    '?':nd_choose }

states = [State()]
code = raw_input()

#Find matching brackets
brackets = [0]*len(code)
stack = []
for i in range(len(code)):
    if code[i]=='[':
        stack.append(i)
    elif code[i]==']':
        b = stack.pop()
        brackets[i]=b
        brackets[b]=i

while states:
    new_states = []
    for s in states:
        c = code[s.code_i]
        n = instructions[c](s)
        if n:
            new_states.append(n)
    states.extend(new_states)
    terminated = filter(lambda s:s.code_i == len(code),states)
    if any(map(lambda s:s.arr[s.arr_i],terminated)):
        print 1
        break
    states = filter(lambda s:s.code_i < len(code),states)
    if len(states) == 0:
        print 0
        break