# HG changeset patch
# User Robert McIntyre <rlm@mit.edu>
# Date 1333419654 18000
# Node ID d263df762c59c69996c096ab7e45128380abc7e9
# Parent  363b650a77ccab0ef2f2d01bc8eadfc18bc172d3
greatly speed up scroll-text by using binary-search.

diff -r 363b650a77cc -r d263df762c59 clojure/com/aurellem/gb/gb_driver.clj
--- a/clojure/com/aurellem/gb/gb_driver.clj	Mon Apr 02 20:30:28 2012 -0500
+++ b/clojure/com/aurellem/gb/gb_driver.clj	Mon Apr 02 21:20:54 2012 -0500
@@ -142,7 +142,7 @@
   ([]
     (continue! @current-state)))
 
-(defn run-moves [state moves]
+(defn run-moves [moves state]
   (set-state! state)
   (dorun (map #(Gb/step (button-mask %))
               moves))
diff -r 363b650a77cc -r d263df762c59 clojure/com/aurellem/gb/saves.clj
--- a/clojure/com/aurellem/gb/saves.clj	Mon Apr 02 20:30:28 2012 -0500
+++ b/clojure/com/aurellem/gb/saves.clj	Mon Apr 02 21:20:54 2012 -0500
@@ -15,4 +15,7 @@
   (read-state "talk-to-oak"))
 
 (defn normal-conv []
-  (read-state "normal-conversation"))
\ No newline at end of file
+  (read-state "normal-conversation"))
+
+(defn oak-battle []
+  (read-state "oak-battle"))
\ No newline at end of file
diff -r 363b650a77cc -r d263df762c59 clojure/com/aurellem/gb/util.clj
--- a/clojure/com/aurellem/gb/util.clj	Mon Apr 02 20:30:28 2012 -0500
+++ b/clojure/com/aurellem/gb/util.clj	Mon Apr 02 21:20:54 2012 -0500
@@ -154,7 +154,7 @@
       (zipmap backbone
               (apply (partial map list) seqs))))))
 
-(defn temporal-compare [& states]
+(defn memory-compare [& states]
   (apply common-differences
          (map (comp vec memory)
               states)))
diff -r 363b650a77cc -r d263df762c59 clojure/com/aurellem/run/util.clj
--- a/clojure/com/aurellem/run/util.clj	Mon Apr 02 20:30:28 2012 -0500
+++ b/clojure/com/aurellem/run/util.clj	Mon Apr 02 21:20:54 2012 -0500
@@ -30,6 +30,55 @@
           [new-actions new-state]
           (recur new-actions new-state))))))
 
+
+(defn binary-search [metric]
+  (let [baseline (metric 0)]
+    (loop [low 1
+           high 2]
+      (let [low-val (metric low)
+            high-val (metric high)]
+        (println low high)
+        (cond
+          ;; base case
+          (and (= low (dec high))
+               (not= low-val high-val))
+          high
+          ;; exponential growth
+          (= baseline high-val low-val)
+          (recur high (* high 2))
+
+          ;; binary search
+          (and (= baseline low-val)
+               (not= baseline high-val))
+          (let [test (int (/ (+ low high) 2))
+                test-val (metric test)]
+            (if (= test-val baseline)
+              (recur test high)
+              (recur low test))))))))
+
+(defn delayed-difference
+  [base alt delay difference-metric [moves root :as script]]
+  (let [generator
+        (memoize
+         (fn [n]
+           (run-moves
+            root
+            (repeat n base))))
+        len
+        (binary-search
+         (fn [n]
+           (= (difference-metric
+               (run-moves
+                (generator n)
+                (concat [alt] (repeat delay base))))
+              (difference-metric
+               (run-moves
+                (generator n)
+                (repeat (inc delay) base))))))
+        new-moves (concat moves (repeat len base) [alt])
+        new-state (run-moves (generator len) [alt])]
+    [new-moves new-state]))
+
 (defn delayed-difference
   [base alt delay difference-metric [moves root :as script]]
   (loop [branch-point root
@@ -49,6 +98,10 @@
         (recur base-branch (conj actions base))))))
 
 
+            
+
+
+
   
 ;; (defn advance
 ;;   ([base alt difference-metric [commands state]]
@@ -146,9 +199,12 @@
 
 
 
-(common-differences
- (vec (memory (step (talk-to-oak) [:a])))
- (vec (memory (step (talk-to-oak) []))))
+(memory-compare 
+ (step (talk-to-oak) [:a])
+ (step (talk-to-oak) [])
+ (step (oak-battle) [])
+ (step (oak-battle) [:a]))
+
  
 
 
diff -r 363b650a77cc -r d263df762c59 save-states/oak-battle.sav
Binary file save-states/oak-battle.sav has changed