# 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/retaining-wall/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 | @unordered_memoized |

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.