Question

Anyone have solutions to problem set 3?

Answer 1

Working on it at the moment. Are we to use the strings given in the problem set? (ie atgacatgcacaagtatgcat)

Answer 2

They are good test cases, albeit you should have more strings to test. Test for strange patterns also ("atgcaatgccatgccatgcaatgc", searching for "atgc", for instance). Optimally, you should have a tester function to try different test cases. Back when I solved this problem set, I had some strange errors on my solution whenever I put repetitive strings together, i.e. looking for atga on a string that had atgaatga. Strange bugs exist in our solutions :-)

Answer 3

Also test for limit cases, like finding a pattern in a one letter string, stuff like that. Empirical testing is never exhaustive, but can increase your confidence at least by a fair amount.

Answer 4

I'm up to problem 3. I've got a working function, but I don't think it returns the correct answer. I seem to get quite a few of them.

http://codepad.org/1ijd19FJ

Answer 5

@LyonsDF I am at college right now, can't check your code more in depth. One thing I would ask you: in your recursive function, what would happen if, after you sliced the string, it would collapse into a new pattern? Say, "atgatgccfoobar". and you sliced after atgc, one pattern found would be the correct or the wrong answer? (I ask you also because it's kind unclear to me whether or not this is a valid problem.)

Answer 6

@forrest273: Yes, but it would be better for you to post your attempt and get criticism/help than to just look at other people's work.

Answer 7

@LyonsDF: I think your recursive one is actually closer to the solution for the iterative one, and you iterative one is really just wrapping the problem's Match() function around the count() function.

I think I have a recursive function with ok logic, but I can't see how to keep count.

http://codepad.org/5yNsyJQm

I also don't understand the instructions about slicing the string. I can't think of how it would help. At first I thought you would just find one match then operate on the remainder of the string, but that won't always work, for example if the string is "ababab" and the key is "aba". When you find "aba" at [0] and continue searching in slice [3:5] "bab", you would miss one because you didn't search slice [2:5] "abab".

So it seems you have to recusively call [0:5], [1:5], [2:5], [3:5], unwind. What am I missing? Thanks.

Answer 8

@klwdallas Yeah, my "recursive" one certainly is an iterative one (it did it before I had a grasp on the terms) and my "iterative" one is just cheating...

Now I've started ACTUALLY attempting a recursive one. I'm having a similar problem, I can't keep count. I actually get in searching 'atgc' in target1, I get two results ('atgc' does appear twice in that target string). However, I can't get it to just count how many times it goes through the loop (if initialize a 'count' variable, every time the function calls itself, anything I add to the count gets zeroed out (because it states count = 0 at the beginning of the function). Hrrrmm.

As far as your problem, instead of slicing the string after the length of the key. Try slicing the target string starting 1 index after where the first found string began.

here's what I've got so far:

http://codepad.org/g7yXSrkv

Answer 9

I do believe you have to declare a global variable in order to keep the count, because of the recursive call inside the function body would reinitialize the local variables, like you said.

Answer 10

Thanks @bmp, the solution was right under my nose:

http://codepad.org/Xr2OSL9D

That seems to work

Answer 11

Yeah, took the same slicing approach which seemed wrong based on the hints, and seemed inefficient. But it's the best solution.

I also settled on a global variable and was coming here to share. Felt strange also because the concept wasn't covered in the lectures. I think I'm ahead of the lessons too. Maybe I dozed off.

Answer 12

Here is mine:

http://codepad.org/J8RNr9Jw

It checks the key size relative to the string. It should save a few cycles.