imarunpaul
BAN USER```
# Lazy Bar tenderer code
# A bar has m type of drinks and has n customers having
# their personal preference of drinks known
# This is represented by a 2D array represented
# as the rows represent each customer and columns as their preferred drinks type
# We have a lazy bar tenderer who would like to make(or even learn) the least number of
# drinks so as to serve the customers their choice of drinks
# we have the array, m the number of drink types, and n the number of customers as the input
# we as supposed to give the least count of drinks the bar tenderer needs to make as 'count'
#
# Sample input
array = [
[0, 1, 3, 6],
[1, 4, 7],
[2, 4, 7, 5],
[3, 2, 5],
[5, 8]
]
n = 5
m = 9
# Sample output should be count = 2 (the drink number 5 and 1)
#
# We will make an array of m rows each representing the drink type number
# and n+1 columns where n columns are for customers with preference represented as
# binary value either 0 or 1
# and the +1 column for the sum of preferences for each drink row
#
# The arr for sample input is
#
# 0 1 2 3 4 Sum
#
# 0 1 0 0 0 0 1
# 1 1 1 0 0 0 2
# 2 0 0 1 1 0 2
# 3 1 0 0 1 0 2
# 4 0 1 1 0 0 2
# 5 0 0 1 1 1 3
# 6 1 0 0 0 0 1
# 7 0 1 1 0 0 2
# 8 0 0 0 0 1 1
#
# We will find the max value of sum ie the most preferred drink, so naturally the bar tenderer
# needs to know how to make it
# So we can eliminate the drink with the customers whom we can serve with the drink
# Now just increment the count variable count++
# and shortlist the array as below
#
# 0 1 Sum
#
# 0 1 0 1
# 1 1 1 2
# 2 0 0 0
# 3 1 0 1
# 4 0 1 1
# 6 1 0 1
# 7 0 1 1
# 8 0 0 0
#
# Now you may need to select the drink with maxim preference and
# go on...until all of the customers are served
# ie, till the array is empty or customers left is zero
# For the example thats it ... all are served with the two drinks, drinks 5 and 1
# Now lets go to the codes for that....
#
# The method to find the least number of drinks
def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end
```
- imarunpaul August 05, 2020