roman_numeral_recursion.md

Instructions

1. Fork this gist, then "edit" the gist
2. Fill out the questions below
3. Click the "Add file" button and add your source code to the gist
4. Submit by the due time as instructed in Zoom

Do not publish your code on a public repl.it or repo or other public means.

Prompt

Write a recursive function that converts an integer into a string such that the number is represented in Roman Numerals in the most efficient way. eg, the number 4 could be written as 'IIII' but it's more efficient to use 'IV' since that's a shorter string Assume no number is greater than 4,000 Here are the Roman Numeral equivalents you'll need to know:

• 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

Rewrite the question in your own words:

Write an algorithm that takes an input of an integer, anywhere from 1 to 4,000, and outputs the Roman Numeral version of that number. For example, if the input is 4, the output should be the string "IV".

What assumptions will you make about this problem if you cannot ask any more clarifying questions? What are your reasons for making those assumptions?

For this problem, I will assume that all of the output numerals will be capitals - there will be no non-capital letters. I will also assume that there will be no negative integers involved.

What are your initial thoughts about this problem? (high level design, 2-3 sentences)

Right off the bat, it is clear that this will need to be solved recursively, meaning the function will need to continually call itself to ultimately output the final Roman Numeral.

It also feels like this problem will rely highly on pattern recognition, because it will need to know the general pattern of which numbers correlate to which numbers.

How would you identify the elements of this problem?

• Searching of Data
• Sorting of Data
• Pattern Recognition
• Build/Navigate a Grid
• Math
• Language API knowledge
• Optimization

Which data structure(s) do you think you'll use? What pros/cons do you see with that choice?

For this problem, I will be using strings and numbers. I will also use an array to hold onto all of the base numbers and roman numeral conversions.

Write out a few lines of initial pseudocode: (mid-level design, this should be short, and not be real code!)

// Create an array grid / matrix to define all of the numbers and their conversions to roman numerals. Each array will consist of two indices - the first being the base representative number, and the second being the roman numeral conversion. 
// Loop over this array matrix to convert the integer into the roman numeral. The matrix will go from highest to lowest. 
// If the number passed into the function is greater than the given 0 index within the matrix, it will return the 1 index of that given array, and then call the function again until the number is complete. 
let romanArray = [
  [1000, 'M'], 
  [900, 'CM'], 
  [500, 'D'], 
  [400, 'CD'], 
  ...
]

What do you think the Big O complexity of your algorithm is? (time complexity and space complexity)

I did not get a working solution here. Considering that every time I run the code in the terminal, it says that the maximum call stack has been exceeded, I am assuming that my time complexity is way too high. The space complexity, on the other hand, can't be super high because I'm just storing the romanArray and returning the final output romanNumeral.

JS Starter Code

function toRoman(num) {
  // your code goes here
}

console.log(toRoman(128));  // should return "CXXVIII"
console.log(toRoman(2000)); // should return "MM"
console.log(toRoman(2017)); // should return "MMXVII"
console.log(toRoman(1999)); // should return "MCMXCIX"

Ruby Starter Code

def to_roman(num)
  # your code goes here
end

puts to_roman(128)   # should return "CXXVIII"
puts to_roman(2000)  # should return "MM"
puts to_roman(2017)  # should return "MMXVII"
puts to_roman(1999)  # should return "MCMXCIX"

toRoman.js

let romanArray = [
  [1000, 'M'],
  [900, 'CM'],
  [500, 'D'],
  [400, 'CD'],
  [100, 'C'],
  [90, 'XC'],
  [50, 'L'],
  [40, 'XL'],
  [10, 'X'],
  [9, 'IX'],
  [5, 'V'],
  [4, 'IV'],
  [1, 'I'],
  [0, '']
]


function toRoman(num) {
  if (num < 0) {
    return NaN;
  }
  for (let i = 0; i < romanArray.length; i++) {
    if (num >= romanArray[i][0]) {
      return romanArray[i][1] + toRoman(num - romanArray[i][0]);
    }
  }
}

console.log(toRoman(128));  // should return "CXXVIII"
console.log(toRoman(2000)); // should return "MM"
console.log(toRoman(2017)); // should return "MMXVII"
console.log(toRoman(1999)); // should return "MCMXCIX"