James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1444 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

Little Puzzlers–Positive Integer to Roman Numerals

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

There’s really no “ah-hah!” moment with this problem, but it is still – I find – a good programming problem for seeing how well a candidate’s mind works in structuring logic and finding patterns.

The Problem

Given a positive integer (i.e. > 0), please return a string representation of that integer using Roman Numerals.  You may assume IV for four, though you can optionally use IIII if you prefer the standard clock representation of 4.

Interesting side note: some say that the reason IIII is used instead of IV on clocks is because IV represented the Roman god Jove, and thus was omitted from the clock face to avoid “blasphemy”.

If you’re not familiar with Roman Numerals, you can find a good primer nearly anywhere on the internet (such as here on Wikipedia), though the basics are:

  • I = 1
  • V = 5
  • X = 10
  • L = 50
  • C = 100
  • D = 500
  • M = 1000

Roman numerals are generally written from highest denominate to lowest denomination, except where the previous “unit” letter is used to create 1 of the previous “unit” less than the next. 

  • I can be placed before V and X to make 4 (IV) and 9 (IX) respectively
  • X can be placed before L and C to make 40 (XL) and 90 (XC) respectively
  • C can be placed before D and M to make 400 (CD) and 900 (CM) respectively.

Note that V, L, and D are not used to prefix the next number since this would obviously be redundant (i.e. VX is the same as V, LC is the same as L). 

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

Print | posted on Tuesday, May 5, 2015 2:48 AM |

Feedback

Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

This was one of my co-workers interview questions that I decided to code up recently. It turned out to be easier than I expected.

https://gist.github.com/jimlamb/67071b382f0e0f00fa7b
5/5/2015 4:05 AM | Jim Lamb
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

For an interview it's a good exercice to see how the canditate think bur I also expect the candidate to check if it's not already somewhere in the .NET famework :)

http://referencesource.microsoft.com/#PresentationFramework/Framework/MS/Internal/PtsHost/ListMarkerSourceInfo.cs,67fcfe0e269ca900,references
5/5/2015 4:14 AM | Sam
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

I think that expecting the candidate to know about a rarely-used part of WPF is stretching it a little, let alone taking a dependency on it :-)

I coded this up, TDD-style, way back in 2004: http://blog.differentpla.net/blog/2004/01/12/test-first-roman-numeral-conversion/
5/5/2015 4:52 AM | Roger Lipscombe
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

Here's my take.

https://gist.github.com/anonymous/d4c00418627b0afe5970
5/5/2015 7:17 AM | Stephen
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

Here's a short solution in F#: http://stackoverflow.com/a/18142246/2012417 which coincidentally uses a table based approach in a similar fashion to Roger's TDD based solution in C++.
5/5/2015 7:48 AM | Phillip Trelford
Gravatar

# Mr

Here's my LINQ-based version: https://dotnetfiddle.net/jwWdM0
5/5/2015 8:02 AM | James C-S
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

>X can be placed before L and C to make 40 (XL) and 90 (XC) respectively

That's the reason I have always thought that XML is not valid ;)
5/5/2015 8:04 AM | Philippe
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

@Philippe: Hah! Well played!
5/5/2015 8:55 AM | James Michael hare
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

Yeah, tried this as a TDD kata while learning Scala. Ended up being a surprisingly straightforward classic greedy-selection algorithm.

https://github.com/armstnp/Scala-Kata/blob/72199670338fea63560c4bfd5e425205ec2ca6ad/src/main/scala/RomanNumerals/RomanNumeral.scala#L1-L48
5/5/2015 11:54 AM | Nathan Armstrong
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

@James C-S: That's exactly the Functional LINQy approach I would have taken.
5/5/2015 12:23 PM | Mike C
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

@Mike C, James C-S: Indeed, very nice! Mine is extremely similar in the use of the tables and subtraction.

5/5/2015 12:36 PM | James Michael Hare
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

@James C-S:

One side note, I'd recommend you use an array or ordered dictionary for your table. Yes, it seems that Dictionary currently returns those entries in the same order they were entered, but that's not guaranteed:

http://stackoverflow.com/questions/4007782/the-order-of-elements-in-dictionary
5/5/2015 1:02 PM | James Michael Hare
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

The tory I heard to explain IIII for 4 on clocks, is that, if you add up all the letters needed that way, you get 20 Is, 4 Vs, and 4 Xs. Hence you could have a metal die with an X, a V and 5 Is, and in 4 stamps get all the piece needed.
5/5/2015 2:49 PM | James Curran
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

@James Michael Hare - I've updated to remove the dictionary - https://dotnetfiddle.net/tRvSUM
5/5/2015 10:01 PM | James C-S
Gravatar

# re: Little Puzzlers–Positive Integer to Roman Numerals

Fwiw, I did an implementation of a Roman number type some time ago...
http://realfiction.net/2013/07/26/Exploring-Haskells-type-system-A-Roman-number-type//
I'll go and compare it now :)
5/6/2015 12:51 AM | frank quednau
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: