Problem 150 - Palindromic numbers question

[Peter]

Hello

Running the code below in repl returns in less than a second but on
the site it gives a timeout. Not sure what I am doing wrong here

I am sure there are more elegant solutions for this problem, but for
now I would like to stick with what I have and understand what might
be wrong with it.

All help warmly welcomed.

Tx

Peter


[code]

user=> (def __
(fn p151 [n]
(letfn [
(palindromic? [n] (= (seq (str n)) (reverse (str n))))
(nxtpal [n]
(let [
strn (str n)
strln (.length strn)
firsthalf (subs strn 0 (/ strln 2))
middle (subs strn (/ strln 2) (+ (rem strln 2) (/ strln 2)))
guess1 (read-string (apply str (concat firsthalf (concat middle
(reverse firsthalf)))))
]
(if (> guess1 n)
guess1
(let [
nextfirsthalf (str (inc (Integer/parseInt (apply str
(concat firsthalf middle)))))
guess2 (cond
(= (.length nextfirsthalf) (.length
firsthalf)) (concat nextfirsthalf (reverse nextfirsthalf))
(= 2 (- (.length nextfirsthalf) (.length
firsthalf))) (concat (reverse (rest (reverse nextfirsthalf))) (rest
(reverse nextfirsthalf)))
:else
(concat nextfirsthalf (rest (reverse nextfirsthalf)))
)
] (read-string (apply str guess2))
)
)
)
)
(nextpalindrome [n] (if (< n 9) (inc n) (nxtpal n)))
] (if (palindromic? n)
(iterate nextpalindrome n)
(rest (iterate nextpalindrome n))
)
)
)
)
#'user/__
user=>
user=>
user=>
user=> (= (take 26 (__ 0)) [0 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77
88 99 101 111 121 131 141 151 161])
true
user=> (= (take 16 (__ 162)) [171 181 191 202 212 222 232 242 252 262
272 282 292 303 313 323])
true
user=> (= (take 6 (__ 1234550000)) [1234554321 1234664321 1234774321
1234884321 1234994321 1235005321])
true
user=> (= (first (__ (* 111111111 111111111))) (* 111111111
111111111))
true
user=> (= (set (take 199 (__ 0))) (set (map #(first (__ %)) (range 0
10000))))
true
user=> (= true (apply < (take 6666 (__ 9999999))))
true
user=> (= (nth (__ 0) 10101) 9102019)
true
user=>

[/code]

[Leif]

Hi, Peter.

This looks very similar to my code, which worked. The only thing that
comes to mind is that I didn't use `read-string`, and that function
might cause problems in the restricted environment the site uses to
run our code. Someone who knows more about Clojail might know if that
guess is true.

Maybe modify those parts of `nxtpal` to use a different method of
converting strings to integers?

Good luck,
Leif

[Peter]

Hi Leif

Tx for the suggestion. Tried Integer/parseInt iso read-string but that
seems to result in a similar behavior.

Peter

[Leif]

Hello again, Peter.

You might want to change (.length s) to something that doesn't use
Java interop. Unlike my last suggestion, this is not speculation :)

If anyone that understands 4clojure's execution environment is
listening, a brief description (maybe with constructs to avoid) would
be nice to have on the site's "Help" page.

--Leif

[Peter]

Leif,

Thanks for the tip. Can't get it working though. Think all Java
interop is out now.

Below is what I have

I kind of let it go btw. If the code works in REPL I am happy
enough :)

Tx

Peter

