tag:blogger.com,1999:blog-1307152710341271576.post2403175236361098258..comments2012-08-30T06:57:45.474+01:00Comments on Johan Jeuring's blog: Finding palindromesJohan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comBlogger32125tag:blogger.com,1999:blog-1307152710341271576.post-88015286969152488572012-08-30T06:57:45.474+01:002012-08-30T06:57:45.474+01:00Why don't you have a look at one of the soluti...Why don't you have a look at one of the <a href="http://finding-palindromes.blogspot.nl/2012/07/other-implementations-and-solutions.html" rel="nofollow">solutions using other languages</a> posted on my more extensive blog on <a href="http://finding-palindromes.blogspot.nl/" rel="nofollow">finding palindromes</a>?Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-9950889360384324492012-08-30T06:28:35.302+01:002012-08-30T06:28:35.302+01:00i need your help
i need a program that display a ...i need your help <br />i need a program that display a longest palindrome using object oriented programming<br />i hope you can help me<br />THANKS A LOT!!!rosalie de castrohttp://www.blogger.com/profile/17813492218553023752noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-88140727970309105522012-04-26T08:29:09.267+01:002012-04-26T08:29:09.267+01:00wonderful post. This one really explained it well....wonderful post. This one really explained it well.Abhishekhttp://www.blogger.com/profile/06446786244471842032noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-67802850321557701172012-04-26T08:26:32.577+01:002012-04-26T08:26:32.577+01:00wonderful post. This one really explained it well....wonderful post. This one really explained it well.Abhishekhttp://www.blogger.com/profile/06446786244471842032noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-4361355680553309882012-04-22T08:41:29.822+01:002012-04-22T08:41:29.822+01:00To rishi: the algorithm is really linear-time. I w...To <a href="http://www.blogger.com/profile/03745374063001928646" rel="nofollow">rishi</a>: the algorithm is really linear-time. I will publish a much more extensive description of the algorithm and its background in a month time or so.Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-92019332534381635942012-04-05T23:11:45.597+01:002012-04-05T23:11:45.597+01:00I'm really not counting the time taken or addi...I'm really not counting the time taken or adding complexities due to reading or printing or addition / comparison. I'm simply counting the no of iterations that are happening in the loop. I've tried this algorithm in Java / C / python / JS / PHP and I simple counted the no of iterations that are practically happening. Usually, Its has slight variances but always larger than O(n). As I said before, its still the most efficient algo I've come across but it doesn't seem to have a practical complexity of O(n). I will still digg a bit deeper and check if I've gone wrong somewhere or may be my understanding of the algorithm is still not as correct as it should be.rishihttp://www.blogger.com/profile/03745374063001928646noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-47995846593073685422012-03-19T08:41:00.237+01:002012-03-19T08:41:00.237+01:00Yes, I'm afraid you are missing something. I d...Yes, I'm afraid you are missing something. I don't check naively for the longest palindrome around each centre. I calculate this list of palindromes around each centre, together with the longest tail palindrome, in one sweep over the list. At each step I either move the centre, or I extend the longest tail palindrome, and there are only a linear amount of such steps available.Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-68812385123382032682012-03-18T03:14:04.542+01:002012-03-18T03:14:04.542+01:00Consider that you're trying to find the longes...Consider that you're trying to find the longest palindrome for the string "aaaaa". We will be performing O(n^2) operations in this case because every time the current center of the palindrome moves to the right by only one place till it reaches the center of the string (at which a time we stop checking because of the mirror property). Hence, we have (2n+1)/2 movements of the center of the palindrome and in the worst case the number of characters it has to check to the left and right of the center to see if it's a palindrome is O(n). Hence, O(n^2) in the worst case. Am I missing something?Shankhttp://www.blogger.com/profile/02599040071552171959noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-28818973435583029342012-03-17T14:11:04.435+01:002012-03-17T14:11:04.435+01:00To rishi: the theoretical analysis of the algorith...To <a href="http://www.blogger.com/profile/03745374063001928646" rel="nofollow">rishi</a>: the theoretical analysis of the algorithm shows it is linear-time (O(n)). My implementation might be worse than linear time, but not because of the algorithm used. It might be caused by printing, reading, etc.Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-36464482589670647592012-03-17T13:49:10.221+01:002012-03-17T13:49:10.221+01:00To Noah: I've now compared your lazy solution ...To <a href="http://www.blogger.com/profile/12638229035633367208" rel="nofollow">Noah</a>: I've now compared your lazy solution with my random-access solution using Criterion on the text of the King James' Bible. It turns out that the random access solution is about 1.7 times faster under unoptimized compilation. Using -O2 makes both solutions go slower.Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-73797488389703837202012-02-29T02:11:04.087+01:002012-02-29T02:11:04.087+01:00I just have one question, is the linear answer the...I just have one question, is the linear answer the best case or the worst case. <br /><br />I tested a string "cddeeeffffggggghhhhhhhiiiiiiii" which the loops run for around 104 times for a string of length of 30 and you'll find the same case with similar patterns. <br /><br />more data [here](http://pastebin.com/QawhPeuv). seems either worst case is not O(n) but O(nlogn) or worse. <br /><br />PS: except in such patterns it's still a fast solution.rishihttp://www.blogger.com/profile/03745374063001928646noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-63408309873273592012-01-05T08:21:08.752+01:002012-01-05T08:21:08.752+01:00Interesting. Both ideas (using a zipper-like struc...Interesting. Both ideas (using a zipper-like structure and returning results lazily) make sense. I'll have a look at your implementation, and will try to find out how the efficiency compares with my implementation.Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-59624739844743958142012-01-02T01:24:24.043+01:002012-01-02T01:24:24.043+01:00Awesome algorithm. Since it doesn't require f...Awesome algorithm. Since it doesn't require full random access, just forward and backward movement of the start of the palindrome, you can adapt it to work on list-based input using a zipper.<br /><br />Here's <a href="https://github.com/rampion/Palindrome/blob/master/Palindrome.hs" rel="nofollow">my implementation</a> that does so. It also produces lazy output, so `take 10 $ maximalPalindromeLengths (repeat ())` is `[0..9]`.Noahhttp://www.blogger.com/profile/12638229035633367208noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-33001129438533127122009-11-03T09:33:42.662+01:002009-11-03T09:33:42.662+01:00If I run palindromes on your input I get:
johan-j...If I run palindromes on your input I get:<br /><br />johan-jeurings-macbook-2:johanj$ palindromesi <br />aabbaabba<br />"abbaabba"<br /><br />as expected. (Here I use the software available via http://www.jeuring.net/Palindromes/.) I did not change anything in the software for calculating palindromes, so it should work for the code posted in this blog as well. Can you maybe contact me with the exact details?Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-62942449688077483612009-11-02T12:23:31.781+01:002009-11-02T12:23:31.781+01:00Please be kind enough to respondPlease be kind enough to respondAnuraghttp://www.blogger.com/profile/04743278571921953005noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-51161165338768285012009-11-02T12:21:59.673+01:002009-11-02T12:21:59.673+01:00I am finding the same problem with every above pro...I am finding the same problem with every above proposed algorithm. Kindly let me know where am I wrong-<br /><br />for the case "aabbaabba"<br />I am getting the same result with all the above codes, i.e. "aabbaa"<br /><br />while I expected the longest palindrome as "abbaabba"Anuraghttp://www.blogger.com/profile/04743278571921953005noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-25129358922264804022009-10-25T11:20:38.009+01:002009-10-25T11:20:38.009+01:00OK! I figured out why your solution is such a geni...OK! I figured out why your solution is such a genius :)<br /><br />abababa did it!Mhttp://www.blogger.com/profile/04296475349435748706noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-4784719407428366932009-10-25T11:06:16.807+01:002009-10-25T11:06:16.807+01:00Ok so I thought about this and wrote this code:
__...Ok so I thought about this and wrote this code:<br />_______________________<br /><br />string in; //load in as the input string<br />vector(int) a; //integer array <br /> //initialized to 1<br /> for(int i=1;i< a . size();i++)<br /> {<br /> if(in[i]==in[i-1])<br /> a[i]=2;<br /> if(i-a[i-1]-1 >=0)<br /> if(in[i]==in[i-a[i-1]-1])<br /> a[i]=a[i-1]+2;<br /> }<br />ans=max(a);<br />It seems to work for me. So why do you need to maintain anything except the palindrome number for the ith element?Mhttp://www.blogger.com/profile/04296475349435748706noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-80640462001435944312009-10-24T08:37:38.198+01:002009-10-24T08:37:38.198+01:00what is a longest 'tail' palindrome? how i...what is a longest 'tail' palindrome? how is it different from a simple palindrome? I am missing something here!Mhttp://www.blogger.com/profile/04296475349435748706noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-38971038674561915222009-07-11T10:36:30.690+01:002009-07-11T10:36:30.690+01:00This comment has been removed by a blog administrator.reythttp://www.blogger.com/profile/12576698580091921153noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-40276346644578140182007-12-02T12:01:00.000+01:002007-12-02T12:01:00.000+01:00Excuse me could somebody please rewrite the code u...Excuse me could somebody please rewrite the code using C as i (and probably more people) have problem following your idea...yiannishttp://www.blogger.com/profile/15589288288774932734noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-15746122516796530882007-10-24T14:52:00.000+02:002007-10-24T14:52:00.000+02:00I agree, it would be nice if I could easily change...I agree, it would be nice if I could easily change lists for something like Data.Sequence.<BR/><BR/>Thanks for the formatting error, corrected now.Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-73222967800086446332007-10-22T08:00:00.000+02:002007-10-22T08:00:00.000+02:00Aha. That makes more sense.As originally published...Aha. That makes more sense.<BR/>As originally published,<BR/> finalCentres n t c === (reverse (take n t)) ++ c<BR/>and I wondered why you used a more complicated-looking definition.<BR/><BR/>I believe using a fingertree (Data.Sequence) instead of a list for centres gives the queue performance characteristics needed for online streaming, but that makes the code less pretty.<BR/><BR/>(It would be lovely if the Prelude-defined list (and string) syntax were typeclasses, so efficient alternatives could be used with the same elegant-looking code.)<BR/><BR/><BR/>(Formatting note: The corrected, longer definition of finalCentres now runs off past the margin, chopping off the end of the line, in Firefox on Mac, unless I shrink the display font)Michael Rogerhttp://www.blogger.com/profile/08729150476888743293noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-82715098850277851392007-10-11T15:57:00.000+02:002007-10-11T15:57:00.000+02:00There was something wrong in a corner case. In par...There was something wrong in a corner case. In particular, the function finalCentres was lacking an occurrence of min (added to the post now). <BR/><BR/>Unfortunately, this error wasn't caught by my unit tests. I have now added a QuickCheck property to my code:<BR/><BR/>> propPalindromes :: Property<BR/>> propPalindromes = <BR/>> forAll (arbitrary:: Gen [Int]) $ <BR/>> \l -> let a = array (0,length l - 1) (zip [0..] l)<BR/>> in reverse (longestPalindromes a) == <BR/>> longestPalindromesQ a<BR/><BR/>That is, functions longestPalindromes and longestPalindromesQ should return the same result. This property passes 1000 tests.<BR/><BR/>And indeed, function longestPalindromes returns the list of lengths of palindromes in reverse. This is easily reversed of course, but requires some tricks in order to make the algorithm still `on-line' (a result is printed whenever it has been computed).Johan Jeuringhttp://www.blogger.com/profile/14035760811349164958noreply@blogger.comtag:blogger.com,1999:blog-1307152710341271576.post-69466867206478314942007-10-10T09:25:00.000+02:002007-10-10T09:25:00.000+02:00Either I failed to copy-paste correctly, or someth...Either I failed to copy-paste correctly, or something is not right in the corner cases:<BR/><BR/># These results are backwards:<BR/>> let arr = array (0,2) (zip [0..2] [1,2,2]) in longestPalindromes arr<BR/>[0,1,2,1,0,1,0]<BR/><BR/>> let arr = array (0,2) (zip [0..2] [2,2,1]) in longestPalindromes arr<BR/>[0,1,0,1,2,1,0]<BR/><BR/><BR/>This result is backwards and a bit wrong:<BR/><BR/>> let arr = array (0,3) (zip [0..] [2,2,1,2]) in longestPalindromes arr<BR/> [2,1,0,3,0,1,2,1,0]<BR/><BR/>-- Should be <BR/>-- [0,1,2,1,0,3,0,1,0]Michael Rogerhttp://www.blogger.com/profile/08729150476888743293noreply@blogger.com