Abraham Kassahun Negash
Hailey James-Sorenson, Bruk Zewdie
Our trusty Mini-Tron has been tasked with the diffusion of a bomb. Mini-Tron has never diffused a bomb before and has no idea how to do it. It is up to you to tell the robot how to proceed. However, there is one problem. The robot doesn't have enough memory to store all your instructions. So you decide to make your instruction as short as possible and take out the spaces. But now Mini-Tron is receiving a string which it doesn't understand. Can you help Mini-Tron be able to break the string into the original instructions?
def check(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
If we are given the string "mynameisyosef," it is easy for us to read the information even though there are no spaces between words. We understand that the natural way to break apart this string into a meaningful sentence is: "my name is yosef." Is there a way that we can program a computer to solve the same problem?
We knew that the way we broke the string apart is valid because we know that the words "my", "name", "is", and "yosef" are all real words. If we broke the string apart in this way: "my namei syosef," we realize that this doesn't make any sense because "namei" and "syosef" are nonsense strings. So, it seems like we need to first have a dictionary of real words before we can decide how to split up a string in a valid way.
However, sometimes it is impossible to break apart an input string. Consider the string "xvqyyyyyy". There is no valid way to break this string apart with the words in the English Dictionary no matter where we insert spaces.
NOTE : The answers to Problem 1 are located at the bottom of the jupyter notebook
Create a list myWords
below that stores all of the following strings: "a", "b", "c", "d", "e", "bcd", "abc", "ab" and "de".
# YOUR ANSWER HERE
Write down all the ways that you can break apart the string "abcde" given the words in myWords
. For example, given the string "freshmango" and a complete English dictionary, we can break this string apart into "fresh man go" or "fresh mango".
# YOUR ANSWER HERE
How many valid ways did you break the string?
# YOUR ANSWER HERE
Given a string S
and a list of words w
, write a greedy algorithm that determines if there is a valid way to break apart S
. Return True
if there is a valid way and False
if there is not.
# Write your solution here
def greedyBreakable(S, w):
return False
Test your algorithm on the string "abcde" using myWords
and make sure it returns True
# Run your algorithm and make sure it works!
check(greedyBreakable("abcde", ["a", "b", "c", "d", "e", "bcd", "abc", "ab", "de"]), True)
Function should return the value True, it is returning the value False
check(greedyBreakable("mynameisyosef", ["my", "name", "is", "yosef"]), True)
Function should return the value True, it is returning the value False
Now test your algorithm on the string "icecreamcone" using a list of these words: "i", "ice", "cream", "cone", "con", "am", "ream" and "one". You can use the check
function we used in the last two blocks
# Now test your algorithm on this new input string and list of words
There's a small chance that the algorithm you wrote succeeded and told you that the string "icecreamcone" is able to be broken apart (a correct solution would be "ice cream cone").
However, there is an even greater chance that your greedy algorithm failed. Suppose you test the word "i" first. You then try to find a valid way to break apart the rest of the string, "cecreamcone". There is no valid way to break this apart and your algorithm claims that there is no valid way to break apart the original string "icecreamcone". But you know that there is a valid way to break it apart! It's just "ice cream cone" like we mentioned a moment ago.
The greedy approach is clearly not a reliable solution -- because it's greedy, it misses some of the possible ways to break up the string. We want to make sure we test every possible way to break up the string. One way to do this is through recursion. Instead of commiting to using the first valid word we find, we should try that one and any others. Write a recursive algorithm that does exactly this. Again, you are given a string S
, a list of words w
, and your code must return either True
or False
.
Hint: How can you make sure you consider every word as a possible first word?
# Write your solution here
def recursiveBreakable(S, w):
return False
Now test your algorithm on the same input from problem 2.3. Your input string is "icecreamcone" and your list of words is: "i", "ice", "cream", "cone", "con", "am", "ream" and "one".
words = ["i", "ice", "cream", "cone", "con", "am", "ream", "one"]
# Check
check(recursiveBreakable("icecreamcone", words), True)
Congratulations, the test case passed!
# Let's modify words by deleting "ice" so that if you run your algorithm, it returns False
words = ["i", "cream", "cone", "con", "am", "ream", "one"]
# Check
check(recursiveBreakable("icecreamcone", words), False)
Congratulations, the test case passed!
1.1 myWords = ["a", "b", "c", "d", "e", "bcd", "abc", "ab", "de"]