# [python] pset 9

## Viewer

pset 9
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 * i * i, 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]
24.         h = inators[i]
25.         w = inators[i]
26.         l = inators[i]
27.
28.         # Dimensions of the box we last nested. The box we compare i to.
29.         bL = j
30.         bW = j
31.         bH = j
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]
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 ((< 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)):
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])
73.             return tuples_list
74.         if parent == (None, 'No'):
75.             return tuples_list
76.         else:
77.             tuples_list.append(parent)
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:
Latest Code Pastes