## wctjerry 3 years ago For ps4 in mit 6.00 SC: When I was trying the provided solution, I found it slow to run 'decrypt_fable()'. Does anybody know why?

1. Constantine

Hi, It is very slow because of "brute force", exhaustive key search! Let's say 5 keys have been used! This means five tuples of 2 elements : (position, shift)! You are using brute force, say you are trying all the possibilities to find the good keys. If the plaintext had 100 words, you will need (in the worst case) to try 100 positions for one value of the shift!!!! We have 27 possible values for shift! This means that, just for the first (position, shift) pair, you will decipher the text (in the worst case) 27*100 = 2700 times!!!!!!!!!! this is huge! For all the text, for discovering all the five keys, you could need something like 2700^5 deciphering operations!!!!!! This effectively takes a lot of time!!!!!!!!!! cheers!

2. wctjerry

Thanks, Constantine. I am trying to use str.split to make it faster, avoiding testing eash of the letters. But something wrong is in my code I can't figure out. Could u give me a favor? I just change the find_best_shifts_rec function.

3. wctjerry

I pasted my codes here: http://pastebin.com/9nPkvwMr

4. Constantine

Ok Jerry! I saw your code! Look carefully to the split function! It cannot make the job here! Let's say you have a partial decrypted text like this : "my-friend--xtrtyiop". Note that I'am using '-' instead of the space character! Of course, the "xtrtyiop" stuff is the remaining ciphertext! Now, if you use split, you end up with the list ['my', 'friend', 'xtrtyiop']! There is a VERY BIG problem there! The space character just before the "xtrtyiop" IS NOT a space character! It is a very part of the remaining ciphertext!!!!! Some letter has been turned into it by the cipher procedure!!! But our split function doesn't know about that. Thus, your algorithm will fail since it will never find a valid decryption for "xtrtyiop". The good spliting function has to give this ['my', 'friend', '-xtrtyiop'] instead of this ['my', 'friend', 'xtrtyiop']. You can't use the split function! You have to cut the text by yourself (letter by letter ?). Oh oh, It seems that there is no escape here my friend! Cheers!!!

5. wctjerry

Thanks, friend. I got that.

6. ComputerAbuser

I ran into this problem as well. Thought I was all crafty using split, but as you know, you run into problems with leading spaces being dropped. It wouldn't be a problem if you could tell split to include leading spaces and stop once it hits a space after the word.

7. ComputerAbuser

Actually, I just realized how you can use split. After applying the shift, you need to verify that the first character is not a space. If it is, then you can skip that shift, otherwise you can use split to grab all of the characters before the next space.