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

ricklove
I was just introduced to Elixir and Phoenix. I was told about the 2 million websocket test that was done 2 years ago. From my research, t...
New
rms.mrcs
A couple of days ago I was discussing with a friend about different approaches to write microservices. He said that if he was going to w...
New
MarioFlach
Hello, I want to share a project I’ve been working on for a while: https://github.com/almightycouch/gitgud Background Some time ago I ...
New
jer
I’ve been using umbrellas for a while, and generally started off (on greenfield projects at least) by isolating subapps based on clearly ...
New
Fl4m3Ph03n1x
Background This question comes mainly from my ignorance. Today is Black Friday, one of my favorite days of the year to buy books. One boo...
New
pillaiindu
I want to convert a Phoenix LiveView CRUD website to a CRUD mobile app. What do you think is the easiest way to do so?
New
Rustixir
Hi everyone, im working on find best language/framework/system for high concurrency, high performance and stable performance after wor...
New

Other popular topics Top

rms.mrcs
Hi, I need to transform a list of numbers into a map where the keys are the indexes and the values are the original values of the list. ...
New
KronicDeth
Elixir plugin for JetBrain’s IntelliJ Platform (including Rubymine) This is a plugin that adds support for Elixir to JetBrains IntelliJ...
289 36689 110
New
baxterw3b
Hi guys, i’m new in the Elixir world, and i have to say, that i love it! i’m having some problem to understand anonymous functions with ...
New
shijith.k
I am trying to start a new phoenix project with elixir 1.9, but mix phx.new does not work. It says that ** (Mix) The task "phx.new" could...
New
SoCreat
i’m a new one to elixir which editor can i use vs code? or atom? Thanks! :smiley:
New
Harrisonl
We have an ECS cluster with 4 services, where each task joins a single cluster, via discovery ECS discovery service. Currently when I de...
New

We're in Beta

About us Mission Statement