Roman Numeral Conversion

RomanNumeralConverter.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Order;

using System;
using System.Collections.Generic;
using System.Linq;

namespace BackToSchool.CSharp.Misc
{
    /// <summary>
    /// Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
    /// Symbol       Value
    /// I             1
    /// V             5
    /// X             10
    /// L             50
    /// C             100
    /// D             500
    /// M             1000
    /// For example, 2 is written as II in Roman numeral, just two ones added together.
    /// 12 is written as XII, which is simply X + II.
    /// The number 27 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.
    /// Example 1:
    /// Input: s = "III"
    /// Output: 3
    /// Explanation: III = 3.
    /// 
    /// Example 2:
    /// Input: s = "LVIII"
    /// Output: 58
    /// Explanation: L = 50, V= 5, III = 3.
    /// 
    /// Example 3:
    /// Input: s = "MCMXCIV"
    /// Output: 1994
    /// Explanation: M = 1000, CM = 900, XC = 90 and IV = 4
    /// </summary>
    public class RomanNumeralConverter
    {
        private readonly char[] _validChars =
        [
            'I',
            'V',
            'X',
            'L',
            'C',
            'D',
            'M'
        ];

        /// <summary>
        /// need to capture the "gotchyas" (i.e. 4 == IV != IIII, etc)
        /// from above:
        /// IV => 4
        /// IX => 9
        /// XL => 40
        /// XC => 90
        /// CD => 400
        /// CM => 900
        /// </summary>
        private readonly Dictionary<string, int> _gotchyas = new Dictionary<string, int>()
        {
            { "IV", 4 },
            { "IX", 9 },
            { "XL", 40 },
            { "XC", 90 },
            { "CD", 400 },
            { "CM", 900 },
        };

        private readonly Dictionary<char, int> _romanValues = new Dictionary<char, int>()
        {
            { 'I', 1},
            { 'V', 5},
            { 'X', 10},
            { 'L', 50},
            { 'C', 100},
            { 'D', 500},
            { 'M', 1000},
        };

        public int ToRoman(string roman)
        {
            var allChars = roman.ToArray();

            var left = 0;
            var right = 1;
            var sum = 0;
            var maxLeft = allChars.Length;

            while (left < maxLeft)
            {
                // look at the left
                var leftChar = allChars[left];

                if (!_validChars.Contains(leftChar))
                    return 0;

                var rightChar = (maxLeft - 1 == left) ? leftChar : allChars[right];

                // are we in a subtraction scenario?
                var pair = left == right ? string.Empty : $"{leftChar}{rightChar}";

                if (_gotchyas.TryGetValue(pair, out var gotchya))
                {
                    sum += gotchya;
                    left = right + 1;
                    right = left + 1;
                }
                else
                {
                    sum += _romanValues[leftChar];
                    left++;
                    right++;
                }
            }

            return sum;
        }

        public int ToRomanAsSpan(string roman)
        {
            var allChars = roman.ToArray().AsSpan();

            var left = 0;
            var right = 1;
            var sum = 0;
            var maxLeft = allChars.Length;

            while (left < maxLeft)
            {
                // look at the left
                var leftChar = allChars[left];

                if (!_validChars.Contains(leftChar))
                    return 0;

                var rightChar = (maxLeft - 1 == left) ? leftChar : allChars[right];

                // are we in a subtraction scenario?
                var pair = left == right ? string.Empty : $"{leftChar}{rightChar}";

                if (_gotchyas.TryGetValue(pair, out var gotchya))
                {
                    sum += gotchya;
                    left = right + 1;
                    right = left + 1;
                }
                else
                {
                    sum += _romanValues[leftChar];
                    left++;
                    right++;
                }
            }

            return sum;
        }
    }

    [MemoryDiagnoser]
    [Orderer(SummaryOrderPolicy.FastestToSlowest)]
    [RankColumn]
    public class RomanNumeralConverterBenchmarks()
    {
        private static readonly RomanNumeralConverter _sut = new();
        private const int RepetitionCount = 100_000;

        [Benchmark(Baseline = true)]
        public void ToRoman()
        {
            for (var i = 0; i < RepetitionCount; i++)
            {
                _sut.ToRoman("MCMXCIV");
            }
        }

        [Benchmark]
        public void ToRomanAsSpan()
        {
            for (var i = 0; i < RepetitionCount; i++)
            {
                _sut.ToRomanAsSpan("MCMXCIV");
            }
        }
    }
}

Tests:

using BackToSchool.CSharp.Misc;

using FluentAssertions;

using Xunit;

namespace BackToSchool.CSharp.Tests.Misc
{
    public class RomanNumeralConverterTests
    {
        RomanNumeralConverter _sut = new RomanNumeralConverter();

        [Theory]
        [InlineData("III", 3)]
        [InlineData("IV", 4)]
        [InlineData("", 0)]
        [InlineData("LVIII", 58)]
        [InlineData("MCMXCIV", 1994)]
        [InlineData("AAABBB", 0)]
        public void ToRoman_TestCases(string roman, int expectedInt)
        {
            // arrange

            // act
            var result = _sut.ToRoman(roman);

            // assert
            result.Should().Be(expectedInt);

        }
    }
}

I only made minor changes to the code - just enough to show my usage of Benchmark.Net and my approach for finding the optimal solution with regards to both|and/or runtime and memory.

( not the expectation that i had - but that's why i use the tool. i could definitely do a better job with more time. )

p.s. I still have yet to dig into LanguageExt. Curious to see if there is a functional approach to this. Will check it out.

So, while hanging at the pool with my son, I had the thought: Roman numerals don't really get that big. Perhaps I could just do a brute force on it and see what happens:

Here is the code (Benchmark.net to follow). I'll bet I can make it even faster. In this case, the brute force might actually be best.

        public int ToRoman_NaiveBruteForce(string roman)
        {
            // just do a string replacement
            foreach (var romanChar in roman)
            {
                if (!_romanValues.ContainsKey(romanChar))
                    return 0;
            }

            var values = new List<int>();

            foreach (var foo in _gotchyas)
            {
                while (roman.Contains(foo.Key))
                {
                    values.Add(_gotchyas[foo.Key]);
                    roman = roman.Replace(foo.Key, string.Empty);
                }
            }

            foreach (var letter in roman)
            {
                values.Add(_romanValues[letter]);
            }

            return values.Sum();
        }

So while having coffee this morning, I decided to take another stab at it. Knew there was an even better way.

This time I took a linear approach and defined the triggering conditions. Used a List to keep a track of all values. If I found the triggering condition, perform subtraction on the last entry and current value.

Code here:

        public int ToRomanLinear(string roman)
        {
            var romanSpan = roman.AsSpan();
            var values = new List<int>();

            char? prev = null;
            char current;

            for (var i = 0; i < romanSpan.Length; i++)
            {
                current = romanSpan[i];

                if (!_validChars.Contains(current))
                    return 0;

                if (prev == null)
                {
                    values.Add(_romanValues[current]);
                    prev = current;
                    continue;
                }

                _triggers.TryGetValue(current, out char triggerValue);
                if (triggerValue == prev)
                {
                    // just update the lastmost entry in values
                    values[^1] = _romanValues[current] - values[^1];
                }
                else
                {
                    values.Add(_romanValues[current]);
                }

                prev = current;

            }

            return values.Sum();
        }

Performance is superior to everything else

One last update. Made a couple of changes to the linear approach . used a span for char validation

        public static int ToRomanLinearAlt(string roman)
        {
            var romanSpan = roman.AsSpan();
            var validCharsSpan = _validChars.AsSpan();

            var values = new List<int>();
            
            char? prev = null;

            var max = romanSpan.Length;
            for (var i = 0; i < max; i++)
            {
                var current = romanSpan[i];

                if (!validCharsSpan.Contains(current))
                    return 0;

                if (i == 0)
                {
                    values.Add(_romanValues[current]);
                    prev = current;
                    continue;
                }

                _triggers.TryGetValue(current, out char triggerValue);
                if (triggerValue == prev)
                {
                    // just update the lastmost entry in values
                    values[^1] = _romanValues[current] - values[^1];
                }
                else
                {
                    values.Add(_romanValues[current]);
                }

                prev = current;

            }

            return values.Sum();
        }

ok. this is absolutely the FINAL update on this gist. I simply cannot leave well-enough alone.

        public static int ToRomanLastShot(string roman)
        {
            var romanSpan = roman.AsSpan();

            var romanCharsSpan = _romanChars.AsSpan();
            var romanValuesSpan = _romanVals.AsSpan();

            var triggerCharsSpan = _triggerChars.AsSpan();
            var triggerValuesSpan = _triggerVals.AsSpan();

            var sum = 0;

            char? prev = null;
            var prevValue = 0;

            var max = romanSpan.Length;
            for (var i = 0; i < max; i++)
            {
                var current = romanSpan[i];

                var romanCharIndex = romanCharsSpan.IndexOf(current);
                if (romanCharIndex < 0)
                {
                    return 0;
                }

                var romanValue = romanValuesSpan[romanCharIndex];

                if (i == 0)
                {
                    sum += romanValue;
                    prev = current;
                    prevValue = sum;
                    continue;
                }

                // Does this character have a trigger?
                var triggerCharIndex = triggerCharsSpan.IndexOf(current);

                if (triggerCharIndex > -1)
                {
                    // yes, it does
                    // get the value for the trigger
                    var triggerValue = triggerValuesSpan[triggerCharIndex];

                    if (triggerValue == prev)
                    {
                        // perform subtraction to update the sum
                        sum += (romanValue - prevValue) - prevValue;
                        prev = current;
                        prevValue = romanValue;
                        continue;
                    }
                }

                prevValue = romanValue;
                sum += prevValue;
                prev = current;

            }

            return sum;
        }

Performance becomes even more pronounced at 10,000,000 iterations:

At this point, I can honestly say that I have exhausted all options known to me. With that said: I did NOT consult external sources for this exercise. Perhaps there is a purely-mathematical way of achieving this.

Now that I am really and truly done - think I'll go Google what the "real" answer is.

Thanks for your time.

Regards,
Randall

Well, I did not have the fastest version. Found some code on SO that made mine pale. https://stackoverflow.com/a/45064346/403890