[python] pset 9

Viewer

  1. def inator_destroyer(inators,incinerator_size):
  2.     """
  3.     inputs 
  4.         inators: a list of tuples of the format ((height,width,length),evil_potential)
  5.         incinerator_size: a tuple of (height,width,length) of the incinerator
  6.     return value:
  7.         a list of tuples of the format (height,width,lenth) [allowed to be returned in any order] such that this subset of the boxes 
  8.         can nest inside each other in the incinerator and evil potential is maximized
  9.     """
  10.     memo = dict()
  11.     p = dict()
  12.  
  13.     inators.sort(key=lambda i: i[0][0] * i[0][1] * i[0][2], reverse=True)
  14.  
  15.     def DP(i,j):
  16.         """
  17.         inputs:
  18.             i: the index we are currently lookin at
  19.             j: a tuple of ((height,width,length), evil)
  20.         """
  21.         # Set curr to be the (i,j) pair we're looking at
  22.         curr = (i, j)
  23.         evil = inators[i][1]
  24.         h = inators[i][0][0]
  25.         w = inators[i][0][1]
  26.         l = inators[i][0][2]
  27.  
  28.         # Dimensions of the box we last nested. The box we compare i to.
  29.         bL = j[0][2]
  30.         bW = j[0][1]
  31.         bH = j[0][0]
  32.  
  33.         if curr in memo:
  34.             return memo[curr] # if current subproblem in memo just return value
  35.         # base case
  36.         if i == len(inators) - 1:
  37.             # If it can fit, add it in and set parent to none since last one
  38.             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)):
  39.                 memo[curr] = inators[i][1]
  40.                 p[curr] = (None, 'Yes')
  41.                 # print("adding None at key:" + str(curr))
  42.             # Else it cannot fit and contributes 0 evil
  43.             else:
  44.                 memo[curr] = 0
  45.                 p[curr] = (None, 'No')
  46.                 # print("adding none at key:" + str(curr))
  47.         else:
  48.             first = float('-inf')
  49.             second = float('-inf')
  50.             # First option: nest box
  51.             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)):
  52.                 # first option
  53.                 first = evil + DP(i+1, inators[i])
  54.             # Second option: don't nest box and skip
  55.             second = DP(i+1, j)
  56.             # If first option is better, store that value as memo and its parent as the recursion.
  57.             if first > second:
  58.                 memo[curr] = first
  59.                 p[curr] = (i+1, inators[i])
  60.                 # print('adding ' + str((i+1, inators[i])) + ' at key ' + str(curr))
  61.             # Else, store second.
  62.             else:
  63.                 memo[curr] = second
  64.                 # p[curr] = (i+1, j)
  65.                 # print('adding ' + str((i+1, j)) + ' at key ' + str(curr))
  66.         return memo[curr]
  67.  
  68.     tuples_list = []
  69.     def build_list(item):
  70.         parent = p[item]
  71.         if parent == (None, 'Yes'):
  72.             tuples_list.append(inators[item[0]][0])
  73.             return tuples_list
  74.         if parent == (None, 'No'):
  75.             return tuples_list
  76.         else:
  77.             tuples_list.append(parent[1][0])
  78.             build_list(parent)
  79.     DP(0, (incinerator_size, float('-inf')))
  80.     # print(p)
  81.     build_list((0, (incinerator_size, float('-inf'))))

Editor

You can edit this paste and save as new:


File Description
  • pset 9
  • Paste Code
  • 06 May-2021
  • 3.37 Kb
You can Share it: