Stock Pipe Cutting using Recursion

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): ");
}
}

/* 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) {
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;
}

-
You edited your question once, altering the code. Whilst doing so whilst there are no answers yet is acceptable, keep in mind that everything about the code is up for review. That is your indentation, your comments, your naming, algorithm, solution, the way you split things in functions... literally everything. Even blank space. So try to keep code edits to a minimum, if possible. – Pimgd Aug 5 '14 at 10:04
Hi thank you letting me know. I should have been mindful of the formatting especially. I guess copying and pasting from a properly formatted code in emacs24 doesn't translate the same here. Thanks for pointing that out, I shall be more careful of that in the future. – rdsarna Aug 5 '14 at 10:11
@rdsarna This could be an indication that you've improperly mixed spaces and tabs in your indentation. StackExchange will normalise tabs to four spaces. – Schism Aug 5 '14 at 19:20

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!

-
Hi Edward, thank you for the encouraging words. And a big thank you for going through the code and giving feedback on it. I shall try and make the changes you have suggested. But I'm a little confused about "Consider bounding the problem". What would the formula be used for and how would it be implemented? For example, for the sequence {10, 10, 6, 5, 7, 4} and stockLength 10, the formula gives m = 4.2 but the minimum required pipes would be 5. I hope this isn't an obvious thing that I'm missing completely :) – rdsarna Aug 5 '14 at 13:48
@rdsama: Note that the equation uses the ceiling function, so 4.2 becomes 5. It would be used for an "early bailout". If, at any point, you have calculated that number of pipes, your algorithm has completed and can stop right there. – Edward Aug 5 '14 at 13:52
Ok, got it. I haven't come across the ceiling function before. So, using this formula would always give the answer required by the assignment! The problem doesn't ask to return or display the optimum subsets. – rdsarna Aug 5 '14 at 14:00
@rdsarna: It only calculates a lower bound, not the actual value. For instance, consider {4, 4, 4, 4, 4} with stockLength = 5. The lower bound would be 4 but the correct answer is actually 5. – Edward Aug 5 '14 at 14:05
Ah! Right, now it clicked with me. Thanks a lot. – rdsarna Aug 5 '14 at 14:07
    while (true) {
int votes = getInteger("Enter required length (-1 to quit): ");
}


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;


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
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.

-
It's not within the scope of CodeReview to criticise the decision to use recursion. This is given by the assignment. Sure you may mention, that an iterative approach is possible, but please refrain from criticising the recursivity. This is nothing OP can help and completely unconstructive. – Vogel612 Aug 5 '14 at 11:06
It's a minor point, but there are many programmers who don't use an IDE. – Edward Aug 5 '14 at 14:07
@Edward how about an online beautifier? – Pimgd Aug 5 '14 at 14:14
@Pimgd: No online beautifier needed here. I use an editor as do some other people whose names you may have heard. – Edward Aug 5 '14 at 14:21
@JerryCoffin I see. Seems I made a mistake, then. However, this problem seems to be NP-Complete, since it's an array of Knapsack problems. So I'm not too worried about the solution being wrong. – Pimgd Aug 6 '14 at 7:08

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)

-
That's reasonable, but it assumes that the non-standard Vector class used in this program supports iterators. – Edward Aug 5 '14 at 17:19
@Edward: And I was wondering why the OP was using a non-standard one. Perhaps it's still good for general advice. – Jamal Aug 5 '14 at 17:21
@Jamal I do not think the Vector class supports std::accumulate but its a helpful tip that I shall keep in mind when working with standard data structures (wherever it is applicable). Btw, I found a solution to this problem online. But I do not understand it completely. Can I post that solution here as an answer in order to have a discussion about it? Or is this the wrong forum for that? – rdsarna Aug 6 '14 at 14:04
@rdsarna: No, it would not belong here. It would belong on Stack Overflow, though. – Jamal Aug 6 '14 at 15:23