Consider This Catharsis
Pages
Author  Topic: Consider This Catharsis 

Guardian
Member # 6670

written Tuesday, October 23 2007 14:20
Profile
Homepage
Meh; the last time I did something like this a few people partook. quote: quote: Posts: 1509  Registered: Tuesday, January 10 2006 08:00 
Law Bringer
Member # 2984

written Tuesday, October 23 2007 15:01
Profile
Homepage
This is brainstorming, not a formal description: If we do not need to work in place, I'd first make a copy of the string that is stripped of case and nonalpha characters. This is only a single pass over the string  O(n)  and takes at most as much memory as the string. This would greatly simply the analysis as we don't need to account for spaces or case any more. I would then try to find potential center positions first  two characters that are consecutive, or one that is sandwiched between the same characters.  For each character from 0 to length of string  Is next character equal to this character or to previous character?  Store the current index in a collection of potential palindromes. This step can be done in a single pass over the string and is O(n). (We need to store the information whether this is an even or odd length palindrome, and I can think of no elegant solution but only a special case checking. The following assumes an oddlength palindrome for simplicity.) Next, we eliminate these candidates by extending each and finding out how long they get.  Start i at 1  While there are still values in the collection  Increment i  For each value in the collection  Compare characters at distance i in both directions from the value  If they're not equal (or one of the positions compared lies outside string boundaries), eliminate this value  The longest palindrome (still assuming odd length) is (i1)*2+1. Because this algorithm identifies all candidates first and eliminates this tree of possibilities in Level Order, it is most efficient on a string with few such candidates or even just a single long palindrome. In that ideal case it could be practically linear. The worst case scenario is a string of equal letters. In this case, all letters are potential candidates and will be examined until each reach the edge and only the center is left, causing it to become O(n^2). An alternative solution would be to eliminate each candidate completely in their own order, starting at the ones closest to the center (most room to expand). This would be faster in some cases but slower in others  I'm not sure how common each of these cases far.  Gah. Tired. I hope I haven't just excreted complete nonsense. [ Tuesday, October 23, 2007 15:02: Message edited by: Xian ]  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
Post Navel Trauma ^_^
Member # 67

written Tuesday, October 23 2007 15:04
Profile
Homepage
He's making your life difficult  the substring doesn't have to be consecutive, so AxByA should return ABA.  Barcoorah: I even did it to a big dorset ram. New Mac BoE Posts: 1798  Registered: Thursday, October 4 2001 07:00 
Law Bringer
Member # 2984

written Tuesday, October 23 2007 15:07
Profile
Homepage
WTF? Ouch, forget it then...  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
Nuke and Pave
Member # 24

written Tuesday, October 23 2007 16:16
Profile
Homepage
Why do I have a feeling that this problem is NPcomplete? :) I haven't done any NPcompleteness proofs in several years, so I'll think about it after work, but it is looking similar to some other innocentlooking problems that turn out to have only exponential solutions. (The obvious algorithm for this one is to look at all substrings that are skipping a single letter, then run recursively until you get down to strings of length 1, which gives you a O(n!) running time.)  Be careful with a word, as you would with a sword, For it too has the power to kill. However well placed word, unlike a well placed sword, Can also have the power to heal. Posts: 2649  Registered: Wednesday, October 3 2001 07:00 
Law Bringer
Member # 335

written Tuesday, October 23 2007 16:44
Profile
Homepage
I am not a programmer, so here's my terrible solution. It very quickly gets out of hand for long strings with many nonunique characters, but it should eventually spit out a solution. Define variables longestPalindrome and currentPalindrome. Identify characters that appear more than once in the string. If there are no such characters, add 1 to currentPalindrome and compare currentPalindrome to longestPalindrome. If the string is an empty set, don't increment currentPalindrome. If longest is shorter, let longest = current. For every character that is nonunique, find the first and last instance of the character, then call the same function with the string of characters between those two characters as its argument. Add 2 to currentPalindrome. —Alorael, who thinks this will get the right number if it doesn't crash the computer with an immense string. Using this kind of algorithm on the Bible would be a bad idea. Posts: 14579  Registered: Saturday, December 1 2001 08:00 
Nuke and Pave
Member # 24

