There are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get at least one dish of his choice. What is the minimum number of different type of dishes we can order? Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row. n = 6 k = 7 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 Output 3 Explanation Take dish number 5,6,7.
Update the dishes array with the input vector.
N(i) = (N(i) << 1) | V(i)
void updateDishes(vector<string> list, int **dishes)
{
int index = 0;
for (vector<string>::const_iterator i = list.begin(); i != list.end(); ++i)
{
*((*dishes)+index) = (*((*dishes)+index) << 1) | (stoi(*i) & 0x1);
index++;
}
}
Read the input file and update the dishes array.
int *CreateArrayFromFile(string filename, int &totalDishes, int &totalPersons)
{
int *num = NULL;
string line;
string buf;
ifstream inFile(filename);
// Read line by line for processing
while ( getline (inFile, line) )
{
// Tokenize the line
stringstream ss(line);
vector<string> tokens;
// Store all the tokens in a vector
while (ss >> buf)
tokens.push_back(buf);
// Allocate the memory for the dishes array
if (NULL == num)
{
totalDishes = tokens.size();
num = new int[totalDishes]();
#ifdef DEBUG
for (int i=0; i<tokens.size(); i++)
cout << i << ": " << num[i] << endl;
#endif
}
// Update the dishes array with person's like/dislike
updateDishes(tokens, &num);
#ifdef DEBUG
for (int i=0; i<tokens.size(); i++)
cout << i << ": " << num[i] << endl;
printVector(tokens);
#endif
totalPersons++;
}
// Return the updates dishes array
return num;
}
This counts the numbers of bits set in a given numbers. Its a very silly way of counting bits set :(
int getOnesCount(int num)
{
int count = 0;
while(num)
{
count = count + (num & 0x1);
num = num >> 1;
}
return count;
}
It interartes over the range (1..2^n) where n is the total number of dishes and create sets which holds the same number of bits set. This data will be used to find all the possible combinations of the same number of bits set in the range.
void getCombinations(vector < vector <int> > &combinations, int totalDishes, int totalPersons)
{
// Place holders for all the sets
for (int i=0; i<totalDishes; i++)
{
combinations.push_back(vector <int>());
}
// Update the sets
int end = (1 << totalDishes);
for (int i=1; i<end; i++)
{
combinations[getOnesCount(i)-1].push_back(i);
}
#ifdef DEBUG
for (int i=0; i<combinations.size(); i++)
{
cout << "Vector " << i+1 << " : " ;
for (vector<int>::iterator it = combinations[i].begin(); it != combinations[i].end(); ++it)
{
cout << *it << " ";
}
cout << endl;
}
cout << endl;
#endif
}
Checks if the given combination (bits set in the given num) satisfies all the persons.
bool doesSatisfy(int *dishes, int num, int totalPersons)
{
int satisfy = (1 << totalPersons) - 1;
int result = 0;
int index = 0;
bool retval = false;
while (num)
{
if (num & 0x1)
result = result | *(dishes+index);
index++;
num = num >> 1;
}
if(result == satisfy)
retval = true;
return retval;
}
This is our main function.
int findMinDishCount(int *dishes, int totalDishes, int totalPersons)
{
int start = 0;
int end = totalDishes - 1;
int index = (int) ((end - start) / 2);
int retval = -1;
// Get the combinations with respect to the number of bits set
vector < vector <int> > combinations;
getCombinations(combinations, totalDishes, totalPersons);
/*
* Here we are using binary search tree traversal to select the numbers of dishes to
* satisfy all the persons likes.
*/
while (start != end)
{
#ifdef DEBUG
cout << "[Start:" << start << "] [End:" << end << "]" << endl;
#endif
index = (int) (start + ((end - start) / 2));
bool foundMatch = false;
for (vector<int>::iterator it = combinations[index].begin(); it != combinations[index].end(); ++it)
{
#ifdef DEBUG
cout << "[" << index << "] (" << *it << ") ";
#endif
if (doesSatisfy(dishes, *it, totalPersons) == true)
{
foundMatch = true;
retval = index;
#ifdef DEBUG
cout << "true" << endl;
#endif
// If the combination satisfies all the persons likes, We do not need to check
// with other combinations from the same set
break;
}
#ifdef DEBUG
cout << "false" << endl;
#endif
}
if (foundMatch == true)
{
end = index;
}
else
{
if (start == end-1)
{
if (end == totalDishes - 1 && doesSatisfy(dishes, combinations[end][0], totalPersons) == true)
{
retval = end;
}
break;
}
start = index;
}
}
return retval + 1;
}
Here is the helper/wrapper function.
int main(int argc, char **argv)
{
int totalDishes = 0;
int totalPersons = 0;
int *dishes = NULL;
cout << "Filename: " << argv[1] << endl;
dishes = CreateArrayFromFile(argv[1], totalDishes, totalPersons);
cout << "Total Dishes: " << totalDishes << endl;
cout << "Total Persons: " << totalPersons << endl;
cout << endl;
printLikesDislikes(dishes, totalDishes, totalPersons);
cout << endl;
int minDishes = findMinDishCount(dishes, totalDishes, totalPersons);
cout << "Minimun dishes to statisfy everyone: " << minDishes <<endl;
return 0;
}
Supportive hearders.
#include <iostream> #include <fstream> #include <string> #include <sstream> #include <vector> using namespace std;These functions will be used to get the output in verbose mode.This will be useful in debugging.
void printVector(vector<string> list)
{
for (vector<string>::const_iterator i = list.begin(); i != list.end(); ++i)
{
cout << "[" << *i << "] ";
}
cout << endl;
}
void printLikesDislikes(int *dishes, int totalDishes, int totalPersons)
{
string heading = "------------";
cout << "Dishes : ";
for (int j=1; j<=totalDishes; j++)
{
cout << j << " ";
heading = heading + "--";
}
cout << endl << heading << endl;
for (int i=totalPersons-1; i>=0; i--)
{
string likeDislike = "";
for (int j=0; j<totalDishes; j++)
{
int pos = 1 << i;
likeDislike = likeDislike + " " + ((pos & *(dishes+j)) == 0 ? "0" : "1");
}
cout << "Person " << totalPersons - i << " : " << likeDislike << endl;
}
}
