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 ![]()
Most Liked
idi527
![]()
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
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
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
Popular in Discussions
Other popular topics
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #javascript
- #code-sync
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #advent-of-code
- #elixirconf-us
- #distillery
- #processes
- #forms
- #api
- #metaprogramming
- #security
- #performance








