Code:
#include <iostream>
#include "console.h"
#include "vector.h"
#include "simpio.h"
using namespace std;
//constants
const int STOCK_PIPE_LENGTH = 10;
//prototypes
int cutStock(Vector<int> &requests);
void recursiveCut(Vector<int> &requests, Vector<int> remainingPipes, Vector<int> &answers);
/*
* The main function creates a Vector<int> called requests that represents the list of
* pipe lengths needed. The getInteger() function is used to get this list from the user.
* The user repreatedly enters lengths, prompted by the message "Enter pipe length: ".
* To signal the end of input, the user enters any value equal to or less than 0, or greater
* than the length of the constant STOCK_PIPE_LENGTH. The program cannot accomodate lengths
* greater than STOCK_PIPE_LENGTH.
*
* int main() then outputs to the console the minimum number of pipes of length STOCK_PIPE_LENGTH
* needed to accomodate the list of lengths provided by the user, represented by the
* Vector<int> requests. For example, assuming STOCK_PIPE_LENGTH is equal to 10, and the user has
* given the values 2 and 8, the program should output the answer 1, as one stock pipe of length
* 10 can be cut into lengths 2 and 8. If the user entered 6, 6, and 6, the program should
* output the answer 3. If the user entered 3, 3, 3, and 3, the answer would be 2.
*
* This is all assuming the function cutStock(Vector<int> &requests) will successfully return
* the correct answer.
*/
int main() {
int x = 0;
Vector<int> requests;
while (true) {
while (true) {
x = getInteger("Enter pipe length: ");
if (x <= 0) break;
requests.add(x);
}
if (requests.size() <= 0) break;
cout << cutStock(requests) << " stock pipes needed." << endl;
requests.clear();
}
return 0;
}
/*
* Function: int cutStock(Vector<int> &requests)
* ---------------------------------------------
* This function should return the smallest number of stock pipes of length STOCK_PIPE_LENGTH
* needed to accomodate a list of lengths requested by the user. This list is represented by
* the Vector<int> requests, passed by reference as a parameter when the function is called.
*
* The function begins by creating two new Vector<int> objects, Vector<int> remainingPipes
* and Vector<int> answers.
*
* Vector<int> remainingPipes will be used to represent all of the pipes from which a request
* can be cut. A pipe used in this way will have its length reduced by the ammount of the
* request it is being used to fill. A pipe in remainingPipes will not be used unless its
* length is greater than or equal to the length of the request. Thus, an element of
* remainingPipes can never be a negative number. If a pipe is reduced to length 0, it is
* still kept, as it is part of the answer.
*
* Vector<int> answers will be used to store a list of the number of pipes used in any
* possible strategy of cutting from and adding to the pipes in remainingPipes. Assuming
* the function recursiveCut() works as intended, the answer to the problem is simply
* the lowest number in answers. While a Set<int> object would be more appropriate in
* this role, I have chosen to use a Vector<int> object so that readers of this code will
* not need to be bothered to consider yet another type from an unfamiliar library.
*
* cutStock(Vector<int> &requests) therefore has three steps in its operation.
*
* 1. create the two new Vector<int> objects.
*
* 2. call the recursive function recursiveCut(), passing as parameters the Vector<int> requests
* object, as well as the empty Vector<int> objects remainingPipes and answers. requests and
* answers are passed by reference, while remainingPipes is not.
*
* 3. find the lowest element of the Vector<int> answers, and return it.
*/
int cutStock(Vector<int> &requests) {
int result = -1;
Vector<int> remainingPipes;
Vector<int> answers;
recursiveCut(requests, remainingPipes, answers);
for (int i = 0; i < answers.size(); i++) {
if (answers[i] < result || result == -1) {
result = answers[i];
}
}
return result;
}
/*
* Function: recursiveCut(Vector<int> &requests, Vector<int> remainingPipes, Vector<int> &answers)
* ------------------------
* This function is where the work is done in this program. It takes as its paramenters
* three Vector<int> objects.
*
* Vector<int> requests represents the list if lengths input by the user.
* Vector<int> remainingPipes represents the list of pipes to be added to or cut from.
* Vector<int> answers represents a list of the number of pipes used in any combination
* of cutting and adding to remainingPipes.
*
* This is a recursive function. The simple case occurs when the size of Vector<int> requests
* is equal to 0.
*
* The function starts with a for loop that will, at each iteration, remove a single element
* from requests and store its value in a variable:
*
* int currentRequest
*
* This value is processed and then plugged back into the Vector<int> object at the same place
* from which it was removed. This is done for each element in the Vector<int> requests object.
*
* In a single iteration of this for loop, the idea is this:
* Start by getting the value, storing it in currentRequest, and removing it from the vector.
*
* From here, there are two possibilities.
*
* One possibility is that the ideal answer involves cutting this
* length from a pipe already contained in the Vector<int> remainingPipes, which represents
* the list of pipes already in use, and their current lengths. To this end, the nested for
* loop using int j as its index variable will cycle through each element of remainingPipes.
* If the current element of remainingPipes is greater than or equal to the length of
* the currentRequest (if (remainingPipes[j] >= currentRequest)) then the length of
* currentRequest is subtracted from that element of remainingPipes, and the function
* recursiveCut calls itself recursively, in this new configuration. In this new call,
* requests now has one less element than it did on the original call, remainingPipes contains
* an element from which has been subtracted the length of the request that no longer exists
* in requests, and everything is just generally awesome and everyone is having a great time.
*
* After this recursive call, the length of currentRequest is added back to the element of
* remainingPipes from which it was subtracted, and the for loop moves on to the next element
* of remainingPipes. Note that if remainingPipes has 0 elements, this for loop is effectively
* skipped entirely.
*
* After this for loop completes, it is time to check for the other possibility, which is:
* The ideal answer involves cutting the length of currentRequest from a brand new pipe instead
* of a pipe already contained in remainingPipes. All new pipes will be of length STOCK_PIPE_LENGTH,
* so to make this happen we just create a new pipe of length STOCK_PIPE_LENGTH - currentRequest.
*
* int newPipe = STOCK_PIPE_LENGTH - currentRequest
*
* This element is then added to the Vector<int> remainingPipes, and the function calls itself
* recursively in this new configuration. In this new call, Vector<int> requests has one less
* element than it did in the original call, and remainingPipes has one new element added it,
* of length STOCK_PIPE_LENGTH minus the length of the element that was removed from requests
* in the previous call.
* After this recursive call is complete, the new element that was added to remainingPipes
* is then removed. (remaining.remove(remaining.size() - 1))
*
* The simple case occurs when requests has no more elements (if (requests.size() <= 0))
* In this case, the idea is to simply take the number of elements in remainingPipes (including,
* of course, elements whose length is 0, as this is simply another pipe that has been used and
* must have been purchased), and add this number as a new element to the Vector<int> answers.
*
* In this way, every possible way of cutting from and adding new pipes to remainingPipes to
* cover all elements of requests will have been searched, and the Vector<int> answers will
* contain as its elements the number of pipes of length STOCK_PIPE_LENGTH that were needed
* in each configuration. Thus, after the first call of recursiveCut() as called by the
* function cutStock() has completed, the program only needs to take the lowest number contained
* in the Vector<int> answers and return this number as the solution to the problem, the least
* number of pipes of length STOCK_PIPE_LENGTH needed to fill the set of requests represented
* by the Vector<int> requests.
*/
void recursiveCut(Vector<int> &requests, Vector<int> remainingPipes, Vector<int> &answers) {
if (requests.size() <= 0) {
answers.add(remainingPipes.size());
return;
}
for (int z = requests.size() - 1; z >= 0; z--) {
int currentRequest = requests[z];
requests.remove(z);
for (int j = remainingPipes.size() - 1; j >= 0; j--) {
if (remainingPipes[j] >= currentRequest) {
if (requests.size() <= 0) {
answers.add(remainingPipes.size());
} else {
remainingPipes[j] -= currentRequest;
recursiveCut(requests, remainingPipes, answers);
remainingPipes[j] += currentRequest;
}
}
}
int newPipe = STOCK_PIPE_LENGTH - currentRequest;
remainingPipes.add(newPipe);
recursiveCut(requests, remainingPipes, answers);
remainingPipes.remove(remainingPipes.size() - 1);
requests.insert(z, currentRequest);
}
}