Post date: Jul 15, 2013 6:59:6 AM
Problem
you have data provided to you in pairs. the relationship is that the 2nd element is a child of the first element.
print out the final output with tabs as shown in examples below
input: <a,b>
output: a
b
input: <a,b> <b,c> <d,c>
output: a
d
b
c
input: <a,b> <c,d>
output: a
c
b
d
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Print ordered chars with specified format
Created Date : 15-July-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <hash_map>
#include <algorithm>
#include <set>
using namespace std;
void PrintOrderedChars(set<pair<char, char>> pairs)
{
hash_map<char, int> hm;
for(auto it = pairs.begin(); it != pairs.end(); ++it){
hm[it->first] = 0;
hm[it->second] = 0;
}
bool changed;
do{
changed = false;
for(auto it = pairs.begin(); it != pairs.end(); ++it){
int ord1 = hm[it->first];
int ord2 = hm[it->second];
if(ord2 != max(ord1 + 1, ord2)){
changed = true;
hm[it->second] = max(ord1 + 1, ord2);
}
}
}while(changed == true);
vector<pair<char, int>> orderedPairs;
cout << "----------------------------" << endl;
for(auto it = hm.begin(); it != hm.end(); ++ it){
orderedPairs.push_back(make_pair(it->first, it->second));
}
sort(orderedPairs.begin(), orderedPairs.end(),
[=](pair<char, int> i, pair<char, int> j)->bool
{return i.second < j.second;});
for(auto it = orderedPairs.begin(); it != orderedPairs.end(); ++it){
for(int i = 0; i < it->second; ++ i){
cout << '\t';
}
cout << it->first << endl;
}
}
void DoTest(set<pair<char, char>> pairs)
{
cout << "The input pairs are: " << endl;
for(auto it = pairs.begin(); it != pairs.end(); ++it){
cout << "(" << it->first << ", ";
cout << it->second << ") ";
}
cout << endl;
PrintOrderedChars(pairs);
cout << "-----------------------------" << endl;
}
int main(int argc, char* argv[])
{
set<pair<char, char>> testCase0;
testCase0.insert(pair<char, char>('a', 'b'));
DoTest(testCase0);
set<pair<char, char>> testCase1;
testCase1.insert(pair<char, char>('a', 'b'));
testCase1.insert(pair<char, char>('b', 'c'));
testCase1.insert(pair<char, char>('d', 'c'));
DoTest(testCase1);
set<pair<char, char>> testCase2;
testCase2.insert(pair<char, char>('a', 'b'));
testCase2.insert(pair<char, char>('c', 'd'));
DoTest(testCase2);
return 0;
}
Output
The input pairs are:
(a, b)
----------------------------
a
b
-----------------------------
The input pairs are:
(a, b) (b, c) (d, c)
----------------------------
a
d
b
c
-----------------------------
The input pairs are:
(a, b) (c, d)
----------------------------
a
c
b
d
-----------------------------
Press any key to continue . . .