Question

Hi. I decided to get back on the horse and start by doing ps3. What am I looking at here? Anybody try it?

Answer 1

It's not bad as it looks. There's one part that would have been difficult but he did out most of it in his template already. Which reminds me, don't forget to download the supplementary files in the column next to the assignment :)

Answer 2

Thanks. I've been programming and reading books. I've been actually thinking about going back to school, but that's not in the cards right now. Gonna really step up my game in 2012.

Answer 3

Altogether, it's a cool PSet. Just a heads-up: it's not really clear on the pdf, but always keep in mind the case where the substring matches are overlapping, i.e., 'banana', 'ana' should count 2, rather than 1. The straightfoward solution doesn't really catch this subtlety, but it's an easy fix.

Answer 4

Really? I've never encountered that overlapping issue. Post the code, pretty please?

Answer 5

Thing is, the straightfoward slice will reduce 'banana' to 'bna' (I mean, the one that people, including me, generally implement at first glance). A snippet completely different from this PSet that returns overlapping substrings is http://codepad.org/wSfTcXpi

Answer 6

I meant that my code does return overlapping substrings. Now I am not sure whether the problemset wanted us to or not.
I think I wanted to see the code for the straightfoward slice, since I didn't think of the overlapping issue until now.

Answer 7

http://codepad.org/OtJNYucq I think this snippet won't respond correctly to overlapping substrings, if this is what you want :-)

Answer 8

Ahhh. I didn't think to slice the string up, which is probably why I didn't encounter the problem. I used a simple counter instead. http://pastebin.com/CxR7wkXi

Question: in your code, why is it:
string = string[:x] + string[x+len(pattern):]
instead of just making string = string[x+1:] ?

Answer 9

Edit: I was thinking initializing the variable in the function was an interesting use in recursion, but the code doesn't actually work since your counter variable is being re-initialized every time the function is being called.

I would be interested to know how to implement a recursive counter, tho.

Answer 10

sorry for multi post >.>
but here is your problem http://codepad.org/KfwrmUzx

Answer 11

No problem. I actually solved it months ago, it was just something that I never thought about, until I tried out 'banana' 'ana' as input :-)
My favorite, albeit inefficient, solution is:
[i-1 for i in xrange(len(some_string)) if string.startswith(key, i - 1)]
Implement the counter as a 'hidden' initialized argument in the function works well, you actually pass the modified counter whenever you call some_recursive_function(input, counter), i.e. http://codepad.org/UAAPP2Ku

Answer 12

Ty. Will be very useful. But now really stumps me why your string slicing thing is always returning 1... hmmm...
Sorry for hijacking your thread, Jwalker >_<

Answer 13

Probably has to do it with some inner mechanics, somewhat confusing. I can't put my finger on it yet, so I would wait someone more acknowledged to say what they think about it. I would generally code it in a class, it's safer and more self-contained, i.e.
http://codepad.org/tP9Go8Y5

Answer 14

A cleaner one without the import at the beginning :-P http://codepad.org/aDOHLXwP

Answer 15

Probably should say that I don't follow the course 100%

Answer 16

Mate, the class stuff up there is not necessary to know at this point, I just pointed out a safer, and somewhat cleaner, way to code it.
Keep in mind that you should use find() function to return the index of the found pattern, then jump some length and carry on from there, but as string are immutable, you will need to assign a new one every time you slice (string[:index]), that's why in the problem set pdf indicates reading about slicing a list (and a string, for that matter). You don't neccessarily need to use it to solve the problem (as seleneyue showed with a clean code), but it's more intuitive.
Think about it this way, in order to a recursive function to work, you need two things: 1) a base case, one that will always be reached and guarantees that the function will terminate; 2) reduce the problem in each step. With slices, you can take as input some string of length X, then after the first step in the function, you reduce the string to X-length(pattern), until you reach the base case (no more matches in the string) :-)

Answer 17

I figured out why your code wasn't working :)
countStringMatchRec(string,pattern,numStrng) needs to be part of what is returned. The following modified code produces the expected non-overlapping answer.
Substituting string=string[x+1:] produces an overlapping count.

def recount(string,pattern, numStrng = 0):
x = find(string, pattern)
if x != -1:
numStrng += 1
string = string[:x] + string[x+len(pattern):]
return countStringMatchRec(string,pattern,numStrng)

Answer 18

Dumb me, haha. I was trying almost everything, except returning the function :-). Kudos for the catch.

Answer 19

Np. You probably wrote it a bit too long ago. :D

Answer 20

i think this one works
http://dpaste.com/679227/