(Codewars Kata) Memoised Log Cutting

Question

(I am not sure of the official CS name for the problem in question, so I just gave it the name of the kata).

---

Problem

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:

# 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:

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:

# 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)

---

Solution

def cut_log(p, n):
 for i in range(2, len(p)):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

It passes all the tests. I'm putting it up for review because I'm pretty proud of it and experience as shown me that there's usually some improvement to be made.

Answer 1

I see three problems with this function:

• Why calculate the values up to len(p), when you are actually interested in p[n] (which may be larger or smaller than len(p))? In the case of n > len(p) your code actually raises an exception (and it seems not to be excluded by the rules, but also not to be checked by the online judge).
• This is not really using memoization, since you calculate everything again whenever the function is called.
• You mutate p, which might lead to unexpected results (in general), although here it happens to work out fine.

The second (and third) problem are not so easy to fix (probably only by memoizing all different p ever seen and for each of them the maximum n used). Also the online judge may or may not use the same p again.

The first one however is an easy fix:

def cut_log(p, n):
 for i in range(2, n + 1):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

• Tobi Alafin: The first one is actually an artifact of me stripping coverage for when n > p. I realised that case did not show up at all, and then removed it from my code to make it more succinct. But I like the suggestion of using memoisation, and I would consider it.
• Tobi Alafin: Also, your third suggestion sounds to me like a feature not a bug? Mutating p uses less space than building a new array (and should be faster as well). Isn't that desirable?
• Graipher: @TobiAlafin Well one design philosophy is that functions should either be pure (so not mutate their inputs and just return an output) or the opposite (mutate the input but return only None). This philosophy is followed by almost all built-in functions (list.pop is the only exception I can think of right now) and is therefore the expected behavior in Python. If your function behaves differently you would want to make very sure that you documented that properly.
• JaDogg: IMHO OPs original code remembers sub problems by mutating the array. Which makes it O(n^2) and this is a correct approach. Since p can change there is really no point in having it cached again at the function level. Unless you cache it for each kind of prices array and n using some hashing for the array and n and solve it for different n. These online judge programs run the code again for new input and memory is not preserved AFAIK.
• Graipher: @422_unprocessable_entity The OP's code does remember subproblems, but doesn't use that fact since the loop runs regardless. And yes to the second point, which is why I did not present a solution for that but just commented on it.

Answer 2

I incorporated suggestions that @Graipher made in his answer. This is the improved function that resulted from it.

Solution

history = {}
def cut_log(p, n):
 global history
 ln = len(p)
 if id(p) not in history:
 p = p + [0]*max(n - ln, 0)
 for i in range(2, max(n+1, ln)):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 history[id(p)] = p
 else:
 p = history[id(p)]
 ln = len(p)
 if n+1 > ln:
 p = p + [0]*max(n - ln, 0)
 for i in range(ln, n+1):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

I wasn't memoising the function, and I added that for increased performance.

• JaDogg: id is not a hash. It is the pointer like thing. If you use a tuple you can directly add it to a dict. Also see my comment above.
• Tobi Alafin: 422_unprocessable_entity thanks for the suggestion, I'll soon edit my solution to incorporate it.
• Sᴀᴍ Onᴇᴌᴀ: While OPs are encouraged to answer their own questions bear in mind that "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted."... From review
• JaDogg: Consider making this community wiki and accepting above answer, so you can edit this as you wish and respect valuable time and effort spent by Graipher.