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;
}