Coding Challenge - Sorting Royal Names

[NicolaBernini]

Overview

Given a list of Royal Names in the form Name RomanNumber like Louis III sort them according to the following rules

• first sort lexigraphically considering the name only
• in case of same name, sort numerically in ascending order according to roman number value

Example

Louis IX
Louis VIII
Philippe I
Philip II

becomes

Louis VIII
Louis IX
Philip II
Philippe I

[NicolaBernini]

Solution

#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;


unsigned int r2i(const string& r)
{
	unordered_map<char, unsigned int> r2i_lut = { {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50} }; 
	
	if(r.size()==0) return 0; 
	if(r.size()==1) return r2i_lut[r[0]]; 
 
	unsigned int res=0; 
	for(unsigned int i=0; i<r.size(); ++i)
	{
		if((i<r.size()-1) && (r2i_lut[r[i+1]] > r2i_lut[r[i]])) { res += (r2i_lut[r[i+1]] - r2i_lut[r[i]]); i++; }
		else res += r2i_lut[r[i]]; 
	}
	return res; 
}




string i2r(unsigned int n) 
{ 
	string res; 
    array<unsigned int, 7> r_n = {1,4,5,9,10,40,50}; 
    array<string, 7> r_d = {"I","IV","V","IX","X","XL","L"}; 
    unsigned int i = 7; 
	for(unsigned int i=6; (i>=0) && (n>0); --i)
	{
    	unsigned int d = n / r_n[i]; 
    	n = n % r_n[i]; 
    	for(unsigned int j=0; j<d; ++j) res+=r_d[i];     		
	}
    return res; 
} 



vector<string> tokenize(const string& s, const char c)
{
	vector<string> res; 
	auto ss = stringstream(s); 
	string temp; 
	while(getline(ss, temp, c)) res.push_back(temp); 
	return res; 
}


vector<string> getSortedList(const vector<string>& names) 
{
	vector<string> res; 
	map<string, vector<unsigned int>> d; 
	for(const auto& e : names)
	{
		auto s = tokenize(e, ' '); 
		d[s[0]].push_back(r2i(s[1])); 
	}
	
	
	for(auto& name : d)
	{
		sort(name.second.begin(), name.second.end()); 
		for(const auto& r : name.second)
		{
			res.push_back(name.first + " " + i2r(r)); 
		}
	}
	
	return res; 
}

string to_str(const vector<string>& s)
{
	string res=""; 
	for(const auto& e : s) res += e + "\n"; 
	return res; 
}



const vector< vector<string> > test = {{"Louis IX", "Louis VIII", "Philippe I", "Philip II"}}; 

int main() {
	// your code goes here
	for(const auto& e : test)
	{
		cout << "Original" << endl << "---------" << endl << to_str(e) << "--------" << endl << 
		"Sorted" << endl << "---------" << endl << to_str(getSortedList(e)) << "----------" << endl; 
	}
	return 0;
}