brainfuck.clj

(ns brainfuck)

(defn build-jumpmap [source]
  (let [points (for [x (range (count source))
                        :when (or (= \[ (nth source x)) (= \] (nth source x)))]
                  x)]
    (loop [[first & coll] points
           stack '() 
           map { }]
      (if first
        (if (= (nth source first) \[)
          (recur coll (conj stack first) map)
          (when (= (nth source (peek stack)) \[)
            (let [begin (peek stack)]
              (recur coll (pop stack) 
                (assoc map begin first first begin)))))
        map))))
    
(defn interpret [state jumpmap]
  (if (>= (:cp state) (count (:source state)))
    state
    (recur
      (let [cmd (nth (:source state) (:cp state))]
        (cond 
          (= \> cmd)
              (assoc state 
                  :cp (+ 1 (:cp state)) 
                  :dp (+ 1 (:dp state))
                  :memory (if (= (count (:memory state)) (+ 1 (:dp state)))
                            (concat (:memory state) [0])
                            (:memory state)))
          (= \< cmd)
              (assoc state 
                  :cp (+ 1 (:cp state)) 
                  :dp (- (:dp state) 1))
          (= \+ cmd)
              (assoc state 
                  :cp (+ 1 (:cp state)) 
                  :memory (assoc 
                    (vec (:memory state))
                    (:dp state)
                    (+ 1 (nth (:memory state) (:dp state)))))
          (= \- cmd)
              (assoc state 
                  :cp (+ 1 (:cp state)) 
                  :memory (assoc 
                    (vec (:memory state))
                    (:dp state)
                    (- (nth (:memory state) (:dp state)) 1)))
          (= \, cmd)
              (assoc state 
                  :cp (+ 1 (:cp state)) 
                  :memory (assoc 
                    (vec (:memory state))
                    (:dp state)
                    (first (:input state)))
                  :input (rest (:input state)))
          (= \. cmd)
              (assoc state 
                  :cp (+ 1 (:cp state)) 
                  :output (concat (:output state) [(nth (:memory state) (:dp state))]))
          (= \[ cmd)
              (assoc state 
                  :cp (if (= 0 (nth (:memory state) (:dp state)))
                        (get jumpmap (:cp state))
                        (+ 1 (:cp state))))
          (= \] cmd)
              (assoc state 
                  :cp (if (= 0 (nth (:memory state) (:dp state)))
                        (+ 1 (:cp state))
                        (get jumpmap (:cp state))))))
      jumpmap)))
      
(defn execute-string
  "Evaluate the Brainfuck source code in `source` using `input` as a source of
  characters for the `,` input command.

  Either returns a sequence of output characters, or `nil` if there was
  insufficient input."
  [source input]
  (let [state 
    {
      :cp 0 
      :dp 0
      :memory '(0)
      :input (map int (seq input))
      :source (seq source)
      :output '()
    }]
    (let [result (interpret state (build-jumpmap source))]
      (if (empty? (:output result))
        nil
        (apply str (map char (:output result)))))))