[python] pset 9
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
- def inator_destroyer(inators,incinerator_size):
- """
- inputs
- inators: a list of tuples of the format ((height,width,length),evil_potential)
- incinerator_size: a tuple of (height,width,length) of the incinerator
- return value:
- a list of tuples of the format (height,width,lenth) [allowed to be returned in any order] such that this subset of the boxes
- can nest inside each other in the incinerator and evil potential is maximized
- """
- memo = dict()
- p = dict()
- inators.sort(key=lambda i: i[0][0] * i[0][1] * i[0][2], reverse=True)
- def DP(i,j):
- """
- inputs:
- i: the index we are currently lookin at
- j: a tuple of ((height,width,length), evil)
- """
- # Set curr to be the (i,j) pair we're looking at
- curr = (i, j)
- evil = inators[i][1]
- h = inators[i][0][0]
- w = inators[i][0][1]
- l = inators[i][0][2]
- # Dimensions of the box we last nested. The box we compare i to.
- bL = j[0][2]
- bW = j[0][1]
- bH = j[0][0]
- if curr in memo:
- return memo[curr] # if current subproblem in memo just return value
- # base case
- if i == len(inators) - 1:
- # If it can fit, add it in and set parent to none since last one
- if ((h < bH and l < bL and w < bW) or (h < bH and l < bW and w < bL) or (h < bL and l < bH and w < bW) or (h < bL and l < bW and w < bH) or (h < bW and l < bH and w < bL) or (h < bW and l < bL and w < bH)):
- memo[curr] = inators[i][1]
- p[curr] = None
- # Else it cannot fit and contributes 0 evil
- else:
- memo[curr] = 0
- p[curr] = None
- else:
- first = float('-inf')
- second = float('-inf')
- # First option: nest box
- if ((h < bH and l < bL and w < bW) or (h < bH and l < bW and w < bL) or (h < bL and l < bH and w < bW) or (h < bL and l < bW and w < bH) or (h < bW and l < bH and w < bL) or (h < bW and l < bL and w < bH)):
- # first option
- first = evil + DP(i+1, inators[i])
- # Second option: don't nest box and skip
- second = DP(i+1, j)
- # If first option is better, store that value as memo and its parent as the recursion.
- if first > second:
- memo[curr] = first
- p[curr] = (i+1, inators[i])
- # Else, store second.
- else:
- memo[curr] = second
- p[curr] = (i+1, j)
- return memo[curr]
- tuples_list = []
- def build_list(item):
- tuples_list.append(item[1][0])
- if p[item] == None:
- return tuples_list
- else:
- return build_list(p[item])
- print(DP(0, (incinerator_size, float('-inf'))))
- build_list((0, (incinerator_size, float('-inf'))))
- return tuples_list
Editor
You can edit this paste and save as new:
File Description
- pset 9
- Paste Code
- 04 May-2021
- 2.95 Kb
You can Share it:
Latest Code Pastes