How to build a retaining wall
When we moved into our first house we inherited a half finished retaining wall.
We had posts already built,
eventually we where kindly gifted some wood planks represented as a list of lengths wood_lengths
to finish the retaining wall we had to cut the planks to get planks of all the lengths we require,
so we had another list of lengths required_lengths
.
We want to use as few cuts as possible because we are lazy programmers.
Task: write an algorithm to find the list of cuts you should make.
A cut can be described as:
wood_num
is the index of the length of wood to cut from in wood_lengths
cut_amount
the length of wood to cut from this wood_num
e.g.
1  { 
describes cutting a plank of length 10 from wood_lengths[0]
test cases:
1  wood_lengths=[6] required_lengths=[2, 2, 2] > 
Finding an optimal solution means generating all valid possibilities and taking the one with optimal output (with the smallest amount of cuts in this case).
One strategy for trying all possibilities is to imagine:
for required_lengths[0]
we could take the cut from any length in wood_lengths
for required_lengths[1]
we could take the cut from any length in wood_lengths
…
This recursive algorithm would run generate a recursive call tree with len(wood_lengths)
branches at each step and len(required_lengths)
deep
so it would take atleast $O( len(wood\_lengths) ^ {len(required\_lengths)} )$ time.
There are some conditions allowing you to prune this recursive call tree:
 You can’t take a cut of size N from a wood_length less than N.
 Only consider non duplicate wood lengths (If you have planks A and B both of size N then you could take a cut from either, it would be equivalent)
1  class RetainingWallSolver(object): 
Example tests https://github.com/lee101/retainingwall/blob/master/retaining_wall_test.py
Whats wrong with this solution?
Overlapping subsolutions:
consider the call tree when we pass the following parameters
1  wood_lengths=[6, 8, 8] required_lengths=[2, 2, 2] 
Notice how wood_lengths=[4, 6, 8] required_lengths=[2]
is computed twice,
when inputs get large this can mean the algorithm spends a massive amount of time solving problems that it has already solved.
If the lengths in wood_lengths
(regardless of order) is the same and required_length_idx
is the same then retaining_wall_recursive
should return the same thing.
One way to improve a recursive algorithm to not compute the same thing twice is called memoization (caching the function call),
We could store a hashtable (a dict) mapping the given arguments to the output of the function.
One way to implement this in python is with decorators, its quite nice because our caching logic is in one place.
1  import copy 
We can then use the decorator as follows:
1 

This runs a lot faster, but does use more memory, could we be better about our memory usage by smartly evicting keys?
TODO: finish dynamic programming example
Extra follow on problems:
Maximise reuse/Minimise waste
What if there where multiple solutions with the fewest cuts, then how should we decide the best?
That is first and foremost we want to make the fewest cuts
Secondly we want to maximize reuse (we want nice long offcuts we can use for other things).
How should we define reuse?
Well we know we want to build another retaining wall which will have similar distances between posts (and thus similar required_lengths
)
As a heuristic we know we will only be able to use a leftover plank if its at least the smallest length in required_lengths
This means we can define reuse as the amount of times you can cut the smallest required_length
out of your remaining planks.
Waste is how much reuse a solution doesn’t get (The total length of all the offcuts that can’t be reused).
Another way of wording this is that we want to minimize waste.