辅导data程序、讲解program程序设计、Python编程语言调试讲解留学生Processing|解析Haskell程序

项目预算：开发周期：发布时间：要求地区：

Homework 8
Total Points: 100 (Correctness and Style)
Due Dates (SD time):
● Entire Assignment: Tuesday, December 1st, 11:59pm
● Checkpoint (read below): Sunday, November 29th, 11:59pm
Read ALL instructions carefully.
Starter Files
Download hw08.zip. Inside the archive, you will find starter files for the questions of
this homework. You cannot import anything to solve the problems.
Style Requirements
Please refer to the style guide on the course website.
Docstring and Doctest Requirements
● Each docstring is surrounded by triple double quotes (""") instead of triple
single quotes (''')
● Ensure that each of your functions has a well-formed docstring and that you
have at least 3 doctests of your own. Try to think of the cases that would
break your code rather than test it on easy to pass scenarios.
Testing
At any point of the homework, use the following command to test your work:
>>> python3 -m doctest hw08.py
For Windows users, please use py or python instead of python3.
Checkpoint Submission
Due Date: Sunday, November 29th, 11:59pm (SD time)
You can earn 5 points extra credit by submitting the checkpoint by the due date
above. In the checkpoint submission, you should complete Question 1 and submit
the hw08.py file to gradescope.
Checkpoint submission is graded by completion, which means you can get full
points if your code can pass some simple sanity check (no tests against edge
cases). Note that in your final submission, you should still submit these questions,
and you may modify your implementation if you noticed any errors.
Final Submission
Submit your work to gradescope, under the hw08 portal. You can submit multiple
times before the due date, but only the final submission will be graded.
Required Questions
1. DO NOT IMPORT ANY PACKAGES.
2. Please add your own doctests (at least one for the
class constructors, and at least three for the
remaining methods/functions) as the given doctests
are not sufficient. You will be graded on the doctests.
3. No assert statements are required for all questions. You
can assume that all arguments will be valid.
Question 1
In this question, you will implement a counter for iterable objects. A counter counts
and stores the occurrences of provided items, and it allows you to query the count
of a specific item in the counter.
All doctests for this question are in the function counter_doctests(). You need to
initialize 1 more instance of each class as constructor tests, and add 3 more
doctests for each method you implement.
Part 1: Counter
The Counter class abstracts a generalized counter for all kinds of iterable objects.
In the constructor (__init__), you need to initialize the following instance
attributes:
● nelems (int): The total number of items stored in the counter. Initialize it
with 0.
● counts (dict): A dictionary that stores all item (keys) to count (values)
pairs. Initialize it with an empty dictionary.
Then, implement the following 4 methods:
● size(self): Returns the total number of items stored in the counter.
● get_count(self, item): Returns the count of an object item. If the item
does not exist in the counter, return 0.
● get_all_counts(self): Returns a dictionary of all item to count pairs.
● add_items(self, items): Takes an iterable object (like list) of objects
(items) and adds them to the counter. Make sure to update both counts and
nelems attributes.
Note:
For the item argument and each object in the items argument, you can assume that
they can be used as a dictionary key. All immutable objects and a tuple of
immutable objects would qualify as valid dictionary keys. However, mutable objects
(such as list) are not valid keys, and you can assume they will not appear as items
to count. If you attempt to use a mutable object as a key of dictionary, the
following error will occur:
>>> counts[[1]]
Traceback (most recent call last):
File "", line 1, in
TypeError: unhashable type: 'list'
Part 2: Alphanumeric Counter
In this part, we will build a counter for only Alphanumeric characters in strings.
When we need to count the characters in a string, we could further optimize the
counter in terms of time and space by replacing the dictionary with a counter list,
where each index represents an item, and the value at this index is the count of
this item.
To use a list as a counter, we need to figure out a way to convert characters to
integer indices, so that we could use the indices to query the list. Luckily, we
already have such a conversion rule available in our system. Since computers can
only understand numbers, each character is internally mapped to a non-negative
integer. The most basic conversion rule is ASCII, which provides mappings to
alphanumeric characters and some special characters. You can refer to the ASCII
table for the specific mapping.
In Python, we could perform the ASCII mapping through built-in functions ord() and
chr(). The ord() function takes a character and converts it to its integer
representation, and the chr() function does the opposite. For example:
After obtaining this mapping, we can start to build our counter list for the
alphanumeric characters. The list will be of length 10 + 26 + 26 = 62, which will
store digits (0-9), lowercase letters (a-z) and uppercase letters (A-Z). Specifically,
the mappings between each index and the character it represents are as follows:
To use this counter list (let’s call it counts), if we want to query the count of
character 'b', we first need to convert it to index 11, then retrieve counts[11].
For this class, you must use ord() and chr() for the conversion. You cannot
hardcode the entire mapping using list, dictionary, string, or if-elif-else statements.
>>> ord('0')
48
>>> chr(48)
'0'
>>> ord('A')
65
>>> chr(65)
'A'
>>> ord('a')
97
>>> chr(97)
'a'
index 0 1 ... 9 10 11 ... 35 36 37 ... 61
char '0' '1' ... '9' 'a' 'b' ... 'z' 'A' 'B' ... 'Z'
In the constructor (__init__), you need to initialize the following instance
attributes (you can reuse Counter’s constructor):
● nelems (int): The total number of items stored in the counter. Initialize it
with 0.
● counts (list): A counter list of length 62 as described above.
Since this counter performs a conversion between characters and indices to store
and query the count, you need to implement the following helper methods:
● get_index(self, item): Given an item, return its corresponding index (0-9
for digits, 10-35 for lowercase letters, 36-61 for uppercase letters). If the
item is not an alphanumeric character, return -1.
● get_char(self, index): Given an index (0-61), return the corresponding
character.
You can use the built-in functions str.isnumeric(), str.islower() and str.isupper() to
distinguish different kinds of characters.
Then, overwrite the following methods:
● get_count(self, item): Returns the count of a character item. If the item
does not exist in the counter, return 0.
● get_all_counts(self): Returns a dictionary of all item to count pairs. You
need to build the dictionary by iterating through the counts list and add all
pairs with non-zero counts to the new dictionary. The dictionary should have
characters as keys (instead of indices) and counts as values.
● add_items(self, items): Takes a string items and adds each character to
the counter. Note that you should not add non-alphanumeric characters to
this counter. Make sure to update both counts and nelems attributes.
Question 2
Write a recursive function that takes two sequences of numeric values (main and
sub), and calculate two kinds of sum of the main sequence:
(1)Sum of intersection: the sum of all numbers in the main sequence that also
appear in the sub sequence.
(2)Sum of differences: the sum of all numbers in the main sequence that do not
appear in the sub sequence.
This function should return a tuple of (sum_of_intersection, sum_of_difference), if
the main sequence is empty, return (0, 0).
You CANNOT use sum(), range(), or any loops/list comprehensions.
def find_two_sums_rec(main, sub):
"""
>>> main_seq = [0, 1, 1, 2, 3, 3, 4, 5, 5]
>>> find_two_sums_rec(main_seq, [])
(0, 24)
>>> find_two_sums_rec(main_seq, [1, 2])
(4, 20)
>>> find_two_sums_rec(main_seq, [3, 4, 5])
(20, 4)
"""
# YOUR CODE GOES HERE #
Question 3
Write a recursive function that takes a base string and a non-empty pattern string,
and computes the length of the largest substring of the base that starts and ends
with the pattern. If no match is found, return 0.
Notes:
(1) This function should look for exact matches (case-sensitive).
(2) The start pattern and end pattern of the largest substring could fully or
partially overlap (see examples below).
Examples:
def compute_max_string(base, pattern):
"""
>>> compute_max_string("jumpsjump", "jump")
9
>>> compute_max_string("hwhwhw", "hwh")
5
>>> compute_max_string("frontsdakonsakdna", "front")
5
>>> compute_max_string("life", "life")
4
"""
# YOUR CODE GOES HERE #
base pattern output
jumpsjump jump 9 (not overlapped)
hwhwhw hwh 5 (partially overlapped)
frontsdakonsakdna front 5 (fully overlapped)
life life 4 (fully overlapped)
Question 4 (Extra Credit)
Write a recursive function that takes a list of positive integers (nums, not empty)
and a positive integer target, and find whether it’s possible to pick a combination of
integers from nums, such that their sum equals the target. Return True if we can
pick such a combination of numbers from nums; otherwise, return False.
Hints:
(1) For each recursive call, you should only deal with one number in the list.
Think about how to approach these sub-problems with recursion: if we
include this number in the combination, can we reach the target sum? How
about excluding this number from the combination?
(2) Although we assume that the initial arguments are positive integers and the
initial nums list is not empty, you might observe that, at some point, a
recursive call will receive arguments that violate these assumptions (for
example, the nums list becomes empty). You might find it helpful to treat
these situations as base cases.
Examples:
def group_summation(nums, target):
"""
>>> group_summation([3, 34, 4, 12, 5, 2], 9)
True
>>> group_summation([1, 1, 1], 9)
False
>>> group_summation([1, 10, 9, 8], 17)
True
"""
# YOUR CODE GOES HERE #
nums target output
[3, 34, 4, 12, 5, 2] 9 True
[1, 1, 1] 9 False
[1, 10, 9, 8] 17 True

辅导data程序、讲解program程序设计、Python编程语言调试 讲解留学生Processing|解析Haskell程序

辅导data程序、讲解program程序设计、Python编程语言调试讲解留学生Processing|解析Haskell程序