I am competing in an online competition and the scenario is like this : I coded with my basic knowledge of clojure and got 11 out of 20 testcases and others being timed out and one being runtime error..
I started optimizing my code and read https://groups.google.com/forum/#!searchin/clojure/performance/clojure/SxT2MaOsip8/xoMkDVHeOqMJ and other google articles for performance.. but after that i just managed to solve only one more problem and i am stuck at 12 solved.. ( the time for each case is 8 seconds max) The last 12th was completed in 7.05 secs :) .. just on the border huh... :) The problem is about that of Solving calculataor expressions like "2+3/2/2/(2+8)" mod 10^8+7 gives answer 10^8+3.. Nevertheless it is the concern but optimizing code is :) This is current condition of my code : (ns fpcontest.expression) (def Term) (def Factor) (def ToMod (int (+ 1000000000 7))) ;; (int ToMod) (def toPrint false) (defn myprintln [& args] ;; (if toPrint ;; (apply println args)) ) (defn EulerDivNonMemo [^long x ^long p] (let [ToMod (+ p 2)] (loop [num (long 1) toPow p numDouble x] (if (= 0 toPow) ;;(do (myprintln " EulerDiv : " num " for " x p)) num (let [numDouble2 (rem (* numDouble numDouble) ToMod) halfToPow (bit-shift-right toPow 1)] (if (odd? toPow) (recur (rem (* num numDouble) ToMod) halfToPow numDouble2) (recur num halfToPow numDouble2)) )))) ) (def EulerDiv (memoize EulerDivNonMemo) ) ;; (EulerDiv 2 2) ;; (defn TestEulerDiv [] ;; (and ;; (= 2 (mod (* 4 (EulerDiv 2 (- 3 2))) 3)) ;; (= 1 (mod (* 2 (EulerDiv 2 (- 3 2))) 3)) ;; (= 1 (int (mod (* 2 (EulerDiv 2 (- ToMod 2))) ToMod)))) ;; ) ;; (= true (TestEulerDiv)) (defn Expression [lst] (let [term (Term lst) ;; p (myprintln term " term for exp " lst) sizeTerm (count term) evaluateExpr (fn [opr lst] (let [expr (Expression (drop 2 lst)) ;; p (myprintln expr " expr for Expr " lst " and " opr) intLst (first lst)] (cons (rem (opr intLst (first expr)) ToMod) (drop 1 expr))))] (if (> sizeTerm 2) (if (= (second term) "+") (evaluateExpr + term) (if (= (second term) "-") (evaluateExpr - term) term) ) ;; first of term is the answer term ) )) (defn Term [lst] (let [factor (Factor lst) ;; p (myprintln factor " factor for term " lst) sizeFactor (count factor) evaluateExpr (fn [opr lst] (let [expr (Term (drop 2 lst)) ;;p (myprintln expr " term for expr " lst " and " opr) intLst (first lst)] (cons (rem (opr intLst (first expr)) ToMod) (drop 1 expr) )))] (if (> sizeFactor 2) (if (= (second factor) "*") (evaluateExpr * factor) (if (= (second factor) "/") (let [expr (Term (drop 2 factor)) fExpr (first expr)] (cons (rem (* (first factor) (EulerDiv fExpr (- ToMod 2))) ToMod) (drop 1 expr)) ) ;;(evaluateExpr / factor) factor) ) factor ) )) (defn Factor [lst] (let [fFactor (first lst) ;;p (myprintln " Factor has : " lst) ] (if (= fFactor "+") (cons (int (Integer. (second lst))) (rest lst)) (if (= fFactor "-") (cons (- (int (Integer. (second lst)))) (rest (rest lst))) (if (= fFactor "(") ;; remove the '(' and ')' (let [expr (Expression (rest lst))] (cons (first expr) (drop 2 expr)) ) ;; (if (= (count lst) 1)) (cons (int (Integer. (first lst))) (rest lst)) ;;(myprintln "I do not know where i am... " lst) ) )) ) (defn split-with-delim [d s] (clojure.string/split s (re-pattern (str "(?=" d ")|(?<=" d ")")))) (defn make-calulator-list [s] (->> s (split-with-delim #"[\/\+\-\*\(\) ]") (filter #(not (or (= "" %) (= " " %)))) doall )) (defn StartRun [FuncToCall inputParse outputParse] (let [lines (line-seq (java.io.BufferedReader. *in*))] (outputParse (FuncToCall (inputParse (first lines))))) ) and this is how i am testing my code ................................ ****************** Test ******************************** (defn RunTests [] (and (= 1717 (int (first (Expression (make-calulator-list " 22 * 79 - 21"))))) (= 12 (int (first (Expression (make-calulator-list " 4/2/2 + 8"))))) (= 4 (int (first (Expression (make-calulator-list "4/-2/2 + 8"))))) (= 999998605 (int (mod (first (Expression (make-calulator-list "55+3-45*33-25"))) ToMod))) (= 999999987 (int (mod (first (Expression (make-calulator-list "4/-2/(2+8)"))) ToMod))) (= 22 (int (first (Expression (make-calulator-list "(22)*+1/-1+(1)"))))) (= 22 (int (first (Expression (make-calulator-list "11*(2/2)*2"))))) (= 11 (int (first (Expression (make-calulator-list "22*2/2*2"))))) (= '("4" "/" "-" "2" "/" "2" "+" "8") (make-calulator-list "4/-2/2 + 8")) (= '("4" "/" "-" "2" "/" "(" "2" "+" "8" ")") (make-calulator-list " 4/-2/(2 + 8)")) ) ) (RunTests) (Expression '("3" "+" "2")) (conj '("3") 1) (cons 2333 '(2 3 4)) (cons 2 (drop 1 '())) (drop 1 '()) (str (int 1.0)) (cons "1" '(1 "3")) (cons "1" nil) (int (Integer. "1")) (int (mod (first (Expression (make-calulator-list "4/-2/(2+8)"))) ToMod)) (mod (first (Expression (make-calulator-list "4/2"))) ToMod) (defn diffTime [func & args] (let [start (.getTime (java.util.Date.)) res (apply func args) end (.getTime (java.util.Date.))] (- end start))) (defn somuchtime= [times] (let [start (java.util.Date.) ] (loop [iTime 0] (if (= iTime times) start (recur (inc iTime)))))) (defn GenerateCalculatorTests [nums] (loop [num 0 sb (StringBuilder.)] (if (= num nums) (str "1" (.toString sb)) (->> sb ((fn [sb] (let [r (rand-int 500)] (do (if (< r 100) (.append sb "+") (if (< r 200) (.append sb "-") (if (< r 300) (.append sb "*") (if (< r 497) (.append sb "/") (.append sb (str "*(" (GenerateCalculatorTests 4) ")+")))))) (.append sb (rand-int 1000000000)) sb)))) (recur (inc num)) )) ) ) (GenerateCalculatorTests 50) (defn Execute [num] (let [str (GenerateCalculatorTests num)] (do (println str " = " ) (Expression (make-calulator-list (GenerateCalculatorTests num)))))) (diffTime Execute 2074) I find that the last problem which is giving runtime error is may be StackOverflow as i get it in with (diffTime Execute 3000) ;; where 3000 tries to get a calculator expression of 3000 or more ints.. see GenerateCalculatorTests.. with diffTime i also found that using rem is faster than using mod.. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
