I’m now well over a week behind with these challenges, so it’s Thursday of week 5, but we’re just finishing up week 4. Part of the issue is I’m quite bust, but part of the issue is that I am trying to use this as an opportunity to learn elixir, and I’m doing the elixir learning track. This means that the exercises are locked until I do the relevant learning exercises that teach the concepts. Elixir has quite an extensive learning track, and this exercise is quite far down the tree, so I actually had to do quite a few learning exercises to unlock it.

This was a fun one, and I took my time to make three different(ish) solutions. This week’s challenge was Roman Numerals: turn a number into a roman numeral.

Elixir

The simplest of my solutions was one I did in Elixir.

defmodule RomanNumerals do
  @doc """
  Convert the number to a roman number.
  """
  @spec numeral(pos_integer) :: String.t()
  def numeral(number) do
    _numeral(number,[])
  end
  def _numeral(number, acc) do
    case number do
      number when number >= 1000 -> _numeral(number - 1000, acc ++ ~c"M")
      number when number >= 900 ->  _numeral(number - 900,  acc ++ ~c"CM")
      number when number >= 500 ->  _numeral(number - 500,  acc ++ ~c"D")
      number when number >= 400 ->  _numeral(number - 400,  acc ++ ~c"CD")
      number when number >= 100 ->  _numeral(number - 100,  acc ++ ~c"C")
      number when number >= 90 ->   _numeral(number - 90,   acc ++ ~c"XC")
      number when number >= 50 ->   _numeral(number - 50,   acc ++ ~c"L")
      number when number >= 40 ->   _numeral(number - 40,   acc ++ ~c"XL")
      number when number >= 10 ->   _numeral(number - 10,   acc ++ ~c"X")
      number when number >= 9->     _numeral(number - 9,    acc ++ ~c"IX")
      number when number >= 5 ->    _numeral(number - 5,    acc ++ ~c"V")
      number when number >= 4 ->    _numeral(number - 4,    acc ++ ~c"IV")
      number when number > 0 ->     _numeral(number - 1 ,   acc ++ ~c"I")
      0 -> to_string(acc)
      _ -> "NOPE"
    end
  end
end

Nothing much to explain here: if the number is big enough, append the relevant characters to the acc (accumulator) then recursively call the function with the modified acc and the smaller number. ~c"XYZ" is how elixir creates a list of characters (which elixir distinguishes from strings). The function passes around a pair of (number, acc) until number is 0, and then it just returns acc, the string. (This kind of ambiguity in return type is something that a language haskell would not appreciate).

One issue with this approach is that, as the number gets smaller, the recursive calls to _numeral still runs through all the checks. But if you work through how it works, number only ever gets smaller, so if the number >= x check is false, it will be false on all future recursive calls to _numeral.

The other issue is that there’s a lot of repetitious code here. In essence, we have a dozen or so lines that are all doing the same thing, just with a different number to check against, and a different character list to add to the accumulator.

Can we do better? That very much depends what you mean by better, but I decided to haskell-brain my way to a solution that is no shorter, probably no more efficient, but does not have either of the two specific defects I mentioned above.

Haskell

Here it is:

module Roman (numerals) where

type FunctionGen = (Integer, String)
type NumeralAccumulator = (Integer, String)

multiply :: (Integer, String) -> FunctionGen -> FunctionGen
multiply (multiplier , string_multiples) (number,roman_num) = (multiplier * number, map (character_multiply string_multiples) roman_num)
  where character_multiply (s:_) 'I' = s 
        character_multiply (_:s:_) 'V' = s
        character_multiply (_:_:s:[]) 'X' = s

numerals_list :: [FunctionGen]
numerals_list = units ++ tens ++ hundreds ++ thousands
  where units = [ (1, "I"), (4, "IV"), (5, "V"), (9, "IX") ]
        tens  = map (multiply (10, "XLC")) units
        hundreds = map (multiply (100, "CDM")) units
        thousands = map (multiply (1000, "MZZ")) units

function_creator :: FunctionGen -> NumeralAccumulator -> NumeralAccumulator
function_creator (number, roman_number) (remainder, accumulator) 
  | remainder >= number = until (\(x, _) -> x < number) (\(x, y) -> (x - number, y ++ roman_number)) (remainder, accumulator)
  | otherwise = (remainder, accumulator)

function_list :: [NumeralAccumulator -> NumeralAccumulator]
function_list = map function_creator numerals_list

numerals :: Integer -> Maybe String
numerals n = Just . snd $ foldr (.) id function_list $ (n,"")

