代写data程序、代做program程序设计、Python编程语言调试

日期：2020-12-03 11:29

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 "<stdin>", line 1, in <module>

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