How to solve Lazy bartender problem : A Complete Algorithm with Code
Problem statement:
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.
Examples:
Input Type:
argument 1:
2D Array where each row number represents the unique customer and each row values represent the drinks that satisfies the corresponding customer
argument 2:
number of drinks
argument 3:
number of customers.
Output Type : An integer value which represents the fewest number of drinks that satisfy all the customers.
Input:
{
{0,1,3,6},
{1,4,7},
{2,4,7,5},
{3,2,5},
{5,8}
}
,9, 5
Output : 2
Algorithm:
a) Create a 2D array named ar with size m*(n+1) where m represents the number of drinks and n represents the number of customers.
b) Each row index indicates the number/id of the drinks and each column index indicates the number/id of the customer.
c) Fill the newly created array with the value 1 wherever there is a combination of drink and customer.
d) For example, as seen from the input, customer 0 is satisfied by the drinks 0,1,3,6 so we set the value of arr[0][0], arr[1][0],
arr[3][0], arr[6][0] as 1.
e) The extra column we created in the array arr which is named as sum is used to store the number of customers that each drink satisfies.
f) For example, arr[0][n+1] stores the number of customers satisfied by drink 0 which is 1. Similarly arr[1][n+1] represents
the number of customers satisfied by drink 1 which is 2.
g) Traverse through the last column of the array arr and find the maximum value and its corresponding row index.
h) The maximum value is 3 and its row index is 5.
i) The row index from the above step represents the drink number which satisfies the maximum number of customers.
j) We increase the count variable to one as we found one drink which is numbered 5 that can satisfies a total of 3 customers
named 2,3,4.
k) Here is the tricky part. We still have to find out other drinks which can satisfy remaining two customers 0 and 1.
l) So we eliminate the row indexed 5 and the columns indexed 2, 3, 4 in the array arr. Because we have already taken these drink and customers into account.
m) Calculate the values of last column again with the rows and columns left over from the above step.
n) Here we go, we repeat the same procedure from step g to step m until the number of customers left out is zero.
Note: Technically to emulate the removal of rows and columns follow the procedure below.
a) We traverse through the row which has maximum customers that is index 5.(which we found from step g).
b) If you encounter the value 1, then pause the row traverse and start traversing through the column.
c) For example while traversing through the row indexed 5 the value of arr[5][2] is 1. So Pause the row traverse and start traversing
through the column. i.e. from arr[0][2] to arr[m][2].
d) While traversing through column if you find the value 1 then make it zero and reduce the value in the last column by 1 in the same row. For example the values of arr[2][2],arr[4][2],arr[5][2],arr[7][2] are 1. So make them as 0 and and reduce the values arr[2][n+1], arr[4][n+1],arr[5][n+1],arr[7][n+1] by 1.
e) And finally resume the row traverse from step b and follow the procedure until the end of the row.
CODE (JAVA):
