News for hackers. Stuff that matters.
Re:Can you solve it? The Greplin programming challenge by l0nwlf on Friday October 08, 2010 @03:25PM (#1772996)
Brute works here because of bad test case. Author could have generated a smart test case and then optimal algorithm could be using suffix array which takes O(n), brute would take O(n!). However a bit smart brute gave the answer in approx 3-4 minutes ( computation + coding time). And yes, Python FTW.
Re:Can you solve it? The Greplin programming challenge by orangecat on Friday October 08, 2010 @04:38PM (#1773279)
Isn't brute force just O(n^3)? Loop over each character to start potential palindrome, loop from start character to end, reverse substring and compare. But yeah, the test input should be longer and/or smarter. Ditto on the third problem.
Re:Can you solve it? The Greplin programming challenge by brown9-2 on Friday October 08, 2010 @04:49PM (#1773323)
reverse substring and compare

D'oh! My is_palindrome(word) just got a lot shorter, thanks :)

Re:Can you solve it? The Greplin programming challenge by johnfn on Friday October 08, 2010 @07:44PM (#1773880)
3-4 minutes!

Try this:

    for i in range(len(str)):
         for j in range(i, len(str)):
              if str[i:j] == str[i:j][::-1]:
                  #...
Choose the start and end indices. Then take a slice to see if it's a palindrome. Nice and speedy! :)
Re:Can you solve it? The Greplin programming challenge by preek on Friday October 08, 2010 @06:25PM (#1773672)
3-4min? Since it was only like 5 lines of code I did it in brute force. Python and Mac Mini here - the answer came almost instantaneously.
Re:Can you solve it? The Greplin programming challenge by l0nwlf on Friday October 08, 2010 @11:18PM (#1774240)
By 3-4 minutes I mean both computation as well as coding time. Solution of mine came in < 1s.