So me and my friend came up with a rather interesting (maybe?) algorithm question but ironically, we are having a hard time solving it. The question goes like this:
There is a sale of precious stones going on in a city of the Rich. Each stone on sale has one or more variants of it. For example, a diamond can be round, Oval, Cushion, etc. Each variant must be counted as a separate stone.
The stones are placed like this (example):
Diamond Ruby Emerald Sapphire
round red colorless
oval green
cushion
This kind of placement prevents forming a perfect 2D array, since the number of types of each stone may vary.
Now rich customers come to buy the stones, and each customer has a set of stones that they like. A customer will be satisfied if they are able to purchase at least one of the stones that they like.
Given the number of customers, number of stones and associated variants, find out whether it is possible to satisfy all customers.
Bonus: If possible, find out the stones purchased by each customer.
Note: Customer preferences cannot be empty, i.e., each customer likes at least one stone.
What I have tried
(For finding out if it is possible to satisfy all customers)
Backtracking:
We have a list of preferences for each customer. So, just assign the first possible stone to the customer (from his/her list) and move on to the next customer. Keep doing it for all customers.
If, for a customer, it is not possible to assign a stone, go to the previous customer and change the assigned stone.
Repeat till at least one stone is assigned for each customer.
If you reach back to the first customer, and assigning no stone can lead to the solution, print "Impossible".
I have following concerns about this algorithm (assuming it is correct):
- It is hard to implement. I encountered too many temporary variables while trying to implement it. (I left it midway).
- It kind of feels like brute force, because I am actually trying every possible combination.
Is this algorithm correct? Can it be made better? Is there an alternative which is easy to implement?