Python Exercises 28

Debugging Problem 1: Summable Sublists

For this problem let me explain the subset summation problem. I want to be able to figure out if a list has a sublist which sums to a specified number.

For instance if that number is 5, and the list is [1, 2, 3] then we see that the sublist [2, 3] sums to five. On the other hand, if we want 7 on the same list [1, 2, 3], then there's no way to add to that given the numbers here. [Previously it said 4, but 1 + 3 = 4].

My "solution" uses the idea that either we will take the 1st element or not into the sum. If we do, then we'll include it with the goal variable, else we'll just go on without it and ask if the rest of the list can add up to the goal.

I've implemented it recursively. My code is available at: https://github.com/UMBC-CMSC-Hamilton/CMSC201-Spring2020/b lob/master/Midterm2/summing_sublists.py And /afs/umbc.edu/users/e/r/eric8/pub/cs201/spring20/summing_sublists.py

Here are some basic test cases that I ran on working code with correct answers. Your code should not only eventually match

print(sum_goal_buggy(1, 2, 3], 5)) # True
print(sum_goal_buggy(1, 2, 3), 17)) # False
print(sum_goal_buggy([1, 2, 3), 3)) # True
print(sum_goal_buggy [1, 2, 3, 6, 8, 121, 18)) # True
print(sum_goal_buggy[1, 2, 3, 6, 8, 12), 33)) # False

Note: The function should remain recursive.

def sum_goal_buggy(my_list, goal):
"""
:param my_list: list of numbers
:param goal: goal to be added up
:return: True if some sublist adds to goal, False else
"""
if goal == 0:
return True
else:
# ignore my_list[0]
if sum_goal_buggy(my_list[1:], goal):
return True
# include my_list[0] in the sum
elif sum_goal_buggy(my_list[2:], goal + my_list[0]):
return True
return False

Debugging Problem 2: Anagramatics

An anagram is a pair of words which are the same up to a rearrangement of letters. For instance the anagrams of "auctioned" are:

cautioned
education

Now, we're going to consider two words anagrams regardless of whether they're English words, so happy has anagrams:

Yppah
Yahpp
Pahyp
Etc.

We're going to implement a function called:

def anagram_buggy(first_word, second word):

This function should take two strings, convert them to the same case (to ignore case), and then check if they are anagrams.

The original anagram_buggy function can be found at: https://github.com/UMBC-CMSC-Hamilton/CMSC201-Spring2020/blob/master/ Midterm 2/anagrams.py

Or /afs/umbc.edu/users/e/r/eric8/pub/cs201/spring20/anagrams.py

Fix the function to working order, run a number of tests on it so that you know it works, and then submit it.

def anagram_buggy(first_word, second_word):
first_word = first_word.lower()
second_word = second_word.upper()
first_word_dict = {}
second_word_dict = {}
for letter in first_word:
if letter in first_word_dict:
first_word_dict[letter] += 1
for letter in second_word_dict:
if letter in second_word_dict:
second_word_dict[letter] += 1

for letter in first_word_dict:
if first_word_dict[letter] != second_word_dict[letter]:
return False

return True

Problem 1: Palindrome

Let's define what an almost palindrome is (we're inventing it). A string is a k-almost palindrome if it is a palindrome with up to k errors. For instance, O-almost palindromes are regular palindromes with zero errors.

Here are some examples:

abcdcba is a palindrome, so a 0-almost palindrome.
abedfba is not a 0-almost palindrome because but it is a 1-almost palindrome since it has one error.
arglebargle is a 4-almost palindrome since it has 4 errors pairs, but it's not a 3-almost palindrome.

Write a recursive function: def almost_palindrome/the_string, num_errors): This function should determine if the_string is an almost-palindrome with at most num_errors errors. The function should return True or False only and must be recursive.

Problem 2: Find a Square

Create a function where you look for a "square" on a grid. The function will be sent a 2d-list and be expected to return the upper left coordinate of a "square."

A square in a grid will consist of 4 "*" symbols:

When the grid is called on this array for instance it should return: [1, 2] as a list. If there are multiple squares, return any one of them. A square will be exactly 4 stars which are not separated by any space and no larger squares than exactly 4 block squares should be searched for. Any other character but "*" does not make a square.

The function should be defined as:

def find_a_square/the_grid, height, width):

The_grid is a two dimensional list of height (first index) height, and second index of width. Return a list of the indices (row first, then column) for the position of one square. If none exist, return an empty list.

Problem 3: Cities and Countries

Create a class CitiesAndCountries with at least three methods:

class CitiesAndCountries:
def add_country(self, country_name):
"""
:param country_name: name of new country
:return: True if added, False if duplicate
"""

def add_city(self, country_name, city_name):
"""
:param country_name: must be a country in the already defined countries
:param city_name: name of new city
:return: True if added, False if not added

def find_city(self, city_name):
"""
:param city_name: get all cities with that name, in all different countries
:return: list of countries which have a city with that name, empty list if none
"""

You may implement more methods than this, but you must support at least this functionality. You must use a dictionary inside of the class.

You must implement the methods to be consistent with their documentation.