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

Откройте почти любую реализацию перевода чисел из арабской системы в римскую и вы почти со 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 можно обобщить. И с обратной конверсией проблем тоже не возникнет, нужно только придумать, как обобщить регулярку проверки валидного римского числа. Но это уже совсем другая история:)

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