1.1 --- a/clojure/com/aurellem/run/util.clj	Thu Apr 05 15:05:08 2012 -0500
     1.2 +++ b/clojure/com/aurellem/run/util.clj	Fri Apr 06 07:22:18 2012 -0500
     1.3 @@ -38,50 +38,76 @@
     1.4            (recur new-actions new-state))))))
     1.5  
     1.6  (defn binary-search [metric]
     1.7 -  (let [baseline (metric 0)]
     1.8 -    (loop [low 1
     1.9 -           high 2]
    1.10 -      (let [low-val (metric low)
    1.11 -            high-val (metric high)]
    1.12 -        (println low high)
    1.13 -        (cond
    1.14 -          ;; base case
    1.15 -          (and (= low (dec high))
    1.16 -               (not= low-val high-val))
    1.17 -          high
    1.18 -          ;; exponential growth
    1.19 -          (= baseline high-val low-val)
    1.20 -          (recur high (* high 2))
    1.21 -
    1.22 -          ;; binary search
    1.23 -          (and (= baseline low-val)
    1.24 -               (not= baseline high-val))
    1.25 -          (let [test (int (/ (+ low high) 2))
    1.26 -                test-val (metric test)]
    1.27 -            (if (= test-val baseline)
    1.28 -              (recur test high)
    1.29 -              (recur low test))))))))
    1.30 +  (loop [low 0
    1.31 +         high 1]
    1.32 +    (let [low-val (metric low)
    1.33 +          high-val (metric high)]
    1.34 +      (println "(" low high ")")
    1.35 +      (cond
    1.36 +       ;; base case
    1.37 +       (and (= low (dec high))
    1.38 +            (not= low-val high-val))
    1.39 +       high
    1.40 +       ;; exponential growth
    1.41 +       (= high-val low-val)
    1.42 +       (recur high (* high 2))
    1.43 +       
    1.44 +       ;; binary search
    1.45 +       (not= low-val high-val)
    1.46 +       (let [test (int (/ (+ low high) 2))
    1.47 +             test-val (metric test)]
    1.48 +         (if (= test-val low-val)
    1.49 +           (recur test high)
    1.50 +           (recur low test)))))))
    1.51  
    1.52  
    1.53  (defn delayed-difference
    1.54 +  "determine the shortest sequence of the form:
    1.55 +
    1.56 +   sequence = (concat (repeat n base) alt)
    1.57 +    which will cause difference-metric
    1.58 +   to yield a different value between.
    1.59 +
    1.60 +   (concat sequence (repeat delay base))
    1.61 +   and
    1.62 +   (repeat (+ n 1 delay base))
    1.63 +
    1.64 +   This search function is good for finding the optimum keypresses
    1.65 +   whose effect on the game is not revealed until several frames after
    1.66 +   those keys have been pressed (such as scrolling text)."
    1.67    [base alt delay difference-metric [moves root :as script]]
    1.68 -  (let [generator
    1.69 -        (memoize
    1.70 -         (fn gen [n] 
    1.71 -           (run-moves
    1.72 +  (let [states-cache (atom {})
    1.73 +        generator 
    1.74 +        ;; (memoize  ;; 32947 msecs
    1.75 +        ;;  (fn gen [n] 
    1.76 +        ;;    (run-moves
    1.77 +        ;;     root
    1.78 +        ;;     (repeat n base))))
    1.79 +
    1.80 +        (fn gen [n]  ;; 21150 msecs
    1.81 +          (if (= 0 n)
    1.82              root
    1.83 -            (repeat n base))))
    1.84 +            (if-let [cached (@states-cache n)]
    1.85 +              cached
    1.86 +              (do (swap!
    1.87 +                   states-cache
    1.88 +                   #(assoc % n
    1.89 +                           (run-moves
    1.90 +                            (gen (dec n))
    1.91 +                            [base])))
    1.92 +                  (gen n)))))
    1.93 +            
    1.94          len
    1.95          (binary-search
    1.96 -         (memoize (fn [n]
    1.97 -           (= (difference-metric
    1.98 -               (run-moves
    1.99 -                (generator n)
   1.100 -                (concat [alt] (repeat delay base))))
   1.101 -              (difference-metric
   1.102 -               (run-moves
   1.103 -                (generator n)
   1.104 -                (repeat (inc delay) base)))))))
   1.105 +         (memoize
   1.106 +          (fn [n]
   1.107 +            (if (= n 0) true
   1.108 +                (=(difference-metric
   1.109 +                   (run-moves
   1.110 +                    (generator n)
   1.111 +                    (concat [alt] (repeat delay base))))
   1.112 +                  (difference-metric
   1.113 +                    (generator (+ n 1 delay))))))))
   1.114          new-moves (concat moves (repeat len base) [alt])
   1.115          new-state (run-moves (generator len) [alt])]
   1.116      [new-moves new-state]))
   1.117 @@ -135,8 +161,8 @@
   1.118    ([^SaveState state]
   1.119       (character-codes->str
   1.120        (subvec (vec (memory state))
   1.121 -              text-address
   1.122 -              (+ text-address 82))))
   1.123 +              (+ text-address 0)
   1.124 +              (+ text-address  90))))
   1.125    ([] (displayed-text @current-state)))
   1.126  
   1.127  (defn scroll-text