ECE241 Homework4 solution FA21

question1_sol.py

### Longest Palindrome
# test_cases = [
#  "a", "abaab", "racecar", "bullet", "rarfile",
#  "computer", "windows", "saippuakivikauppias",
#  "aaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
#  "kkkkkkkkkkkkkkkkkkkkkkdldkkkkkkkkkkkkkkkkkkkkkk",
#  "ddddddddddddddddddddddddddddddddddddddddddddddddddks"
# ]

test_cases = ["a", "rarfile","0000000000000ooooo00ooooo", "windows", "saippuakivikauppias",
"abrakadabra", "123412341234","professordigbo", "tarattarat", "bab", "a123321a", "kd"
"123232223388939389393837389393999999999999999999999999999999999338839",
"ululululululululululululululululululululululullululululululululululululululul",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabkkkkkkl"]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = 0       # Start position of longest palindrome 
        end = 0         # End position of longest palindrome

        for i in range(0, len(s)):
            # Palindome can be centered around 1 character or 2 characteres.
            # example aba  -> center is a
            #         abba -> center is bb
            # Try both methods and see which one gives the longer palindome.
            l1 = self.expand_around(s, i, i)
            l2 = self.expand_around(s, i, i+1)

            l = l1 if l1 > l2 else l2       

            if l > end - start:
                start = i - int((l-1) / 2);
                end   = i + int(l/2)
                
        return s[start : end+1]
    
    def expand_around(self, s, left, right):
        while(left >= 0 and right < len(s) and s[left] == s[right]):
            left = left - 1
            right = right + 1

        return right - left - 1
        
        
        
if __name__ == "__main__":
    solution = Solution()
    
    for test_case in test_cases:
        print(test_case)
        print(solution.longestPalindrome(test_case))
    

question2_sol.py

"""
UMass ECE 241 - Advanced Programming
Homework #4     Fall 2021
question2.py - DP planks with turtle
"""

class Fence_Builder:
    def __init__(self, planks):
        self.plank_list = planks

    def dpChoosePlanks(self, plankList, totalDistance, minPlanks, planksUsed):
        """
        plankList = [1,5,10,21,25] # list of possible planks
        distance = 63 # Actual amount
        minPlanks = [0,0...0] (64)
        planksUsed = [0,0...0] (64)
        """
        count = 0
        for dist in range(totalDistance + 1):  # loop 64 times
            distCovered = dist  # dist = 0,1..64 (iterations-wise)
            newPlank = min(plankList)
            # print("Cents:{}".format(dist))
            # list of usable coins in each iteration
            for j in [c for c in plankList if c <= dist]:
                # print("j:{},minPlanks:{};planksUsed:{}".format(j, minPlanks, planksUsed))
                count += 1
                if minPlanks[dist - j] + 1 < distCovered:
                    distCovered = minPlanks[dist - j] + 1
                    newPlank = j
            minPlanks[dist] = distCovered
            planksUsed[dist] = newPlank

        return minPlanks[totalDistance]

    def printPlanks(self, planksUsed, totalDistance):
        dist = totalDistance
        plankOrder = []
        while dist > 0:
            thisDistance = planksUsed[dist]
            plankOrder.append(thisDistance)
            dist = dist - thisDistance
        return plankOrder[::-1]


    def select_planks(self, totalDist):
        planksUsed = [0] * (totalDist + 1)
        distCovered = [0] * (totalDist + 1)

        self.dpChoosePlanks(self.plank_list, totalDist, distCovered, planksUsed)
        A_list = self.printPlanks(planksUsed, totalDist)
        return A_list



if __name__ == "__main__":
    plankList = [1,5,10, 21, 25]
    fb = Fence_Builder(plankList)

    print(fb.select_planks(64))
    print(fb.select_planks(67))
    

question3_sol.py

class Solution:
	def solve(self):
		''' TREE TRAVERSAL
			- Select a traversal scheme answer each of the questions below.
			 options: (DFS, BFS, BOTH)
			 
			 - Select BOTH if the order of traversal makes no difference.
		'''
		ans = None
		
		
		''' EXAMPLE
		Find the minimum element in a binary search tree '''
		ans = "DFS"
		print(ans)
		
		''' 1
		Given a node n, find its nearest neighbour'''
		ans = "BFS"
		print(ans)
		
		''' 2
		Find the shortest path between 2 vertices(nodes) in a graph.'''
		ans = "BFS"
		print(ans)
		
		''' 3
		Find the shortest cycle in a directed graph'''
		ans = "BFS"
		print(ans)
		
		''' 4
		Find the longest cycle in a directed graph'''
		ans = "DFS"
		print(ans)
		
		''' 5
		Which tree traversal scheme uses more memory'''
		ans = "BFS"
		print(ans)
		
		''' 6
		Which traversal scheme can be implemented using a queue'''
		ans = "BFS"
		print(ans)
		
		''' 7
		Finding the destination of a packet routed through a network'''
		ans = "BFS"
		print(ans)
		
		
	
if __name__ == "__main__":
	sol = Solution()
	sol.solve()