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 <[email protected]> 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 <[email protected]> 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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
