/*
  Problem 1169. Invalid Transactions
  Medium
  
  A transaction is possibly invalid if:

    * the amount exceeds $1000, or;

    * if it occurs within (and including) 60 minutes of another
    * transaction with the same name in a different city.
      
  You are given an array of strings transaction where transactions[i]
  consists of comma-separated values representing the name, time (in
  minutes), amount, and city of the transaction.
  

  Return a list of transactions that are possibly invalid. You may
  return the answer in any order.

  Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
  Output: ["alice,20,800,mtv","alice,50,100,beijing"]

  Explanation: The first transaction is invalid because the second
  transaction occurs within a difference of 60 minutes, have the same
  name and is in a different city. Similarly the second one is invalid
  too.  

 */

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // map of name -> minutes,amount,city,index
    multimap<string, tuple<int,int,string,size_t>> nameMap;
    // set of unique names
    set<string> nameSet;
    
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<string> result;
        size_t index = 0;        
        for (auto i: transactions)
        {
            regex re(R"(^(\w+),(\w+),(\w+),(\w+)$)");
            smatch base_match;                
            regex_match(i, base_match, re);
            ssub_match base_sub_match1 = base_match[1]; string name =      base_sub_match1.str().c_str();
            ssub_match base_sub_match2 = base_match[2]; int minutes = atoi(base_sub_match2.str().c_str());
            ssub_match base_sub_match3 = base_match[3]; int amount  = atoi(base_sub_match3.str().c_str());
            ssub_match base_sub_match4 = base_match[4]; string city =      base_sub_match4.str().c_str();
            cout << " tran: " << name << "," << minutes << "," << amount << "," << city << "," << index << endl;
            nameMap.insert({name,{minutes,amount,city,index++}});
            nameSet.insert(name);
            if (amount > 1000)
            {
                result.push_back(i);
            }
        }
        
        for (auto i: nameSet)
        {            
            // look for transactions with same name, diff city, and time within 60 min of each other
            if (nameMap.count(i) > 1)
            {
                auto range = nameMap.equal_range(i);
                cout << i << " count: " << nameMap.count(i) << endl;
                for (auto j = range.first; j != range.second; j++)
                {
                    tuple<int,int,string,size_t> t_j = j->second;
                    cout << "tuple_j: " << get<0>(t_j) << "," << get<1>(t_j) << "," << get<2>(t_j) << "," << get<3>(t_j) << endl;
                    int minutes_j  = get<0>(t_j);
                    int amount_j   = get<1>(t_j);
                    string& city_j = get<2>(t_j);
                    size_t index_j = get<3>(t_j);
                    for (auto k = next(j); k != range.second; k++)
                    {
                        tuple<int,int,string,size_t> t_k = k->second;
                        cout << "tuple_k: " << get<0>(t_k) << "," << get<1>(t_k) << "," << get<2>(t_k) << "," << get<3>(t_k) << endl;
                        int minutes_k  = get<0>(t_k);
                        int amount_k   = get<1>(t_k);
                        string& city_k = get<2>(t_k);
                        size_t index_k = get<3>(t_k);
                        if (city_j != city_k)
                        {
                            if (abs(minutes_j - minutes_k) <= 60)
                            {                                
                                cout << "found: "
                                     << i << "," << minutes_j << "," << amount_j << "," << city_j << "," << index_j << " "
                                     << i << "," << minutes_k << "," << amount_k << "," << city_k << "," << index_k << endl;
                                
                                result.push_back(transactions.at(index_j));
                                result.push_back(transactions.at(index_k));
                            }
                        }
                        cout << "********************\n";                        
                    }
                }
            }        
        }
        return result;
    }
};

int main(void)
{
    vector<tuple<vector<string>,vector<string>>> testCases = {
        //                                             time diff within and including 60min for tran with same name and diff city 
        //{ {"alice,20,800,mtv","alice,50,100,beijing"}, {"alice,20,800,mtv","alice,50,100,beijing"} },
        //                                             amount > 1000
        //{ {"alice,20,800,mtv","alice,50,1200,mtv"},    {"alice,50,1200,mtv"} },
        //                                             amount > 1000        
        //{ {"alice,20,800,mtv","bob,50,1200,mtv"},      {"bob,50,1200,mtv"} },
        
        //{ {"alice,20,800,mtv","alice,50,100,mtv","alice,51,100,frankfurt"},{""} },

        // three dup transactions in the input
        { {"alice,20,800,mtv","bob,50,1200,mtv","alice,20,800,mtv","alice,50,1200,mtv","alice,20,800,mtv","alice,50,100,beijing"},
          // result has dup transactions ??????
          {"alice,20,800,mtv","bob,50,1200,mtv","alice,20,800,mtv","alice,50,1200,mtv","alice,20,800,mtv","alice,50,100,beijing"} },
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<string>& transactions = get<0>(tc);
        vector<string>& expected = get<1>(tc);
        vector<string>result = s.invalidTransactions(transactions);
        cout << "  result: [";
        for (size_t i = 0; i < result.size(); i++) {if (i < result.size() - 1) cout << result.at(i) << ","; else cout << result.at(i); }
        cout << "]\n";        
        cout << "expected: [";
        for (size_t i = 0; i < expected.size(); i++) {if (i < expected.size() - 1) cout << expected.at(i) << ","; else cout << expected.at(i); }
        cout << "]\n";
        cout << "-----------------------\n";        
    }

    return 0;
}