Римские числа или как не запоминать составные варианты

Откройте почти любую реализацию перевода чисел из арабской системы в римскую и вы почти со 100% вероятностью увидите там знаменитые дифтонги «CM» (900), «CD» (400) и так далее. И поначалу кажется, что без них не обойтись. Но это не так!

На самом деле, без них можно обойтись и за этим процессом стоит достаточно простая, красивая математика. О чем я хочу рассказать сегодня.

Немного правил и объяснений

Если в какой-то момент осознать, что уникальных чисел в римской нумерации всего 3, то все становится немного проще:

1. «I»

2. «V»

3. «X»

Все остальное получается их комбинацией и домножением на по правилу off by one. Например, «CM» это всего лишь «IX» , то есть умножение происходит на ту степень, в какой позиции мы ожидаем это число увидеть в арабской записи. Причем, поскольку запись «IX» равнозначна «10 — 1», то при умножении эти скобки можно раскрыть: «I» «C», «X» «M» и составить в той же последовательности.

Это крайне простой трюк, но в этом и сложность – увидеть эту закономерность и понять, как её реализовать.

Взглянем на код

Сначала определим наши константы чисел в обеих нумерациях

const integers = [1000, 500, 100, 50, 10, 5, 1] const literals = 'mdclxvi'  const arabicToRomanMap = new Map(integers.map((int, index) => [int, literals[index]]))

А затем реализуем конвертер

function toRoman(value: number): string { if (!Number.isInteger(value)) throw new Error(`Expected integer, got ${value}`) if (value <= 0 || value >= 5000) throw new Error(`Expect value between 0 and 5000 exclusive, got ${value}`)  if (arabicToRomanMap.has(value)) return arabicToRomanMap.get(value)!  return value .toString() .split('') .map(Number) .map(processArabicDigit) .map((digit, index, array) => processRomanDigit(digit, array.length - index)) .join('') }

Разберемся блочно, что вообще тут происходит.

value   .toString()   .split('')   .map(Number)

Этот код просто превращает число в массив цифр: 4956 становится [4, 9, 5, 6]. А дальше начинается магия:)

Посмотрим на реализацию функции processArabicDigit :

const processArabicDigit = (digit: number) => { if (digit === 0) return '' if (arabicToRomanMap.has(digit)) return arabicToRomanMap.get(digit)!  const foundLessByOne = integers.find(integer => integer - digit === 1) if (foundLessByOne !== undefined) return `i${arabicToRomanMap.get(foundLessByOne)}`  return integers.reduce((accumulator, integer) => { while (digit >= integer) { accumulator += arabicToRomanMap.get(integer) digit -= integer }  return accumulator }, '') }

Основная цель этой функции, превратить любую арабскую цифру в последовательность базовых цифр римской нумерации: «I», «V», «X».

• 0 даст пустую строку

• 1 и 5 базовые

• 4 и 9 подчиняются правилу off by one. Они равны в точности «I{цифра + 1}»

• 2, 3, 6, 7, 8 пройдут по жадному алгоритму и превратятся в «II», «III», «VI», «VII», «VIII» соответственно.

То есть, изначальное число 4956 превратится в [«IV», «IX», «V», «VI»]. Осталось провести операцию потенциирования, которой занимается функция processRomanDigit:

const processRomanDigit = (digit: string, position: number) => { if (position === 4) return 'm'.repeat(toArabic(digit))  return digit .split('') .map(char => romanToArabicMap.get(char)!) .map(digitNumber => arabicToRomanMap.get(digitNumber * 10 ** (position - 1))!) .join('') }

Заметим, что position = 4 является граничным случаем. То есть конструирование количество тысяч выпадает из правила, но это не страшно.

Остальные же числа разбиваются на свои базовые и домножаются на 10 в нужной позиции:

• «I» с позицией 4 станет «MMMM»

• «IX» с позицией 2 станет «CM» (рассматривалось в примере объяснений)

• «V» с позицией 1 станет «L»

• «VI» с позицией 0 останется неизменным

Последний шаг – собрать все вместе. Итого, 4956 превратится «MMMMCMLVI»

Зачем такой подход вообще нужен?

На то есть несколько причин, и одна из них, это просто весело. Не принимать на веру какие-то правила и докапываться до истины вещей, как можно обобщить правило или его вывести.

Вдобавок, варианты реализаций через запоминание дифтонгов плохо масштабируются, если кому-либо когда-либо захочется расширить домен римских чисел сверх 5000. А здесь, это просто придумать буквы, взять следующие значения (5000, 10000) и все. И так до бесконечности.

Даже то захардкоженное значение position = 4 можно обобщить. И с обратной конверсией проблем тоже не возникнет, нужно только придумать, как обобщить регулярку проверки валидного римского числа. Но это уже совсем другая история:)

Весь код, включая обратную конверсию, можно найти в репозитории.