Reducing Roman Numerals

I’m sure a mathematical solution exists to condense Roman numeral values. The values ending in 4 or 9 can be reduced, but whatever that solution is, it’s beyond me. So for my resolution to the Roman numeral reduction problem, I rely on strings instead of math.

Assuming that the original Roman numeral is ordered high-to-low, and that no value is out of sequence, then only six character sequences (strings) exist that can be reduced:

DCCCC to CM
CCCC to CD
LXXXX to XC
XXXX to XL
VIIII to IX
IIII to IV

In each of these reductions, repeating values of four characters are present: CCCC, XXXX, and IIII. I tried to craft a function that looked for those strings, but in the end it was easier to do a search for all six strings and replace them with their reduced counterparts — a search-and-replace.

The function I wrote is called rn_srink() and it requires a pointer to an existing Roman numeral string. The function searches for one of the six instances shown above and replaces it with the reduced characters. The string must be dissected and then reassembled to complete this task. Because pointers are used, special care is required to ensure that the memory locations don’t get lost; it’s difficult to manipulate a pointer passed to a function (Lesson/Series), so I created a local copy of the string for manipulation.

Here’s the rn_shrink() function:

void rn_shrink(char *r)
{
    char *change_from[6] = {
        "DCCCC", "CCCC", "LXXXX", "XXXX", "VIIII", "IIII"
    };
    char *change_to[6] = {
        "CM", "CD", "XC", "XL", "IX", "IV"
    };
    char new_r[SIZE];
    char *base,*rest;
    int x;

    for(x=0;x<6;x++)
    {
        base = strstr(r,change_from[x]);
        if( base != NULL)
        {
            rest = base+strlen(change_from[x]);
            if( base == r)
            {
                strcpy(new_r,change_to[x]);
            }
            else
            {
                *base = '\0';
                strcpy(new_r,r);
                strcat(new_r,change_to[x]);
            }
            if( *rest != '\0')
                strcat(new_r,rest);
            strcpy(r,new_r);
        }
    }
}

The for loop processes the string six times, one for each element in the change_from[] and change_to[] arrays. The strstr() function attempts to locate the string. If found, its location is saved in the rest pointer.

The if( base == r) test is true when the search text (long value) is found at the start of the string. In that case, the replacement string (short value) is copied from change_to[] into the new_r buffer. Otherwise, the first part of the original string r is copied (strcpy())to the new_r buffer. Otherwise, the reduced string from change_to[] is appended to new_r by using the strcat() function. Finally, the if( *rest != '\0') test ensures that the replacement didn’t occur at the end of the string. If not, the rest of the original string is appended to new_r by using another strcat() function. Figure 1 illustrates this operation.

Figure 1. How the find, slice, and build operation works.

The rn_shink() function is added code presented in last week’s Lesson. To view the full code, click here.

Here are some sample runs:

Type an integer value: 2999
The value 2999 is MMDCCCCLXXXXVIIII
Shortened value is MMCMXCIX

Type an integer value: 1974
The value 1974 is MDCCCCLXXIIII
Shortened value is MCMLXXIV

I feel that this solution is rather clunky; I’d much rather find a mathematical solution and simply rebuild the string from scratch, but like many programs, this one works so I’m good with it.

Leave a Reply