josefrichter

josefrichter

Challenge: Roman numbers parser?

I was looking at recursion, Sasa Juric’s talk on parsers and combinators, and was curious how a parser from roman to arabic numbners could look like (not the other way around, I’ve seen some examples of that here).

I feel like this could be just a 5-10 lines recursive function in elixir, but it’s a bit beyond my skills. In other languages, I’ve seen only kinda “brute force” approaches where the roman number was sliced and compared to some dictionary like “X”: 10, “IX”: 9, etc. I guess there should be a much more elegant way to implement that tricky bit of subtraction logic in roman numbers.

Did anyone try this exercise before? Sounds like a nice job interview question :slight_smile:

Most Liked

idi527

idi527

:waving_hand:

Roman numerals/Decode - Rosetta Code might be interesting for you.

And

  def decode(<<x>>), do: to_value(x)

  def decode(<<h1, h2, rest::bytes>>) do
    case {to_value(h1), to_value(h2)} do
      {v1, v2} when v1 < v2 -> v2 - v1 + decode(rest)
      {v1, _} -> v1 + decode(<<h2, rest::bytes>>)
    end
  end

  def decode(""), do: 0

  defp to_value(?M), do: 1000
  defp to_value(?D), do: 500
  defp to_value(?C), do: 100
  defp to_value(?L), do: 50
  defp to_value(?X), do: 10
  defp to_value(?V), do: 5
  defp to_value(?I), do: 1

if you want to decode binaries instead of lists.

al2o3cr

al2o3cr

You could avoid subtraction entirely and rely on pattern-matching instead:

defmodule RomanParser do
  def parse(input, total \\ 0)

  def parse("M" <> rest, total), do: parse(rest, total + 1000)
  def parse("CM" <> rest, total), do: parse(rest, total + 900)
  def parse("D" <> rest, total), do: parse(rest, total + 500)
  def parse("CD" <> rest, total), do: parse(rest, total + 400)
  def parse("C" <> rest, total), do: parse(rest, total + 100)
  def parse("XC" <> rest, total), do: parse(rest, total + 90)
  def parse("L" <> rest, total), do: parse(rest, total + 50)
  def parse("XL" <> rest, total), do: parse(rest, total + 40)
  def parse("X" <> rest, total), do: parse(rest, total + 10)
  def parse("IX" <> rest, total), do: parse(rest, total + 9)
  def parse("V" <> rest, total), do: parse(rest, total + 5)
  def parse("IV" <> rest, total), do: parse(rest, total + 4)
  def parse("I" <> rest, total), do: parse(rest, total + 1)

  def parse("", total), do: total
end

RomanParser.parse("MMMDXVI")

(nimble_parsec can produce similar code with less typing, fwiw)

Both this solution and the other one up-thread have a similar bug/feature: they accept incorrect numbers and do their best to render them. For instance, "IIIIVM" is parsed to 1006 by both and "IM" is parsed to 1001 by this solution and 999 by the subtraction method.

ityonemo

ityonemo

We have is_map_key/2 guard now!:

defmodule Roman do

  @numerals %{
    "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}

  def parse(<<num::binary-size(2)>> <> rest) when is_map_key(@numerals, num), do: parse(rest) + @numerals[num]
  def parse(<<num::binary-size(1)>> <> rest) when is_map_key(@numerals, num), do: parse(rest) + @numerals[num]
  def parse(""), do: 0

end

Roman.parse("MMMDXVI") #=> 3516
Roman.parse("MMCMVI") #=> 2906

Where Next?

Popular in Discussions Top

jswny
I would like to better understand what the advantages/disadvantages of umbrella applications are compared to structuring your app as as s...
New
PragTob
Hello everyone, I know we had quite some threads (read through lots of them) about background job processing but it remains a hotly deba...
New
axelson
Decided against including more info in the title, but the gist is that Plataformatec sponsored projects will continue with the assets bei...
New
sashaafm
Piggy backing a bit on @dvcrn topic BEAM optimization for functions with static return type?, I’ve been trying to understand in a deeper ...
New
Crowdhailer
I’ve been hearing much about the new formatter and it’s something I have been keen to try. I find examples buy far the most illuminating...
248 19204 150
New
crabonature
I’m still quite new to Elixir. As I understand we got in Elixir “multi guards” as convention to simplify one large guard with or’s?: de...
New
PragTob
Hey everyone, this has been brewing in my head some time and it came up again while reading Adopting Elixir. GenServers, supervisors et...
New
boundedvariable
I am going through the kafka architecture. All the features what the kafka is providing are already in Erlang. I would like hear your opi...
New
hazardfn
I suppose this question is effectively hackney vs. ibrowse but we are at a point in our project where we have to make a choice between th...
New
klo
Got a question about when to concat vs. prepending items to list then reversing to achieve appending. So i know lists boil down to [1 | ...
New

Other popular topics Top

marius95
Hello everyone, I try to use an Javascript Event Handler in my root.html.leex file. Therefore I created a function in the app.js file: ...
New
electic
Hi, I am new to Elixir. I am trying to use the DateTime component to insert a date into MySQL however the there seems to be no way to fo...
New
jerry
Good day to you all. I have been struggling to get a query involving like and ilike to work. Can anyone assist me on this, please? pro...
New
josevalim
Hi everyone, One of the features added to Elixir early on to help integration with Erlang code was the idea of overridable function defi...
New
alice
Hey, Just curious what are the main benefits of Elixir compared to Clojure? When is Elixir more useful than Clojure and vice versa? Th...
New
jason.o
In the code below, if the create action is not set to accept “extra_key” as an input, it errors out with a message shown above. Is there ...
New
dblack
I’ve got an issue with an app and I’ve no idea of how to troubleshoot it. I’m hoping someone here might have seen something similar. I p...
New
boundedvariable
I am going through the kafka architecture. All the features what the kafka is providing are already in Erlang. I would like hear your opi...
New
marick
I had some trouble figuring out how to make many-to-many associations work. Once I got it working, I wrote a blog post. Because I’m a nov...
New
Qqwy
Update: How to use the Blogs &amp; Podcasts section You can post links to your blog posts or podcasts either in one of the Official Blog...
3271 126479 1222
New

We're in Beta

About us Mission Statement