-
Notifications
You must be signed in to change notification settings - Fork 0
/
assign4.txt
99 lines (75 loc) · 5.48 KB
/
assign4.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
Assign4: Due 11:59PM April 12th
A company is in the business of buying rods in wholesale, cutting it, and
selling the pieces in the retail market. The market fluctuates and the price
for different sizes of rods changes by the day. Here's where we come in, the
company wants our help to know how much maximum money they can make, and how
to cut the rods of a given length to get that maximum money.
For example, if the rods of various lengths sell at the following prices on
a given day:
Inch price
1 $1
2 $1
3 $2
4 $3
5 $4
6 $5
7 $5
8 $9
9 $9
10 $10
Cutting a 20 inches rod into ten pieces of 2 inches each will only get them
$10. However, if they cut it into 6 pieces of two 8-inches, and four 1-inches
will get them $22. There may be other combinations that produce better price.
The additional challenge is the prices fluctuate each day.
We're asked to write a program, but in a way the algorithm for computing
the sizes can be changed.
Write a class RodCutter that will take the various lengths and their prices.
Then write one method on the class, cutRod that takes a length as parameter
and returns two things - maximum price the company can expect and the
size of the rods that they should cut the given length to get that price.
For example, if the input parameter is 2 (and the prices are as above),
then the output will be $2 and the sizes will be 1, 1 (for 2 pieces).
First write the class RodCutter so it works with a simple algorithm.
Then (and only after fully completing the above, not before), create another
version of RodCutter that will use techniques to shorten the
time to compute the result. The two versions must produce the same result,
just their computational efficiencies must be different.
Write a test to verify that the time taken by the second implementation is at least an order of magnitude faster than the first solution.
After you complete the program, answer the following questions:
1. What design principles did you use in this program. Explain each
and specify the classes that participated.
In this program, the main design principle we used was the DRY principle. Throughout the review process for this assignment, we were constantly
reminded to keep our program DRY. For each test class (rod_cutter_test and optimal_rod_cutter_test), we initially thought it was necessary to have
both classes test the same unit tests. This meant that we had to reinitialize the prices dictionary so that optimal_rod_cutter could test for those
values. Also, we initially had the same algorithm in cut_rod from the rod_cutter class in the optimal_rod_cutter class as we were trying to implement memoization. This proved to be violating DRY, as well as ignoring the fact that we could simply reuse the initial cut_rod function. Once this was done, optimal_rod_cutter's only responsibility was to implement memoization and to verify that the time taken by the second implementation was indeed faster than the initial naive solution.
Another design principle we used was LSP (Liskov Substitution Principle). In our case, the OptimalRodCutter class inherited from RodCutter in order
to reuse the algorithm. From here, the cut_rod in OptimalRodCutter overrode the naive recursive solution to implement memoization, without changing
the parameters that cut_rod would accept. The objects of OptimalRodCutter ended up behaving the same way as did the objects of the superclass, without
having to rewrite any existing code.
The two aforementioned design principles were the main focuses of our program. However, we still had to ensure that we honored OCP and SRP. OCP
mainly applied to the initial naive recursive solution in the RodCutter class. In the assignment specifications, we had to write the program
in a way that would allow the algorithm to compute rod lengths with changing prices. At first, we had the prices dictionary within the RodCutter
constructor, but this was not a good approach, as we needed to avoid keeping states as much as possible in order to make our program extensible. In
addition, we initially tried to modify the naive cut_rod in OptimalRodCutter, resulting in duplicated code.
2. What design patterns did you use in this program. Explain each
and specify the classes that participated.
The first pattern we used was factory method pattern. This is shown in the tests classes where we are using a method to initialize our testing objects.
For both rod cutter algorithms we are calling the same method to initialize in their respective testing objects.
Another design pattern we found to have used was flyweight pattern as it deals with the storing of data in a dictionary (hash-map) to increase performance. When
it came time to implement memoization in OptimalRodCutter, we made a cache (rod_cutter_cache) to store the previous computations from cut_rod in RodCutter.
With this cache, if a rod of a particular length had its max profit previously calculated, then the optimized cut_rod did not have to repeat unnecessary
computations, and would simply look up that rod's max profit value. This significantly reduced the complexity of the computational tree of the unoptimized
cut_rod method, resulting in much faster performance.
Total [100]: 94
All tests pass [20]:
Test Quality [10]:
Performance Test Quality [10]:
Code Coverage [10]:
Design Quality [20]:
Code Quality [10]: -1
def compute_time(self, rod_class):
rod_cutter = rod_class
No need for this extra local variable assignment.
Q1 [10]:
Q2 [10]: -5
Not quite Flyweight, the data was not shared between instances.