Let’s start at the bottom and work backwards. We’re taking a similar approach of having a function that takes a number and an accumulator (string) and, if the number is big enough, appends something to the accumulator and returns a new number and the new accumulator. The haskell version wants the output to be Maybe String, so we take the second element of the output pair and wrap it in a Just: that’s what the Just . snd is about. The . is just function composition. Unlike the elixir solution, however, we are composing functions rather than using recursion. So we get a list of functions (one function that checks if number is bigger than 1000 and if so appends M to acc, one that checks 900 and appends CM etc etc) and we use foldr (.) to create one function that composes the whole list of functions together. Other languages sometimes call foldr “reduce” or similar. (Haskell has several different kinds of folding we don’t need to get into which of these corresponds to reduce in some other language). Now, function composition is a two-place function, and thus something that can be used in foldr. The starting accumulator for this fold is the identity id. So foldr (.) id [f,g,h] is going to give us f . g . h. Or, more carefully, f . (g . (h . id)). For this to work, you need the input and output types of the functions to match up (h’s output is g’s input etc). In our case, this works because the input and output types of all the functions is going to be the same: NumeralAccumulator.

Now we just want to create our list of functions. Each function is the same, it just depends on two parameters, the number to check against, and the string to append if the input is bigger than the number. This pair of parameters is gathered together in FunctionGen. So there’s two things we need to do: create the list of pairs of parameters, and turn each parameter pair into a function.

It’s probably worth explaining at this point why I have two type synonyms for the same type at the top. So FunctionGen and NumeralAccumulator are both synonyms for (Integer, String), why define both? The point is that FunctionGen and NumeralAccumulator use their String and their Integer for different purposes. For NumeralAccumulator, as we’ll see, the Integer is the remaining value of the number that hasn’t been converted into Roman numerals yet, and the String is the accumulated characters of the converted number. For FunctionGen, the Integer is the value that the function will check its input against, and the String is the string to append if the check passes. This is also a way to use code instead of comments. If you look at the type signature for function_creator (repeated below), for example, without the type synonyms, this would just be (Integer, String) -> (Integer, String) -> (Integer, String) and it would be harder to figure out what it’s doing. But since we’re using type synonyms we can see that the first parameter is to be treated as a FunctionGen and the second is a NumeralAccumulator. And since the function is called function_creator, and its first argument is called FunctionGen, we have some inkling that this is going to be partially applied to create functions. So we pass in a FunctionGen and get as output a function from NumeralAccumulator to NumeralAccumulator.

For creating a list of functions, we can use the same trick I’ve used before, map a two-argument function over a list of parameters (a list of the type of the first argument), to get a list of functions. Using some symbols, take a function a -> b -> c and map it over a list of a to get a list of functions b -> c. That’s what function_list is doing. The remaining work is to generate the list of parameters, and to write the function that turns a parameter into a function.

function_creator :: FunctionGen -> NumeralAccumulator -> NumeralAccumulator
function_creator (number, roman_number) (remainder, accumulator) 
  | remainder >= number = until (\(x, _) -> x < number) (\(x, y) -> (x - number, y ++ roman_number)) (remainder, accumulator)
  | otherwise = (remainder, accumulator)

Let’s take function generation – function_creator – first. So, as we said, this is a function that takes a FunctionGen and returns a function from NumeralAccumulator to NumeralAccumulator. But what we’re actually going to do is write a function that takes a FunctionGen and a NumeralAccumulator and returns a NumeralAccumulator but it’s then just going to be partially applied to return the function. So function_creator takes its two arguments, and uses pattern matching to break down both arguments into the component integers and strings. Then the function basically does what a single line of the elixir _numeral function did: check if remainder >= number, and if it is append roman_number to accumulator. But there is one important wrinkle here.

In the elixir code, consider what happens with the number 2. That is, consider _numeral(2, []). It drops down to the number when number > 0 line, and thus calls _numeral(2 - 1, [] ++ ~c"I"). This recursive call also drops down to the same line on the elixir code which thus calls _numeral(0, ~c"II") which outputs "II". Now with the haskell code, we aren’t using recursion, we are composing the functions, so the function generated from (1, "I") has to handle turning 2 into "II" and 3 into "III" in one pass. That’s why we are using until. Now, until p f x keeps doing f to x until p x is true. That is, it checks p x and if it’s false, it does f x. Then it checks if p (f x) and if it’s false it does f (f x). And so on. That is, it passes the value to both p and f and if p returns false, do the same thing with the output, otherwise return the output of f. So the until line in the above code is a bit horrible because each of those f and p functions are lambdas (anonymous functions). The p in this context is (\(x, _) -> x < number) which checks if the number is less than x, and the f is \(x, y) -> (x - number, y ++ roman_number) which takes the number away from x and appends roman_number to the y. So let’s do:

