Roman Numerals Problem - Exercism Elixir Solution & Tutorial

— Last Updated February 25, 2019

Damn! Another 2 hour marathon to solve this problem! 😅💦 The challenge today was to convert integers into a string of Roman Numerals. It was a really interesting problem that pushed my brain and my Elixir skills to the limit. Honestly, I found this one pretty hard and I’m not sure if I missed an easy way to do it! This one is rated as easy on Exercism… I’m getting scared for any that are marked as medium. That being said, I have found that within easy there are problems I can do in 10 minutes and also problems like this, that take me 2 hours+.

My solution to the Phone Number problem on Exercism’s Elixir track

Live solution video

This is my daily live stream video solution to this problem.

Video available here: https://youtu.be/97UtVhJvF00
Also streaming on Twitch: https://www.twitch.tv/percygrunwald

Explanation of the solution

Function to split an integer into the integers that make it up

The idea of this function is to do something like this:

split_integer(123) => [1, 2, 3]
split_integer(456) => [4, 5, 6]

My solution to this problem was to convert the integer into a string, then split up that string into a list of individual characters before parsing each character back into an integer. Something like this:

123 => "123" => ["1", "2", "3"] => [1, 2, 3]

Here’s my solution:

defp split_integer(int) do
  int
  |> Kernel.to_string()
  |> String.split("", trim: true)
  |> Enum.map(fn int_string ->
    Integer.parse(int_string)
    |> case do
      {int, _} ->
        int

      _ ->
        0
    end
  end)
end

Function to multiply each integer in the list by it’s correct order of magnitude

This combines with the previous function to do something like this:

multiply_by_ten_power([1, 2, 3]) => [100, 20, 3]
multiply_by_ten_power([4, 5, 6, 7]) => [4000, 500, 60, 7]

We’ll pass each one of those into the next function in order to get the correct Roman Numeral representation. Here’s my solution:

defp multiply_by_ten_power(int_list) do
  int_list
  |> Enum.with_index(1)
  |> Enum.map(fn {int, index} ->
    ten_factor = :math.pow(10, length(int_list) - index) |> :erlang.floor()

    int * ten_factor
  end)
end

Recursive function to get the integers from a combination of a pool of integers adhering to the rules of Roman Numerals

This is a complex recursive function that is designed to get as input an integer of a particular order of magnitude – i.e. 100, 20 or 3 instead of 123 – and return that number expressed as a list of integers following the rules of Roman Numerals:

100 => [100]
20 => [10, 10]
3 => [1, 1, 1]

The function tries to make the number up out of the pool of integers representing the roman numerals: [1, 5, 10, 50, 100, 500, 1000]. It finds the closest number in the number pool and the difference, then puts the closest number into the accumulator acc and calls itself again if it hasn’t reached the exact value. For example:

Given 100, the function will find 100 in the pool of numbers, the difference is 0 so it’s done, returning [100].
Given 20, the function first finds 10, adds it to acc and calls itself again because the difference between 20 and 10 is 10. The next pass of the function is trying to find 10 and finds it in the pool, returning [10, 10].
Given 3, the function will find 1 in the pool then call itself twice again finding 1 each time, returning [1, 1, 1].

There are some cases when the first number passed to the function will be negative: e.g. 90. The function finds 100 as the closest number from the pool, then calls itself again with -10 as the number to find. Because we’re dealing only with positive numbers, we find the closest positive number, then put it to the left of 100 in the resulting list: [10, 100].

The bulk of the heavy lifting is done by the

defp get_combined_numbers(int, acc \\ {[], 0}) do
  is_negative? = int < 0
  abs_int = :erlang.abs(int)
  number_pool = Map.keys(@int_to_roman_numeral_map)
  {acc_list, last_index_inserted} = acc
  {difference, closest_int} = get_difference_and_closest_int(abs_int, number_pool)

  index_to_insert =
    if is_negative? do
      last_index_inserted - 1
    else
      last_index_inserted + 1
    end

  acc_list = List.insert_at(acc_list, index_to_insert, closest_int)

  if difference == 0 do
    acc_list
  else
    get_combined_numbers(difference, {acc_list, index_to_insert})
  end
end

(very ugly) Function to get the option from a pool with the lowest difference, but adhering to the rules of Roman Numerals

The purpose of this function is to find the closest item in a number pool to the one passed in, but with the crucial difference that it follows the rules of Roman Numerals. For example: if 80 is passed in, the function should return {30, 50} instead of {-20, 100}, even though -20 is the smaller difference. This is because Roman Numerals expects 80 to be represented as LXXX, not XXC. The general rule that this function follows is:

If the difference is negative, the difference must be equal to a single item in the number pool, otherwise choose the item one before the lowest difference.

That is, choose {30, 50} instead of {-20, 100} because -20 cannot be expressed as a single item from the number pool (10 + 10). But in the case of 90, we should choose {-10, 100} instead of {40, 50} because -10 can be made with a single item from the number pool (10).

defp get_difference_and_closest_int(abs_int, number_pool) do
  number_pool_with_differences =
    number_pool
    |> Enum.map(fn int_to_compare ->
      {abs_int - int_to_compare, int_to_compare}
    end)

  {{difference, closest_int}, index} =
    number_pool_with_differences
    |> Enum.with_index()
    |> Enum.min_by(fn {{difference, _int_to_compare}, _index} ->
      :erlang.abs(difference)
    end)

  cond do
    difference == 0 ->
      {difference, closest_int}

    difference > 0 ->
      {difference, closest_int}

    difference < 0 ->
      # 85 => LXXXV
      # 85 => ... ___{35, 50}___, {-15, 100} ...
      #
      # 90 => XVC
      # 90 => ... {40, 50}, ___{-10, 100}___ ...
      abs_difference = :erlang.abs(difference)

      exact_match = Enum.find(number_pool, fn number -> number == abs_difference end)

      if not is_nil(exact_match) do
        {difference, closest_int}
      else
        Enum.at(number_pool_with_differences, index - 1)
      end
  end
