Last active
May 18, 2024 15:04
-
-
Save jrandallsexton/c90d4e3471e7e6d322a08aa124478dcb to your computer and use it in GitHub Desktop.
Roman Numeral Conversion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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"); | |
} | |
} | |
} | |
} |
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;
}
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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: