Stock Pipe Cutting using Recursion

Question

This problem is from the Stanford Open Course CS106B Programming Abstractions Assignment #3 Problem number 6 here.

"You are charged with buying the plumbing pipes for a construction project. Your foreman gives you a list of the varying lengths of pipe needed. Home Depot sells stock pipe in one fixed length. You can divide each stock pipe in any way needed. Your job is to figure out the minimum number of stock pipes required to satisfy the list of requests, thereby saving money and minimizing waste.

The recursive function CutStock(Vector<int> & requests, int stockLength) is given a vector of the lengths needed and the stock pipe length. It returns the minimum number of stock pipes needed to service all requests in the vector. For example, if the vector contains {4,3,4,1,7,8} and the stock pipe length is 10, you can purchase three stock pipes and divide them as follows: {4,4,1} {3,7} {8} and have two small leftover remnants. There are other possible arrangements that also fit into three stock pipes, but it cannot be done with fewer."

We are allowed to use the specified function as a wrapper function.

Here is my solution code. Is this a good way to solve the problem? Are there any other ways to do so?

/*
* CutStock.cpp
* ------------
* Name: Ratul Sarna
* This program accepts a list of lengths of pipes needed by the
* user and the length of the stock pipe available. It returns the minimum
* number of stock pipes required to satisfy the list of requested pipes
*/

#include "simpio.h"
#include "console.h"
#include "vector.h"
#include <iostream>
using namespace std;

void initializeRequests(Vector<int> & requests);
int cutStock(Vector<int> & requests, int & stockLength);
int recCutStock(Vector<int> & reqCopy, int stockLength);

int main() {
    Vector<int> requests;
    initializeRequests(requests);
    int stockLength = getInteger("Enter the stock length: ");
    cout << "Minimum number of stock pipes required to meet the requests = "
<< cutStock(requests, stockLength) << endl;
    return 0;
}

/* Accepts the requested pipe lengths and stores them in the vector requests */
void initializeRequests(Vector<int> & requests) {
    while (true) {
int votes = getInteger("Enter required length (-1 to quit): ");
if (votes == -1) break;
requests.add(votes);
    }
}

/* This is a wrappper function for the actual recursive function that returns
* the minimum number of stockpipes required to satisfy the list of requests */
int cutStock(Vector<int> & requests, int & stockLength) {
    // make a deep copy of the given vector of requests so that it can be
    // manipulated on
    Vector<int> reqCopy = requests;

    // call the actual recursive function and return its value
    return (recCutStock(reqCopy, stockLength));
}

/* Prototypes for helper functions */
void removeRequestedPipes(Vector<int> & reqCopy, int stockLength, Vector<int> & subsetPipes, int index);
int sumOf(Vector<int> & subsetPipes);
bool isBetterPipe(int checkThisPipe, Vector<int> & subsetPipes, int stockLength, int sum, int & targetIndex);
void swap(int maxIndex, int index, Vector<int> & subsetPipes, Vector<int> & reqCopy);


/* Recursively calculates the minimum number of stock pipes (of stockLength) required
* to satisfy the list of requests
* The basic strategy is-
* 1. If there are requests remaining to be serviced then,
* find a subset of the pipe lengths such that the wastage is minimized when those
* pipes are cut from a pipe of stockLength.
* 2. Remove that subset from the original requested pipe lengths.
* 3. Recursively service the remaining requested pipe lengths
*/
int recCutStock(Vector<int> & reqCopy, int stockLength) {
    // if all requests have been met
    if (reqCopy.isEmpty()) return 0; // Base Case

    Vector<int> subsetPipes;
    removeRequestedPipes(reqCopy, stockLength, subsetPipes, 0);

    // return 1 stock pipe for the combination removed by the function above and then recursively
    // calculate the number of stock pipes needed to service the rest of the requested pipes
    return 1 + recCutStock(reqCopy, stockLength);
}

