I have done an exercise on SPOJ to practice advanced algorithms.
The Problem Statement is as follows:
Harish went to a supermarket to buy exactly ‘k’ kilograms apples for his ‘n’ friends. The supermarket was really weird. The pricing of items was very different. He went to the Apples section and enquired about the prices. The salesman gave him a card in which he found that the prices of apples were not per kg. The apples were packed into covers, each containing ‘x’ kg of apples, x > 0 and ‘x’ is an integer. An ‘x’ kg packet would be valued at ‘y’ rupees. So, the placard contained a table with an entry ‘y’ denoting the price of an ‘x’ kg packet. If ‘y’ is -1 it means that the corresponding packet is not available. Now as apples are available only in packets, he decides to buy at most ‘n’ packets for his ‘n’ friends i.e he will not buy more than n packets of apples. Harish likes his friends a lot and so he does not want to disappoint his friends. So now, he will tell you how many friends he has and you have to tell him the minimum amount of money he has to spend for his friends.
This is the code I used to solve the problem:
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::cin;
using std::vector;
using std::endl;
int MinValueOf(int a, int b)
{
return (a < b) ? a : b;
}
int BuyingApple(vector<int> PriceaTag, int Friends, int KilogramsToBuy)
{
vector<vector<int>> Table(Friends + 1, vector<int>(KilogramsToBuy + 1, 0));
for(int i = 1; i <= Friends; i++)
{
for(int j = 0; j <= i; j++)
{
Table[i][j] = INT32_MAX;
if(j == 0)
Table[i][0] = 0;
else if(PriceaTag[j] > 0)
Table[i][j] = MinValueOf(Table[i][j], Table[i - 1][i - j] + PriceaTag[j]);
}
}
return (Table[Friends][KilogramsToBuy] == 0) ? -1 : Table[Friends][KilogramsToBuy];
}
int main()
{
vector<int> Price;
int Friends, Kilogram, t;
cin >> t;
for(int i = 0; i < t; i++)
{
cin >> Friends >> Kilogram;
vector<int> Price(Kilogram + 1, 0);
for(int i = 1; i <= Kilogram; i++)
{
cin >> Price[i];
}
cout << BuyingApple(Price, Friends, Price.size() - 1) << endl;
}
return 0;
}
I/O of the code is as follows:
The first line of input will contain the number of test cases, C. Each test case will contain two lines. The first line containing N and K, the number of friends he has and the amount of Apples in kilograms which he should buy. The second line contains K space separated integers in which the ith integer specifies the price of a 'i' kg apple packet. A value of -1 denotes that the corresponding packet is unavailable.
The output for each test case should be a single line containing the minimum amount of money he has to spend for his friends. Print -1 if it is not possible for him to satisfy his friends.
Constraints:
0 < N <= 100
0 < K <= 100
0 < price <= 1000
But as I submitted my code, I received a message SIGABRT runtime error although my code ran smoothly in both Windows compiler (G++ 14) and Linux Compiler (G++ Clang 9). I have tried to debug but I failed. What might be wrong?
Since this is a SPOJ question, and you're not given the test data, what you should do is to randomize the tests until you get a failure. That way, you may be able to get a sample case that fails. This is called fuzzing, and is a technique that can be used in your question.
The following will work for the cases that cause segmentation faults, and in some cases, to verify if a given output matches the expected output. In other words, instead of trying to figure out the test data, let the computer generate the tests for you.
The way you do this is to look at the constraints that the question gives you, and generate random data that fits the constraints. Since they are all integers, you can do this by using the <random> header, and using a uniform_int_distribution.
Here is a sample of fuzzing the data using the following constraints for N, K, and the data for prices:
Constraints:
0 < N <= 100
0 < K <= 100
0 < price <= 1000
OK, so given this information, we can take your exact code, remove the cin statements, and replace everything with randomized data that fit the constraints. In addition, we can test for an out-of-bounds access if we use at() to access the vectors in the function that causes the issue.
Given all of this information we can start with changing main to produce random data that fit the constraints of the question:
#include <random>
#include <algorithm>
#include <vector>
//...
int main()
{
// random number generator
std::random_device rd;
std::mt19937 gen(rd());
// Prices will be distributed from -1 to 1000
std::uniform_int_distribution<> distrib(-1, 1000);
// N and K are distributed between 1 and 100
std::uniform_int_distribution<> distribNK(1, 100);
// This one will be used if we need to replace 0 in the Price vector with
// a good value
std::uniform_int_distribution<> distribPos(1, 1000);
// our variables
int Friends;
int Kilogram;
vector<int> Price;
// we will keep going until we see an out-of-range failure
while (true)
{
try
{
// generate random N and K values
Friends = distribNK(gen);
Kilogram = distribNK(gen);
// Set up the Price vector
Price = std::vector<int>(Kilogram + 1, 0);
// Generate all the prices
std::generate(Price.begin() + 1, Price.end(), [&]() { return distrib(gen); });
// Make sure we get rid of any 0 prices and replace them with a random value
std::transform(Price.begin() + 1, Price.end(), Price.begin() + 1, [&](int n)
{ if (n == 0) return distribPos(gen); return n; });
// Now test the function
std::cout << BuyingApple(Price, Friends, Price.size() - 1) << std::endl;
}
catch (std::out_of_range& rError)
{
std::cout << rError.what() << "\n";
std::cout << "The following tests cause an issue:\n\n";
// The following tests cause an issue with an out-of-range. See the data
std::cout << "Friends = " << Friends << "\nK = " << Kilogram << "\nPrice data:\n";
int i = 0;
for (auto p : Price)
{
std::cout << "[" << i << "]: " << p << "\n";
++i;
}
return 0;
}
}
}
Given all of this, we can change the BuyingApple function by replacing [ ] with at():
int BuyingApple(vector<int> PriceaTag, int Friends, int KilogramsToBuy)
{
vector<vector<int>> Table(Friends + 1, vector<int>(KilogramsToBuy + 1, 0));
for (int i = 1; i <= Friends; i++)
{
for (int j = 0; j <= i; j++)
{
Table.at(i).at(j) = INT32_MAX;
if (j == 0)
Table[i][0] = 0;
else if (PriceaTag[j] > 0)
Table[i][j] = MinValueOf(Table[i][j], Table.at(i - 1).at(i - j) + PriceaTag.at(j));
}
}
return (Table[Friends][KilogramsToBuy] == 0) ? -1 : Table[Friends][KilogramsToBuy];
}
Now we have an automatic case generator, and will catch and display any cases that could cause an issue with the vectors. Note that we keep looping forever until we get a test case that "crashes". We then output the crashed case and can now use those values to debug the issue.
We used std::generate and std::transform as an illustration of how to populate a vector (or any sequence container your test uses), and how to specialize the test (like making sure that Price has no 0 values). Another SPOJ question may need other specializations, but hopefully you get the basic idea.
Here is a Live Example.
We see that a test case caused an out-of-range exception to be thrown. The main function has a try/catch to process this error, and we can see the data that caused the issue.
So it seems that if we have more friends than apples, the issue occurs where we go out-of-bounds. I will not attempt to fix the issue, but you now have a test case where the input fails.
In general, you can use this technique with many, if not most of the "online judge" sites if the site doesn't show you failing test cases.
Edit:
Updated the lambda in the std::transform to only replace 0 in the Price vector.
Edit: Here is a random string fuzzer that can produce fuzzed string data.
You can control the number of strings, the minimum and maximum size of each string, and the alphabet of characters that will be used when generating each string.
#include <random>
#include <string>
#include <vector>
#include <iostream>
struct StringFuzzer
{
unsigned int maxStrings; // number of strings to produce
unsigned int minSize; // minimum size of a string
unsigned int maxSize; // maximum size of the string
bool fixedSize; // Use fixed size of strings or random
std::string alphabet; // string alphabet/dictionary to use
public:
StringFuzzer() : maxStrings(10), minSize(0), maxSize(10), fixedSize(true), alphabet("abcdefghijklmnopqrstuvwxyz")
{}
StringFuzzer& setMaxStrings(unsigned int val) { maxStrings = val; return *this; };
StringFuzzer& setMinSize(unsigned int val) { minSize = val; return *this; };
StringFuzzer& setMaxSize(unsigned int val) { maxSize = val; return *this; };
StringFuzzer& setAlphabet(const std::string& val) { alphabet = val; return *this; };
StringFuzzer& setFixedSize(bool fixedsize) { fixedSize = fixedsize; return *this; }
std::vector<std::string> getFuzzData() const
{
// random number generator
std::random_device rd;
std::mt19937 gen(rd());
// Number of strings produced will be between 1 and maxStrings
std::uniform_int_distribution<> distribStrings(1, maxStrings);
// string size will be distributed between min and max sizes
std::uniform_int_distribution<> distribMinMax(minSize, maxSize);
// Picks letter from dictionary
std::uniform_int_distribution<> distribPos(0, alphabet.size() - 1);
std::vector<std::string> ret;
// generate random number of strings
unsigned int numStrings = maxStrings;
if ( !fixedSize)
numStrings = distribStrings(gen);
ret.resize(numStrings);
for (unsigned int i = 0; i < numStrings; ++i)
{
std::string& backStr = ret[i];
// Generate size of string
unsigned strSize = distribMinMax(gen);
for (unsigned j = 0; j < strSize; ++j)
{
// generate each character and append to string
unsigned pickVal = distribPos(gen);
backStr += alphabet[pickVal];
}
}
return ret;
}
};
int main()
{
StringFuzzer info;
auto v = info.getFuzzData(); // produces a vector of strings, ready to be used in tests
info.setAlphabet("ABCDEFG").setMinSize(1); // alphabet consists only of these characters, and we will not have any empty strings
v = info.getFuzzData(); // now should be a vector of random strings with "ABCDEFG" characters
for (auto s : v)
std::cout << s << "\n";
}