Question

Has anyone done problem set 4? the ps4 solution doesn't match the ps4 skeleton file. and I can't find the solution to #3 for ps4

Answer 1

Which exact MIT course? There are different years and the problem sets change.

Answer 2

Sorry I thought this was automatically categorized. This is for course 6.00 Introduction to Computer Science, Spring 2011

Answer 3

This is the problem set about the Caesar cipher and specifically I'm looking for help on Problem 3. Multi-level Encryption & Decryption. I can't find the solution in the provided solutions (the solution doesn't entirely match the assignment).

Answer 4

def apply_shifts (text, shifts):
message = list(text)
multiLevelMsg = ''

for level in shifts:
list(level)
print (level)
for index in range(len(message)):
print(index)
if index == level[0]:
i = index
print ("i = ", i)
while i< len(message):
multiLevelMsg += encoder(message[i],level[1])
print (multiLevelMsg)
i+=1
else:
multiLevelMsg += message[index]
print (multiLevelMsg)
return multiLevelMsg

Answer 5

That's my code right now, I put a bunch of print statements so I can see what's going on. I know I need to replace the original message with the shifted message, then i need to apply a shift over that message. I'm still thinking about how to replace that message and where to insert it. The second issue I can't resolve is how to start shifting from the desired index, since each takes place at a different part of the string.

Answer 6

i finally figured out a solution. here is my code. what do you think? is there a better way?

def apply_shifts (text, shifts):

message = list(text)
multiLevelMsg = ''

#creates dictionary of shift location and shift value
shiftDict = {}
for level in shifts:
list(level)
shiftDict[level[0]] = level[1]

index = 0
for letter in message:

if index not in shiftDict: #if index is not in shiftDict increase index by one to check next index
index += 1

else: #index in shiftDict: #if in shiftDict we will change the message starting from the current index
i = index
while i < len(message):
message[i] = encoder(message[i],shiftDict[index])
i += 1
index += 1 #after shifting entire message, move to the next index

#creates the layered message
x = 0
while x < len(message):
multiLevelMsg += message[x]
x += 1

return multiLevelMsg

Answer 7

please use a code pasting site:

- http://dpaste.com
- http://pastebin.com
- https://gist.github.com/
- http://pastie.org
- http://codepad.org
- http://ideone.com
- http://www.repl.it/

paste your code there and post the link here. select Python syntax highlighting when u paste.

Answer 8

here's mine:
http://dpaste.com/1308187/

Answer 9

bwCA, thanks for posting your answer. it's amazingly simple. I wish I could see the rest of your program. I just learned from your solution that you can do that in a for statement. Thanks for that

Answer 10

here are probs one and two; http://dpaste.com/1309240/
feel free to ask if you have any questions
do you understand the slices?

Answer 11

thanks for the solution to one and two. i'm starting to get a better feel of slices. can i ask what it means to put a ':' next to the location variable why way you did... i haven't seen that before text -- [:location] and text[location:] ? what does it do when you put the colon on the left side then on the right side of the variable?

Answer 12

looking at your answers, it makes me realize there's a lot i don't know. should i know that much by now this far into the course? i haven't seen 'zip' and 'join' before. thanks again

Answer 13

6.00 assumes a lot about the programming ability of the person. They have a different class to get people up to the basics on programming. This is actually the intro to engineering class.

Answer 14

the class is teaching computer science (how to think computationally) and programming techniques. It is not a Python language class. They chose Python because it is very easy to learn for most people. Python has a lot to offer, lots of tools to help you solve problems, if you want to make use of them you will need to dig into the documentation - here is the online version ... http://docs.python.org/2.7/

one of the best ways to learn Python is to experiment in a shell. the table here, http://docs.python.org/2.7/library/stdtypes.html#sequence-types-str-unicode-list-tuple-bytearray-buffer-xrange gives a short description of slices. if you omit an expression from the left side of the colon (in a slice) it defaults to 0. if you omit an expression from the right side of the colon (in a slice) it default to the length of the sequence plus one.
http://dpaste.com/1309645/
http://docs.python.org/2/tutorial/introduction.html#strings
http://wiki.python.org/moin/MovingToPythonFromOtherLanguages

http://www.diveintopython.net/index.html

Answer 15

One professor took Python a different way:

http://www.pythonlearn.com/book.php

That is a free book and video course on Python for Informatics, which teaches basic utility programming through Python. It is an intro to the language that does not focus on a lot of things like algorithm optimization and recursion. However, it is a great way to learn much of Python.

That would make someone very ready for the MIT 6.00 course because you would know the language used and would mainly be seeing it used in new ways. Computer Science is the new name for Software Engineering and that part is what MIT 6.00 really focuses on. They have a different class to intro Python, but there are no videos for it, which is why I think the Informatics class is a better independent primer for programming. The other nice things is you can work them concurrently. After the first say three videos and some of the book work on Informatics, the MIT 6.00's first few classes and homework should be a lot easier.

If you want something less structured, TheNewBoston has a bunch of videos on Python. They are partially sequential, as in the later ones assume you understand many of the features from the earlier ones but they are largely single topics. So you can look at bits of Python without working through a full course of stuff. Then apply what you learned for getting through the MIT 6.00 stuff.

http://thenewboston.org/list.php?cat=36

Answer 16

Thank you for all the reading material. I've got it all bookmarked. and especially thanks for the examples of the splices, i've got a good handle on it now. I also experimented with the zip function and the way i understand it is it can, for example, take two lists and pair the first item of each list, then the second item of each list etc. and if zip is used with dict, it can pair two lists to create key:value... do i understand it correctly? i'll have to keep trying to use it to see what else it can do.

in any case, can I get help starting part 4 of this problem set (multi-level code-breaking)? What throws me off is that they've given two functions called 'find_best_shifts' and 'find_best_shifts_rec' and I don't understand the relationship between the two functions. Will 'find_best_shifts_rec' depend on 'find_best_shifts'? Or do both functions do the same thing except 'find_best_shifts_rec' does it recursively? I'm also thinking of how to break this problem down recursively. The base case that comes to mind is "unshifting" to unveil words that are at the beginning of the string. Then, once a word is found we are left with the rest of the scrambled string and repeat the process. If that is the process of finding the 'shifts', i'm not sure how the parameter 'start' falls into place because naturally i would think i would just start from the beginning. I would appreciate any help! or you can just post your solution and I can study it. TIA

Answer 17

"The base case that comes to mind is "unshifting" to unveil words that are at the beginning of the string. Then, once a word is found we are left with the rest of the scrambled string and repeat the process."
that was my approach:
- find the shift that produces the most words at the beginning of the string
- remove & save the decoded portion from the beginning of the string
- recurse with the rest of the string

"If that is the process of finding the 'shifts', i'm not sure how the parameter 'start' falls into place because naturally i would think i would just start from the beginning."
I concur - however, instead of removing and saving the decoded beginning of the string prior to recursing, you could just find the 'end' of decoded portion and recurse with the entire string while updating the start argument.

I didn't even write 'find_best_shifts' - i just implemented the recursive version.

Answer 18

So here is what I have so far: http://dpaste.com/1311626/

The idea is if I find a value for shift that creates a word at index 0 then I store the value of location,shift in shifts. Once it does that, it drops the beginning word of the text.

What I want it to do now is reset the value of shift back to one and start checking again until it finds a word at the beginning of the string. I inserted a print statement to check, and I can see that shift is not being reset. Any pointers? Or is this approach not going to work? At this point I know that the value of the second location will not be right, but I just wanted to get to the point where it is checking values of shift starting from 1 at the beginning of the new string. TIA

Answer 19

Oh and you might have noticed that I just set location = start cause I still haven't seen a way to use the parameter 'start' in a better way. i just call the function by setting start to 0 by calling 'find_best_shifts_rec(wordlist, text, 0)'

Answer 20

line 24+
the for loop will iterate over a sequence, you don't have to use range() to index into the sequence - http://dpaste.com/1311652/

if you need the index as well as the item in the sequence use enumerate():
http://dpaste.com/1311659/

http://docs.python.org/2.7/tutorial/controlflow.html#for-statements

you might want to spend some time reading the Tutorial in the Python docs

you have an outer loop that 'iterates' over shifts in the range 1-28
- at the top of the first iteration, shifts is an empty list, and the shift is 1
- if a shift of 1 decodes 3 words at the beginning of the text,
how many items will be in shifts at the bottom of the (outer) loop?

Answer 21

Thanks for the info! I finally came up with a solution, although I don't know if it's the most efficient.

http://dpaste.com/1311902/

any pointers would be great! can you post your answer please so i can learn from it? TIA

Answer 22

did you try it? does it work?

line 23 - 26:
if the text was encoded with shift of 5 at location 3 and later at 20,
would shifts contain (3, 5) and (20, 5)?

is it possible for different shifts to decode a word or words at the beginning of the text?
how do you account for that? i don't see any comparisons, how are you determining which shift is the best shift?

Answer 23

Ok I see now, basically my code will return the wrong answer in two scenarios:

1)if a shift of 'x' is used in the beginning of the string, then another shift 'y' in the middle, then shift 'x' again at the end because it would not record the location,shift since 'x' had already been used

and

2) if a shift value finds a word in the beginning and the following shift guesses dont find any other valid words then it will store the wrong location,shift

so i guess the best way to do this is keep track of valid words as the shift is applied. something similar to problem 2 in this problem set. and the tuple with the highest amount of valid words is returned. still trying to wrap my head around this approach. am i on the right track?

Answer 24

I think I've improved upon my last solution. Can you please give me your thoughts on this approach? Here's the link:

http://dpaste.com/1312484/

I put comments next to the code to explain what I think I'm doing. I am using the 'random_scrambled' function they provided to test my solution and it actually works for the most part. but sometimes the function hangs so I do a keyboard interrupt and the last line it was on was line 25, checking if the first word is a valid word. I'm not sure if it's a code related problem or a hardware problem. Please let me know if there's a better algorithm to this problem. TIA

Answer 25

how often does line 37 execute?

have you tried this out on anything yet?
- it is easier to debug your code if you try it out on something (small)
you could make a short text encoded with just a few shifts and use it for testing
this has three shifts - http://dpaste.com/1313609/

do you intend to use recursion?

you might want to write out your pseudocode again and check it against your code

this was my approach:
- iterate over all possible shifts and find the best shift
- the best shift produces the most (contiguous) words
at the beginning of the text
- remove (& save) the decoded portion from the beginning of the text
- repeat(recurse) with the rest of the string
- stop when all text has been decoded
- all text has been decoded if text is an empty string
- or start points to the end of the string

