A community for students.
Here's the question you clicked on:
 0 viewing
wctjerry
 2 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?
wctjerry
 2 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?

This Question is Closed

Constantine
 2 years ago
Best ResponseYou've already chosen the best response.1Hi, 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!

wctjerry
 2 years ago
Best ResponseYou've already chosen the best response.0Thanks, 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.

wctjerry
 2 years ago
Best ResponseYou've already chosen the best response.0I pasted my codes here: http://pastebin.com/9nPkvwMr

Constantine
 2 years ago
Best ResponseYou've already chosen the best response.1Ok 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 : "myfriendxtrtyiop". 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!!!

wctjerry
 2 years ago
Best ResponseYou've already chosen the best response.0Thanks, friend. I got that.

ComputerAbuser
 2 years ago
Best ResponseYou've already chosen the best response.0I 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.

ComputerAbuser
 2 years ago
Best ResponseYou've already chosen the best response.0Actually, 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.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.