## Daily Coding Problem: Problem #297 [Medium]

This problem was asked by Amazon.

At a popular bar, each customer has a set of favorite drinks, and will happily accept any drink among this set. For example, in the following situation, customer `0`

will be satisfied with drinks `0`

, `1`

, `3`

, or `6`

.

```
preferences = {
0: [0, 1, 3, 6],
1: [1, 4, 7],
2: [2, 4, 7, 5],
3: [3, 2, 5],
4: [5, 8]
}
```

A lazy bartender working at this bar is trying to reduce his effort by limiting the drink recipes he must memorize. Given a dictionary input such as the one above, return the fewest number of drinks he must learn in order to satisfy all customers.

For the input above, the answer would be `2`

, as drinks `1`

and `5`

will satisfy everyone.

### Solution 1

#### Dynamic Programming using Recursion and Memoization

##### Solution written in c++

- First i arrange the given input into recipes and the count of customers interested in each recipe using c++ stl map – which i call cnt. Each recipe form the key of the map, while the count of customers interested in each recipe is assigned as the value for each key.
- Then i call
**Calc_Min_Recipe**function passing two parameters: the map and the size of the given input. - Calc_Min_Recipe is the recursive function. Here, what i want to achieve is find all possible combination of recipe set that satisfy all customers – note that each value of my map represent that set. For instance the given input gives me this map:

```
cnt[0] = 1 //only customer 0 interested in recipe 0
cnt[1] = 2 //only customers 0 and 1 interested in recipe 1
cnt[2] = 2 //only customers 2 and 3 interested in recipe 2
cnt[3] = 2 //only customers 0 and 3 interested in recipe 3
cnt[4] = 2 //only customers 1 and 2 interested in recipe 4
cnt[5] = 3 //only customers 2, 3 and 4 interested in recipe 5
cnt[6] = 1 //only customer 0 interested in recipe 6
cnt[7] = 2 //only customers 1 and 2 interested in recipe 7
cnt[8] = 1 //only customer 4 interested in recipe 4
```

All set sizes discovered must total to the no. of customers (and set elements must not repeat) – for our given input, all set sizes added together must equal 5. Possible combinations are: cnt[1], cnt[2] and cnt[8] i.e values: 2, 2, 1 totals 5 for the set elements (0, 1), (2, 3) and (4); another combination is: cnt[1] and cnt[5] i.e values: 2, 3 totals 5 for the set elements (0, 1) and (2, 3, 4).

```
int Calc_Min_Recipe(map<int, int> &m, int sz){
static map<int, int> memo;//initialize memoization map
//Our base cases//////
if(m.empty()) return 1;//no particular reference, you can make 1 recipe for all custormers
if(memo.count(sz)) return memo[sz];
if(sz == 0) return 0;
if(sz < 0) return sz;
//base cases end here//
int min_recipe = sz;//initialize to this incase every customers preference is unique
for(auto x: m){
int bal = sz - x.second;
int result = Calc_Min_Recipe(m, bal);
memo[bal] = result;//store result in memo map (used for memoization)
int curr_min_recipe = result;
if(curr_min_recipe >= 0) curr_min_recipe += 1;
if(curr_min_recipe >= 0 && curr_min_recipe < min_recipe){
min_recipe = curr_min_recipe;
}
}
return min_recipe;
}
int Lazy_bartender(vector<vector<int>> &pref){
map<int, int> cnt;
int n = pref.size();
/*This block of code arranges preferences into
count of customers which each recipe satisfies*/
for(int r=0;r<pref.size();r++){
for(int c=0;c<pref[r].size();c++){
cnt[pref[r][c]]++;
}
}
int res = Calc_Min_Recipe(cnt, n);
return res;
}
int main(){
vector<vector<int>> preferences = {//returns 2
{0, 1, 3, 6},
{1, 4, 7},
{2, 4, 7, 5},
{3, 2, 5},
{5, 8}
};
/*vector<vector<int>> preferences = {//returns 1
{0, 1},
{1}
};*/
/*vector<vector<int>> preferences = {//returns 2
{5, 3},
{5, 4},
{5, 4},
{5, 4},
{5, 3},
{6, 4},
{7, 3}
};*/
/*vector<vector<int>> preferences = {//same preferences - returns 1
{5, 3, 4, 6, 7},
{5, 3, 4, 6, 7},
{5, 3, 4, 6, 7},
{5, 3, 4, 6, 7},
{5, 3, 4, 6, 7},
{5, 3, 4, 6, 7},
{5, 3, 4, 6, 7}
};*/
/*vector<vector<int>> preferences = {//unique preferences - returns 5
{5},
{3},
{4},
{6},
{7}
};*/
/*vector<vector<int>> preferences = {//no preferences - returns 1
{},
{},
{},
{},
{}
};*/
int result = Lazy_bartender(preferences);
cout<<"The minimum recipe required is : "<<result;
return 0;
}
```

