1
\$\begingroup\$

Here is a "Roman Numerals" kata implementation. Given a decimal number one has to return a corresponding roman number.

I have following questions:

  1. Is memory management correct? Here I assume that the caller is responsible for freeing memory.
  2. Does this code conform to c code style?
  3. Does it look like idiomatic c?

Thanks!

toRoman.h:

char * toRoman(int n);

typedef struct DecimalToRoman {
    int decimal;
    const char * roman;
} DecimalToRoman;

toRoman.c:

char * toRoman(int n) {
    if (n < 1) return NULL;

    const DecimalToRoman numbers[] = {
        { 1000, "M"  },
        {  900, "CM" },
        {  500, "D"  },
        {  400, "CD" },
        {  100, "C"  },
        {   90, "XC" },
        {   50, "L"  },
        {   40, "XL" },
        {   10, "X"  },
        {    9, "IX" },
        {    5, "V"  },
        {    4, "IV" },
        {    1, "I"  }
    };

    size_t resultLen = 1;
    int tmp = n;
    for (size_t i = 0; i < sizeof numbers / sizeof(DecimalToRoman) && tmp; i++) {
        while(tmp >= numbers[i].decimal) {
            tmp -= numbers[i].decimal;
            resultLen += strlen(numbers[i].roman);
        }
    }

    char * result = malloc(resultLen);
    if (result == NULL) {
        perror("allocate");
        return NULL;
    }
    memset(result, '\0', resultLen);

    for (size_t i = 0, r = 0; r < sizeof numbers / sizeof(DecimalToRoman); r++) {
        while (n >= numbers[r].decimal) {
            n -= numbers[r].decimal;

            int j = 0;
            while (numbers[r].roman[j])
                result[i++] = numbers[r].roman[j++];
        }
    }
    return result;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ By "Roman Numerals", do you mean codewars.com/kata/51b62bf6a9c58071c600001b/c? Or did you try to solve the problem in general? Is the header part of Codewars provided code or your own? \$\endgroup\$ – Zeta May 10 at 19:37
  • 1
    \$\begingroup\$ Yes, this is the kata. But I was practicing it here cyber-dojo.org \$\endgroup\$ – xuesheng May 11 at 20:08
2
\$\begingroup\$
toRoman.h

Is there any reason to expose DecimalToRoman to callers?


char * toRoman(int n)

Nit: it might be preferable to take unsigned rather than int as you cannot really handle negative numbers.


if (n < 1) return NULL;

Seems reasonable. If you took unsigned, then you would only have to handle 0. In that case, it might make sense to return "" so you always return a valid string.

On second thought, there's sort of an upper-bound on what you can reasonably write as a roman numeral. Does it make sense to write two billion in terms of thousands? If you choose an upper bound, you can make assumptions about the length of your buffer.


const DecimalToRoman numbers[] = {
....

I love that this is written out so clearly. Nice.


size_t resultLen = 1;

Help a reader out by saying why you init to 1. IMO it's not obvious until you get to malloc.

int tmp = n;
for (size_t i = 0; i < sizeof numbers / sizeof(DecimalToRoman) && tmp; i++) {
    while(tmp >= numbers[i].decimal) {
        tmp -= numbers[i].decimal;
        resultLen += strlen(numbers[i].roman);
    }
}

How about making this a function? There's a common pattern:

Type thing = init;
...actually figure out what thing is often with a loop...

// don't change thing anymore!
... use thing ...

This is almost always more clearly written as:

Type const thing = createThing(init);
... use thing ...

But anyway back to this code.

sizeof numbers / sizeof(DecimalToRoman)

How about making this a variable named lenNumbers or something like that? Super nit: I like that you used parens for the type and not for the expression, but IMO it looks weird with the operator/. More clear: (sizeof numbers) / sizeof(DecimalToRoman).


if (result == NULL) {
    perror("allocate");
    return NULL;
}

Good. I admit I usually assert in situations like this since there's not much you can do when you're out of memory (and it rarely happens in the things I do), but this is the party line.


memset(result, '\0', resultLen);

Isn't this overkill? You're about to overwrite the memory anyway. Could just set the last character to '\0` (and you might as well do that after you write the answer for cache locality).


        int j = 0;
        while (numbers[r].roman[j])
            result[i++] = numbers[r].roman[j++];

Better option: a for loop. Best option: strcpy.


You could remove the calls to strlen by storing the length in DecimalToRoman. The lengths are tiny so this is more a question of simplicity than optimization.


There's a common pattern in C APIs for returning buffers. The idea is you let the user pass in the buffer and you return an error code. Something like:

int getRomanNumerals(int nInput, char* strOut, int* nLen);

The return value is either success, failure, or "insufficient buffer" (you probably want an enum or a preprocessor #define for this). In any case, the user passes in a buffer and the buffer's length. You always set nLen to the number of bytes needed, and you set strOut if you have enough space (maybe you start setting strOut assuming the buffer is long enough, but stop writing if you run out of space and only need to set nLen).

This way the user can do crazy stuff like store the result in a weird place or maybe the user knows they don't have enough memory to store the whole thing etc.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Is memory management correct? Here I assume that the caller is responsible for freeing memory.

Yes. The allocated size needed is correct. Proper NULL allocation test done.

Does this code conform to c code style?

DecimalToRoman; in .h unnecessarily exposes implementation. Format looks similar to the C spec.

Does it look like idiomatic c?

Not as much as it could. .h file lacks any indication that the caller needs to free anything. Consider that the .c file is opaque to the user. A return value of NULL is a surprise. Function name does not hint at allocation. The .h lacks useful info to understated the function.

I see C moving more toward the caller supplying the buffer and size for such helper function. Also with size leading the pointer.


3 ideas: together to form a nifty result:

  1. Consider passing in the destination buffer and its size and use unsigned.

    char * toRoman(size_t sz, char *dest, unsigned n);
    
  2. Roman numbers did employ () or the like for large numbers. "N" is is reasonable result for 0.

    5000 --> "(V)"
    0 --> "N"
    
  3. Using #2, then for a given UINT_MAX, there is a small, pre-determinate max size needed.

Now the resultLen pre-calculation is not needed. Just use a temp buffer of the max size and copy. This ROMAN_SZ belongs in the .h file so a caller may benefit knowing the max size.

#if UINT_MAX == ‭42949672965u
  #define ROMAN_SZ 52  /* (((III)))((DCCCLXXXVIII))(DCCCLXXXVIII)DCCCLXXXVIII */

#else if ...

Putting this together

char * toRoman(char *dest, size_t, sz, unsigned n) {
  char tmp[ROMAN_SZ];

  // Fill tmp based on `n`, no worry about overrun.

  size_t needed = strlen(tmp) + 1;
  if (needed > sz) {
    Handle_error();  // could use NULL or "" to indicate error
  } else {
    return strcpy(dest, tmp);
  }

Now the fun part, use a macro and compound literal for an malloc()-less TO_ROMAN()

 #define TO_ROMAN(u) toRoman(ROMAN_SZ, (char [ROMAN_SZ]){""}, (u))

Code can use TO_ROMAN() to form a string that is valid to the end of the block with no *alloc(), free() needed.

int main(void) {
  printf("%s %s\n", TO_ROMAN(42), TO_ROMAN(12345));
}

This is akin to printing in any base

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.