written Tuesday, October 23 2007 16:52
Profile
Homepage
EDIT: Never mind. [ Tuesday, October 23, 2007 16:54: Message edited by: Zeviz ]  Be careful with a word, as you would with a sword, For it too has the power to kill. However well placed word, unlike a well placed sword, Can also have the power to heal. Posts: 2649  Registered: Wednesday, October 3 2001 07:00 
Shaper
Member # 32

written Tuesday, October 23 2007 17:26
Profile
 Lt. Sullust Quaere verum Posts: 2462  Registered: Wednesday, October 3 2001 07:00 
Law Bringer
Member # 2984

written Wednesday, October 24 2007 08:57
Profile
Homepage
I think better in terms of numerical operations than character comparisons. Perhaps we can reduce the problem (requiring at most quadratic time, which is still less than the current solutions) by first comparing all characters with each other and building a boolean matrix: I'll vainly demonstrate on my name: I believe that in this matrix, we can, navigating through rows and columns, find the longest possible chain. I still need to figure out how, but I posted this here to give you all a little nudge in a direction that might show promise.  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
Law Bringer
Member # 2984

written Wednesday, October 24 2007 09:31
Profile
Homepage
Edit: To make clear how the matrix visualizes the solutions, here is another image that shows the matches we are looking at with X instead of 1: Obviously, whenever we pick a certain 1 as a starting place, we then look at the triangle below and to the left of this position. There is still the problem of identifying the most promising place  look at the current example, where merely looking at the outmost matches wouldn't have helped us find which solution was better. If it were "Dintiraden", the "nadan" solution would not exist, but we couldn't have known it from the outmost matches: Perhaps we should instead start at the other end, where we know we must end up? Start on the main diagonal or all those 1 positions that lie adjacent. In this case, whenever we consider a certain position, what is left is not a triangle, but a rectangle  above and to the right of the position we're looking at. You then have to pick another match out of the triangle that's left, and repeat the process. This process might still take polynomial time, though  if the problem is provably NPcomplete, there's no way around that.  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
By Committee
Member # 4233

written Wednesday, October 24 2007 09:39
Profile
Caveat: I am not a programmer If there are no characters in the string, it would return 0. You would then need to search for all pairings of identical characters within the string. If there are no pairs, then the function returns a maximum palindrome length of 1. After that, once the algorithm has identified pairs, we would make the function recursive, such that the function would repeat within each substring between the identified pair. Is there some other way to go about this? What does NPcomplete mean?  In today’s America, there are more World of Warcraft players than farmers. Posts: 2242  Registered: Saturday, April 10 2004 07:00 
Law Bringer
Member # 2984

written Wednesday, October 24 2007 09:41
Profile
Homepage
Wait wait wait. Do you know how we solved a labyrinth in FORTRAN, entirely without backtracking? We passed over the entire field, beginning at the entrance, and set each field unexplored field (value "0") adjacent to an explored field (value >0) equal to the value of the explored field + 1. This way, each field of the labyrinth had the minimum number of steps required to reach it. A long path might still take almost n^4 calculations (Longest theoretical path is n^2 steps, and each step requires a loop over the n^2 board), but we got rid of the backtracking and recursion. Perhaps we can "accumulate" a solution here too? By incrementing all the values in the rectangle shown in the last post by 1... the only problem is that the rectangles overlap...  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
Shaper
Member # 32

written Wednesday, October 24 2007 10:15
Profile
I'll need to think about it a bit more, but I'm pretty sure my solution runs in polynomial time. Albeit with a fairly large exponent...  Lt. Sullust Quaere verum Posts: 2462  Registered: Wednesday, October 3 2001 07:00 
Nuke and Pave
Member # 24

written Wednesday, October 24 2007 10:17
Profile
Homepage
Drew, "NP" is a class of problems that are assumed to have No Polynomialtime solutions. NPComplete problems are the hardest problems in that group. The "complete" part of description means that if you can solve one of these problems in polynomial time, you can solve all of them, and by extention all of NP problems. "Polynomial time" means that for a problem of size X, it will take X, or X^2, or X^3, or some other fixed power of X steps to solve the problem. For example:  Checking if a list of size X contains letter 'a' takes at most X steps.  An obvious algorithm for finding biggest number in a list of size X takes X^2 steps. (For each number in the list, go through the whole list looking for a bigger number.) Aran, that labirinth solution was a simple BreadthFirst Search of a graph. I don't think you can reduce this problem to a BFS. The solutions proposed so far have exponential worstcase running time (when run on a string of same letters), but polynomial averagecase running time. This sounds very familiar, but I don't remember the details. I need to reread my algorithms textbook.  Be careful with a word, as you would with a sword, For it too has the power to kill. However well placed word, unlike a well placed sword, Can also have the power to heal. Posts: 2649  Registered: Wednesday, October 3 2001 07:00 
Shaper
Member # 32