end

The main function tying it all together

The function below implements the following data flow:

Split the integer into its parts 2085 => [2, 0, 8, 5]
Multiply by the correct power of 10 depending on position [2, 0, 8, 5] => [2000, 0, 80, 5]
Remove any 0s [2000, 0, 80, 5] => [2000, 80, 5]
Represent each number as the correct numbers from the number pool [2000, 80, 5] => [[1000, 1000], [50, 10, 10, 10], [5]]
Flatten the list [[1000, 1000], [50, 10, 10, 10], [5]] => [1000, 1000, 50, 10, 10, 10, 5]
Map each integer to its corresponding Roman Numeral [1000, 1000, 50, 10, 10, 10, 5] => ["M", "M", "L", "X", "X", "X", "V"]
Join the list of strings into a single string ["M", "M", "L", "X", "X", "X", "V"] => "MMLXXXV"

More succinctly:

2085 => [2, 0, 8, 5] => [2000, 0, 80, 5] => [2000, 80, 5] 
=> [[1000, 1000], [50, 10, 10, 10], [5]] 
=> [1000, 1000, 50, 10, 10, 10, 5] 
=> ["M", "M", "L", "X", "X", "X", "V"] 
=> "MMLXXXV"

And the solution in code:

@int_to_roman_numeral_map %{
  1 => "I",
  5 => "V",
  10 => "X",
  50 => "L",
  100 => "C",
  500 => "D",
  1000 => "M"
}

@doc """
Convert the number to a roman number.
"""
@spec numerals(pos_integer) :: String.t()
def numerals(number) do
  number
  |> split_integer()
  |> multiply_by_ten_power()
  |> Enum.reject(fn int -> int == 0 end)
  |> Enum.map(&get_combined_numbers/1)
  |> List.flatten()
  |> Enum.map(&Map.get(@int_to_roman_numeral_map, &1, ""))
  |> Enum.join()
end

Full solution in text form

Here’s the full solution in text form, in case you want to look over the final product:

defmodule Roman do
  @int_to_roman_numeral_map %{
    1 => "I",
    5 => "V",
    10 => "X",
    50 => "L",
    100 => "C",
    500 => "D",
    1000 => "M"
  }

  @doc """
  Convert the number to a roman number.
  """
  @spec numerals(pos_integer) :: String.t()
  def numerals(number) do
    number
    |> split_integer()
    |> multiply_by_ten_power()
    |> Enum.reject(fn int -> int == 0 end)
    |> Enum.map(&get_combined_numbers/1)
    |> List.flatten()
    |> Enum.map(&Map.get(@int_to_roman_numeral_map, &1, ""))
    |> Enum.join()
  end

  defp split_integer(int) do
    int
    |> Kernel.to_string()
    |> String.split("", trim: true)
    |> Enum.map(fn int_string ->
      Integer.parse(int_string)
      |> case do
        {int, _} ->
          int

        _ ->
          0
      end
    end)
  end

  defp multiply_by_ten_power(int_list) do
    int_list
    |> Enum.with_index(1)
    |> Enum.map(fn {int, index} ->
      ten_factor = :math.pow(10, length(int_list) - index) |> :erlang.floor()

      int * ten_factor
    end)
  end

  defp get_combined_numbers(int, acc \\ {[], 0}) do
    is_negative? = int < 0
    abs_int = :erlang.abs(int)
    number_pool = Map.keys(@int_to_roman_numeral_map)
    {acc_list, last_index_inserted} = acc
    {difference, closest_int} = get_difference_and_closest_int(abs_int, number_pool)

    index_to_insert =
      if is_negative? do
        last_index_inserted - 1
      else
        last_index_inserted + 1
      end

    acc_list = List.insert_at(acc_list, index_to_insert, closest_int)

    if difference == 0 do
      acc_list
    else
      get_combined_numbers(difference, {acc_list, index_to_insert})
    end
  end

  defp get_difference_and_closest_int(abs_int, number_pool) do
    number_pool_with_differences =
      number_pool
      |> Enum.map(fn int_to_compare ->
        {abs_int - int_to_compare, int_to_compare}
      end)

    {{difference, closest_int}, index} =
      number_pool_with_differences
      |> Enum.with_index()
      |> Enum.min_by(fn {{difference, _int_to_compare}, _index} ->
        :erlang.abs(difference)
      end)

    cond do
      difference == 0 ->
        {difference, closest_int}

      difference > 0 ->
        {difference, closest_int}

      difference < 0 ->
        # 85 => LXXXV
        # 85 => ... ___{35, 50}___, {-15, 100} ...
        #
        # 90 => XVC
        # 90 => ... {40, 50}, ___{-10, 100}___ ...
        abs_difference = :erlang.abs(difference)

        exact_match = Enum.find(number_pool, fn number -> number == abs_difference end)

        if not is_nil(exact_match) do
          {difference, closest_int}
        else
          Enum.at(number_pool_with_differences, index - 1)
        end
    end
  end
end

Subscribe to updates from TopTechSkills.com