until (\(x, _) -> x < 1) (\(x, y) -> (x - 1, y ++ "I")) (2, "")

Let’s do the check from the first function, (\x, _) -> x < 1) on input (2, ""): well the first thing we do is throw away the second parameter (_ in the lambda) and we check if 2 < 1. It is not, so let’s do \(x, y) -> (x - 1, y ++ "I") to input (2, ""): this returns (1, "I"). Now, since the check was false, we do it all again with the new input. Do (\x, _) -> x < 1) on input (1, "I"): again, false. Do \(x, y) -> (x - 1, y ++ "I") to input (1, "I"): (0, "II"). The check was false so we do it all again: Do (\x, _) -> x < 1) on input (0, "II"): true! So we return (0,"II"). We need to do this for (10, "X"), (100, "C") and so on. But, importantly, it doesn’t matter if we also do it for, for example (5,"V") because the until check will always be true on the second pass at most, so we’ll never get repeats of "V" or "L". (Why this is so is left as an exercise for the reader).

So now we have a function that turns a FunctionGen – a pair of an Integer and a String – into a function from NumeralAccumulator to NumeralAccumulator. Now all we need to do is generate the list of FunctionGen values we need to pass in to make function_list. I could, at this stage, just write out all the pairs [(1, "I"), (4, "IV"), (5, "V"), (9, "IX")] etc etc. But instead I decided to produce that list by exploiting the patterns in the list (why am I like this?). Notice that, given the work that the until is doing providing us with repeats, we need functions for 1, 4, 5, 9 and then we need 10, 40, 50, 90. And the pattern of characters is the same, even if the characters themselves are different. That is, the value for 4 is the value for 1 followed by the value for 5, and the value for 40 is the value for 10 followed by the value for 50. So the values for the tens can be filled in by just replacing I, V, X with X, L, C; and likewise the hundreds can be generated by using replacements C, D, M. As for the thousands, the exercise says we only need to go up to 3999, so there’s no need to figure out a symbol for 4000 or 5000, but we can replace I by M to handle thousands. So using the FunctionGen list called units – [(1, "I"), (4, "IV"), (5, "V"), (9, "IX")] – we can generate the other function_creator parameters we need by multiplying the integers by the relevant power of ten and replacing the characters by their counterparts as described above. So that’s what the multiply function does:

multiply :: (Integer, String) -> FunctionGen -> FunctionGen
multiply (multiplier , string_multiples) (number,roman_num) = (multiplier * number, map (character_multiply string_multiples) roman_num)
  where character_multiply (s:_) 'I' = s 
        character_multiply (_:s:_) 'V' = s
        character_multiply (_:_:s:[]) 'X' = s

numerals_list :: [FunctionGen]
numerals_list = units ++ tens ++ hundreds ++ thousands
  where units = [ (1, "I"), (4, "IV"), (5, "V"), (9, "IX") ]
        tens  = map (multiply (10, "XLC")) units
        hundreds = map (multiply (100, "CDM")) units
        thousands = map (multiply (1000, "MZZ")) units

We use it to map over the units list to generate the rest of the FunctionGen parameters we need. It takes a number to multiply by (a power of ten) and a string that represents the substitutions that need doing, and it outputs the modified FunctionGen. So multiply (10, "XLC") (1,"I") will output (10, "X"). The 1 has been multiplied by 10, and the "I" has been transformed into "X" through the magic of map (character_multiply "XLC") "I". The inputs to character_multiply are chars not strings, but in haskell, unlike elixir, a string just is a list of chars. So mapping character_multiply over a string just performs that function on each character in the string.

And we’re done. Putting it all together, we generate numerals_list through the use of multiply to create the tens, hundreds and thousands lists out of the units list and we concatenate them all together. We use that list to generate a list of functions using function_creator, we compose all those functions together into one big function that takes a number and a string (we pass in the empty) string, and that function adds to the string, and subtracts from the number until the number is 0 and the string corresponds to the roman numeral of the number we started with. Does this method have any virtues over the elixir method? Not especially, but it was fun getting it pieced together.

JavaScript

Both of these methods, however, are infinitely better than the Programming Crime I created in JavaScript.

