Solving Roman numerals with Julia's metaprogramming

Question

I solved the exercise with regular Julia code, wasn't too hard:

function to_roman(number::Int64)
    0 < number < 4000 || error("not in range")

    parts = Char[]
    while number > 0
        if number >= 1000
            push!(parts, 'M')
            number -= 1000
        elseif number >= 500
            push!(parts, 'D')
            number -= 500
        # ...
            number -= 10
        elseif number >= 5
            push!(parts, 'V')
            number -= 5
        elseif number >= 1
            push!(parts, 'I')
            number -= 1
        end
    end
    join(parts)
end

This only solves naïve numerals, but keeps the example shorter. Now me being me, I'm appalled by the redundancy in this. So I made iteration 2:

const values = Dict(
    'M' => 1000,
    'C' => 100,
    'X' => 10,
    'I' => 1,
    'D' => 500,
    'L' => 50,
    'V' => 5,
)
Base.:+(number::Integer, c::Char) = number + values[c]
Base.:-(number::Integer, c::Char) = number - values[c]

function to_roman(number::Int64)
    0 < number < 4000 || error("must be between 1 and 3999 inclusive")

    parts = Char[]
    while number > 0
        for digit in "MDCLXVI"
            if number >= values[digit]
                push!(parts, digit)
                number -= digit
                break
            end
        end
    end
    join(parts)
end

That also does it, but got me thinking. Couldn't I create the redundant ifs above with metaprogramming? That's something I wanted to learn about anyway and this seems like a not too hard place to wet my feet. But it's also not overly simple, like an unless.

I'm aware that this is not what you use metaprogramming for. It is about the learning experience. Just as nobody needs to compute Fibonacci, but still we all learn to code it in FP.

But I can't even get close:

macro gen(number)
    code = quote
        parts = Char[]
        while $(esc(number)) > 0
        end
    end
    for (i,c) in enumerate("MDCLXVI")
        exp = :(
            if $(esc(number)) >= $(values[c])
                push!(parts, $c)
                $(esc(number)) -= $(values[c])
            end
        )
        if i > 1
            exp.head = :elseif
        end
        # This is not correct anymore because I introduced the while.
        push!(code.args, exp)
    end
    push!(code.args, :(return parts))
    dump(code)
    return code
end

function test(number)
    @gen number
end

test(1111)

This is the best I could do, but then I noticed I need to have the while around (so this code doesn't work). Now I don't even know which .args to append to, because also there are several LineNumberNode nodes in there that shift the important ones around.

I got the feeling, I'm not approaching this from the right angle / am using the right tools.

So the overall question would be “How can I use metaprogramming to abstract away the if chain and redundancy of the primitive example in spirit of the second example?”

Answer 1

Take a break and suddenly, stuff works.

My problem was that I was thinking kind of a top-down approach with manually mutating the .args of an Expr and counting which indices I need from examples and such… Way too manual and complicated.

Coming back to it, I realized I need to go bottom up, starting with the I case as a complete if and then always interpolating what I have so far in the newer, bigger ifs else.

In the end, package it all up in a while and take care of the array, done.

macro generate_ifs(number)
    values = Dict(
        'M' => 1000,
        'C' => 100,
        'X' => 10,
        'I' => 1,
        'D' => 500,
        'L' => 50,
        'V' => 5,
    )
    code = :()
    for c in "IVXLCDM"
        code = :(
            if $(esc(number)) >= $(values[c])
                push!(parts, $c)
                $(esc(number)) -= $(values[c])
            else
                $code
            end
        )
    end
    return quote
        parts = Char[]
        while $(esc(number)) > 0
            $code
        end
        return join(parts)
    end
end

function to_roman(number::Int64)
    0 < number < 4000 || error("must be between 1 and 3999 inclusive")
    @generate_ifs number
end

---

As suggested in the comments, one can do away with the outer while by replaceing the ifs:

macro generate_ifs(number)
    values = Dict(
        'M' => 1000,
        'C' => 100,
        'X' => 10,
        'I' => 1,
        'D' => 500,
        'L' => 50,
        'V' => 5,
    )
    code = :()
    for c in "IVXLCDM"
        code = quote
            while $(esc(number)) >= $(values[c])
                push!(parts, $c)
                $(esc(number)) -= $(values[c])
            end
            $code
        end
    end
    return quote
        parts = Char[]
        $code
        return join(parts)
    end
end

---

Anyway, that's the solution I came up with, I was also able to solve the proper numerals.

I'm still interested in comments and ideas.

Answer 2

The following implementation might be helpful:

const roman_vals = [1000,500,100,50,10,5,1]
const roman_lets = collect("MDCLXVI")
function roman(V)
    r = Char[]
    for (z,c) in zip(roman_lets,roman_vals)
        while c < 2*V
            if c > V
                j = findlast(>=(c-V), roman_vals)
                c <= 2*roman_vals[j] && break
                push!(r, roman_lets[j])
                V += roman_vals[j]
            end
            push!(r, z)
            V -= c
        end
    end
    join(r)
end

Giving:

julia> roman(19)
"XIX"

julia> roman(1890)
"MDCCCXC"