Seller and Buyer Problem


  • 0
    Y

    Given several sellers and buyers, each seller has an amount of products, each buyer wants to buy several products from sellers. Some sellers can not transact with some buyers, if a buyer can not get enough products as he wants, the transaction will not succeed. If we know there is one strategy that can satisfy all buyers, how to find this strategy?

    I draw a graph to illustrate the problem, this is just an example. The question wants you to provide a transaction strategy for each buyer so that all buyers can get enough products they want.0_1483990333784_Seller&Buyer.jpeg


  • 0
    A

    Reframe the solution in terms of edges, have transactions be weights, then use Djisktra's algorithm. Is there anything I'm missing here?


  • 0
    Y

    @abilityfun I dont think we can use Dijisktra since this question does not ask us to get path with minimum weights between 2 points. In this question, each buyer can buy products from multiple sellers and sellers can transact with multiple buyers. Each seller has some products in stock and can not sell products more than this amount. The problem here is that the transaction is done only when buyers get enough products as they want.Lets say there are two sellers and two buyers : Seller 1 has 4 products and he can sell his products to both buyer 1 and 2, Seller 2 has 5 products but he can only transact with buyer 2. Buyer 1 wants to get 4 products and buyer 2 wants to get 5 products. So here we know that both buyers can be fulfilled( Seller 1 sell product to buyer 1 and seller 2 sell product to buyer 2), but if seller 2 sell products to buyer 1, it will not have enough product to buyer 2 and buyer 2 can not be fulfilled. In some cases not all buyers can be satisfied so we need to find a strategy to satisfy as many buyers as possible.


  • 0
    K

    I am aware that this is a school assignment for you and I shouldn't be posting a code.
    But I'm feeling really lazy to explain, but the short version is this:
    You need to sell products to the buyer that has the largest resource discrepancy.
    Meaning you need to sell first to the buyer who has the minimum of (Available Resources to Buyer - Buy Amount).

    In the constructor of the "economy" class, I have used the example that you have scanned in your question. So the { 0, 1, 3 } corresponds to buyer "a", { 0, 1, 2} corresponds to "b" so on.

    By the way, according to my execution, either buyer c or d will not fully be supplied.

    Main.cpp

    #include "Economy.h"
    using namespace std;
    
    int main() {
    	Economy eco;
    	eco.startTransactions();
    
    	getchar();
    }
    

    Economy.h

    #pragma once
    #include <vector>
    
    class Economy {
    public:
    	Economy();
    	~Economy();
    
    	void startTransactions(void);
    private:
    	// Denotes product storage of buyers
    	std::vector<int> m_sellers;
    	// Denotes requested amount of products
    	std::vector<int> m_buyers;
    	// Each index denotes buyer, the nested vector denotes seller index
    	std::vector<std::vector<int>> m_links;
    };
    
    

    Economy.cpp

    #include "Economy.h"
    
    #include <iostream>
    #include <queue>
    
    struct Scarcity {
    	int buyer_index;
    	int amount;
    	Scarcity(int buyer_index, int amount) : amount(amount), buyer_index(buyer_index){}
    	Scarcity() : amount(0), buyer_index(0) {}
    };
    
    class CompareScarcity {
    public:
    	bool operator()(Scarcity& t1, Scarcity& t2) {
    		if (t1.amount < t2.amount || t1.amount == t2.amount)
    			return false;
    		return true;
    	}
    };
    
    Economy::Economy()
    {
    	m_sellers = {5, 3, 4, 2, 3};
    	m_buyers  = {4, 3, 4, 2};
    	m_links = { { 0, 1, 3 }, { 0, 1, 2}, {3, 4}, {3, 4} };
    }
    
    Economy::~Economy() {
    }
    
    void Economy::startTransactions(){
    
    	// Denotes how many products each buyer has the access for
    	std::priority_queue<Scarcity, std::vector<Scarcity>, CompareScarcity> buyer_rank;
    	Scarcity scarcity;
    
    	for (size_t i = 0; i < m_links.size(); ++i){
    		scarcity.buyer_index = i;
    		scarcity.amount = -1 * m_buyers[i];
    		for (size_t j = 0; j < m_links[i].size(); ++j){
    			scarcity.amount += m_sellers[m_links[i][j]];
    		}
    		buyer_rank.push(scarcity);
    	}
    
    	size_t resSize = buyer_rank.size();
    	int currentBuyer = 0, currentSeller = 0, sellAmount = 0;
    
    	// Traverse buyers starting from the scarcest ones
    	for (size_t i = 0; i < resSize; i++){
    		currentBuyer = buyer_rank.top().buyer_index;
    		// For each buyer, get products from sellers
    		// Traverse sellers for this buyer
    		for (size_t i = 0; (m_buyers[currentBuyer] != 0) && i < m_links[currentBuyer].size(); ++i){
    			currentSeller = m_links[currentBuyer][i];
    			// Seller has more stocks than buyer needs
    			if (m_sellers[currentSeller] >= m_buyers[currentBuyer]) {
    				// Sell the remaining amount
    				sellAmount = m_buyers[currentBuyer];
    			} // This seller doesn't have enough
    			else {
    				// Sell the remaining amount
    				sellAmount = m_sellers[currentSeller];
    			}
    			m_sellers[currentSeller] -= sellAmount;
    			m_buyers[currentBuyer] -= sellAmount;
    			std::cout << "Seller [" << currentSeller << "] -> Buyer [" << currentBuyer << "]: " <<
    				sellAmount << std::endl;
    		}
    		// Go to next buyer
    		buyer_rank.pop();
    	}
    
    	std::cout << "----- FINAL STATE -----" << std::endl;
    	std::cout << "      BUYERS" << std::endl;
    	for (size_t i = 0; i < m_buyers.size(); ++i){
    		std::cout << '[' << i << "]: " << m_buyers[i] << std::endl;
    	}
    	std::cout << "      SELLERS" << std::endl;
    	for (size_t i = 0; i < m_sellers.size(); ++i){
    		std::cout << '[' << i << "]: " << m_sellers[i] << std::endl;
    	}
    
    	getchar();
    }
    

    Program Output

    Seller [3] -> Buyer [2]: 2
    Seller [4] -> Buyer [2]: 2
    Seller [3] -> Buyer [3]: 0
    Seller [4] -> Buyer [3]: 1
    Seller [0] -> Buyer [0]: 4
    Seller [0] -> Buyer [1]: 1
    Seller [1] -> Buyer [1]: 2
    ----- FINAL STATE -----
          BUYERS
    [0]: 0
    [1]: 0
    [2]: 0
    [3]: 1
          SELLERS
    [0]: 0
    [1]: 1
    [2]: 4
    [3]: 0
    [4]: 0
    

  • 0
    Y

    @kirkdokuzelli Hi Kirk thank you for your reply. Actually this is not a school assignment but a real interview problem. Yes greedy can get a good strategy but it might not be the optimal strategy. For example, if there are two sellers A and B, two buyers a and b. Seller A has 4 products and seller B has 5 products, buyer a requires 4 products and buyer b requires 5 products. Seller A can only sell product to buyer a and seller B can sell products to both buyer a and b.

    So if you only use greedy to sort which buyer to serve first, if buyer a gets 4 products from Seller B, then buyer b can not be satisfied. But we know that both buyers can be satisfied right?


  • 0
    K

    @YolandaXiao You didn't even read or try my algorithm.......
    In your last example:

    Buyer "a" will have the scarcity value
    (4 + 5 - 4) = 5. 
     A   B   a
    Buyer "b" will have the scarcity value
    (5 - 5) = 0.
     B   b
    

    Since we will always start from the lowest scarcity, b will be served first and a will be served second. Everyone gets their supply. This algorithm doesn't have any chance to fail.


  • 0
    Y

    @kirkdokuzelli ohhhh so sorry mb. I 'm not quite familiar with cpp but I can understand what does your algorithm do after reading your code. Yes your code can solve the problem in the example I mentioned. And I tried your code with other test cases , but one problem is that in your algorithm, buyers are served based on their discrepancy. If the test case has one buyer with maximum product requirement but it has very small discrepancy, your algorithm will serve this buyer first, but other buyers have much smaller product requirement but their discrepancy is greater than the first buyer. In such case, your algorithm can only satisfy 1 buyer but this question wants to find a strategy to satisfy as many buyers as possible. So fulfill buyers with larger discrepancy will get a better result.

    To be more specific, I draw this case: 0_1484852306574_WechatIMG1.jpeg


  • 1
    K

    READ YOUR OWN ORIGINAL POST.

    @YolandaXiao said in Seller and Buyer Problem:

    Given several sellers and buyers, each seller has an amount of products, each buyer wants to buy several products from sellers. Some sellers can not transact with some buyers, if a buyer can not get enough products as he wants, the transaction will not succeed.
    If we know there is one strategy that can satisfy all buyers,
    how to find this strategy? I draw a graph to illustrate the problem, this is just an example. The question wants you to provide a transaction strategy for each buyer so that
    all buyers can get enough products they want.

    You can't just add new clauses to the original question and expect every algorithm to work for everything.

    So since you're asking for a solution to a NEW problem, for which there are not enough supplies for the buyers, let me ask you:

    • Do you want to satisfy the most amount of buyers? (maximum number of buyers that are completely fulfilled)
    • Do you want to distribute the supply evenly? (Every buyer gets supplies proportionate to their request)

    So in your latest example, if you want clause 1, their supplies will be like this:

    a = 7
    b = 2
    c = 3
    

    so a needs 4 more but b and c are fully supplied.

    For the second clause, it will be something like this:

    a = 8
    b = 2
    c = 2
    

    Here all the buyers have about %75 of their original supplies, but none of them are fully satisfied.

    Like I've said, my solution solves the original problem completely. But for the NEW problem you're asking:

    • If you want clause 1, obviously supply the buyers with minimum requests first, very easy. (b > c > a)
    • If you want clause 2, you do like this:
    Overall discrepancy = (total supplies / total requests)
                                    = (3 + 4 + 5) / (11 + 2 + 3)
                                    = 12 / 16 
                                    = %75
    
    So, calculate for each customer request. For example 
    a = 11 * 75 / 100 = 8.25 --> Round it --> 8
    b = 2 * 75 / 100 = 1.5    -->Round it --> 2
    c = 3 * 75 / 100 = 2.25   -->Round it --> 2
    

    You're pissing me off and wasting my time. Ask the question once, and properly. I'm not helping you out any further.


  • 0
    Y

    @kirkdokuzelli

    • if I pissed you off because I did not try your code and replied you in haste, I said sorry, I should have considered you solution carefully.

    • If you feel that I wasted your precious time arguing two totally different stupid questions, sorry the last test case I said was not correct and misleading, but I just wanted to show you that your solution cant solve my ORIGINAL SOLUTION in some cases

    I met this question in an interview and I didn't come up with a perfect solution and I came here ask for help. Your algorithm is not correct because you only calculate the order of buyers.

    0_1484967200593_Screen Shot 2017-01-20 at 9.53.01 PM.png

    This graph must have a perfect solution which sould be:

    Buyer 1 : get 1 from seller 1, get 2 from seller 2
    Buyer 2: get 1 from seller 1, get 1 from seller 3, get 1 from seller 5
    Buyer 3: get 1 from seller 3, get 2 from seller 4
    Buyer 4: get 1 from seller 5, get 2 from seller 6

    In Your Solution:

    First, calculate the discrepency:

    Buyer 1 = 2 + 2 - 3 = 1;
    Buyer 2 = 2 + 2 + 2 - 3 = 3;
    Buyer 3 = 1;
    Buyer 4 = 1;

    So Buyer 1, Buyer 3 , Buyer 4 should be served first.

    Buyer 1 get 2 products from seller 1, get 1 product from seller 2
    Buyer 3 get 2 products from seller 3, get 1 from seller 4
    Buyer 4 get 2 from seller 5 get 1 from seller 6

    Buyer 2 can not be fulfilled.

    What will happen??????

    You can never get the best solution

    I wasted my time drawing this graph with Word, so we are even. Anyway thank you for your PERFECT solution.


  • 1
    K

    First of all, you are right, I didn't think sellers would run out of supplies that was my mistake. However you can just apply the same algorithm to sellers and the problem will be over. After my initial solution, it's not too hard to come up with a new solution.

    "I wasted my time drawing this graph with Word, so we are even." You're the one asking for a solution here, we (by we I mean me) are providing solutions to YOUR problem. People get paid for this, I'm doing this out of curiosity and for free so don't be rude. We're helping you out here. Also I've thought about the algorithm, written the code for it and tested it. You're saying a word diagram is equal to all that?

    Anyway here's the new algorithm. For each buyer and for each seller, you calculate the resource difference.

    buyer_difference = available suplies to this buyer - this buyers request;
    
    seller_difference = buyer requests from this seller - this sellers supplies;
    
    • After that you're still going to iterate over the buyers with the lowest buyer_difference in the collection.
    • When you want to transfer supplies to this buyer, you're going to trade with the seller that has the lowest seller_difference among the buyer's links.
    • When you are doing the trade, you will update the buyer_difference and seller_difference for all of the linked traders (a different buyer linked to the same seller will be updated as well).
    • Now go to step 1 until there are either no supplies left, or until no buyers left.

    I have added both of the examples in the code, just uncomment from the "// FIRST EXAMPLE START!" until "// END OF FIRST EXAMPLE". I've also made the code simpler to read. No priority queues etc. You can do this in any language.

    Output of the second example:

    ----- CURRENT STATE -----
          BUYERS
    [0]: 3
    [1]: 3
    [2]: 3
    [3]: 3
          SELLERS
    [0]: 2
    [1]: 2
    [2]: 2
    [3]: 2
    [4]: 2
    [5]: 2
    
    Seller [1] -> Buyer [0]: 2
    Seller [0] -> Buyer [0]: 1
    Seller [3] -> Buyer [2]: 2
    Seller [2] -> Buyer [2]: 1
    Seller [0] -> Buyer [1]: 1
    Seller [2] -> Buyer [1]: 1
    Seller [4] -> Buyer [1]: 1
    Seller [4] -> Buyer [3]: 1
    Seller [5] -> Buyer [3]: 2
    
    ----- CURRENT STATE -----
          BUYERS
    [0]: 0
    [1]: 0
    [2]: 0
    [3]: 0
          SELLERS
    [0]: 0
    [1]: 0
    [2]: 0
    [3]: 0
    [4]: 0
    [5]: 0
    

    Output of the first example

    
    ----- CURRENT STATE -----
          BUYERS
    [0]: 4
    [1]: 3
    [2]: 4
    [3]: 2
          SELLERS
    [0]: 5
    [1]: 3
    [2]: 4
    [3]: 2
    [4]: 3
    
    Seller [4] -> Buyer [2]: 3
    Seller [3] -> Buyer [2]: 1
    Seller [3] -> Buyer [3]: 1
    Seller [0] -> Buyer [0]: 4
    Seller [0] -> Buyer [1]: 1
    Seller [2] -> Buyer [1]: 2
    
    ----- CURRENT STATE -----
          BUYERS
    [0]: 0
    [1]: 0
    [2]: 0
    [3]: 1
          SELLERS
    [0]: 0
    [1]: 3
    [2]: 2
    [3]: 0
    [4]: 0
    

    If the supplies aren't enough (like the first case), and you want to "satisfy maximum amount of customers" you just need to change the "getNextLowestBuyer" method and the rest of the algorithm will still work. Depends on what you want to do. So this currently works for both buyers and sellers running out of resources. I can't think of anything else that might cause a problem.

    Execution.cpp

    #include "Economy.h"
    
    
    int main() {
    	Economy eco;
    	eco.printCurrentState();
    	eco.performTransactions();
    	eco.printCurrentState();
    	getchar();
    }
    

    Economy.h

    #pragma once
    #include <vector>
    
    struct trader {
    	int supply;
    	int supply_difference;
    
    	trader(int supply) :
    		supply(supply),
    		supply_difference(-1 * supply){
    	}
    };
    
    class Economy {
    public:
    	Economy();
    	~Economy();
    
    	void performTransactions(void);
    	void printCurrentState(void);
    private:
    	int getLowestSeller(int buyerIndex);
    	int getNextLowestBuyer(void);
    	void makePurchase(int buyerIndex, int sellerIndex, int amount);
    	bool sellerSuppliesRemain();
    	bool sellerSuppliesRemain(int buyerIndex);
    private:
    	// Sorted vector of sellers
    	std::vector<trader> m_sellers;
    	// Sorted vector of buyers
    	std::vector<trader> m_buyers;
            // "first" of the pair is buyer, "second" of the pair is seller
    	std::vector<std::pair<int, int>> m_links;
    };
    

    Economy.cpp

    #include "Economy.h"
    
    #include <iostream>
    #include <algorithm>
    
    Economy::Economy()
    {
    	// FIRST EXAMPLE START!
    	// BUYERS
    	for (int i = 0; i < 4; ++i){
    		m_buyers.push_back(trader(3));
    	}
    	// SELLERS
    	for (int i = 0; i < 6; ++i){
    		m_sellers.push_back(trader(2));
    	}
    
    	// "first" of the pair is buyer, "second" of the pair is seller
    	m_links = { { 0, 0 },
    	{ 0, 1 },
    	{ 1, 0 },
    	{ 1, 2 },
    	{ 1, 4 },
    	{ 2, 2 },
    	{ 2, 3 },
    	{ 3, 4 },
    	{ 3, 5 } };
    	// END OF FIRST EXAMPLE
    
    	//// SECOND EXAMPLE START!
    	//m_buyers.push_back(trader(4));
    	//m_buyers.push_back(trader(3));
    	//m_buyers.push_back(trader(4));
    	//m_buyers.push_back(trader(2));
    
    	//m_sellers.push_back(trader(5));
    	//m_sellers.push_back(trader(3));
    	//m_sellers.push_back(trader(4));
    	//m_sellers.push_back(trader(2));
    	//m_sellers.push_back(trader(3));
    
    	//// "first" of the pair is buyer, "second" of the pair is seller
    	//m_links = { { 0, 0 },
    	//{ 0, 1 },
    	//{ 0, 3 },
    	//{ 1, 0 },
    	//{ 1, 1 },
    	//{ 1, 2 },
    	//{ 2, 3 },
    	//{ 2, 4 },
    	//{ 3, 3 },
    	//{ 3, 4 } };
    	//// END OF SECOND EXAMPLE
    
    	// Now adjust differences
    	for (size_t i = 0; i < m_links.size(); ++i){
    		m_buyers[m_links[i].first].supply_difference += m_sellers[m_links[i].second].supply;
    		m_sellers[m_links[i].second].supply_difference += m_buyers[m_links[i].first].supply;
    	}
    }
    
    Economy::~Economy() {
    }
    
    int Economy::getLowestSeller(int buyerIndex){
    	if (m_buyers[buyerIndex].supply == 0)
    		return -1;
    
    	int min_diff = INT_MAX, min_index = -1, seller_index = 0;
    
    	for (size_t i = 0; i < m_links.size(); ++i){
    		seller_index = m_links[i].second;
    		if (m_links[i].first == buyerIndex &&
    			m_sellers[seller_index].supply_difference < min_diff &&
    			m_sellers[seller_index].supply > 0){
    			min_diff = m_sellers[seller_index].supply_difference;
    			min_index = seller_index;
    		}
    	}
    	return min_index;
    }
    
    void Economy::makePurchase(int buyerIndex, int sellerIndex, int amount){
    
    	m_sellers[sellerIndex].supply -= amount;
    	m_buyers[buyerIndex].supply -= amount;
    
    	// Re-adjust differences
    	for (size_t i = 0; i < m_links.size(); ++i){
    		// Adjust buyers for that seller
    		if (m_links[i].second == sellerIndex)
    			m_buyers[m_links[i].first].supply_difference -= amount;
    		// Adjust sellers for that buyer
    		if (m_links[i].first == buyerIndex)
    			m_sellers[m_links[i].second].supply_difference -= amount;
    	}
    }
    
    int Economy::getNextLowestBuyer(void) {
    	int min_diff = INT_MAX, min_index = -1;
    
    	for (size_t i = 0; i < m_buyers.size(); ++i){
    		if (m_buyers[i].supply_difference < min_diff &&
    			m_buyers[i].supply > 0 &&
    			sellerSuppliesRemain(i)){
    			min_diff = m_buyers[i].supply_difference;
    			min_index = i;
    		}
    	}
    	return min_index;
    }
    
    bool Economy::sellerSuppliesRemain(){
    	for (size_t i = 0; i < m_sellers.size(); ++i){
    		if (m_sellers[i].supply > 0)
    			return true;
    	}
    	return false;
    }
    
    bool Economy::sellerSuppliesRemain(int buyerIndex) {
    
    	for (size_t i = 0; i < m_links.size(); ++i){
    		if (m_links[i].first == buyerIndex &&
    			m_sellers[m_links[i].second].supply > 0)
    			return true;
    	}
    	return false;
    }
    
    void Economy::performTransactions() {
    	int seller_index = 0, buyer_index = 0, sell_amount = 0;
    
    	// Start from the lowest buyer	
    	buyer_index = getNextLowestBuyer();
    	// Go until all buyers are satisfied or all sellers are 0
    	while (buyer_index != -1 && sellerSuppliesRemain()){
    		// Get the first lowest seller for this buyer
    		seller_index = getLowestSeller(buyer_index);
    
    		// While there is a need and there is a seller
    		while (seller_index != -1) {
    			// Seller has more stocks than buyer needs
    			if (m_sellers[seller_index].supply >= m_buyers[buyer_index].supply) {
    				// Purchase the need, completely
    				sell_amount = m_buyers[buyer_index].supply;
    			} // This seller doesn't have enough
    			else {
    				// Sell the remaining amount
    				sell_amount = m_sellers[seller_index].supply;
    			}
    			makePurchase(buyer_index, seller_index, sell_amount);
    
    			std::cout << "Seller [" << seller_index << "] -> Buyer [" << buyer_index << "]: " <<
    				sell_amount << std::endl;
    
    			seller_index = getLowestSeller(buyer_index);
    		}
    		buyer_index = getNextLowestBuyer();
    	}
    }
    
    void Economy::printCurrentState(){
    	std::cout << "\n----- CURRENT STATE -----" << std::endl;
    	std::cout << "      BUYERS" << std::endl;
    	for (size_t i = 0; i < m_buyers.size(); ++i){
    		std::cout << '[' << i << "]: " << m_buyers[i].supply << std::endl;
    	}
    	std::cout << "      SELLERS" << std::endl;
    	for (size_t i = 0; i < m_sellers.size(); ++i){
    		std::cout << '[' << i << "]: " << m_sellers[i].supply << std::endl;
    	}
    	std::cout << std::endl;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.