Correct site for a specific programming question?

T

tzl99

n00b
Joined
Oct 25, 2007
Messages
49
Hey all,
Would this forum be ok to post a relatively specific question about a program I'm trying to complete. Last month I posted in the thread about easy programming languages. During the last 4 weeks, I've been slowling going through the MIT open courseware for course 6.00 (Intro to programming) which features Python 2.x. This is for my own education and not part of a course or school. I'm having a hard time getting my head around a program that needs recursion to solve a problem involving reversing a multi-layered Caesar cipher. It may take a while to post with outside links and I don't want to burden this forum with inappropriate content. Thanks,
Louie.
 
People frequently ask programming questions here; I don't see why it would be a problem.
 
I am no authority in this forum but it sounds fine.

Also, while you do mention Python, your problem doesn't have much to do with Python, does it? The problem being logic itself? You can likely pseudo code it rather than writing Python for a broader audience.

Last but not least, you mentioned a program that needs recursion. Recursion is rarely needed, if ever. Recursion can get you into trouble if it goes deep enough.
 
Ok, thanks Mikeblas & Krogen:
First off, Python really isn't needed it just happens to be the language I'm trying to learn. Also, I have come up with a program that can solve the problem without recursion but the problem set instructions say recursion will be easier to implement and I did want to solve the problem the way it was meant to be solved. The problem is on this MIT page:

http://ocw.mit.edu/courses/electric...g-2011/unit-2/lecture-10-hashing-and-classes/

Near the bottom they include a problem set and even a helpful pseudocode though it hasn't helped me so far. I've completed every part of the problem without much difficulty until the last section where the recursion method starts.

So, in this problem a message is encoded with a Caesar cipher but it is layered. The layering is only allowed at the beginning of a word and only English is allowed. There is already a helpful built-in function "is_word" which checks for the validity of a word from a wordlist of about 55K words.

For recursion to work I've been taught that a problem must be broken down into the smallest possible solution which is the "base case" & work from there. Then it is suggested I have a 3rd parameter for the recursive function which is a start parameter where the search is to begin. They give a hint that "0" (or starting from the beginning) is incorrect.

My head banging starts here. Should my base case be an empty string and my search always start at the end moving backwards from the end to the front? Or is the base case the finding of a valid word at the end? I don't want a full answer at this time, though I may be pleading for one in another week, but a hint perhaps better than the hint in the pseudocode.

My non-recursive method involves:
1. A "while loop" which works as long as the string length is greater than one.
2. Then I start a for-loop of shifts (1-27). The 27th letter in this alphabet is a space.
3. I break the string down into a list of words using a space as a separator.
4. I use the "is_word" function looking from left to right to check for valid words.
5. If the first word is valid, I move to the 2nd word and so on.
6. I record the current shift that worked and the index of the last correct word.
7. Once an incorrect word is found, I save the shift magnitude and position at the end of the last final word and add it to my original start position and put it in a list of tuples.
8. I truncate my string by removing the valid words found so far, exit the inner loop and start the while loop again with the new encrypted string that is shorter.
9. I'm now back in the shift loop (step 2 above) and I keep moving to the right.

So, each time I search until the end of any valid words found. I record a new tuple but the start location at this time is added to the length of previous words I've found so I can keep track of the start locations of the subsequent successes.
Eventually I run out of words and end.
My final result is a list of tuples that records the locations and value of the shifts. This program should work even if there is only one shift.

But I don't see the need for a "start" parameter that is so prominent in the function specified in the lecture since I always start at the beginning of my encrypted string.

Any suggestions or hints for the recursive method? Thanks again,
Louie.
P.S. I've googled this all over and I've found many other questions about the same problem set yet so far no solution. Also, the lecture has a solution program but conveniently they didn't get as far as the recursive section either.
 
Looking at that problem and breaking down this example:

Code: 
s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])

Valid places they could have started the shift are at 0, 3, 12, 18, 21, or 29. They chose 0, 3, and 12. At each shift operation, the string looks like this:

Code: 
000000000011111111112222222222333333
012345678901234567890123456789012345
Do Androids Dream of Electric Sheep? (0,6)
*                                   
JUFGTJXUOJYFJXKGSFULFKRKIZXOIFYNKKV? (3,18)
   *                                
JUFYKAOLFAPXAOBYJXLCXBIB QOF XPEBBM? (12,16)
            *                        
JUFYKAOLFAPXQDRNZMASMRYRPFDVPMEURRB? output

The problem with your solution is here:
5. If the first word is valid, I move to the 2nd word and so on.
...
7. Once an incorrect word is found, I save the shift magnitude and position at the end of the last final word and add it to my original start position and put it in a list of tuples.
8. I truncate my string by removing the valid words found so far, exit the inner loop and start the while loop again with the new encrypted string that is shorter.
Click to expand...

