Question

Stuck on PS4 Q4 - I'm trying to follow the pseudocode they provided for the problemfound here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-2/lecture-10-hashing-and-classes/MIT6_00SCS11_ps4-pseudo.pdf
How is step 7 implemented? If the recursive call returns none how do you have the program go back and try different shifts?

Answer 1

Also, the solution to this problem wasn't in the provided solutions file, where can I find it?

Answer 2

For me this was a difficult problem which I got it working just yesterday. My solution is a non recursive one but the concepts are very similar for the recursive case. I believe key is to run every possible shift in each call and then select from all possible valid words the one that is more likely to be correct I choose the one with the greatest length. You can check my solution it might help you: http://pastebin.com/MyUBYYra

Answer 3

Torres - thanks for the reply and the code, picking the word with the greatest length is a clever solution but what happens when you need to decode a short word? I think there has to be a mechanism for going back and trying different shifts after a valid word is decoded, but is found later on to not be the correct word (I'm lost as to how this would be coded though).

Answer 4

I thought about that to but right now I can not think of a solution for it. I guess you can check is the last word of the string is a valid word if not you have to go back but how far that is the question. If you find a good solution for this please let me know. I remember in one of the lectures the professor mention some probabilistic algorithms to decode some texts, therefore that is why I thought choosing the word with the largest length sort of fits with that concept.

Answer 5

I just thought that in the case of my solution I guess if the last word or if at any point the algorithm can not find a valid word you can look into the shift matrix for the previous shift and then see if there was another shorter valid word if there was then apply that shift and see if the last word of the string is valid if not you keep going back and check again. This looks very time consuming to implement.

Answer 6

I spent a lot of time trying to get this to work recursively. Attached is my solution...it seems correct as far as I can tell, although I have a tough time explaining it to myself, so I won't even try to explain it to someone else. I followed the steps in the pseudocode.

Answer 7

ekim49 your solution is 99% right except for "he boarded the car and turned a a he power" which should be "he boarded the car and turned on the power" and "came ox ward with subscriptions" which should be "came forward with subscriptions". This is because in some recursive call the algorithm is picking a valid word that is too short in length

Answer 8

you can easily fix this by modifying your algorithm slightly: I am including the code with very minor modifications to your function find_best_shifts_rec which fixes this problem

Answer 9

Good catch torres. Appreciate the code. I also noticed i was getting valid words after applying my code, but that the sentences didn't necessarily make sense.

In a sense though, isn't this solution "overfitting" the algorithm to the data? In other words, I could imagine there exists another encrypted passage where my original algorithm would produce a meaningful sentence, whereas the algorithm with the solutions you provided would not. Or maybe I am misunderstanding something conceptually? What do you think?

Answer 10

akin49 disregard probability calculation is wrong but in any case I think there is a higher probability in been right by picking the word with the largest length

Answer 11

Nice solution ekim, much more simple than I thought was possible: First, .split is very useful here, I was using enumerate and another for loop which was complicating things.

Second, I thought the problem with my code before was that a valid word was being decoded- but it was happening incidentally, that it wasn't the correct word - and so the shift would be wrong. But your code doesn't run into that problem at all - it correctly decodes all the words, and only very rarely decodes a valid word that isn't the one you want.

Anyway I've spent far too much time looking at this one problem, going to move on to the next lecture/ps now, thanks for the help.

Answer 12

Am I understanding this correctly? If the condition: "if ans is not None:" is not met (i.e. ans returns None) - then the program will return to the for loop and try a different shift? And in this way you correct for when a valid word incidentally decoded resulting in an incorrect shift.

Answer 13

Yep, that's right. And it spirals all the way throughout the recursion so if at any point down the recursion you can't get a valid word, each step prior to adjusts itself until that point that couldn't get a valid word can retrieve a valid word. If, after going through all possible combinations of prior shifts at all possible words, you still can't get a valid word at that point, the entire program will return None. (i think that's the right explanation...lol)