/* Starting with the first requested pipe length (in reqCopy), removes a combination of requested pipes
* from all the given requests (in reqCopy) in such a way that the stock pipe is used with the minimum
* amount of wastage */
void removeRequestedPipes(Vector<int> & reqCopy, int stockLength, Vector<int> & subsetPipes, int index) {
    if (index >= reqCopy.size()) return; // Base Case

    int sum = sumOf(subsetPipes), targetIndex = 0;
    // requested pipe being considered in this call
    int currentPipe = reqCopy[index];

    // if the current pipe length can be cut from the stockLength pipe then add it into the
    // subsetPipes vector and then remove it from the original requests
    if (sum + currentPipe <= stockLength) {
        subsetPipes.add(currentPipe);
        reqCopy.remove(index);
        removeRequestedPipes(reqCopy, stockLength, subsetPipes, index);
    }

    // if the pipe length from original requests is longer any of the pipes in the  subsetPipes
    // and it can be cut from the stockLength then replace it in the subset
    else if (isBetterPipe(reqCopy[index], subsetPipes, stockLength, sum, targetIndex)) {
        swap(targetIndex, index, subsetPipes, reqCopy);
        removeRequestedPipes(reqCopy, stockLength, subsetPipes, index);
    }

    else {
        removeRequestedPipes(reqCopy, stockLength, subsetPipes, index + 1);
    }
}

/* Returns the sum of all the elements in the vector */
int sumOf(Vector<int> & subsetPipes) {
    int sum = 0;
    for (int i = 0; i < subsetPipes.size(); i++)
        sum += subsetPipes[i];
    return sum;
}

/* Checks if the pipe length given in "checkThisPipe" is longer than any of the pipes in subsetPipes
* while still being smaller or equal to the stockLength given.
* if yes then update the targetIndex to the element that is smaller and return true.
* else return false */
bool isBetterPipe(int checkThisPipe, Vector<int> & subsetPipes, int stockLength, int sum, int & targetIndex) {
    for (int i = 0; i < subsetPipes.size(); i++) {
        if ((checkThisPipe > subsetPipes[i])
             && ((sum - subsetPipes[i] + checkThisPipe) <= stockLength)) {
            targetIndex = i;
            return true;
        }
    }
    return false;
}

/* Swaps the element at minIndex of subsetPipes with the element at index of reqCopy */
void swap(int minIndex, int index, Vector<int> & subsetPipes, Vector<int> & reqCopy) {
    int temp = reqCopy[index];
    reqCopy[index] = subsetPipes[minIndex];
    subsetPipes[minIndex] = temp;
}

Answer 1

Congratulations on creating a readable, well-structured, working program. That is certainly a sign that you're well on your way to mastering programming in C++. I have found a couple of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Think carefully about signed vs. unsigned integers

We don't have the contents of the non-standard include files "simpio.h", "console.h" and "vector.h" but can infer what's likely in them. Specifically, if Vector.size() returns a signed number, all is well, but if (as with std::vector<>), Vector.size() returns and unsigned number, then each of the comparisons should probably also use an unsigned number. This suggests, for example, that your index and possibly the pipe lengths should all be unsigned unless you're contemplating the use of negative length pipes. Negative length pipes are typically not stocked by Home Depot!

Consider bounding the problem