Many words could break down into valid subwords with the wrong rotation, so you have to have backtrack capability. Does that give you enough push in the right direction?
 
Tawnos,
Thanks, but is your "push" a hint for the recursive method? I can see your point about my program so far. On my original find the best shift program I kept track of the shift that created the most valid words. What I shoudl do, with the non-recursive version, is keep track of the shift that creates the most valid but contiguous words from the left. Is that what you meant?

Then whichever shift did that will create a tuple with the start and the shift. It looks like my program will stop at the first shift that can create any valid word at all and move on. Clearly that program will make mistakes, but the test cases I've done so far were just 2-3 words.

The recursive version is still the one that is difficult for me. I can't come up with a base case for that. The simplest case would be text that is uncoded and therefore needs no shift? But then what is the point of a start parameter? Another case would be a single encrypted word rather than a phrase? Again, how does the start parameter fit into this? If I can't solve this problem in a few days I may go on with the lectures and come back to this when I'm done. Thanks,
Louie.
 
tzl99 said:
Tawnos,
Thanks, but is your "push" a hint for the recursive method? I can see your point about my program so far. On my original find the best shift program I kept track of the shift that created the most valid words. What I shoudl do, with the non-recursive version, is keep track of the shift that creates the most valid but contiguous words from the left. Is that what you meant?
Click to expand...
Any problem that can be solved recursively can also be solved iteratively. You just have to have a data structure to be able to backtrack with - a stack (so, essentially, you recreate recursion but without having to pass as many things around).


...

The recursive version is still the one that is difficult for me. I can't come up with a base case for that. The simplest case would be text that is uncoded and therefore needs no shift? But then what is the point of a start parameter? Another case would be a single encrypted word rather than a phrase? Again, how does the start parameter fit into this? If I can't solve this problem in a few days I may go on with the lectures and come back to this when I'm done. Thanks,
Louie.
Click to expand...

Base case: start >= string length (there's nothing else to rotate)

Other cases are a modification of the basic cipher, which can be thought of as the following, where start = 0
(a) from start-> length of string, rotate the string by some value
(b) check if the string is composed only of valid words
(c) if (b) is not true, increment the value and return to (a). Else, you're done

Now that you have multiple possible rotations, you have to change the above so that start isn't always 0, and at step (b), you can either recurse at the of each valid word, or continue through the next valid word.

If that doesn't help enough, I'll put together spoiler pseudocode later.
 
jimmyb said:
While your solution will probably work, I'm curious what the hinted at solution is.
Click to expand...

He misread the hint they gave, and you misread the comment I made.

They say the base case is not start = 0 - "What value of start would make a good base case? (Hint: the answer is NOT zero.) "

The base case in recursion is the end state, not the beginning state. It's the state where you say "recursion can't progress further here, let's head back up".

The comment I made wasn't even addressing that, though. It was discussion the basic caesar cipher, where you start at 0 and mutate the entire string until a solution is reached. This cipher requires you to be able to start at 0 through string length - 1 (that is, you need to be able to start everywhere from the first character of the string until the last character of the string). That means the base case, here, is when you are being asked to start at string length or beyond (beyond because of a bug, safety first! ;) ).
 
Tawnos said:
He misread the hint they gave, and you misread the comment I made.
Click to expand...

My initial understanding of your comment was in line with your clarification, ie. an index into the string.

I agree that the OP misinterpreted the hint; I was racking my brain trying to think of some (improved) approach that started at a non-zero index, but in light of that not being the hint I'd guess there isn't one.
 
Tawnos,
First, thanks for taking the time to give advice and hints. Yes, I really could not figure out why they said not to start at zero until you clarified it. In the example they were giving about reversing a string they too started the decryption from the beginning.

Due to your help, I wrote another function tonight to try to get this to work. I tried using the function in a recursive way to more along from left to right and found a way to use the "start" parameter also, after the first word is found.

At first, the program appeared successful in allowing the:
"Do Androids Dream of Electric Sheep?" with shifts [(0,6), (3, 18), (12, 16)]) to be descrambled. But I knew there was trouble because my program appended about 3 more tuples at the end of the successful ones, though the three tuples all had shift values of "0". So they didn't do anything wrong when I tried to descramble, but they shouldn't have been there.

Then I started testing out descrambling 1-5 word scrambled text phrases using a function in the skeleton program that can create scrambled texts. Since it used my own "apply_shifts" function I put in a print in there so I could see the words they were scrambling to verify I could unscramble them.

