MIT 6.00.1x: Problem Set 1
Introduction to Computer Science and Programming Using Python
Let’s get down to business. This first problem set is composed of three short programming challenges. The first two are fairly easy but the third one will probably require some thinking even for those with programming experience. I do not have any programming experience. Here’s how I did it:
Warning: my solutions are not the best solutions or the “right” solutions. They are simply my solutions.
Problem 1
Assume
s
is a string of lower case characters.Write a program that counts up the number of vowels contained in the string
s
. Valid vowels are: 'a
', 'e
', 'i
', 'o
', and 'u
'. For example, ifs = 'azcbobobegghakl'
, your program should print:Number of vowels: 5
This problem is basically just to check you know the basic concepts of conditional statements. Python, like many programming languages, allows you to create if-else expressions that perform certain computations depending on whether a Boolean condition evaluates to True or False.
Lets say I want to create a program that prints out whether an ice cream store has ice cream in stock.
First we define a variable called iceCreamAvailable and set it to True.
iceCreamAvailable = True
One cool thing about Python is that you don’t have specify a data type preceding your variable declaration. Whether we set our variable to a Boolean value, an integer, a float, or a string, we would simply just need to change the value right of the equal sign. Some programming languages on the other hand like C don’t even have a built-in Boolean data type (C is still awesome).
The next part of our program is setting up our if-else expression to run depending on whether iceCreamAvailable is equal to true or false.
if iceCreamAvailable == True:
# print statement 1
else:
# print statement 2
If the value of iceCreamAvailable is equal to true here, we will then print statement 1. If iceCreamAvailable evaluates to any other value, it will print statement 2. If I wanted to be more specific for statement 2, I could have used an elif statement like this:
elif iceCreamAvailable == False:
# print statement 2
Due to the fact that the Boolean data type can only evaluate to two values though, the elif is unnecessary. In fact, here I could even remove the double equals sign as if statements automatically evaluate any non-zero and non-null values as True.
if iceCreamAvailable:
# print statement 1
This just makes our a code a little bit more concise and easier to read. I like it.
Finally for our little example program, we want to print our statements. To do this we will use the built in function print. If you’re a complete beginner you probably don’t know what a function is yet. If you weren’t asleep in high school algebra though, you probably have a vague idea of what one is. Basically print just takes in an argument, and prints or outputs it to the shell. This is our first glimpse into the concept of input and output or as nerds call it: IO.
For instance:
print("Hello doggo")
Would print out to the shell:
Hello doggo
So now our entire iceCream program would look a little like this:
iceCreamAvailable = Trueif iceCreamAvailable:
print("Come get some ice cream!"
else:
print("We're all out!")
So let’s get back to our first problem. It’s really not that different from our example program we just made. The only difference is here we are going to use a for loop to repeat our conditional statements a certain number of times. Let’s first set up a variable called vowelCount and set it to zero in order to keep track of the number of vowels in a string.
vowelCount = 0
Next we need to set up our for loop. There’s a several ways of doing this. Here are two of them.
for index in range(len(string)):
This first iterates over a range from 0 to the length of string. That means index here will be equal to an integer every single iteration of the loop.
Let’s try to count just the vowel “a” first by.
for index in range(len(string)):
if string[index] == 'a':
# increment vowelCount
Here, we are accessing each character of the string through its index and then checking to see if it is matches ‘a’. If the character does match ‘a’, we then carryout whatever is inside our if block.
An easier and more readable way to write this code is to access the characters directly instead of going through the index of the string.
for letter in string:
I know. Pretty nice looking right? It reads like English and you don’t have to use the range or len functions.
Finally we want to increase our VowelCount variable count by one inside our conditional statements. We can do this once again in a couple ways.
vowelCount = vowelCount + 1
or
vowelCount += 1
I’ll will use the second one going forward.
Alright now that we have all our little bits to this problem figured out, let’s put it all together.
# variable s is predefined
# define and set variable vowelCount to 0
vowelCount = 0# create a for loop to iterate through each character of s
for letter in s:
# if letter in s equal to each vowel, increment vowelCount by 1
if letter == "a":
vowelCount += 1
elif letter == "e":
vowelCount += 1
elif letter == "i":
vowelCount += 1
elif letter == "o":
vowelCount += 1
elif letter == "u":
vowelCount += 1# print the concatenated first string and vowelCount
print("Number of vowels: " + str(vowelCount))
Boom. First problem down. Not that bad at all right?
Problem 2
Assume
s
is a string of lower case characters.Write a program that prints the number of times the string
'bob'
occurs ins
. For example, ifs = 'azcbobobegghakl'
, then your program should printNumber of times bob occurs is: 2
Okay this one is a little bit harder but it’s not that difficult once you get your head around the concept of accessing substrings through a string’s index. What the heck do I mean by that? Here’s a little example:
name = "cyberdoggo"
lastName = name[5:]
If we print lastName, we get:
doggo
Here what we have to do is iterate through the string accessing substrings s[i:i+3) until we find a substring that matches “bob”
I’ll show what you I mean by that if it still sounds like mumbo jumbo.
First lets define and set a variable bobCount to 0. This variable will have the same purpose the variable vowelCount had in the first program.
bobCount = 0
Here’s where it gets a little complicated. First let’s create our for loop:
for i in range(len(s)):
This once again just iterates a range from 0 to the length of s.
Next we need to create our conditional statement to match a substring to “bob”:
if (s[i:i+3] == 'bob'):
# a statement
This checks to see if the substring created from s[i:i+3] is equal to “bob” as the name bob has a length of three characters and therefor requires the substring to be a length of three. So if s = ‘azcbobobegghakl’, the first substring s[0:3] would be equal to ‘azc.’ Since ‘azc’ does equal ‘bob’, the statement within the if expression would not be executed.
Alright the hardest part here is done. Now we just need to increment bobCount by one within the if statement.
bobCount += 1
Now let’s put it all together:
# s is a predefined string
# define and set bobCount to 0
bobCount = 0# iterate through the range from 0 to the length of s
for i in range(len(s)):
# check to see if the substring accessed is equal to 'bob'
if (s[i:i+3] == 'bob'):
bobCount += 1print("Number of times bob occurs is: " + str(bobCount))
Creating comments by the way is a great habit to pick up early. If you end up working with other people, comments are incredibly vital to making sure your coworkers can understand your code easily. Don’t be “that guy” or “that girl.”
Go eat a snack and then we can get on to the last problem.
Problem 3
Assume
s
is a string of lower case characters.Write a program that prints the longest substring of
s
in which the letters occur in alphabetical order. For example, ifs = 'azcbobobegghakl'
, then your program should printLongest substring in alphabetical order is: beggh
In the case of ties, print the first substring. For example, if
s = 'abcbcd'
, then your program should printLongest substring in alphabetical order is: abc
This problem sucks until you get it. Then it’s not so bad. What do I mean by “get it”? I’ll show you.
First let’s setup a little example:
letters = "abc"
print(letters[1] > letters[0])
If we run this program we get:
True
I know what you’re thinking. “Why did that work?” Well let’s try something else. Enter this statement into your Python shell.
print(ord(‘a’))
You should get the number 97. What ord() is doing is converting the character ‘a’ to its corresponding ASCII numeric value. ASCII is basically just the standard for character encoding. I won’t go too much into this as I would have to write something the length of a Wikipedia article to fully explain it. Fortunately though, someone already wrote a great article there. It’s okay if you don’t get much. I only understand about a quarter of it.
So now that we know we can compare characters against each other, this problem should become a lot easier to grasp.
First let’s define two variables called and longest. You can just set them to empty strings. I explain these later don’t worry.
current = ''
longest = ''
Now let’s set up our for loop to iterate over our string as per usual:
for i in range(len(s)):
Here’s where it gets fun:
if (s[i] >= s[i-1]):
current += s[i]
else:
current = s[i]
Our if statement checks to see if the current character, s[i], is greater than the previous character, s[i-1], in the string. So if s[i] is greater than or equal to s[i-1], it gets added to the string current as s[i] is ahead of s[i-1] in the alphabet. However, if s[i] is before s[i-1] in the alphabet, we need to reset the string current and set it to the value of s[i].
The problem though right now is that we are not finding the longest alphabetical substring in s, we are simply finding the last alphabetical substring in s. This is where the variable longest we defined earlier comes into play. Below our if-else block, we need to create another if statement that sets longest to the string of current if the length of current is greater than longest. Let’s use that len() function we’ve used before in our for loops.
if len(current) > len(longest):
longest = current
That’s pretty much it. Now for the last time, let’s put it all together:
# s is predefined variable set to a string valuecurrent = ''
longest = ''for i in range(len(s)):
if (s[i] >= s[i-1]):
current += s[i]
else:
current = s[i]
if len(current) > len(longest):
longest = currentprint("Longest substring in alphabetical order is: " + longest)
Overall, that wasn’t too bad. Now you can say you’ve completed an MIT problem set! One thing to note is that while my programs completed all of tests MIT put into their grading platform, they are not perfect. When writing code you should always try to make your programs as modular as possible. Always try to look for new ways your program could fail. If you can do that, you are officially more of a hacker than anyone on CSI: GreenTerminals.
See you next time.