Python program to solve the "rod-cutting problem"

Question

An assignment at school required me to write a program for this task:

In the rod-cutting problem, we are given a rod of length n inches and a table of prices p[i] for i = 1, 2, …, n. Here p[i] is the price of a rod of length iinches. We have to find the optimal way of cutting the rod so that maximum revenue can be generated by selling the pieces.

Here is my solution to this task (in Python):

def cut_rod(p, n):
    """
    Take a list p of prices and the rod length n and return lists r and s.
    r[i] is the maximum revenue that you can get and s[i] is the length of the
    first piece to cut from a rod of length i.
    """
    # r[i] is the maximum revenue for rod length i
    # r[i] = -1 means that r[i] has not been calculated yet
    r = [-1]*(n + 1)

    # s[i] is the length of the initial cut needed for rod length i
    # s[0] is not needed
    s = [-1]*(n + 1)

    cut_rod_helper(p, n, r, s)

    return r, s

def cut_rod_helper(p, n, r, s):
    """
    Take a list p of prices, the rod length n, a list r of maximum revenues
    and a list s of initial cuts and return the maximum revenue that you can get
    from a rod of length n.

    Also, populate r and s based on which subproblems need to be solved.
    """
    if r[n] >= 0:
        return r[n]

    if n == 0:
        q = 0
    else:
        q = -1
        for i in range(1, n + 1):
            temp = p[i] + cut_rod_helper(p, n - i, r, s)
            if q < temp:
                q = temp
                s[n] = i
    r[n] = q

    return q


n = int(input('Enter the length of the rod in inches: '))

# p[i] is the price of a rod of length i
# p[0] is not needed, so it is set to None
p = [None]
for i in range(1, n + 1):
    price = input('Enter the price of a rod of length {} in: '.format(i))
    p.append(int(price))

r, s = cut_rod(p, n)
print('The maximum revenue that can be obtained:', r[n])
print('The rod needs to be cut into length(s) of ', end='')
while n > 0:
    print(s[n], end=' ')
    n -= s[n]

where s[n] gives us the length of the first piece, s[n – s[n]] gives us the length of the second piece and so on.

Here is an example output -

Enter the length of the rod in inches: 3
Enter the price of a rod of length 1 in: 3
Enter the price of a rod of length 2 in: 7
Enter the price of a rod of length 3 in: 2
The maximum revenue that can be obtained: 10
The rod needs to be cut into length(s) of 1 2

Times taken for each function -

%timeit cut_rod(p, n)
7.65 µs ± 71.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit cut_rod_helper(p ,n, r, s)
266 ns ± 3.97 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Answer 1

First of all, it's really a bad idea to change the value of the input parameter when this change has an outer effect in some other place in your code.

Also, You can get rid of recursive function calls, that makes your code so much faster. So let's start from cut_rod_helper function:

def cut_rod_helper(p, n, r, s):
    q = 0
    for i in range(1, n + 1):
        temp = p[i] + r[n - i]
        if q < temp:
            q = temp
            s[n] = i
    return q

I removed comments for more clear view here. But it's good to have them in your code.

What I did here is removing recursion. I removed first if statement from your code because we don't do recursive call and don't need end of recursion statement. As you can see at the middle of the function, we get r value from that list directly.

Second change here is I removed second if statement in your code because we don't need this (At least when we only have prices more than zero). Fewer conditions mean better code. Because with fewer if and else, the code is more straightforward and less error-prone. Also in many cases, the if-less code is faster. So always try to minimize the number of if conditions in your code.

We can simply set q value to zero initially. If n be 0, range of for loop will be (1,1), when start and stop values of a for loop are same, that for will not execute. So you don't need to consider a different condition for that.

And the biggest trick is in the third line of the function. We really don't need recursive call. If we start calling helper function from 0 to n index of r, we always have previous values in the r and we can access them directly.

Now let's go to the primary function:

def cut_rod(p, n):
    r = [-1]*(n + 1)
    s = [-1]*(n + 1)
    r[0] = 0
    for i in range(1, n + 1):
        r[i] = cut_rod_hezerolper(p, i, r, s)
    return r, s

We have only two changes here. First, I have been set index 0 of r to zero. It's our initial state and is clear from problem description. length = 0 so price = 0!

Then, for avoiding the change of input parameters, We are looping through the r and set value of each index of it. Because for calculating ith value of r, we only need access to i - 1 values of it, and we have been set initial value r[0] and start our loop from i = 1, now our code works without any problem.

I did not a full performance test, but with few tries, the second version is about 3 times faster than the first version of your code.

In the end, I did not change variable names, because I think that may distract you. But I think you should change your variable names. s, r, q and ... are meaningless. If a variable is a list contains prices, you should name it something like prices_list. If you do that, you don't need many lines of those comments and everyone can find out what you did in your code at first glance. Spending some seconds on naming things in programming, saving minutes and hours later.

I hope this helps you.