# Memoized Log Cutting

## [Memoized Log Cutting](https://www.codewars.com/kata/54b058ce56f22dc6fe0011df)

## **CLEAR CUTTER'S NEEDS YOUR HELP!**

The logging company Clear Cutter's makes its money by optimizing the price-to-length of each log they cut before selling them. An example of one of their price tables is included:

```python
# So a price table p
p = [ 0,  1,  5,  8,  9, 10]

# Can be imagined as:
# length i | 0  1  2  3  4  5 *in feet*
# price pi | 0  1  5  8  9 10 *in money*
```

They hired an intern last summer to create a recursive function for them to easily calculate the most profitable price for a log of length *n* using price table *p* as follows:

```python
def cut_log(p, n):
   if (n == 0):
      return 0
   q = -1
   for i in range(1, n+1)
      q = max(q, p[i] + cut_log(p, n-i))
   return q
```

An example of the working code:

```python
cut_log(p, 5) # => 13
# 5ft = $10, BUT 2ft + 3ft = 5ft -> $5 + $8 = $13 which is greater in value
```

However, their senior software engineer realized that the number of recursive calls in the function gives it an awful running time of 2^n (as this function iterates through ALL 2^n-1 possibilities for a log of length n).

Having discovered this problem just as you've arrived for your internship, he responsibly delegates the issue to you.

Using the power of Stack Overflow and Google, he wants you to create a solution that runs in Θ(n^2) time so that it doesn't take 5 hours to calculate the optimal price for a log of size 50. (He also suggests to research the problem using the keywords in the tags)

**(Be aware that if your algorithm is not efficient, it will attempt to look at 2^49 = 562949953421312 nodes instead of 49^2 = 2401... The solution will automatically fail if it takes longer than 6 seconds... which occurs at right around Log 23)**

## Solutions

### 🐍 Python

```python
_storage = dict()

# DP maximization problem
# I will save max for each log length
# problem also known as 'Cutting Rods'
#p - price, n - length
#could use lru_cache instead of _storage 
def cut_log(p, n):
    if n <= 0:
        return 0

    storage_key = (tuple(p),n)
    if storage_key not in _storage:
        _storage[storage_key] = max([price + cut_log(p, n - i) for i, price in enumerate(p[1:n + 1], 1)])

    return _storage[storage_key]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://anton-veselskyi.gitbook.io/codding-problems-solutions/codewars/4-kyu/memoized-log-cutting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.