written Wednesday, October 24 2007 10:22
Profile
In retrospect, my solution fails for "ababababa", as it will only extract either a string of b's or a string of a's...  Lt. Sullust Quaere verum Posts: 2462  Registered: Wednesday, October 3 2001 07:00 
Electric Sheep One
Member # 3431

written Wednesday, October 24 2007 10:54
Profile
I am interested in understanding better the complexity class NP. I had always supposed that NP stood for 'nonpolynomial', meaning problems for which no algorithm running in polynomial time exists. I have just learned (via the usual oracle call) that NP is 'nondeterministic polynomial', and refers to the 'nondeterministic Turing machine', which seems to be essentially the Turing machine that a god of luck would purposebuild for any problem. As prepayment for any information on the topic, I offer my own modest but nontrivial insight in the general theory of problem solving. Some problems are in the class NC, which stands for Noone Cares. Worse are problems in the class NCComplete, which noone will ever care about, because if they cared about any one of them, they would have to care about all the others too. The insight is that you should avoid working on these problems. *(laugh here) You should not laugh. *(and here)  We're not doing cool. We're doing pretty. Posts: 3335  Registered: Thursday, September 4 2003 07:00 
Guardian
Member # 6670

written Wednesday, October 24 2007 11:16
Profile
Homepage
Erm, not quite. P stands for Polynomial time. This means that the running time is a polynomial function based on the input size. For example, finding the largest item of a list of size 'n' can be solved in 'n' iterations (not n^2, as Zeviz said; just devote some memory to remembering the current maximum). NP stands for Nondeterministic Polynomial time. This means that, given a solution, we can verify it in polynomial time. For instance, consider the general boolean constraint problem: you have an arbitrary number of boolean statements of arbitrary length, sharing an arbitrary number of variables. There's no known algorithm to solve this general case in polynomial time, but if someone hands us a solution, we can check to see if it is correct in polynomial time (just see if every statement evaluates to 'true' with the given variables). Note: All problems in P are in NP (P is a subset of NP). Trivial to show: we can get a solution in polynomial time, and assuming the algorithm is correct, the solution is correct. One of the biggest problems in theoretical computing science is whether or not P=NP. That is, does every problem where we can verify a solution in polynomial time have a method of obtaining that solution in polynomial time? Which brings us to NPC: NPComplete. As Zeviz said, these are the problems that have been shown to be as 'tough' as any other problem in NP. Of course, if P=NP, then NPC is a subset of P. However, if P!=NP, then NPC=NPP. (There's also CoNP, which is the set of problems where we can verify if a problem has no solution in polynomial time.)  In other news, I just reinvented the wheel. Posts: 1509  Registered: Tuesday, January 10 2006 08:00 
Law Bringer
Member # 335

written Wednesday, October 24 2007 11:43
Profile
Homepage
Drew's solution is the same as mine. I wonder if there's something about learning to program that teaches you to think in a more programmish way. —Alorael, who thinks Spiderweb is exactly the right place to throw NCComplete problems. The only better forum for such issues is xkcd's. Posts: 14579  Registered: Saturday, December 1 2001 08:00 
Electric Sheep One
Member # 3431

written Wednesday, October 24 2007 11:53
Profile
Wikipedia told me that verifiability in polynomial time with a deterministic Turing machine is logically equivalent to solvability in polynomial time with a nondeterministic model. Hence the otherwise awkward name 'nondeterministic polynomial'. Evidently the nondeterministic solvability concept was the first one introduced, historically. But this is part of my question. Are nondeterministic Turing machines of any real interest, or were they just a notion people passed through on the way to realizing that verification was what they really wanted to discuss?  We're not doing cool. We're doing pretty. Posts: 3335  Registered: Thursday, September 4 2003 07:00 
Nuke and Pave
Member # 24