Now I see many errors in my program. While in most cases it could descramble words and give correct decrypting shifts, it failed too many times. In most cases, it was as you predicted where a larger word might descramble into a smaller but valid word. The worse occured too often when my program recovered "i" thinking it is "I". It never gets past that point. Also, if the last word can descramble into a word with a space at the end it also fails. For example one scramble had "yaw" at the end. My program discovers "be " ("be" with a space as the last character of the string) and can't move on.

You also talk about a "stack" but while I've been going over this course for about a month, I've only made it into about 10 lectures due to having at most about an hour most nights (after everyone is pretty much asleep) to even begin reading or watching the lectures so my experience level is really low. The last time I came across a "stack" was in the 1980s with the stack in the 2nd page of memory in my C64.

In my current program my base case is in reality just finding the last valid word of any current shift before moving on to try another shift. I thought originally it found the last valid word of the string and then go back from there but I see it really isn't doing that.

I think I'm going to plug away at this for another couple of days, then either move on with the lectures or try another type of tutorial. I have two other links to pdfs, "How to think like a computer scientist" and "Learn Python the hard way" which I've read good things about. They may be better starts for a total noob like me before tackling this course.

I may take you up on your offer of some spoiler psuedocode later. Although I posted a question and a request for help, I don't expect that anybody take up their time helping me with a hobby. So I want you to know I really appreciate the advice and help you've given so far as tonight I've gotten the furthest along in 4 nights. Thanks,
Louie.
 
Ok all,
Just to close this thread. I finally finished the program and it was able to completely descramble the fable. The porgram is iterative rather than recursive, though now after finishing it I think a recursive method would work the same but with a basecase of no more string left to descramble. I'll walk through what I did and also name the story and writer.

I initialize a decrypted text variable as an empty string. Then:

1. Outer while loop while start is <= length of text.
2. Initialize variables to keep track of biggest words, contiguous words and best shift.
3. For loop (1-27) to apply shifts of the text from start position (initially 0) to end.
4. Shifted text is broken down to words (separated by space)
5. Validiy of words from left to right looked at but only contiguous words recorded, an invalid word breaks out of that shift. Best shift also updated if contiguous words found
6. If single word found only it is recorded along with best shfit.
6b. There are situations (many) where 2 or more valid words are produced from a start location with different shifts. I have a variable that keeps track of longest valid word and shift of that word.

When the for loop is finished a couple of if statements follow.
7. If I have found contiguous words these are kept. I add them to my decrypted text so far.
8. I create an offset integer based on length of the words +1 (for the final space)

9. If no contighous words are found, then I pick the longest word found (if only one is found, it is the longest word). I add it to my decrypted text.
10. Calculate the offset by the length of the word +1
11. I add the tuple of my current start position with shift used.
12. Add offset to my start parameter and loop back.
13. In cases (rare) where no valid word is found I add 1 to my start parameter so the program keeps running. This program only searches for English. In case of numbers or foreign words it moves step by step until it finds a valid word again.

In the end, it completely decrypted the text and it worked fine when trying to decrypt random phrases created by a program that was supplied by the problem set creator.

In a recursive version I could avoid the outerwhile loop with a base case of "None" or no further text to decode and it would return a None.

PROBLEMS WITH MY METHOD:
As Mikeblas suggested, I should try to keep track of all valid words at any given start location. While in most cases I could only generate one valid word with the shifts, there were situations where the series of shifts could produce more than 1 word. In every case at least for the fable offered, I never produced more than 2 words and it was usually the case of a large word (that made sense in the context of the decrypted text so far) vs small word like "an" or "em", or "ex". In those cases I gave weight to the largest word per series of shifts.

Some times the shifts would produce several words. I gave the highest weight to them and it worked for my example. However, it is possible a smaller word or a single larger word would be valid. With my inexperience in programming I'm not sure how I can make my program know which valid word is the correct word in the context of the text decrypted so far.

I wonder, if perhaps, in a series of shifts at any given location, if I came up with more than 1 valid word or series that perhaps I record the shifts and words and save them in a variable or array? Then when printing the final decryption I could print out all the single words found, then print out different versions of the remaining text when areas with multiple decryptions are available.

For now though I'm done and will move on with the lectures. Thanks to Tawnos for his help.
Louie.
The fable is "The Flying Machine" by Ambrose Bierce.
 
Last edited:
tzl99 said:
For now though I'm done and will move on with the lectures. Thanks to Mikeblas for his help.
Click to expand...

Mike, we have become the same person. You can stop boiling your water now and come over to Sammamish.

Unless, of course, you were PMing tzl99, in which case I'm sorry for presuming he just got us mixed up.
 
You must log in or register to reply here.
Back
Top