Answer 26

"how often does line 37 execute?"

the code 'shifts.append((location,bestCount[0]))' should only execute if a word at index 0 is found and if the shift value produces the most contiguous words than any previous shift value did. at least that's what i intended for it to do.

"have you tried this out on anything yet?
- it is easier to debug your code if you try it out on something (small)
you could make a short text encoded with just a few shifts and use it for testing
this has three shifts - http://dpaste.com/1313609/ "

I tried to find best shifts with the cipehr text you provided i think the code got stuck in an infinite loop. when i performed a keyboard interrupt, IDLE informed me the last sequence it was executing was 'if is_word(wordlist, txt.split()[0]):' (line 25 in dpaste). I don't know if the problem is at that sequence or the sequence just before it that causes the infinite loop. I also tried a few different different encoded texts and the problem is not always there. The only way I think this infinite loop could happen is if none of the values of shift found a valid word at the initial position, thus causing the value of location to never exceed the length of the text. I probably need to think of a better outer loop to so that the for loop can keep refreshing values of shift.

"do you intend to use recursion?"
To be honest, I thought my algorithm was recursive. I guess I need to review my notes over the topic to get a better understanding of it. My base case was to keep finding words at the beginning of the string. I thought I accomplished that?

Just wanna say thanks again for taking the time to answer. I really want to improve and that wouldn't be possible if someone didn't take the time to help.

Answer 27

Ok I just had a thought. What if two different shift values created the same amount of valid words at the beginning of the string, but only one of the shift values would lead to the solution? If the first value to be stored was the wrong one, then the right shift value would never get to replace it. Could this be why it's causing an infinite loop?

Answer 28

http://dpaste.com/1314002/ is a simple recursive function
see how on line 5 it calls itself? and see at line 4 (in the base case) that it returns without calling itself?
http://tinyurl.com/mst6ohz

the instructions for this problem say that it is easier to code as a recursive procedure - in fact it says that more than a few times.


If location doesn't continually increase then it will never exit
maybe put some print statements in to see what is happening.

I haven't watched any of the 2011 6.00sc lectures but in the edX version they emphasized creating a while loop condition that was guaranteed to exit the loop.

do you have any pseudo-code? if so post it.

Answer 29

I took some time to review recursion and I've gotten a better understanding. I've now written a recursive function to solve problem set 4. BUT I cannot figure out a way to save the starting point and shift because when I recursively call the function, shifts will be reset to blank. Unless of course I make shifts a global variable which I don't think is the most clever solution.

Here is my code: http://dpaste.com/1318621/

I've left my print statements included to show how I checked to make sure it was working. Here is the decoded message: http://dpaste.com/1318623/
of your cipher_text: http://dpaste.com/1313609/
I believe that's a line from the Declaration of Independence.

With regard to the code I've written, I don't feel it's the most efficient way it could be done. Looking forward to some pointers. TIA

Answer 30

I was trying to practice returning a list through recursion. I get a lot of extra parenthesis in the final result

http://dpaste.com/1319589/

Answer 31

cool - print statements rock

there are two ways (that i know of) to preserve 'data' in a recursive procedure/process.

one way is to pass the current state to each new function - when the base case is reached the function just returns the current state. when the call stack 'unwinds' each function returns the result to the function or statement that called it.
http://dpaste.com/1319588/

the other way is to build up a chain of deferred operations - each function has an operation that needs the results of the function it calls - its execution is 'suspended' till it gets those results. http://dpaste.com/1319601/
in this case, the deferred operation is text[-1] + ... at line 7.

this is the best explanation i have seen written - it is for a different language but maybe it will help (might not make sense without reading the previous) - http://mitpress.mit.edu/sicp/full-text/sicp/book/node15.html

maybe try those examples out at http://pythontutor.com/visualize.html and see how their execution is different

Answer 32

a single item tuple has the form (item,) your function is concatenating tuples.
http://docs.python.org/2.7/tutorial/datastructures.html#tuples-and-sequences

somewhere (maybe one of the OCW lectures) i learned to always write the base case first in a recursive procedure. http://dpaste.com/1320764/