const UNITS = "IVX" 
const TENS = "XLC" 
const HUNDREDS = "CDM" 
const THOUSANDS = "MZZ"
const NUMERALS = [UNITS, TENS, HUNDREDS, THOUSANDS]
const PATTERNS = ["", "0", "00", "000", "01", "1", "10", "100", "1000", "02", "2"]
export const toRoman = (n) => {
  return n.toString().split("").reverse()
    .map((c,i) => PATTERNS[parseInt(c)].split("")
      .map(x => NUMERALS[i].split("")[parseInt(x)]).join(""))
    .reverse().join("");
};

Again, we’re using that idea that there’s a pattern to roman numerals. Multiplying something by 10 is simply to replace each I with a X, each V with a L and so on. So the pattern for the numbers 10, 20, 30 and so on reiterates the pattern for numbers 1, 2, 3 but with different characters. So instead of taking the input to be a number, let’s just take the input to be the string representation of that number. Let’s map each numeral 0, 1, 2 etc to a pattern, the pattern of the roman numeral representation of it. Then all we need to do is figure out the position of this character in the string to figure out which characters to use in filling out the pattern for that numeral. So take the number 14. Treat it as a string. Turn each character into the pattern for that character: 1 becomes 0, 4 becomes 01. Then, taking into account the position of the character, map the pattern to a string. So the 1 is in the tens column, so map 0 to X. The 4 is in the units column so 01 maps to IV. If the 4 had been in the tens column, 01 would have mapped to XL. That’s all there is to it, turn a number into a string, into a pair of a pattern and a column, and then map the pattern and column into a string. Concatenate the strings and we’re done. But, instead of writing it out normally, let’s use nested array maps, several reverse operations and let’s also actually make use of a javascript feature that normally trips me up instead of being useful.

Let’s do this line by line. So:

  return n.toString().split("").reverse()

Take a number, turn it into a string, turn the string into a list of characers, and reverse it so that the units are index 0, the tens are index 1 etc. This means we don’t have to mess about with figuring out the index of the units column from the length of the string blah blah. Yes it’s an expensive way of avoiding some fairly simple maths. Sue me. So if we passed in 291, at this intermediate stage, that would have been turned into ['1', '9', '2'].

    .map((c,i) => PATTERNS[parseInt(c)].split("")

Take that list of strings (characters, I don’t think javascript makes a distinction) and map each one to… something. But wait, the function we pass in to map has two parameters. The first is the character from the array we got above, and the second is the index of that element in the array. So we take the first parameter c, we treat it as a number, and use it as the index to PATTERNS. And then we turn that string – the elements of PATTERNS are strings – into a list of characters. So PATTERNS[1] = "0" and thus we map 1 to ["0"], 9 gets mapped to ["1", "2"], and 2 gets mapped to ["0", "0"]. Or, more carefully, we map (1,0) to ["0"], we map (9,1) to ["1", "2"] and (2, 2) to ["0", "0"].

      .map(x => NUMERALS[i].split("")[x]).join(""))

We’re still inside that map, so we are mapping each of ["0"], ["1", "2"], and ["0", "0"]. And this is where we use that second parameter i above. We use i to pick out the correct units for our translation. NUMERALS is a list of strings. Each string in NUMERALS provides the information for how to turn a pattern into the roman numeral string for that pattern. And each string in NUMERALS corresponds to a column in the number. So the first element of NUMERALS is the UNITS which converts 0 into I, 1 into V and so on. and the second is the TENS column, which converts 0 into X, 1 into L and so on. The UNITS string – IVX – is used to do this conversion in the following way: we split("") it into a list, and then use the values in the pattern to pick out the element of that list by index. So a "0" gets mapped to UNITS[0] which is "I". The list of characters then gets turned into a string using join(""). As I’m explaining this, I realise that javascript has silently coerced these strings into numbers to use as indices to an array. It would probably have been safer to use parseInt(x) in place of x here. And that certainly would have been necessary if we had had to do any index maths (if I hadn’t reversed the list to make UNITS be index 0, for example). So our (1,0) uses UNITS to map the pattern to "I", and (9,1) becomes "XC" using TENS and (2,2) gets mapped – using HUNDREDS – to "CC". That extra parenthesis at the end means that we’re now done with both the inner and the outer map.

        .reverse().join("");

Finally, we reverse the list back, so the bigger numbers are to the left, and then we join the parts together. So we get "CCXCI", which is, indeed, 291 in roman numerals.

Now, this works, but it’s horrible to look at, difficult to parse, and I’m just sorry I made you look at it. It does, at least, demonstrate a quite different way to approach creating roman numerals as compared to the elixir and haskell solutions.

Stay tuned for more javascript crimes and haskell-brain next week!