For our given input, the answer is 2 i.e cnt[1] and cnt[5]; values: 2, 3 with the set elements (0, 1) and (2, 3, 4).

### Solution 2

##### Solution written in c++

- Start by arranging customer preferences into recipes and customers which each recipe satisfies using a map.
- Get map key/value pair with the maximum value repeatedly – this is the recipe with the maximum customers preference.
- In each pass, skip, if a customer from the previous max set belongs to new max set
- Otherwise, increment count of minimum_recipe required because you just found a recipe satisfying most customers
- Keep track of what i call final_max in each pass. Once final_max equals the input size, a set of recipe satisfying all customers has been found.

```
bool does_cust_belong_to_prev_recipe_set(int c, vector<int> &old_set){
if(old_set.size() == 0) return false;//base case
for(int x: old_set){//go through old_set and compare with c
if(c == x){
return true;
}
}
return false;
}
int Lazy_bartender(vector<vector<int>> &pref){
map<int, int> recipes;
map<int, vector<int>> recipe_satisfies;
map<int, int> cnt;
vector<int> v;
vector<int> cust_bal;
int result = 0;
priority_queue<int> q;
/*This block of code arranges preferences into
recipes and the customers which each recipe satisfies*/
for(int r=0;r<pref.size();r++){
for(int c=0;c<pref[r].size();c++){
if(recipes.count(pref[r][c])){//if recipe exist
v = recipe_satisfies[pref[r][c]];
v.push_back(r);
recipe_satisfies[pref[r][c]] = v;
//increment cnt of customers to each recipe
cnt[pref[r][c]]++;
}else{//recipe does not exist
recipes[pref[r][c]] = 1;
v = recipe_satisfies[pref[r][c]];
v.push_back(r);
recipe_satisfies[pref[r][c]] = v;
//increment cnt of customers to each recipe
cnt[pref[r][c]]++;
}
}
}
if(cnt.empty()) return 1;//no particular reference, you can make 1 recipe for all custormers
int max = 0;
int recipe_max_cust;
int recipe_max_cust_old = -1;
bool res = false;
vector<int> c_old;
static int final_max;
map<int, int> cnt_left;
while(!cnt.empty()){//as far as map is not empty
for(auto x: cnt){//get recipe set with max customers
if(x.second > max){
max = x.second;
recipe_max_cust = x.first;
}
}
//skip, if a customer from the previous max set belongs to new max set
for(auto c: recipe_satisfies[recipe_max_cust]){
if(recipe_satisfies.count(recipe_max_cust_old)){//if key exist
c_old = recipe_satisfies[recipe_max_cust_old];
}
res = does_cust_belong_to_prev_recipe_set(c, c_old);
if(res == true){
cnt_left[recipe_max_cust] = cnt[recipe_max_cust];
break;
}
}
if(res == true){
cnt.erase(recipe_max_cust);//delete key that has been considered
max = 0;//reset max
continue;//don't consider this set
}
//otherwise, recipe satisfying most customers has been found, increment count of minimum_recipe required
if(recipe_max_cust_old == -1){
recipe_max_cust_old = recipe_max_cust;
}
//increment result by 1
result += 1;
final_max += max;
if(final_max == pref.size()){//A set of recipe satisfying all customers has been found
//reset all variables
cnt = cnt_left;//reset cnt
//reset cnt_left (by deleting all items in the map)
cnt_left.clear();
final_max = 0;
c_old = {};
max = 0;//reset max
recipe_max_cust_old = -1;//reset
q.push(-result);//store result for the completed set of minimum recipe that bartender has to learn
result = 0;
//recipe mix is completed for 1 set - see if you can get another set
continue;
}
cnt.erase(recipe_max_cust);//delete key that has been considered
max = 0;//reset max
//recipe_satisfies(recipe_satisfies);
}
result = abs(q.top());//get set count with the minimum - this is the minimum recipe mix that bartender has to learn to satisfy every customer
return result;
}
```