3

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?

  • 1
    You can probably model it as a maximum flow problem en.m.wikipedia.org/wiki/Maximum_flow_problem (which can be solved in polynomial time). You would have a node for each stone, a node for each buyer and arcs with a capacity of one between the source and the stones, between the buyers and the sink and between each stone and potential buyer for it. If your maximum flow is smaller than your number of buyer you do not have a solution, otherwise you only have to assign the remaining stones on a first come first serve basis. – Renaud M. Jun 30 '16 at 12:23
3

I'd say it's a 1D array, given that a stone and its variant make a single item. Is it a wrong assumption?

Your algorithm should be correct, however it is truly a brute-force solution.

My simple suggestion: sort these items by the amount of people, who have them in their "favourites". Assign the items to people in this order, expanding a tree bounded by the amount of items.

E.g. 2 people like stone A, 3 people like stone B, first assign the stone A, so that you get rid of the less perspective as soon as possible.

This is probably not an optimal solution, however, some dynamic programming might be used, given that the state space is discrete.

1

Backtracking is a good approach. If your implementation gets to complicated you should read some example implementations of backtracking.

Remark: Backtracking is not 'trying every possible combination' because you do not try any combination, where already after a few assignments there could no longer be a valid over all assignment.
See Early stopping variants for a detailed description. (The Sodoku solving animation shows quite nice that you are far from trying each combination)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.