Problem 1
Before starting the coding assignment, please practice by mentally executing the following functions and figuring out what they do. You should practice the technique of predicting what Python code does without using Python.
Describe what each function does, briefly, in English, in a comment in your submitted file. Illustrate your explanation with at least one example call and its result.
Write your explanations and examples into a comment in your code file.
Do not type the code into your computer!
defmystery1(x):"""
signature: str -> str
"""
forzin["yes", "no", "maybe"]:
ifx == z:returnz
return"unknown"
defmystery2(lst):"""
signature: list(str) -> str """
acc = ""
foriteminlst:
acc += item+", "returnacc
defmystery3(lst):"""
signature: list(int) -> list(int) """
i=0
1
whilei len(lst) // 2:
lst[i] += lst[i +len(lst) // 2] i+=1
returnlst[0:len(lst) // 2]
defmystery4():"""
signature: () -> list(str) """
acc = []
forfirstin[1, 2, 3]:
forsecondin["a", "b", "c"]: acc.append(first * second)
returnacc
Problem 2
Write a function named “avg” that fulfills the following specification by replacing thepassline:
defavg (numbers) :"""
signature: list (float) -> float
precondition: numbers != []
returns the average (mean) of a non-empty list of floats """
pass# TODO: implement the body of this function
You may assume that the input is not an empty list. That is, your code doesnotneed to handle the situation whennumbersis[].
Your function should not useprintorinputat all.
Note: for the purposes of this problem, you maynotuse the built-insumfunction, rather
you should write a loop that iterates over the items in the list.
Problem 3
Write a function named “sum_some” with three parameters:lower,upperandnumbers, that returns the sum of the elements of the listnumberswhich are betweenlowerandupper(inclusive). If the listnumbersis empty then your function should return0. Your function should satisfy the signature:int , int , list (int) -> int.
For example:
>>> sum_some (0 , 100 , [])
0
>>> sum_some (0 , 100 , [1,2,3,4,5]) 15
>>> sum_some (2 , 4 , [1,2,3,4,5])
9
>>> sum_some (3 , 3 , [2,2,3,3,4,4]) 6
Your function should not useprintorinputat all.
2
Problem 4
Write a function named “is_sorted” that takes a list of numbers and returnsTruein case the list is in increasing order, andFalseotherwise.
This means that every number in the list should be larger or the same as the preceding number.
By convention, we will returnTruefor the empty list. For example:
>>> is_sorted ([]) True
>>> is_sorted ([1]) True
>>> is_sorted ([1 , 2 , 3]) True
>>> is_sorted ([1 , 2 , 2 , 3]) True
>>> is_sorted ([1 , 2 , 2 , 1]) False
Hint: notice that a list is sorted just in case there is no adjacent pair of entries that is out of order. In other words, a list is sorted if for every adjacent pair of entries, the one on the left is less than or equal to the one on the right.
Note: for the purposes of this problem, you maynotuse any of Python’s built-in sorting functions, instead, you should traverse the list and check that all adjacent pairs of entries are ordered.
Your function should not useprintorinputat all. Test your code thoroughly before submitting it.
Problem 5
Write a function named “indices” with two parameters: an object,needle, and a list of objects,haystack. Your function should return the list of positions of all occurrences ofneedleinhaystack.
For example:
>>> indices []
>>> indices []
>>> indices [0]
>>> indices
[1, 2]
>>> indices [1, 3, 5]
(7 , [])
(7 , [6])
(7 , [7,8,9])
(7 , [1,7,7,6])
(7 , [0,7,1,7,2,7,3])
Notice that the output is a list of positions. That is, in the last example, the result is[1, 3, 5]because theneedle7 appears in thehaystackat positions 1, 3, and 5.
Hint: you’ll need to iterate through the haystack, and, if a given item matches the needle, append it to an accumulator. You are prohibited from using Python’s built-in searching methods, such asindex. You are, however, permitted to use the indexing operator.
3
Your function should not useprintorinputat all. Test your code thoroughly before submitting it.
Problem 6
Write a function namedinterspersethat will prompt the user to enter two sentences. Then it willprinta combined sentence, consisting of alternating words from each sen- tence: first from the first sentence, next from the second sentence, then the first sentence again, etc. If one sentence has more words than the other, the remaining words should be output at the end of the result.
The function should take no parameters. Its signature should be() -> NoneType.
For the purposes of this problem, you may consider a “word” to be any space-separated sequence of non-space characters, including punctuation. You may use thesplitmethod to separate a string into a list of its constituent words. You may use thejoinmethod to combine a list of words into a string.
Please read the example executions below and make sure that your implementation can reproduce these results exactly:
>>> intersperse()
Enter a sentence:This is a test
Enter a sentence:of the emergency broadcast system.
This of is the a emergency test broadcast system. >>> intersperse()
Enter a sentence:It is an ancient mariner
Enter a sentence:Who stoppeth one of three
It Who is stoppeth an one ancient of mariner three >>> intersperse()
Enter a sentence:Five
Enter a sentence:for the symbols at your door
Five for the symbols at your door
Problem 7
Run-length encoding is a technique to reduce the amount of characters used to repre- sent repetitive strings. For example, given the stringaadccccaa, one can see that it contains twoa’s, followed by oned, followed by fourc’s, followed by twoa’s. If we represent the run-length encoding of this string as a list of tuples, where each tuple con- tains an individual character and how many times it’s repeated, it would look like this:[('a', 2), ('d', 1), ('c', 4), ('a', 2)].
Write two functions,rlencodeandrldecodethat will, respectively, convert a string into its run-length encoded format, as given above; and convert a run-length encoding (in the form of a list of tuples ofstrandint) back into the original string. The functionrldecodeis the inverse ofrlencode, so that for any string value ofx, this expression will hold true:rldecode(rlencode(x)) == x
Neither function should useprintorinput. The functions should have the following signatures:
defrlencode(s):"""
signature: str -> list(tuple(str, int)) """
pass
4
defrldecode(rle):"""
signature: list(tuple(str, int)) -> str """
pass
Some more examples:
>>> rlencode("abba")
[('a', 1), ('b', 2), ('a', 1)]
>>> rlencode("aaaaaaaaaaaaaa")
[('a', 14)]
>>> rlencode("Hello!")
[('H', 1), ('e', 1), ('l', 2), ('o', 1), ('!', 1)] >>> rlencode("122333")
[('1', 1), ('2', 2), ('3', 3)]
>>> rldecode(rlencode("Hello!"))
'Hello!'
>>>
Problem 8
In class, we discussed the difference between apure(oreffect-free) function (i.e. one that returns a value, but does not produce an effect) and amutatingfunction (i.e. one that changes the value of its parameters). In this exercise, we ask you to demonstrate your understanding of this distinction by implementing the same functionality as both a pure function, and as a mutating function.
Both functions take alistofintas a parameter. The pure variant will return a newlistcontaining the integers in reversed order. The mutating variant will returnNone, and will instead modify thelistthat it’s given.
Your functions should have these signatures:
defreverse_pure(xs):"""
signature: list(int) -> list(int)
Returns a list of integers in reverse order """
pass
defreverse_mut(xs):"""
signature: list(int) -> NoneType Reverses the list of integers in place """
pass
When implementingreverse_mut, consider carefully how one can reverse the items in a list without creating a new list.
A contrasting example:
>>> mylist = [5, 12, 34, 0, 1]# The list of numbers>>> newlist = reverse_pure(mylist)# Call the pure function
5
>>>print(newlist)
[1, 0, 34, 12, 5]
>>>print(mylist)
[5, 12, 34, 0, 1]
>>> reverse_mut(mylist) >>>print(mylist)
[1, 0, 34, 12, 5]
# The new, reversed list
# The original list is unchanged
# Call the mutating function (returns None) # Original list is reversed in-place
For this problem, you maynotuse the built-in Python functions for reversing list,reverseandreversed. You may not use the slice operator to reverse the list. You must implement the function using a loop.Problem 1
Before starting the coding assignment, please practice by mentally executing the following functions and figuring out what they do. You should practice the technique of predicting what Python code does without using Python.
Describe what each function does, briefly, in English, in a comment in your submitted file. Illustrate your explanation with at least one example call and its result.
Write your explanations and examples into a comment in your code file.
Do not type the code into your computer!
defmystery1(x):"""
signature: str -> str
"""
forzin["yes", "no", "maybe"]:
ifx == z:returnz
return"unknown"
defmystery2(lst):"""
signature: list(str) -> str """
acc = ""
foriteminlst:
acc += item+", "returnacc
defmystery3(lst):"""
signature: list(int) -> list(int) """
i=0
1
whilei len(lst) // 2:
lst[i] += lst[i +len(lst) // 2] i+=1
returnlst[0:len(lst) // 2]
defmystery4():"""
signature: () -> list(str) """
acc = []
forfirstin[1, 2, 3]:
forsecondin["a", "b", "c"]: acc.append(first * second)
returnacc
Problem 2
Write a function named “avg” that fulfills the following specification by replacing thepassline:
defavg (numbers) :"""
signature: list (float) -> float
precondition: numbers != []
returns the average (mean) of a non-empty list of floats """
pass# TODO: implement the body of this function
You may assume that the input is not an empty list. That is, your code doesnotneed to handle the situation whennumbersis[].
Your function should not useprintorinputat all.
Note: for the purposes of this problem, you maynotuse the built-insumfunction, rather
you should write a loop that iterates over the items in the list.
Problem 3
Write a function named “sum_some” with three parameters:lower,upperandnumbers, that returns the sum of the elements of the listnumberswhich are betweenlowerandupper(inclusive). If the listnumbersis empty then your function should return0. Your function should satisfy the signature:int , int , list (int) -> int.
For example:
>>> sum_some (0 , 100 , [])
0
>>> sum_some (0 , 100 , [1,2,3,4,5]) 15
>>> sum_some (2 , 4 , [1,2,3,4,5])
9
>>> sum_some (3 , 3 , [2,2,3,3,4,4]) 6
Your function should not useprintorinputat all.
2
Problem 4
Write a function named “is_sorted” that takes a list of numbers and returnsTruein case the list is in increasing order, andFalseotherwise.
This means that every number in the list should be larger or the same as the preceding number.
By convention, we will returnTruefor the empty list. For example:
>>> is_sorted ([]) True
>>> is_sorted ([1]) True
>>> is_sorted ([1 , 2 , 3]) True
>>> is_sorted ([1 , 2 , 2 , 3]) True
>>> is_sorted ([1 , 2 , 2 , 1]) False
Hint: notice that a list is sorted just in case there is no adjacent pair of entries that is out of order. In other words, a list is sorted if for every adjacent pair of entries, the one on the left is less than or equal to the one on the right.
Note: for the purposes of this problem, you maynotuse any of Python’s built-in sorting functions, instead, you should traverse the list and check that all adjacent pairs of entries are ordered.
Your function should not useprintorinputat all. Test your code thoroughly before submitting it.
Problem 5
Write a function named “indices” with two parameters: an object,needle, and a list of objects,haystack. Your function should return the list of positions of all occurrences ofneedleinhaystack.
For example:
>>> indices []
>>> indices []
>>> indices [0]
>>> indices
[1, 2]
>>> indices [1, 3, 5]
(7 , [])
(7 , [6])
(7 , [7,8,9])
(7 , [1,7,7,6])
(7 , [0,7,1,7,2,7,3])
Notice that the output is a list of positions. That is, in the last example, the result is[1, 3, 5]because theneedle7 appears in thehaystackat positions 1, 3, and 5.
Hint: you’ll need to iterate through the haystack, and, if a given item matches the needle, append it to an accumulator. You are prohibited from using Python’s built-in searching methods, such asindex. You are, however, permitted to use the indexing operator.
3
Your function should not useprintorinputat all. Test your code thoroughly before submitting it.
Problem 6
Write a function namedinterspersethat will prompt the user to enter two sentences. Then it willprinta combined sentence, consisting of alternating words from each sen- tence: first from the first sentence, next from the second sentence, then the first sentence again, etc. If one sentence has more words than the other, the remaining words should be output at the end of the result.
The function should take no parameters. Its signature should be() -> NoneType.
For the purposes of this problem, you may consider a “word” to be any space-separated sequence of non-space characters, including punctuation. You may use thesplitmethod to separate a string into a list of its constituent words. You may use thejoinmethod to combine a list of words into a string.
Please read the example executions below and make sure that your implementation can reproduce these results exactly:
>>> intersperse()
Enter a sentence:This is a test
Enter a sentence:of the emergency broadcast system.
This of is the a emergency test broadcast system. >>> intersperse()
Enter a sentence:It is an ancient mariner
Enter a sentence:Who stoppeth one of three
It Who is stoppeth an one ancient of mariner three >>> intersperse()
Enter a sentence:Five
Enter a sentence:for the symbols at your door
Five for the symbols at your door
Problem 7
Run-length encoding is a technique to reduce the amount of characters used to repre- sent repetitive strings. For example, given the stringaadccccaa, one can see that it contains twoa’s, followed by oned, followed by fourc’s, followed by twoa’s. If we represent the run-length encoding of this string as a list of tuples, where each tuple con- tains an individual character and how many times it’s repeated, it would look like this:[('a', 2), ('d', 1), ('c', 4), ('a', 2)].
Write two functions,rlencodeandrldecodethat will, respectively, convert a string into its run-length encoded format, as given above; and convert a run-length encoding (in the form of a list of tuples ofstrandint) back into the original string. The functionrldecodeis the inverse ofrlencode, so that for any string value ofx, this expression will hold true:rldecode(rlencode(x)) == x
Neither function should useprintorinput. The functions should have the following signatures:
defrlencode(s):"""
signature: str -> list(tuple(str, int)) """
pass
4
defrldecode(rle):"""
signature: list(tuple(str, int)) -> str """
pass
Some more examples:
>>> rlencode("abba")
[('a', 1), ('b', 2), ('a', 1)]
>>> rlencode("aaaaaaaaaaaaaa")
[('a', 14)]
>>> rlencode("Hello!")
[('H', 1), ('e', 1), ('l', 2), ('o', 1), ('!', 1)] >>> rlencode("122333")
[('1', 1), ('2', 2), ('3', 3)]
>>> rldecode(rlencode("Hello!"))
'Hello!'
>>>
Problem 8
In class, we discussed the difference between apure(oreffect-free) function (i.e. one that returns a value, but does not produce an effect) and amutatingfunction (i.e. one that changes the value of its parameters). In this exercise, we ask you to demonstrate your understanding of this distinction by implementing the same functionality as both a pure function, and as a mutating function.
Both functions take alistofintas a parameter. The pure variant will return a newlistcontaining the integers in reversed order. The mutating variant will returnNone, and will instead modify thelistthat it’s given.
Your functions should have these signatures:
defreverse_pure(xs):"""
signature: list(int) -> list(int)
Returns a list of integers in reverse order """
pass
defreverse_mut(xs):"""
signature: list(int) -> NoneType Reverses the list of integers in place """
pass
When implementingreverse_mut, consider carefully how one can reverse the items in a list without creating a new list.
A contrasting example:
>>> mylist = [5, 12, 34, 0, 1]# The list of numbers>>> newlist = reverse_pure(mylist)# Call the pure function
5
>>>print(newlist)
[1, 0, 34, 12, 5]
>>>print(mylist)
[5, 12, 34, 0, 1]
>>> reverse_mut(mylist) >>>print(mylist)
[1, 0, 34, 12, 5]
# The new, reversed list
# The original list is unchanged
# Call the mutating function (returns None) # Original list is reversed in-place
For this problem, you maynotuse the built-in Python functions for reversing list,reverseandreversed. You may not use the slice operator to reverse the list. You must implement the function using a loop.Problem 1
Before starting the coding assignment, please practice by mentally executing the following functions and figuring out what they do. You should practice the technique of predicting what Python code does without using Python.
Describe what each function does, briefly, in English, in a comment in your submitted file. Illustrate your explanation with at least one example call and its result.
Write your explanations and examples into a comment in your code file.
Do not type the code into your computer!
defmystery1(x):"""
signature: str -> str
"""
forzin["yes", "no", "maybe"]:
ifx == z:returnz
return"unknown"
defmystery2(lst):"""
signature: list(str) -> str """
acc = ""
foriteminlst:
acc += item+", "returnacc
defmystery3(lst):"""
signature: list(int) -> list(int) """
i=0
1
whilei len(lst) // 2:
lst[i] += lst[i +len(lst) // 2] i+=1
returnlst[0:len(lst) // 2]
defmystery4():"""
signature: () -> list(str) """
acc = []
forfirstin[1, 2, 3]:
forsecondin["a", "b", "c"]: acc.append(first * second)
returnacc
Problem 2
Write a function named “avg” that fulfills the following specification by replacing thepassline:
defavg (numbers) :"""
signature: list (float) -> float
precondition: numbers != []
returns the average (mean) of a non-empty list of floats """
pass# TODO: implement the body of this function
You may assume that the input is not an empty list. That is, your code doesnotneed to handle the situation whennumbersis[].
Your function should not useprintorinputat all.
Note: for the purposes of this problem, you maynotuse the built-insumfunction, rather
you should write a loop that iterates over the items in the list.
Problem 3
Write a function named “sum_some” with three parameters:lower,upperandnumbers, that returns the sum of the elements of the listnumberswhich are betweenlowerandupper(inclusive). If the listnumbersis empty then your function should return0. Your function should satisfy the signature:int , int , list (int) -> int.
For example:
>>> sum_some (0 , 100 , [])
0
>>> sum_some (0 , 100 , [1,2,3,4,5]) 15
>>> sum_some (2 , 4 , [1,2,3,4,5])
9
>>> sum_some (3 , 3 , [2,2,3,3,4,4]) 6
Your function should not useprintorinputat all.
2
Problem 4
Write a function named “is_sorted” that takes a list of numbers and returnsTruein case the list is in increasing order, andFalseotherwise.
This means that every number in the list should be larger or the same as the preceding number.
By convention, we will returnTruefor the empty list. For example:
>>> is_sorted ([]) True
>>> is_sorted ([1]) True
>>> is_sorted ([1 , 2 , 3]) True
>>> is_sorted ([1 , 2 , 2 , 3]) True
>>> is_sorted ([1 , 2 , 2 , 1]) False
Hint: notice that a list is sorted just in case there is no adjacent pair of entries that is out of order. In other words, a list is sorted if for every adjacent pair of entries, the one on the left is less than or equal to the one on the right.
Note: for the purposes of this problem, you maynotuse any of Python’s built-in sorting functions, instead, you should traverse the list and check that all adjacent pairs of entries are ordered.
Your function should not useprintorinputat all. Test your code thoroughly before submitting it.
Problem 5
Write a function named “indices” with two parameters: an object,needle, and a list of objects,haystack. Your function should return the list of positions of all occurrences ofneedleinhaystack.
For example:
>>> indices []
>>> indices []
>>> indices [0]
>>> indices
[1, 2]
>>> indices [1, 3, 5]
(7 , [])
(7 , [6])
(7 , [7,8,9])
(7 , [1,7,7,6])
(7 , [0,7,1,7,2,7,3])
Notice that the output is a list of positions. That is, in the last example, the result is[1, 3, 5]because theneedle7 appears in thehaystackat positions 1, 3, and 5.
Hint: you’ll need to iterate through the haystack, and, if a given item matches the needle, append it to an accumulator. You are prohibited from using Python’s built-in searching methods, such asindex. You are, however, permitted to use the indexing operator.
3
Your function should not useprintorinputat all. Test your code thoroughly before submitting it.
Problem 6
Write a function namedinterspersethat will prompt the user to enter two sentences. Then it willprinta combined sentence, consisting of alternating words from each sen- tence: first from the first sentence, next from the second sentence, then the first sentence again, etc. If one sentence has more words than the other, the remaining words should be output at the end of the result.
The function should take no parameters. Its signature should be() -> NoneType.
For the purposes of this problem, you may consider a “word” to be any space-separated sequence of non-space characters, including punctuation. You may use thesplitmethod to separate a string into a list of its constituent words. You may use thejoinmethod to combine a list of words into a string.
Please read the example executions below and make sure that your implementation can reproduce these results exactly:
>>> intersperse()
Enter a sentence:This is a test
Enter a sentence:of the emergency broadcast system.
This of is the a emergency test broadcast system. >>> intersperse()
Enter a sentence:It is an ancient mariner
Enter a sentence:Who stoppeth one of three
It Who is stoppeth an one ancient of mariner three >>> intersperse()
Enter a sentence:Five
Enter a sentence:for the symbols at your door
Five for the symbols at your door
Problem 7
Run-length encoding is a technique to reduce the amount of characters used to repre- sent repetitive strings. For example, given the stringaadccccaa, one can see that it contains twoa’s, followed by oned, followed by fourc’s, followed by twoa’s. If we represent the run-length encoding of this string as a list of tuples, where each tuple con- tains an individual character and how many times it’s repeated, it would look like this:[('a', 2), ('d', 1), ('c', 4), ('a', 2)].
Write two functions,rlencodeandrldecodethat will, respectively, convert a string into its run-length encoded format, as given above; and convert a run-length encoding (in the form of a list of tuples ofstrandint) back into the original string. The functionrldecodeis the inverse ofrlencode, so that for any string value ofx, this expression will hold true:rldecode(rlencode(x)) == x
Neither function should useprintorinput. The functions should have the following signatures:
defrlencode(s):"""
signature: str -> list(tuple(str, int)) """
pass
4
defrldecode(rle):"""
signature: list(tuple(str, int)) -> str """
pass
Some more examples:
>>> rlencode("abba")
[('a', 1), ('b', 2), ('a', 1)]
>>> rlencode("aaaaaaaaaaaaaa")
[('a', 14)]
>>> rlencode("Hello!")
[('H', 1), ('e', 1), ('l', 2), ('o', 1), ('!', 1)] >>> rlencode("122333")
[('1', 1), ('2', 2), ('3', 3)]
>>> rldecode(rlencode("Hello!"))
'Hello!'
>>>
Problem 8
In class, we discussed the difference between apure(oreffect-free) function (i.e. one that returns a value, but does not produce an effect) and amutatingfunction (i.e. one that changes the value of its parameters). In this exercise, we ask you to demonstrate your understanding of this distinction by implementing the same functionality as both a pure function, and as a mutating function.
Both functions take alistofintas a parameter. The pure variant will return a newlistcontaining the integers in reversed order. The mutating variant will returnNone, and will instead modify thelistthat it’s given.
Your functions should have these signatures:
defreverse_pure(xs):"""
signature: list(int) -> list(int)
Returns a list of integers in reverse order """
pass
defreverse_mut(xs):"""
signature: list(int) -> NoneType Reverses the list of integers in place """
pass
When implementingreverse_mut, consider carefully how one can reverse the items in a list without creating a new list.
A contrasting example:
>>> mylist = [5, 12, 34, 0, 1]# The list of numbers>>> newlist = reverse_pure(mylist)# Call the pure function
5
>>>print(newlist)
[1, 0, 34, 12, 5]
>>>print(mylist)
[5, 12, 34, 0, 1]
>>> reverse_mut(mylist) >>>print(mylist)
[1, 0, 34, 12, 5]
# The new, reversed list
# The original list is unchanged
# Call the mutating function (returns None) # Original list is reversed in-place
For this problem, you maynotuse the built-in Python functions for reversing list,reverseandreversed. You may not use the slice operator to reverse the list. You must implement the function using a loop.