Solving programming challenges with PEDAC Process. Part 4: Roman Numerals
This is the last post of the series Solving programming challenges with PEDAC Process. In this post, I detail how I used PEDAC to write code that converts Hindu-Arabic numerals (integers) up to 3000 to their Roman numerals equivalent.
What is PEDAC? A brief introduction.
Problem Description
The Romans were a clever bunch. They conquered most of Europe and ruled it for hundreds of years. They invented concrete and straight roads and even bikinis. One thing they never discovered though was the number zero. This made writing and dating extensive histories of their exploits slightly more challenging, but the system of numbers they came up with is still in use today. For example the BBC uses Roman numerals to date their programmes.The Romans wrote numbers using letters - I, V, X, L, C, D, M. (notice these letters have lots of straight lines and are hence easy to hack into stone tablets). 1 => I
10 => X
7 => VIIThere is no need to be able to convert numbers larger than about 3000. (The Romans themselves didn't tend to go any higher)Wikipedia says: Modern Roman numerals ... are written by expressing each digit separately starting with the left most digit and skipping any digit with a value of zero.To see this in practice, consider the example of 1990. In Roman numerals 1990 is MCMXC:1000=M
900=CM
90=XC2008 is written as MMVIII:2000=MM
8=VIII
Part I: Understanding the Problem
Input is a number in Hindu-Arabic numeral system. The one obvious input format, given the examples in problem description, is Integer. The first question that popped in my mind was: “Is a string of integer, e.g "1024" considered a valid input?”
I would definitely ask that question if I were at a job interview. For the purpose of this post, I assume a string of integer is a valid input.
Other potential questions:
- What should be the program’s output if the input is zero since there is no zero representation in Roman Numerals? Should it be considered a bad input? What about negative numbers?
- How should bad inputs be handled?
I would handle bad inputs (including zero, and negative numbers) by simply returning a phrase "Invalid input”.
I broke down the problem as the following:
input
- an integer or string of integer between 1 and 3000 inclusive
- convert valid inputs to their Roman numerals equivalent - implicit knowledge
- Numbers up to 1000 and their Roman numerals equivalent
1 = I 5 = V 10 = X 50 = L 100 = C 500 = D 1000 = M - Hindu-Arabic to Roman numerals conversion rules
- start with left most digit
- skip any digit with value zero - for a digit between 1 and 3, its Roman equivalent is:
- Roman equivalent of its place value, digit times
examples:
- digit = 3, its place value = 1000s,
Roman equivalent is 'M', 3 times = 'MMM'
- digit = 2, its place value = 1s,
Roman Numeral equivalent is 'I', 2 times = 'II' - digit = 1, its place value = 100s,
Roman Numeral equivalent is 'C', one time = 'C' - if a digit is 4, or 9, its Roman equivalent is:
- Roman equivalent of its place value,
prepended to Roman equivalent of (digit + 1) * place value examples
4
place value of 4 = 1
Roman 1 = 'I' and (4 + 1) * 1 = V
4 = I prepended to V = IV
400
place value of 4 = 100
Roman 100 = 'C' and (4 + 1) * 100 = 'D'
400 = 'C' prepended to 'D' = 'CD' 9
place value of 9 = 1
Roman 1 = 'I' and (9 + 1) * 1 = 10 = 'X'
9 = 'I' prepended to 'X' = 'IX' 90
place value of 9 = 10
Roman 10 = 'X' and (9 + 1) * 10 = 100 = 'C'
90 = 'X' prepended to 'C' = 'XC' - if a digit is between 6 and 8, its Roman equivalent
Roman 5 prepended to Roman (digit - 5), in digit's place value example
80
place value of 8 = 10,
Roman 5 in 10s place value = 'L',
Roman (8 - 5) in 10s place value = 'XXX'
80 = 'L' prepended to 'XXX' = 'LXXX'output
- return Roman numeral equivalent of the input
Part II: Examples
The following examples were given with the problem as a test suite
console.log(toRoman(1)); // returns 'I'console.log(toRoman(2)); // returns 'II'console.log(toRoman(3)); // returns 'III'console.log(toRoman(4)); // returns 'IV'console.log(toRoman(5)); // returns 'V'console.log(toRoman(6)); // returns 'VI'console.log(toRoman(9)); // returns 'IX'console.log(toRoman(27)); // returns 'XXVII'console.log(toRoman(48)); // returns 'XLVIII'console.log(toRoman(59)); // returns 'LIX'console.log(toRoman(93)); // returns 'XCIII'console.log(toRoman(141)); // returns 'CXLI'console.log(toRoman(163)); // returns 'CLXIII'console.log(toRoman(402)); // returns 'CDII'console.log(toRoman(575)); // returns 'DLXXV'console.log(toRoman(911)); // returns 'CMXI'console.log(toRoman(1024)); // returns 'MXXIV'console.log(toRoman(3000)); // returns 'MMM'
I copied some examples from test suite, and converted inputs into integer strings,
console.log(toRoman('163')); // returns 'CLXIII'console.log(toRoman('402')); // returns 'CDII'console.log(toRoman('575')); // returns 'DLXXV'console.log(toRoman('911')); // returns 'CMXI'console.log(toRoman('1024')); // returns 'MXXIV'console.log(toRoman('3000')); // returns 'MMM'
…and added a few bad inputs:
console.log(toRoman(0)); // returns 'Invalid input'console.log(toRoman(00)); // returns 'Invalid input'console.log(toRoman(-1)); // returns 'Invalid input'console.log(toRoman('1a4')); // returns 'Invalid input'console.log(toRoman([208])); // returns 'Invalid input'console.log(toRoman('0')); // returns 'Invalid input'console.log(toRoman('0000')); // returns 'Invalid input'console.log(toRoman('1,000')); // returns 'Invalid input'console.log(toRoman('2 9')); // returns 'Invalid input'console.log(toRoman(3001)); // returns 'Invalid input'console.log(toRoman(10.24)); // returns 'Invalid input'console.log(toRoman('10.24')); // returns 'Invalid input'
Part III: Data Structure
I needed to extract one digit at a time, which can be achieved by either using remainder operator(%) within a while loop, or I can convert the input number into an array of digit characters and use Array’s built in iterators like map. I chose the latter for the abstractions would lead to a more readable, easy to follow code.
- Array. Turn input number into array of digits or digit characters
- index (position) matters (determines place value)
- map to determine value of each character(digit)
- based on place value/index
- join Roman numerals equivalent of individual digitsalternatively,
- Integer
- reminder operator(%) to get digit & place value- hash/object
- look up table to map digits+place values with Roman equivalents
I will likely be skipping the mental model part sometimes. I prefer to think out, and explain why I’ve chosen a particular data structure, which not only helps me to see the folly of my choices sometimes, but also doubly serve as my mental model.
Part IV: Algorithm
I usually focus on just the “happy path” algorithm, and worry about guard clauses for bad inputs and whatnot once the initial code works. Based on problem break down and data structure, below is the algorithm I came up with.
- create dictionary to translate numbers to Roman symbols
RomanDictionary = {'1': 'I', '5': 'V', ..... '1000': M }- convert input number to string, split it to array of chars, digits- map digits toRomanNum(), join results & return Rom Num string
- toRomNum(digit, idx)
place_value = last_idx - idx
if digit < 4
return toRomanSymbol(place_value) times digit
if digit = 4 or 9
return toRomanSymbol(place_value) +
toRomanSymbol((digit + 1) * place_value)
if digit >= 6 and <= 8
return toRomanSymbol(5 * place_value) +
toRomanSymbol(place_value) times (digit - 5) - toRomanSymbol(integer)
convert integer to string of integer, integer_string
return RomanDictionary[integer_string]
Part V: Code
Following the algorithm part, the initial code I came up with
The above code works for all valid inputs, integers or string integers between 1 and 3000, but either threw an exception, or returned invalid Roman numerals for bad inputs.
I added a guard clause to check for invalid inputs. Below is the algorithm for the guard clause:
1. Check input num for valid types (string or integer)
- for string, check whether its valid
- split into array of chars
- every char must be >= '0' and <= '9'
- if valid string, convert it into an integer - If num is integer(from input, or converted from string above)
- return num > 0 and num <= 3000 - if we reach this point, its a bad input, return false
The resultant code below, after adding guard clause, returns expected outputs for all tested inputs; valid and invalid ones.
That ends this series. Thanks for reading.
Previous post: Using PEDAC process to solve Word Count problem
