News for hackers. Stuff that matters.
Re:Can you solve it? The Greplin programming challenge by shiven on Friday October 08, 2010 @08:30PM (#1773978)
Seems like I may be the only person to have used a bioinformatics approach to the first problem! bl2seq to the rescue!! I'll explain my approach if anyone seems interested... as I am not sure if posting solutions is acceptable here.

Edit: As others seem to be posting gist/snips etc. so I guess it is OK.

Step 0 - Copied parent string to file: p1.txt

Step 1 - Used python to reverse the entire string and copy to second file: cat p1.txt | python -c "print raw_input()[::-1]" > p2.txt

Step 2 - Formatted the two files, so as to be parsed as FASTA, by adding sequence name headers.

Step 3 - Use bl2seq (blastp) locally or online to align the two "sequences". Final alignment shows only one major chunk of identity, i.e. the answer.

So, in essence, a dynamic programming algo would work.

Re:Can you solve it? The Greplin programming challenge by stygianguest on Saturday October 09, 2010 @10:01AM (#1775024)
If bl2seq gets the longest common subsequence I did exactly the same thing. In haskell it just seems the right thing to do. Actually it would be damn interesting to see if there are patterns in the solutions for every programming language.