written Wednesday, October 24 2007 12:03
Profile
Homepage
quote:As far as I know, they are to quantum computing what regular Turing Machines are to regular computing, but I might be wrong on that. (As an amusing sidenote, there are people already writing graduate dissertations about solving problems on quantum computers, despite the fact that such computers themselves are still over a decade away, by the most optimistic estimates.)  Be careful with a word, as you would with a sword, For it too has the power to kill. However well placed word, unlike a well placed sword, Can also have the power to heal. Posts: 2649  Registered: Wednesday, October 3 2001 07:00 
Post Navel Trauma ^_^
Member # 67

written Wednesday, October 24 2007 13:09
Profile
Homepage
Quantum computers aren't much like nondeterministic turing machines. For a start, they probably can't solve NPcomplete problems in polynomial time. The conception of a quantum computer trying every possibility and picking out the right answer is more about bad science journalism than reality. I'm not sure what nondeterministic turing machines are used for, but if you go down a level or two, nondeterministic finite state automata are useful for thinking about regular expressions. I imagine that nondeterministic turing machines are useful for similar things, where you're looking to see if a solution exists, but don't want your analysis to be bogged down with details about backtracking and search order and whatnot. [ Wednesday, October 24, 2007 13:10: Message edited by: Khoth ]  Barcoorah: I even did it to a big dorset ram. New Mac BoE Posts: 1798  Registered: Thursday, October 4 2001 07:00 
Law Bringer
Member # 2984

written Wednesday, October 24 2007 13:16
Profile
Homepage
I'm still having trouble accepting the claim of NPcompleteness. Here's my next idea that I think runs in polynomial time. It's not a good polynomial (possibly n^3 or even n^4), but the NP property of the algorithm has to rest in a single level  if we can show that a step is repeated n^j times, and is n^k big, we are still in Polynomial complexity in total.  1. Generate my triangle matrix outlined above  O(n^2) 2. Examine the diagonal i=j+a (i is column, j is row). a is 1 in this first cycle. Complexity O(n) as there are less than n such diagonals. 2.1 Examine each value M(i,j+a)=1 in the diagonal. Call this point M(x,y). Complexity O(n) as the diagonal is less than n long. 2.1.1 Examine the triangle of values described by i>j and i<x and j>y. (In graphical terms, this is the triangle between the diagonal and the point to the lower left of M(x,y) ). In the beginning this triangle is empty and the step can be skipped. At the end, this triangle contains at most half the matrix and thus takes O(n^2) to search. 2.1.1.1 Find the largest value inside the triangle. 2.1.2 Set M(x,y) to this largest value + 1. 2.2 Repeat step 2 with a = a+1. 3. Search through the matrix to find the largest value. This has complexity O(n^2) again. 4. Return the largest value, and have some coffee. Aaah. I'm telling you, it's polynomial in the worst case! :P  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
Shaper
Member # 32

written Wednesday, October 24 2007 15:22
Profile
I've done a revamp of the code listed above. It should run correctly now, though at the sacrifice of some efficiency. I've gotten the following run times: The results for the final test are still pending. The rapid increase in time, while not completely eliminating the polynomial scale, certainly seems to indicate exponential. Perhaps I'll trying coding up Aran's solution to see how it compares...  Lt. Sullust Quaere verum Posts: 2462  Registered: Wednesday, October 3 2001 07:00 
Law Bringer
Member # 2984

written Wednesday, October 24 2007 15:58
Profile
Homepage
I've implemented it (in PHP :P ) I'm seeing a rapid increase in time as letters are added. But it's not immediately obvious whether it's a polynomial or a slow exponential, until I'm too tired to do the eyeballing. A sample of 281 letters had 14 seconds. 50 letters had 0.01 seconds. 100 letters had 0.25 seconds. 150 letters had 1.3 seconds. Or, more succinctly: [ Wednesday, October 24, 2007 16:00: Message edited by: Xian ]  The Noble and Ancient Order of Polaris  We're Not Yet Dead. Encyclopedia • Archives • Stats • RSS (This Topic / Forum) • Blog • NaNoWriMo Didchat thentagoespyet jumund fori is jus, hat onlime gly nertan ne gethen Firyoubbit 'obio.' Decorum deserves a whole line of my signature, and an entry in your bookmarks. Posts: 8752  Registered: Wednesday, May 14 2003 07:00 
By Committee
Member # 4233

written Wednesday, October 24 2007 17:54
Profile
quote:Sorry  I realized that just as I finished, but I was dashing out the door at the time. All due props to Alo for the nonprogrammer idea.  In today’s America, there are more World of Warcraft players than farmers. Posts: 2242  Registered: Saturday, April 10 2004 07:00 