someone posted a 200,000 char test-string: http://pastebin.com/raw.php?i=a8veAND3 (doesn't view properly in chrome, view-source and save) and the previous code failed pretty hard..
so, new approach - one pass has all the information on where each character occurs. so, create a map with each character as key having value as list of indices where the character occurs - test for palindrome between these indices for each key(character) - keep track of current-largest-palindrome and ignore strings smaller than that code: http://clojure.pastebin.com/zmmH1G58 new times(for 200,000 char string): real 3m0.351s user 3m1.299s sys 0m1.008s largest palindrome: amanaplanaracecaranalpanama On Oct 15, 1:22 pm, siddarth shankar <sith.darth.shan...@gmail.com> wrote: > i could get it down to around 1.6/1.7 seconds > > s...@sid-xxxxxxxx:~$ time clojure dummy.clj > woohoo palindrome: eve > woohoo palindrome: ranynar > > real 0m1.739s > user 0m2.088s > sys 0m0.124s > > made a couple of changes > - only call 'palindrome?' for substrings between identical > characters(between 2 'p's etc.) > - ignore substrings smaller than our currently largest palindrome > > code: > --------------------------------------------------------------------------- > --------------------------------------------------------------------------- > ------------------------- > (def source2 > "fourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnation > conceivedinzlibertyanddedicatedtothepropositionthatallmenarecreatedequalnow > weareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceiv > edandsodedicatedcanlongendureweareqmetonagreatbattlefiemldoftzhatwarwehavec > ometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavethe > irlivesthatthatnationmightliveitisaltogetherfangandproperthatweshoulddothis > butinalargersensewecannotdedicatewecannotconsecratewecannothallowthisground > thebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorpo > nwertoaddordetracttgheworldadswfilllittlenotlenorlongrememberwhatwesayhereb > utitcanneverforgetwhattheydidhereitisforusthelivingrathertobededicatedheret > otheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvanceditisrath > erforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonor > eddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasure > ofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthi > snationunsdergodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebyth > epeopleforthepeopleshallnotperishfromtheearth") > > (def max-length 2) > > (defn palindrome? > [#^String s] > (let [len (.length s)] > (loop [i 0 > j (dec len)] > (if (> i j) > (do > (println "woohoo palindrome: " s) > (when (> len max-length) ;; set the max-length > thread-safely? > (def max-length len))) > (when (= (.charAt s i) (.charAt s j)) > (recur (inc i) (dec j))))))) > > (defn find-largest-palindrome > [#^String s] > (let [len (.length s)] > (loop [i 0 > j (+ i max-length 1)] > (let [sub-string (.substring s i (inc j))] > (if (= (.charAt s i) (.charAt s j)) > (palindrome? sub-string)) ;; can spawn into a thread- > pool? > (if (= j (- len 1)) > (when (< i (- len max-length)) > (recur (inc i) (if (> len (+ i max-length 1)) > (+ i max-length 1) > (dec len)))) > (recur i (inc j))))))) > > (find-largest-palindrome source2) > --------------------------------------------------------------------------- > ----------------------------------------------------------------------- > > - using clojure 1.1.0 (ubuntu maverick package!!) > - ignoring substrings smaller than current-palindrome makes a > difference of only about .5 secs (maybe better for larger strings?) > - can the recur bits in the code above be more elegant/idiomatic? > looks really hacky > > ps: getting clojure + emacs to work is still bumpy :D > > On Oct 14, 5:19 am, Btsai <benny.t...@gmail.com> wrote: > > > > > I think the indexing in all-combs may be off, causing it to miss > > certain combinations/substrings. > > > user=> (all-combs "abc") > > ("a" "ab") > > > I used this instead: > > > (defn substrings [s] > > (let [length (count s)] > > (for [i (range length) > > j (range (inc i) (inc length))] > > (subs s i j)))) > > > user=> (substrings "abc") > > ("a" "ab" "abc" "b" "bc" "c") > > > On Oct 12, 1:02 pm, tonyl <celtich...@gmail.com> wrote: > > > > Hi, I just started to learn clojure in a more serious way and I am > > > doing the first level of the greplin challenge. > > > > I made it to work with a short palindrome like the example they give > > > me, but when it comes to work with the input file, it takes for ever > > > and I have to stop it. > > > > $ time clj level1.clj > > > ^C > > > real 11m35.477s > > > user 1m44.431s > > > sys 9m3.878s > > > > This is my code: > > > > (defn palindrome? [s] > > > (= s (reduce str (reverse s)))) > > > > (defn all-combs [in] > > > (let [len (count in)] > > > (for [i (range 0 (- len 2)), j (range (+ i 1) len)] > > > (subs in i j)))) > > > > (defn max-comp [x y] > > > (let [lenx (count x), leny (count y)] > > > (cond (< lenx leny) 1 > > > (= lenx leny) 0 > > > (> lenx leny) -1))) > > > > ;;(let [input "I like racecars that go fast"] > > > (let [input (slurp "../_input/level1.in")] > > > (println (nth (sort max-comp (filter palindrome? (all-combs > > > input))) 0))) > > > > The input file is thishttp://challenge.greplin.com/static/gettysburg.txt > > > > It looks a bit procedural. It is long, but I don't think is the > > > biggest bottleneck, I think it is my approach to create all the > > > combinations possible for substrings. Maybe I should be using a lazy > > > seq? How would I go to do that? -- 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