(fn p151 [n]
(letfn [
(palindromic? [n] (= (seq (str n)) (reverse (str n))))
(nxtpal [n]
(let [
strn (str n)

strln (count (str strn))

firsthalf (subs strn 0 (/ strln 2))
middle (subs strn (/ strln 2) (+ (rem strln 2) (/ strln 2)))
guess1 (read-string (apply str (concat firsthalf (concat middle
(reverse firsthalf)))))
]
(if (> guess1 n)
guess1
(let [

nextfirsthalf (str (inc (read-string (apply str (concat
firsthalf middle)))))
guess2 (cond
(= (count (str nextfirsthalf)) (count (str
firsthalf))) (concat nextfirsthalf (reverse nextfirsthalf))
(= 2 (- (count (str nextfirsthalf)) (count (str
firsthalf)))) (concat (reverse (rest (reverse nextfirsthalf))) (rest

(reverse nextfirsthalf)))
:else
(concat nextfirsthalf (rest (reverse nextfirsthalf)))
)
] (read-string (apply str guess2))
)
)
)
)
(nextpalindrome [n] (if (< n 9) (inc n) (nxtpal n)))
] (if (palindromic? n)
(iterate nextpalindrome n)
(rest (iterate nextpalindrome n))
)
)
)

[Greg]

Interestingly, I am also running into timeouts on problem 150 with
code which quickly passes all the tests in a REPL on my machine. As
far as I can see, my code does not have any Java interop. Any other
ideas?

(fn palindromes [min]
(let [smin (str min)
init-power (dec (count smin))
pals
(fn [outer-power]
(letfn [(gen [power ds] (lazy-seq
(let [shell #(+ % (apply * % (repeat power 10)))
expand
(fn [d]
(let [outer (shell d)]
(for [n (gen (- power 2) (rest ds))]
(+ outer (* 10 n))
)))
]
(cond
(zero? power) (range 10)
(= power 1) (range (if (= outer-power 1) 11
0) 100 11)
:else
(let [mind (if (= power outer-power) 1 0)
d (if-let [dc (first ds)]
(max mind (- (int dc) (int \0)))
mind)]
(mapcat expand (range d 10)))
))))
]
(gen outer-power (when (= outer-power init-power) smin))
))
sq (if (zero? init-power)
(mapcat pals (range))
(mapcat pals (iterate inc init-power)))
]
(drop-while #(< % min) sq)
))

[Hamed Asghari]

I am experiencing the same problem with timeouts but REPL is fine and I get correct results. Here's my code which seems as simple as can be:

(fn palindrome? [n]

  (filter #(let [v (str %)] (= (apply str (reverse v)) v)) (iterate inc n)))

Please let me know if anyone was able to figure out a workaround for the timeout.

[Leif]

Hi, Hamed.

Your solution has to check every integer between each palindrome.  This means for the third unit test it checks 500,000 numbers to get 6 palindromes.  This is why the problem states "The most simple solution will exceed the time limit!"  You should try to find an algorithm that generates palindromes instead of just check for them.

Good luck,
Leif

[Colin Jones]

I've got a similar thing going on with #150. I'm sure there are small efficiencies I can get somewhere, but I'm passing all the tests locally (plus some more that I wrote) in ~0.65 seconds. Is the timeout really that low, or the processor on the 4clojure server that slow? 

Thanks to everyone maintaining 4clojure - it's a lot of fun.

[hak]

i had the same problems. What worked for me is:

 - don't use java interop

 - avoid datatype conversions (str to int and vice versa), to achieve this i used a vector of digits (instead of a string) as palindrom representation

[Roman Obukhivskyi]

I've optimized the code to run under 80 ms for all tests but still had timeout.

Replacing 'for' macro with map fixed the problem.

[Alex]

The timeout/sandbox is killing me.

My local (mbp, 2.2ghz i7, 8gb) runs all tests in <= 60 ms for the string approach.  It uses iterate.  The only (explicit) java interop is Long/parseLong, and there are no reflection warnings.

I tried the vector of digits approach but couldn't make it perform anywhere near as fast as the string.

I also tried running the test multiple times in hopes that the sandbox would warmup.

I have an xmpp bot that exposes clojail to me [clojail "1.0.6"].  It is running on an under provisioned VM dev server.

The times for the tests (averaged in ms) is revealing:

;; Test 1 : 10

;; Test 2 : 12

;; Test 3 : 6

;; Test 4 : 2.5

;; Test 5 : 3050

;; Test 6 : 2900

;; Test 7 : 4300