Question

In the problem set 4, problem 4 Multi-level Code-breaking. if i use recursion, the program may find a solution tuple in front part of text, but in the end the program may not find a complete solution.
how can i make the recursion function return None in that case?
ocw site doesn't provide solution for that problem.

Answer 1

I never looked at that one, but I am betting that if you set a temp variable to none and modify it if something is found, it will unwind a bunch of nones and return none in the end.

Answer 2

def find_best(parameters):
result = find_best_shifts_rec(parameters)
if isComplete(result):
return result
return None

Answer 3

what is your base case and what do you return for the base case?

" ... but in the end the program may not find a complete solution. "
can you explain that? it should be able to decode all of the text by applying multiple shifts at the appropriate places.

If you would like to post your code we can look at it.
please use a code pasting site:

Answer 4

thanks for answering, based on dust7 suggestion. I modified my code.
http://dpaste.com/1335237/ In fact that code seem not to work so well.
At least I can't use it to break fable.txt. Is any one have a solution?

Answer 5

i have one, you want to see it or do you want comments on yours?

Answer 6

that's a heck-of-a list comprehension at line 365
- try putting a print statement at the top of the function something like print locals()
- create your own scrambled text (short) that you know the answer to and use it
to test your function: like this http://dpaste.com/1335650/

Answer 7

Hi, bwCA. I try to break the text you provide using my own program.
find_best_shifts_rec() just returns
[[(0, 24), (27, 15)], [(0, 24), (27, 21), (52, 15)]]
Unfortunately, find_best_shifts() returns [], because the word 'harrass' is NOT in the words.txt. Maybe I should see some other approachs to this problem.
bwCA, would you like to share your vision of solution.

Answer 8

hmmm, my bad .. i didn't notice that when i made it - but you get the idea.

did you use your own short test phrase?
did you try using print statements to see what was happening in your code?

your list comprehension has a loop within a loop, is that what you intended?

here is mine
http://dpaste.com/1336412/

Answer 9

this is what i did:
- apply a shift to the text
- split the text on word boundaries --> list
- count how many words at the beginning of the list are in the wordlist
- save that information for comparison
- repeat the above for all 26 (27?) shifts and save the one that
produces the most words
- remove all the cleartext and repeat all of the above with what is left
(just the ciphertext)
- stop when there is no ciphertext left or a shift cannot be found

Answer 10

No, I just use the random_scrambled() to debug the code.
Yes
Yes
I try to solve the problem in a tree model. the node is just (shift, start).
Maybe I should build a class named node, but perhaps the concept
of class is new to me, so I don't intend to use it in this problem.

Answer 11

It seems that the bugs do not arise from find_best_shifts_rec(),
but from the build_coder(). In the solution vision of build_coder(),
there is something like 'string.ascii_lowercase'. So I just copy the
the solution vision of build_coder(), then the program could decrypt fable.txt now.
-------------------------------------------------
BUT, As the Professor indicates: the more bugs you find, the more bugs remained.
I find a case
http://dpaste.com/1337520/
both of our code could not find the right answer on my computer.
(This is my full code for ps4: https://gist.github.com/anonymous/6198294 )
bwCA, Can you find the right answer for that case on your computer?

Answer 12

... mine fails with that also -
it fails because the first (shift, position) decodes an extra word ('a') that is not part of the original text - i don't think that can be fixed

There are some mistakes in the fable decryption also - because of the way i decided to break a tie (two shifts decoding the same number of words)

your (new) build_coder() is kinda like mine
http://dpaste.com/1337734/

Answer 13

@6.00_learner
i was able to get my algorithm to decode your test phrase:
```
s = 'cfgrvn bcbzyosrn ogewoeqvnwmaxlwdfvieoeki'
```

instead of allowing it to identify multiple decoded words at a time i changed it to only look at a single word at a time. it ends up with more iterations but it worked.

interestingly - this fixed the the problem with a few odd words in the decryption of the fable - now it decypts everything correctly.