Converting decimals in Romans using FP
Tags: javascript, functional, programming, coding
Published: 2020-07-06 21:10:41


<span>Photo by <a href="https://unsplash.com/@alschim?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Alexander Schimmeck</a> on <a href="https://unsplash.com/s/photos/romans-numbers?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></span>

Let's explore how we can implement an algorithm that allow us convert a decimal number in it's roman representation. I like functional programming(FP) so also during the implementation I want use common concepts from FP like **pure functions** and **function composition** , so hopefully this also serve as example to show how you can apply FP to problem solving.

We will develop a simple `converter` function that will receive a decimal number as input and output the roman representation of our input, for example:

```js
convert(1679) === 'MDCLXXIX';
```

## Algorithm

Before deep dive in the implementation, let analyze step by step our conversion algorithm. 

First we should know what characters we have available in the roman numeric system and the decimal number that every one of them represent,we have the following set of characters:

> For simplify our converter the algorithm will be for numbers less than `5000`

<center>

| Roman | Decimal |
| ----- | ------- |
| M     | 1000    |
| CM    | 900     |
| D     | 500     |
| CD    | 400     |
| C     | 100     |
| XC    | 90      |
| L     | 50      |
| XL    | 40      |
| X     | 10      |
| IX    | 9       |
| V     | 5       |
| IV    | 4       |
| I     | 1       |

</center>

> As you see I represented some decimals using two letters example `CD`, this is in order to avoid in our algorithm the subtractions that take place in the roman numeric system, think as this 2 characters as a whole that is associated with a decimal value

The next step is for every decimal number try to decompose it as a sum, using only the decimals number exposed previously, we should use the minimum number of operands in our sum, let's see:

![decomposing](https://dev-to-uploads.s3.amazonaws.com/i/em6s87gn1ehlighjd5dz.png)

As we can see, from this decomposition is very straightforward get the roman representation. So this is how our algorithm work, it will go from top to bottom over our available decimals and check if the roman token associated with it should be in our final representation and how many times we should include the respective token.

Our algorithm will build the roman number in an incremental way, for check how many times a specific roman token should be present we use the `/` operator in conjunction with the decimal representation of this token against our input, the `%` operator is used in every step to get the remain that we will use as input when processing the next roman character, as we know an example is worth than thousand words so let see how we can transform `38`:

![processX](https://dev-to-uploads.s3.amazonaws.com/i/gowvy6k9dnqzwbdk46su.png)

![processIX](https://dev-to-uploads.s3.amazonaws.com/i/kiya6roszip03bo8wg46.png)

![processV](https://dev-to-uploads.s3.amazonaws.com/i/r1k2vkhs1nuf0e58j3yn.png)

![processIV](https://dev-to-uploads.s3.amazonaws.com/i/rd4tvp7g9gpcficqutx7.png)

![processI](https://dev-to-uploads.s3.amazonaws.com/i/us8izdor1qstfqgo6ghb.png)
  
At this point we end and Roman = XXXVIII is our initial number represented using roman notation

Note the following in our algorithm:

- We process roman characters from top to bottom staring from M to I.
- In every step we do exactly the same operations (`/` , `concatenation`, `%`) over our arguments.
- We update in every steps our Roman representation concatenating new characters or maybe nothing.
- We update in every step our `input` that will be used in the next step.
- The `/` operation is used to find how many time a specific characters should be included in our representation.
- The `%` operation is used to find the remaining amount that need to be converted.

## Implementation

Now that we saw how the conversion algorithm works let's go through it's implementation.

First I will start implement some utility functions that we will use.

### Divider

As in every step `/` and `%` operations are used let's start implementing a function that help us with this task:

```js
function divider(a, b) {
  return {
    cocient: Math.floor(a / b),
    rest: a % b,
  };
}
```

### Repeat

We need a function that allow us repeat a character a specific amount of times:

```js
const repeat = (times, char) => new Array(times).fill(char).join('');
```

### Pipe

As I mention earlier we will use function composition in the implementation, for this let's use a `pipe` function. With `pipe` we can for example write `g = arg => f2(f1(arg))` as `g = pipe(f1,f2)`, in this example `g` is composed by `f1` and `f2`, the out of `f1` is passed as and argument to `f2`:

```js
const pipe = (...fns) => (arg) => fns.reduce((x, f) => f(x), arg);

/* 
    If you not follow the pipe implementation don't worry 
    just remind that this function serve 
    to pass the output of one function as input to another.
*/
```

Now let's see the implementation, we know that during the conversion we did the same operation in every steps over our input, the only thing different was the roman character and the decimal that is represent. With this in mind let's build a `process` function that receive as arguments a **romanChar** and it's **decimal** representation and return a function `F` that will be responsible to run the conversion algorithm:

```js
function process(romanChar, decimal) {
  /* function to check if our romanChar will we in our final representation */
  return (arg) => {
    /*
        arg:{
          num: decimal number that we are converting
          roman: partial representation of our solution
        }
    */
    const { num, roman } = arg;

    /* num equal 0 imply that there is not anything to transform */
    if (num === 0) {
      return arg;
    }

    /* find how many time we should repeat romanChar and the remain that need to transform */
    const { cocient, rest } = divider(num, decimal);

    /* get the new romans characters */
    const newRomanChars = repeat(cocient, romanChar);

    /* update num as rest and update our actual roman representation concatenating newChars */
    return {
      num: rest,
      roman: `${roman}${newRomanChars}`,
    };
  };
}
```

Ok until this point we have our `process` function that allow us check if a specific roman character should be present in our final transformation for example `const f = process('V', 5)` give us a function `f` that should receive our `arg` object and determine if `V` should be included in our final solution.

The last step is create a converter function composing different function where each one has
only the responsibility to check one character, our transformation will be passed from one function to another.At the end we end with an object which `num` is 0 and `roman` is the full conversion,

```js
const convert = pipe(
  (number) => ({ num: number, roman: '' }),
  process(1000, 'M'),
  process(900, 'CM'),
  process(500, 'D'),
  process(400, 'CD'),
  process(100, 'C'),
  process(90, 'XC'),
  process(50, 'L'),
  process(40, 'XL'),
  process(10, 'X'),
  process(9, 'IX'),
  process(5, 'V'),
  process(4, 'IV'),
  process(1, 'I'),
  ({ roman }) => roman
);
```

Note how our `convert` function receive a number and in the first step(first function) we transform it to our `arg` shape so we can start the conversion, also in the last step we get our `arg` object and extract from it `roman` property with the full conversion.

>Full source code can be found [here](https://github.com/omenlog/articles/blob/master/from-decimals-to-romans-a-functional-way/index.js)

# Conclusions

As we stated at the beginning we used `function composition`, and `pure functions` in the sense that none of our functions rely on side effects, in every step we don't modify our `arg` instead we a create a new object, that will be passed to the next function in our chain.

This example is simple but I hope that it give you some insights on how you can use this concepts in your every day tasks.

This approach to build our `convert` function in a declarative way give us as advantage that is easier adapt to new requirements, for example our `convert` function can be refactored to work with numbers greater than `5000` only adding another call without modify our `process` function.

Thanks for read

If you like this article and want read more from me, you can follow [me](https://twitter.com/omenlog).