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; } }