Advertisement
mohitsaini

Market_Simulation

Aug 19th, 2022 (edited)
743
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.86 KB | None | 0 0
  1. #include <cstdint>
  2. #include <random>
  3. #include <vector>
  4. #include <queue>
  5. #include <cassert>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <tuple>
  9. #include <iostream>
  10.  
  11. using namespace std;
  12.  
  13. // Please disable before submitting.
  14. constexpr bool kDebug = false;
  15.  
  16. using Side = bool;
  17. constexpr bool BUY = true;
  18. constexpr bool SELL = false;
  19.  
  20. struct order {
  21.   uint64_t order_token;
  22.   uint64_t shares;
  23.   double price;
  24.   Side side; // false = sell, true = buy
  25.   uint64_t created_at;
  26.   uint64_t cancelled_or_executed_at;
  27.   void Print() const {
  28.     auto& o = *this;
  29.     std::cerr << "O," << o.order_token << ", price = " << o.price << ", shares = " << o.shares
  30.               << ", " << (o.side ? "BUY" : "SELL") << ", time = " << o.created_at << ", timeout = "
  31.               << o.cancelled_or_executed_at << "\n";
  32.  
  33.   }
  34. };
  35.  
  36. using QueueItem = order;
  37.  
  38. struct query {
  39.   uint64_t query_time;
  40. };
  41.  
  42. enum Type {CANCEL = 0, BUY_SELL = 1, GET_INFO = 2};
  43.  
  44. struct OverAllQuery {
  45.   Type type;
  46.   uint64_t timestamp;
  47.   int index;
  48.   void Print() const {
  49.     std::cout << "Query{type = " << int(type) << ", timestamp = " << timestamp
  50.               << ", index = " << index << "}" << std::endl;
  51.   }
  52.  
  53. };
  54.  
  55.  
  56. struct BuyerCmp {
  57.   bool operator()(const QueueItem& a, const QueueItem& b) {
  58.     return std::make_pair(a.price, -a.created_at) < std::make_pair(b.price, -b.created_at);
  59.   }
  60. };
  61.  
  62. struct SellerCmp {
  63.   bool operator()(const QueueItem& a, const QueueItem& b) {
  64.     return std::make_pair(-a.price, -a.created_at) < std::make_pair(-b.price, -b.created_at);
  65.   }
  66. };
  67.  
  68. // highest prince on top.
  69. using BuyerQueue = std::priority_queue<QueueItem, std::vector<QueueItem>, BuyerCmp>;
  70.  
  71. // lowest price on top.
  72. using SellerQueue = std::priority_queue<QueueItem, std::vector<QueueItem>, SellerCmp>;
  73.  
  74. struct PerShare {
  75.     template<typename MyQueue, typename OppositeQueue>
  76.     void MatchOrder(order oinfo, MyQueue& my_queue, OppositeQueue& queue) {
  77.         while(oinfo.shares > 0 && queue.size() > 0) {
  78.             if (oinfo.side == BUY) {
  79.                 if (queue.top().price > oinfo.price) break;
  80.             } else  {
  81.                 if (queue.top().price < oinfo.price) break;
  82.             }
  83.             auto top = queue.top();
  84.             queue.pop();
  85.             if (top.cancelled_or_executed_at <= oinfo.created_at) continue;
  86.             int matched_size = std::min(top.shares, oinfo.shares);
  87.             // std::cout << "Matched " << matched_size << " shares, with order_token = " << top.order_token << std::endl;
  88.             oinfo.shares -= matched_size;
  89.             top.shares -= matched_size;
  90.             num_outstanding_shares -= matched_size;
  91.             outstanding_shares_of_order[top.order_token] -= matched_size;
  92.             if (top.shares > 0) {
  93.                 queue.push(top);
  94.             }
  95.         }
  96.         if (oinfo.shares > 0) {
  97.             my_queue.push(oinfo);
  98.             num_outstanding_shares += oinfo.shares;
  99.             outstanding_shares_of_order[oinfo.order_token] = oinfo.shares;
  100.             // std::cout << "Put in queue = " << oinfo.shares << " shares." << std::endl;
  101.         }
  102.     }
  103.  
  104.     void MakeOrder(order oinfo) {
  105.         if (oinfo.side == BUY) {
  106.             MatchOrder(oinfo, buyer_queue, seller_queue);
  107.         } else if (oinfo.side == SELL) {
  108.             MatchOrder(oinfo, seller_queue, buyer_queue);
  109.         } else {
  110.             assert(false);
  111.         }
  112.     }
  113.  
  114.     void MakeOverallQuery(const OverAllQuery& q) {
  115.       // std::cout << "\n\nts = " << q.timestamp << std::endl;
  116.       if (q.type == CANCEL) {
  117.         num_outstanding_shares -= outstanding_shares_of_order[q.index];
  118.         // std::cout << "CANCEL: ";
  119.         // orders[q.index].Print();
  120.       } else if (q.type == GET_INFO) {
  121.         output_info[q.index] = num_outstanding_shares;
  122.         // std::cout << "GET_INFO = " << output_info[q.index] << std::endl;
  123.       } else if (q.type == BUY_SELL) {
  124.         // std::cout << "MakeOrder: ";
  125.         // orders[q.index].Print();
  126.         MakeOrder(orders[q.index]);
  127.       } else {
  128.         assert(false);
  129.       }
  130.       // std::cout << "num_outstanding_shares = " << num_outstanding_shares << std::endl;
  131.     }
  132.  
  133.     PerShare(const vector<order> &orders, vector<uint64_t>& output_info)
  134.       : orders(orders), output_info(output_info), outstanding_shares_of_order(orders.size(), 0) { }
  135.     const vector<order> &orders;
  136.     vector<uint64_t>& output_info;
  137.     std::vector<uint64_t> outstanding_shares_of_order;
  138.     BuyerQueue buyer_queue;
  139.     SellerQueue seller_queue;
  140.     uint64_t num_outstanding_shares = 0;
  141. };
  142.  
  143.  
  144. std::vector<uint64_t> your_solution(const vector<order> &orders,
  145.                                     const vector<query> &queries) {
  146.   std::vector<OverAllQuery> overall_queries;
  147.   for (int i = 0; i < int(orders.size()); i++) {
  148.     auto& o = orders[i];
  149.     if (o.cancelled_or_executed_at <= o.created_at) continue;
  150.     overall_queries.push_back(OverAllQuery{BUY_SELL, o.created_at, i});
  151.     overall_queries.push_back(OverAllQuery{CANCEL, o.cancelled_or_executed_at, i});
  152.   }
  153.   for (int i = 0; i < int(queries.size()); i++) {
  154.     auto& q = queries[i];
  155.     overall_queries.push_back(OverAllQuery{GET_INFO, q.query_time, i});
  156.   }
  157.   std::sort(overall_queries.begin(), overall_queries.end(),
  158.     [](const OverAllQuery& a, const OverAllQuery& b){
  159.     return std::make_pair(a.timestamp, a.type)
  160.                < std::make_pair(b.timestamp, b.type);
  161.   });
  162.   vector<uint64_t> output_info(queries.size());
  163.   PerShare per_share(orders, output_info);
  164.   for (auto& x : overall_queries) {
  165.     per_share.MakeOverallQuery(x);
  166.   }
  167.   return output_info;
  168. }
  169.  
  170. ///////////////////////////////////////////////////////////////////////////////
  171. // Please do not change any code below.                                      //
  172. ///////////////////////////////////////////////////////////////////////////////
  173.  
  174. std::pair<vector<order>, vector<query>> gen_input(int seed) {
  175.   mt19937 gen(seed);
  176.  
  177.   const uint64_t order_len = 1 << (gen() % 20);
  178.   const uint64_t time_len = 1 << (gen() % 20);
  179.  
  180.   vector<order> orders;
  181.   for (uint64_t i = 0; i < order_len; ++i) {
  182.     const double duration = std::max(1.0, time_len / std::log2(time_len));
  183.     const uint64_t start = gen() % time_len;
  184.     const uint64_t end = std::min<int>(start + duration, time_len);
  185.     order o{
  186.         .order_token = i,
  187.         .shares = static_cast<uint64_t>(gen() % 10000),
  188.         .price = static_cast<double>(gen() % 1000) / 10,
  189.         .side = gen() % 2 ? false : true,
  190.         .created_at = start,
  191.         .cancelled_or_executed_at = end,
  192.     };
  193.     orders.emplace_back(o);
  194.   }
  195.  
  196.   vector<query> queries;
  197.   for (uint64_t i = 0; i < order_len; ++i) {
  198.     query q{
  199.         .query_time = static_cast<uint64_t>(gen() % time_len),
  200.     };
  201.     queries.emplace_back(q);
  202.   }
  203.  
  204.   return {std::move(orders), std::move(queries)};
  205. }
  206.  
  207. int hash_result(const std::vector<uint64_t> &answers) {
  208.   std::hash<uint64_t> hasher;
  209.   uint64_t result = 0;
  210.   for (auto &a : answers) {
  211.     result = hasher(a) ^ (result << 1);
  212.   }
  213.   return result;
  214. }
  215.  
  216. // This test harness generates an input to and hashes the output from your
  217. // solution. Please do not change any code below this line.
  218. int solution(int seed) {
  219.   auto input = gen_input(seed);
  220.   bool debug = kDebug && input.first.size() < 100 && input.second.size() < 100;
  221.   if (debug) {
  222.     for (auto &o : input.first) {
  223.       std::cerr << "O," << o.order_token << "," << o.price << "," << o.shares
  224.                 << "," << (o.side ? 'B' : 'S') << "," << o.created_at << ","
  225.                 << o.cancelled_or_executed_at << "\n";
  226.     }
  227.     for (auto &q : input.second) {
  228.       std::cerr << 'Q' << "," << q.query_time << "\n";
  229.     }
  230.   }
  231.  
  232.   const auto answers = your_solution(input.first, input.second);
  233.  
  234.   if (debug) {
  235.     for (auto &a : answers) {
  236.       std::cerr << "R," << a << "\n";
  237.     }
  238.   }
  239.  
  240.   return hash_result(answers);
  241. }
  242.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement