[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 ((< bH and l < bL and w < bW) or (< bH and l < bW and w < bL) or (< bL and l < bH and w < bW) or (< bL and l < bW and w < bH) or (< bW and l < bH and w < bL) or (< bW and l < bL and w < bH)):
  39.                 memo[curr] = inators[i][1]
  40.                 p[curr] = None
  41.             # Else it cannot fit and contributes 0 evil
  42.             else:
  43.                 memo[curr] = 0
  44.                 p[curr] = None
  45.         else:
  46.             first = float('-inf')
  47.             second = float('-inf')
  48.             # First option: nest box
  49.             if ((< bH and l < bL and w < bW) or (< bH and l < bW and w < bL) or (< bL and l < bH and w < bW) or (< bL and l < bW and w < bH) or (< bW and l < bH and w < bL) or (< bW and l < bL and w < bH)):
  50.                 # first option
  51.                 first = evil + DP(i+1, inators[i])
  52.             # Second option: don't nest box and skip
  53.             second = DP(i+1, j)
  54.             # If first option is better, store that value as memo and its parent as the recursion.
  55.             if first > second:
  56.                 memo[curr] = first
  57.                 p[curr] = (i+1, inators[i])
  58.             # Else, store second.
  59.             else:
  60.                 memo[curr] = second
  61.                 p[curr] = (i+1, j) 
  62.         return memo[curr]
  63.  
  64.     tuples_list = []
  65.     def build_list(item):
  66.         tuples_list.append(item[1][0])
  67.         if p[item] == None:
  68.             return tuples_list
  69.         else:
  70.             return build_list(p[item])
  71.     print(DP(0, (incinerator_size, float('-inf'))))
  72.     build_list((0, (incinerator_size, float('-inf'))))
  73.     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: