roman-to-integer

Table of Contents

1. Roman Numeral to Integer
   1. Problem Statement
   2. Glossary
   3. Ideation
   4. Ruby Playground
   5. Solution
      1. Create Roman Numeral Symbol hash
      2. Define calculate_numeral_value
      3. Test it out

Roman Numeral to Integer

Problem Statement

From the Operation Code #daily-programmer channel

Roman numerals are represented by seven different symbols:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

We should be able to get the following values (where blank means that roman numeral is invalid)

Numeral	Value
III	3
IV	4
IX	9
MCMXCIV	1994
IIII
IL

Glossary

These are the terms as used in this document

• Symbol - A single letter symbol I, V, etc
• Numeral Increment - A valid combination of symbols to make a single instance that represents a "digit". Eg I, III, IV, V, but not VI

Ideation

Basic ass way of doing this. Start from left to right one symbol at a time. As you process the next symbol several things are possible

• It is the same symbol as prev and there are < 3 in a row - add in that symbol to buffer
• It is the next symbol of higher value from prev and there is only one symbol buffered - Add in value from buffer
• It is a lower value symbol - Add in value from buffer and add symbol to buffer
• It is end - add in value from buffer
• Else - Error

Also, since I have a Ruby interview coming up, lets do this in Ruby

Ruby Playground

I'm not good with ruby so lets play with ruby

How exactly would string destructuring work?

ok, I'm seeing something really odd happen where variables inside of functions are not always always visible in an inner scope. Lets check that out.

define_method Ruby local variable is undefined - Stack Overflow

Solution

Create Roman Numeral Symbol hash

According to the logic in we will need the ability to look up a symbol's value, the next highest symbol, and to look a symbol up by its string char

RomanNumeralSymbol = Struct.new("RomanNumeralSymbol", :symbol, :value, :next)

We can now create instances of this and put them into a roman_numeral_symbols hash like we need

rns = symbol_values.map { |(symbol, value)| RomanNumeralSymbol.new(symbol, value)}
rns.zip(rns.drop(1)).each do |(s, n)| 
  s.next = n
end
roman_numeral_symbols = rns.map { |x| [x.symbol, x] }.to_h

Define calculate_numeral_value

class CannotCreateNumeralError < Error
end

def calculate_numeral_values(numeral, roman_numeral_symbols)
  Enumerator.new do |enum|
    prev_symbol, *other_symbols = numeral.chars
    prev = roman_numeral_symbols[prev_symbol]
    buffer = [prev]

    define_method(:finish_buffer) do
      sum = buffer.map { |s| s.value}.reduce(0, :+)
      buffer.clear
      sum
    end

    other_symbols.each do |symbol_char|
      s = roman_numeral_symbols[symbol_char]
      if prev == s and buffer.length < 3 
        #eg III
        buffer.push s
      elsif prev.value < s.value and buffer.length == 1
        #eg IV
        enum.yield (s.value - prev.value)
        finish_buffer()
      elsif prev.value > s.value
        enum.yield finish_buffer()
        buffer.push s
      else
        p "prev", prev.symbol, "s", s.symbol, "buffer", buffer.map {|x| x.symbol}
        raise CannotCreateNumeralError, "This numeral cannot be processed"
      end
      prev = s
    end
    enum.yield finish_buffer()
  end
end

define_method(:calculate_numeral_value) do |numeral|
  calculate_numeral_values(numeral, roman_numeral_symbols).reduce(0, :+)
end

Test it out

test-numeral-values.map do |(numeral, value)| 
  begin
    calculate_numeral_value(numeral)
  rescue CannotCreateNumeralError
    nil
  end
end

III	3
IV	4
IX	9
MCMXCIV	1994
IIII
IL