Question

I am trying to solve the Problem Set #4. I have successfully written the solutions to the first three problems but I am unable to come up with a correct implementation of the recursive algorithm needed in order to solve the 4th problem “Multi-level decryption”.

Here’s what I have done so far:
http://dpaste.com/hold/1034597/

Can anyone please tell me what went wrong in the code?

Answer 1

'Additional Information'

I had the following in mind:
I defined an additional function to give back the position of the space after the last meaningful word in a string. It returns a tuple (True/False, Index/None)
In the main function (find_best_shifts_rec), I want the function to do every possible shift on the text until a bunch of meaningful words and a space appear, in which case the shift and the starting position are saved in a tuple and appended to a list. It breaks out of the shift loop and the function is recursively called from the index after the space.

Answer 2

got to think about this one.
to begin with, i think you have to assume that the text was encrypted with apply_shifts()

that means that there will be some number of consecutive words at the beginning of the text that can be decoded with a single shift,

then there will be a second group of consecutive words that can be decoded with 2 shift applications - one of which will be the same as the first group,

then there will be a third group of consecutive words that can be decoded with 3 shift applications - two of which will be the same as the first and second group .....

hmmm.........

to solve the problem,
-find the shift that decodes the most Consecutive words at the beginning
of the text and apply that shift to the text
-remove the decoded words from the text and 'save' them
-find the shift that decodes the most Consecutive words at the beginning
of the text and apply that shift to the text
-remove the decoded words from the text and 'save' them
-find the shift that decodes the most Consecutive words at the beginning
of the text and apply that shift to the text
-remove the decoded words the text and 'save' them
.......
when there isn't any text left to decode, concatenate all those decoded words that got saved.
save the decoded

Answer 3

Thanks for your answer. Yes, the text was indeed encrypted by apply_shifts().

But ‘find_best_shifts_rec’ is not supposed to return the decoded text. It only returns a list of tuples denoting the location of shifts and their values.

Answer 4

then what should the algorithm "save" instead of the decoded text

Answer 5

It keeps track of the list of tuples. I did a little editing to my function to make this happen:

http://dpaste.com/1034859/

Now the problem is that, as the test-prints in the code show, the list gets filled just before the last tuple and the program gives back nothing. So there must be something wrong with my base case that I don't know of, or some screw-up in the coding.

Answer 6

Final Update:

I figured the flaw in the code above. I used "return" alongside append() which would always return None. I also corrected an error in the indices of the list. Here's the final code that works:

http://dpaste.com/1035001/

Answer 7

that looks similar to where i was going. i'm going to try my hand at it - if you'd like, i'll post what i come up with.

Answer 8

Of course, I would very much like to see your code. Thanks.

Answer 9

Hi guys. First time posting. I got stuck on that recursive function and moved ahead in the course as I was at it for days with no results. Did anyone get the recursive function working? My code always ended up returning for 'a ' or 'at ' or loads of other 1 or 2 letter words with a space after them. Very Very frustrating.

Answer 10

here's what i got - so far, there is still a slight bug in it (some gobbledygook in the text)
http://dpaste.com/1039777/

Answer 11

Your code seems to be working and as the test-runs show, it's even more robust than that of mine. Well done! Please let us know if you edit it any further.

Answer 12

starting at text[493] it should decode to 'a look' - but the shift that decodes the 'a' also decodes 'add' with a space in between, my algorithm chooses 'a add' and messes up the word 'look'

starting at text[593] it should decode to 'came forward' - but the shift that decodes 'came' also decodes 'ox' with a space in between, my algorithm chooses 'came ox' and messes up the word 'forward'

not sure how to fix that

Answer 13

I see. I am now trying to read and understand your code. It seems like 'bestshift' will never be equal to None as the program always spits out a list of shifts for almost every input you give it:

http://dpaste.com/1042388/

Answer 14

... yep i didn't know if i really needed that but i wanted it to stop in case that happened

Answer 15

... yep i didn't know if i really needed that but i wanted it to stop in case that happened

hmmm, i wonder why it is finding shifts for that string of punctuation you posted.?

Answer 16

The other strings are also arbitrary and gibberish. The program should have returned "'NO SHIFT FOUND" for all of them.

Answer 17

thnx for that - here is a quick fix - the more i look at it though the more it looks kludgey to me. changes are at lines 41, 43,44, 48 and 49
http://dpaste.com/1042432/

Answer 18

cleaned up a bit by using a class to hold the state and do some of the nitty-gritty
http://dpaste.com/1044310/