/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <utility>
using MatrixDimensions = std::vector<std::pair<int, int>>;
std::pair<int,int> add_one(const MatrixDimensions &vec){
//find all the unique values ie 1,2,3
std::vector<int> vals;
for (auto const &v: vec){
vals.push_back(v.first);
vals.push_back(v.second);
}
std::sort(vals.begin(), vals.end());
auto it = std::unique(vals.begin(), vals.end());
vals.resize(distance(vals.begin(), it));
// count the number of each unique value in the rows and columns
std::unordered_map<int, int> row;
std::unordered_map<int, int> column;
for(auto const &i : vec){
row[i.first] += 1;
column[i.second] += 1;
};
// find the difference between row column counts
std::unordered_map<int, int> diff;
for (auto val: vals){
if (row.find(val) != row.end()){
if(column.find(val) != column.end())
diff[val] = row[val] - column[val];
else diff[val] = row[val];
}
else diff[val] = -column[val];
}
// add the missing dimension:
std::pair<int,int> added_one = vec[0];
for(auto const &i: diff)
if (i.second == -1)added_one.first = i.first;
else if (i.second == 1) added_one.second = i.first;
return added_one;
}
MatrixDimensions arrangeForMultiplication(const MatrixDimensions& dimensions){
if (dimensions.size() < 2) return dimensions;
MatrixDimensions result{add_one(dimensions)};
MatrixDimensions vec{dimensions};
//create a cycle beginning from the added position then delete the first
while(!vec.empty()) {
auto it = std::find_if(vec.begin(), vec.end(),
[=](std::pair<int, int> a) {
return a.first == result.back().second;
});
result.push_back(*it);
vec.erase(it);
}
result.erase(result.begin());
return result;
}
int main()
{
MatrixDimensions d{{1, 2}, {3, 2}, {2, 3}, {3, 1}};
MatrixDimensions e= arrangeForMultiplication(d);
for(auto p: e) std::cout<<"("<<p.first<<", "<<p.second<<") ";
}
