Hacker News Reader

Comment by siglesias | Hacker News Reader

Anybody else browsing by mobile try to do Level 1 by inspection?

After doing the obvious brute force algorithm, the correct answer is not a real word. So you'll have a tough time getting it on your own

Well, I was suggesting looking for symmetrical triads (or repeating characters) and then working outward. I'd say the eye is pretty good at picking out symmetries.

Why aren't you guys just searching for the palindromes?

There's more efficient ways than doing every character, or groups of them... What constitutes a palindrome? What does that mean to simplify what we're doing?

http://www.w3schools.com/jsref/jsref_obj_string.asp

I was in the middle of thinking through the algorithm when I looked at it and saw the password in the text --- the password worked but I still want to code the algorithm later to confirm.

That's sort of what I mean here. It's like solving a wordsearch puzzle. There can't be more than a couple dozen strings with structure xyx, or xyyx. Find them by eye and work outward and see if it's zxyxz, and so on. Decided to make this process into my algorithm.

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.

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.

reverse substring and compare

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

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! :)

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.

By 3-4 minutes I mean both computation as well as coding time. Solution of mine came in < 1s.

Reply on news.ycombinator.com