Codegolf - Оптимальный Генератор Кратких Римских Цифр

Цель:
Напишите функцию, которая принимает число в качестве входных данных и возвращает сокращенную римскую цифру для этого числа в качестве выходных данных.

Символы римских цифр:

 
 
 
 totalCharacterCount = 0;
for(currentNumber = -1000; currentNumber <= 3000; currentNumber++){

totalCharacterCount += getRomanNumeral(currentNumber).length;
}
return totalCharacterCount;
 
 
 
 

В качестве примера того, что я имею в виду, когда говорю «сокращенные римские цифры», давайте рассмотрим поиск римской цифры, обозначающей 1983 год, потому что это год моего рождения. Один из вариантов — сделать это обычным способом (10 букв):

1983 = MCMLXXXIII = (1000 - 100 + 1000 + 50 + 30 + 3)

Другой вариант — сделать это сокращенно (6 символов):

1983 = MXVIIM = (1000 - (10 + 10) + 1000 + 3)

Вы знаете, что это значит?!?!!?? Если бы я был римлянином, я мог бы сохранять 4 символа каждый раз, когда писал дату своего рождения! Ву-у-у!

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

Правила краткого написания римских цифр:

1. Всегда рассматривайте символы слева направо до тех пор, пока не останется больше символов, подлежащих рассмотрению.
2. Если справа от текущего символа нет символов с более высоким значением:
   • Добавьте значение текущего символа к промежуточной сумме этой римской цифры.
3. Если справа от рассматриваемого вами символа есть символы с более высоким значением:
   • Найдите самый правый символ с самым высоким значением справа от текущего символа.
   • Считайте все символы до этого символа одной римской цифрой.
   • Рассчитайте значение этой римской цифры, используя следующие шаги.
   • Вычтите значение этой римской цифры из промежуточной суммы этой римской цифры.
   • Перейти к следующему символу после группы, которую вы только что рассмотрели.
4. Каждая римская цифра должна содержать хотя бы 1 символ.
5. Вот и все! Все, что соответствует этим правилам, будет принято!

Примеры:

Правила вопросов:

1. Создайте функцию, которая принимает одно число в качестве входных данных и возвращает римскую цифру для этого числа в качестве выходных данных, используя приведенные выше правила. Рассчитайте кодGolfScore этой функции.

   IIIIV = (-(1+1+1+1)+5) = 1 //Don't ask me why you'd want to do this! VVX = (-(5+5) + 10) = 0 //Who said you couldn't represent 0 with roman numerals?!!? VVXM = (-(-(5+5) + 10) + 1000) = 1000 //Again...don't ask me why you'd want to do this! MXIIXMI = (1000-(10-(1+1)+10)+1000+1) = 1983 //Ahhh...such a great year :)

2. Используя функцию из правила 1, сгенерируйте римские цифры от -1000 (верно, ОТРИЦАТЕЛЬНАЯ тысяча) до 3000. Затем просуммируйте длину символов этих римских цифр, чтобы получить общее количество символов. Вот псевдокод для пояснения:

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

3. FinalScore = кодGolfScore + TotalCharacterCount

4. Самый низкий FinalScore побеждает!

Примечание. Поскольку общее количество символов будет превышать десять тысяч, алгоритм определения длины символов должен иметь высший приоритет. Очки в код-гольфе — это всего лишь решающий момент на случай, если несколько пользователей найдут оптимальный алгоритм или алгоритмы, близкие друг к другу.

Удачи и веселитесь завтра вечером на праздновании MMXII!!!

#код-гольф #римские цифры

Хаскелл, 25637 (= 268 + 25369) 26045 (= 222+25823)

 
 
 
 
 
 
 
 Enumerable.Range(-1000, 3000).Sum(i => M.R(i).Length); 
 
 
 
 
 
 
 

использовать, например,

Вы можете оценить сумму длин с помощью простой

Это занимает что-то порядка минуты.

C++, 345 символов кода, 25021 римская цифра = 25366

немного деобфусцирован, с драйвером:

n computes the numerical value of a given roman numeral string V длины f . Strings are encoded base 7 (first digit is s%7, second digit is s/7%7, ...). Each digit is encoded with I=0, V=1, ..., M=6. L выполняет перебор возможных строк римских цифр, чтобы найти ту, которая s evaluates to V .

Общее количество цифр римских цифр является оптимальным. Самая длинная римская цифра, необходимая для [-1000,3000], состоит из 11 цифр (например, -827=CMDDMLXXIII), что на моей машине занимает около 5 минут.

Рубин, 25987 (= 164 + 25823)

Вы можете позвонить int N[]={1,5,10,50,100,500,1000};int V(int s,int L){if(!L)return 0;int K=0,B,m=s%7+1;for(int k=1,b=7;k<L;k++,b*=7){if(s/b%7>=m){K=k;B=b;m=s/b%7;}}return K?V(s/B,L-K)-V(s%B,K):N[s%7]+V(s/7,L-1);}char r[99];char*f(int n){for(int L=1,B=7,i,j;1;L++,B*=7){for(i=0;i<B;i++){if(V(i,L)==n){for(j=0;j<L;j++){r[j]="IVXLCDM"[i%7];i/=7;}r[L]=0;return r;}}}} directly to get the results. The sum over the specified range yields

что является оптимальной суммой, как и в случае с другими решениями.

C# 23537 (639 символов кода + 22898 символов вывода)

Для расчета:

r 0="VVX" r n=s(zip[1000,500,100,50,10,5]"MDCLXV")n ξ ξ='ξ' s[]q f |q<0=s[](5-q)f++"V" |q<1="" |r<-q-1='I':s[]r f s ω@((v,a):l)q f |q>=v,f/=a=a:s ω(q-v)ξ |f==a,γ<-'I':a:s l(q-v+1)ξ,η γ<η(s l q ξ)=γ |f==ξ,γ<-s ω(v-q)a++[a],η γ<η(s l q ξ)=γ |True=s l q ξ η=length