Roman numerals

roman.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct RomanChars_type {
    char *chars;
    unsigned int length;
    size_t size;
} RomanChars;

const size_t RomanCharsDefaultSize = 8;

RomanChars *
RomanChars_alloc(const size_t initial_size)
{
    RomanChars *result = NULL;
    size_t size = (initial_size == 0) ? RomanCharsDefaultSize : initial_size;
    char *c = (char *)malloc(size);
    if (c != NULL) {
        result = (RomanChars *)malloc(sizeof(RomanChars));
        result->chars = c;
        result->length = 0;
        result->size = size;
    }
    return result;
}

bool
RomanChars_expand(RomanChars *rc)
{
    size_t size = rc->size << 1;
    char *chars = (char *)realloc(rc->chars, size);
    if (chars != NULL) {
        rc->chars = chars;
        rc->size = size;
        return true;
    }
    else {
        fprintf(stderr, "Reallocation failed\n");
        return false;
    }
}

void
RomanChars_free(RomanChars *rc)
{
    if (rc != NULL) {
        free(rc->chars);
        free(rc);
    }
}

bool
RomanChars_push(RomanChars *rc, const char c)
{
    if (rc == NULL) {
        return false;
    }
    if (rc->length >= rc->size) {
        if (!RomanChars_expand(rc)) {
            fprintf(stderr, "Could not expand from %lu bytes\n", rc->size);
            return false;
        }
    }
    rc->chars[rc->length] = c;
    rc->length++;
    return true;
}

char
RomanChars_pop(RomanChars *rc)
{
    char c = '\0';
    if (rc != NULL) {
        unsigned int len = rc->length;
        if (len > 0) {
            len--;
            c = rc->chars[len];
            rc->length = len;
        }
    }
    return c;
}

char *
RomanChars_string(RomanChars *rc)
{
    return strndup(rc->chars, rc->length);
}

char *
roman(const unsigned int num)
{
    if (num == 0) {
        return strdup("N");
    }

    RomanChars *base = RomanChars_alloc(0);
    unsigned int n = num;
    while (n >= 1000) {
        RomanChars_push(base, 'M');
        n -= 1000;
    }
    if (n >= 500) {
        RomanChars_push(base, 'D');
        n -= 500;
    }
    while (n >= 100) {
        RomanChars_push(base, 'C');
        n -= 100;
    }
    if (n >= 50) {
        RomanChars_push(base, 'L');
        n -= 50;
    }
    while (n >= 10) {
        RomanChars_push(base, 'X');
        n -= 10;
    }
    if (n >= 5) {
        RomanChars_push(base, 'V');
        n -= 5;
    }
    while (n >= 1) {
        RomanChars_push(base, 'I');
        n--;
    }

    RomanChars *result = RomanChars_alloc(base->size);
    char push_char = '\0', c, next_highest, next_unit;
    unsigned short push_count = 0;
    bool keep_char;
    while (base->length > 0) {
        c = RomanChars_pop(base);

        if (push_count > 0 && c == push_char) {
            push_count++;
        }
        else {
            for (int i = 0; i < push_count; i++) {
                RomanChars_push(result, push_char);
            }
            push_char = c;
            push_count = 1;
        }

        if (push_count == 4) {
            switch (push_char) {
                case 'I':
                    next_highest = 'V';
                    next_unit = 'X';
                    break;
                case 'X':
                    next_highest = 'L';
                    next_unit = 'C';
                    break;
                case 'C':
                    next_highest = 'D';
                    next_unit = 'M';
                    break;
                default:
                    next_highest = '\0';
                    break;
            }
            if (next_highest != '\0') {
                c = RomanChars_pop(base);
                keep_char = (c != next_highest);
                RomanChars_push(result, (keep_char) ? next_highest : next_unit);
                RomanChars_push(result, push_char);
                push_char = (keep_char) ? c : '\0';
                push_count = (keep_char) ? 1 : 0;
            }
        }
    }

    if (push_count > 0 && push_char != '\0') {
        for (int i = 0; i < push_count; i++) {
            RomanChars_push(result, push_char);
        }
    }
    char *chars = RomanChars_string(result);
    RomanChars_free(base);
    RomanChars_free(result);

    unsigned int len = result->length;
    unsigned int mid = len / 2;
    for (int i = 0, j = len - 1; i < mid; i++, j--) {
        c = chars[i];
        chars[i] = chars[j];
        chars[j] = c;
    }
    return chars;
}

int
main()
{
    char *s = NULL;
    for (int i = 0; i < 4000; i++) {
        s = roman(i);
        printf("%s\n", s);
        free(s);
    }
    return 0;
}

roman.py

NUMERALS = 'IVXLCDM'

def roman(num):
    if not num:
        return 'N'
    else:
        assert num > 0

    base = []
    while num >= 1000:
        base.append('M')
        num -= 1000
    if num >= 500:
        base.append('D')
        num -= 500
    while num >= 100:
        base.append('C')
        num -= 100
    if num >= 50:
        base.append('L')
        num -= 50
    while num >= 10:
        base.append('X')
        num -= 10
    if num >= 5:
        base.append('V')
        num -= 5
    while num >= 1:
        base.append('I')
        num -= 1

    result = []
    push_char, push_count = '', 0
    while base:
        char = base.pop()

        if push_count and char == push_char:
            push_count += 1
        else:
            result.append(push_char * push_count)
            push_char, push_count = char, 1

        if push_count == 4 and push_char in 'IXC':
            i = NUMERALS.index(push_char)
            assert not i & 1  # should be an even index
            next_highest = NUMERALS[i + 1]
            next_unit = NUMERALS[i + 2]
            char = base.pop() if base else ''
            keep_char = (char != next_highest)
            result.append(next_highest if keep_char else next_unit)
            result.append(push_char)
            push_char, push_count = (char, 1) if keep_char else ('', 0)

    if push_count > 0:
        result.append(push_char * push_count)

    return ''.join(reversed(result))


if __name__ == '__main__':
    print(' '.join(roman(i) for i in range(0, 1500 + 1)))