The assignment already notes that the maximum number of pipes is simply the length of the Vector (which I'll call \$n\$), but what about the minimum? It's not difficult to see that the minimum would be $$m = \left\lceil\frac{\sum_{i=0}^{n}p_i}{l}\right\rceil$$where \$p_i\$ is the length of each pipe and \$l\$ is the standard pipe length. This suggests that once you get to this number \$m\$, the algorithm can stop because no further reduction is possible. It's an optional test, but it could be useful for very large sets.

Consider improving the algorithm

If we test this code with the sequence {9, 9, 7, 1, 1, 3} with a standard length of 10, the program correctly reports that the number of pipes is 3. However, if we rearrange the array and give it {1, 1, 7, 3, 9, 9} it reports 4. Can you see why? If so, try to alter your algorithm to calculate the correct answer no matter what the sequence.

Consider not making a copy of the vector

The cutStock routine currently makes and operates on a copy of the vector, but is that really needed? If the intent is to leave the original vector untouched, it should be declared const; otherwise simply use it without making a copy.

In all, this is a good effort. Welcome to CodeReview!

Answer 2

    while (true) {
int votes = getInteger("Enter required length (-1 to quit): ");
if (votes == -1) break;
requests.add(votes);
    }

Indentation - properly indent your code. You fixed some of it with an edit already, I assume it's correct in your IDE, then? See if your IDE has automatic formatting. Alternatively, some (online) syntax formatters do exist, but they do come with the overhead of copy-pasting code back and forth or otherwise needing to have the program open. Might not be ideal.

int sum = sumOf(subsetPipes), targetIndex = 0; 

For readability, I suggest splitting this up in two lines instead.

int votes = getInteger("Enter required length (-1 to quit): ");

"to quit" might not be the correct term here. How about "to finish input"? I'll admit that's not a really good one either, but "to quit" might be interpreted as "to quit the program". "to stop input" might be a good one. A bit of user interface there.

int stockLength = getInteger("Enter the stock length: ");

If some joker (that'd be me) fills in 0, the program is going to crash, I think. You might want to handle the case where the pipe length is impossible. That is, alter your program to deal with the case where the stock pipe length is smaller than the largest piece requested. (The assignment states that you don't have to check for this.)

You name your "cutting" function (it cuts a pipe to specified lengths, then returns) removeRequestedPipes. That's confusing, because that's not what it does. What it does is cutPipe.

I'd even rename the arguments:

removeRequestedPipes(Vector<int> & reqCopy, int stockLength, Vector<int> & subsetPipes, int index)

becomes

cutPipe(Vector<int> & requestedPipeLengths, int stockPipeLength, Vector<int> & cutPipes, int attemptPipeIndex)

I don't like the cutPipes and attemptPipeIndex names, but that's because you're actually measuring (otherwise you can't swap pipes, you can't "uncut" a pipe). But measurePipe isn't a nice name either. I don't know what a good name might be, someone else might have a nice idea.

Regarding the overall design of your program: You're passing the same parameters around a lot. Wrapping these in some struct or class might be beneficial for the readability of your program.

---

Leaving the restrictions of the assignment aside...

You have to use recursion for the assignment, but the truth is that for this assignment, recursion is just not needed. Iteratively, one version of the algorithm boils down to this:

Get stock pipe length
Get sections asked
Sort asked sections
While we still need to cut sections
    take a stock pipe
    while pipe not gone
        cut it by the largest section possible left in asked sections list
        remove that section from asked sections list
        if no section could be cut
            throw away pipe
        //end if
   //end while
//end while
print pipes needed

Note that as pointed out by Jerry Coffin in the comments, this algorithm is flawed. However, the problem you describe is NP-Complete, which means that without brute-force checking every combination, there's no way to easily solve this problem. As you can see, it doesn't feature recursion, and introducing recursion just complicates the exercise. Recursion is better used when you need to go deeper multiple times per level. That is, if you had to build a robot, and to build a robot you need to build each limb, and to do that you need to build coverings and servos, and so on and so on, you could use recursion for that.

Answer 3

I've found one thing that was left out:

If Vector supports iterators, then the entire body of sumOf():

int sumOf(Vector<int> & subsetPipes) {
    int sum = 0;
    for (int i = 0; i < subsetPipes.size(); i++)
        sum += subsetPipes[i];
    return sum;
}

can be replaced by one call to std::accumulate.

In addition (and entirely unrelated to iterators): since subnetPipes isn't being modified, it should be passed by const&. This will keep it immutable and also prevent an extra copy.

int sumOf(Vector<int> const& subsetPipes) {
    return std::accumulate(subsetPipes.begin(), subsetPipes.end(), 0);
}

(this can still return int since std::accumulates returns a templated type T)