tło

Wyzwanie to jest inspirowane tą witryną, która opublikowała następujący schemat:

Ten diagram pokazuje nam, że najdłuższe wyrażenie liczby rzymskiej poniżej 250 to 188, które wymaga 9 cyfr do wyrażenia.

Wyzwanie

Standardowe symbole wyrazić Cyfry najbardziej rzymskimi są następujące: { I, V, X, L, C, D, M}, gdzie wartości liczbowe bohaterów są M= 1000, D= 500, C= 100, L= 50, a X= 10, V= 5 I= 1.

W tym wyzwaniu twoim celem jest, biorąc pod uwagę dodatnią liczbę całkowitą n , obliczyć liczbę prawidłowych reprezentacji cyfr rzymskich, które można skomponować poprzez połączenie n standardowych symboli.

Następnie twój program musi wypisać wynik tego obliczenia!

Dane wejściowe : dodatnia liczba całkowita n .

Dane wyjściowe : liczba prawidłowych wyrażeń liczb rzymskich o długości n .

Reguły dla wyrażeń rzymskich

Liczby rzymskie pierwotnie miały tylko „addytywne” parowanie, co oznacza, że ​​cyfry były zawsze zapisywane w kolejności malejącej, a suma wartości wszystkich cyfr była wartością liczby.

Później, parowanie subtraktywne, stosowanie umieszczania mniejszej cyfry przed większą w celu odjęcia mniejszej od większej, stało się powszechne w celu skrócenia wyrażeń rzymskich. Subtraktywne pary nie może być połączony, na przykład w następujący nieprawidłowej ekspresji: IXL.

Poniżej przedstawiono współczesne zasady parowania addytywnego i odejmującego.

1. Tylko jedna cyfra I, X i C może być użyta jako liczba wiodąca w części pary odejmującej.
2. Mogę być umieszczony przed V lub X tylko w odejmującej parze.
3. X można umieścić tylko przed L lub C w parze odejmującej.
4. C można umieścić tylko przed D lub M w parze odejmującej.
5. Liczby inne niż pary odejmujące muszą być w porządku malejącym (co oznacza, że ​​jeśli upuścisz wiodącą cyfrę każdej pary odejmującej, wówczas liczby będą malejące).
6. M, C i X nie mogą być równe ani przekroczone przez mniejsze nominały.
7. D, L i V mogą pojawić się tylko raz.
8. Tylko M można powtórzyć 4 lub więcej razy.

Dalsze uwagi

• Nie będziemy używać notacji słupkowej ; raczej po prostu dodamy więcej M, aby wyrazić dowolną liczbę.

• To jedyne zasady, których będziemy przestrzegać dla naszych cyfr rzymskich. Oznacza to, że wyrażenia nieparzyste, takie jak IVI, będą również uważane za prawidłowe w naszym systemie.

• Pamiętaj również, że nie liczymy liczby liczb, które mają wyrażenia długości n , ponieważ niektóre liczby mają wiele wyrażeń. Zamiast tego liczymy wyłącznie liczbę prawidłowych wyrażeń.

Przypadki testowe

1 → 7

2 → 31

3 → 105

Sprawdziłem to ręcznie, więc proszę dokładnie sprawdzić przypadki testowe i dodać więcej, jeśli możesz!

Zwycięskie kryteria

To wyzwanie dla golfa , więc baw się dobrze! Akceptuję tylko rozwiązania, które potrafią obsłużyć co najmniej dane wejściowe od 1 do 9. Więcej to bonus!

Edytować

Zgodnie z prośbą komentujących, znajdź poniżej lub pod tym linkiem do pastebin, 105 kombinacji policzyłem dla n = 3

III IVI IXI IXV IXX VII XII XIV XIX XVI XXI XXV XXX XLI XLV XLX XCI XCV XCX XCL XCC LII LIV LIX LVI LXI LXV LXX CII CIV CIX CVI CXI CXV CXX CXX CXL CXC CLI CLV CLX CCI CCV CCX CCL CDC CDL CDI CD CMI CMV CMX CML CMC CMD CMM DII DIV DIX DVI DXI DXV DXX DXL DXC DLI DLV DLX DCI DCV DCX DCX DCL DCC MII MIV MIX MVI MXI MXV MXX MXL MXC MLI MLV MLX MCI MCV MCX MCL MCK MCC MCD MCM MDI MDV MDM MDL MDL MMX MML MMC MMD MMM

Edycja 2:

Użyj poniższego kodu nie golfowego , dzięki uprzejmości Jonathan Allan, aby sprawdzić swoje wyniki.

Edycja 3:

Przepraszam za wszystkie błędy w tym wyzwaniu. Następnym razem zrobię lepszą robotę!

Siatkówka , 111 bajtów

~(`.+
*$(CM)CDXCXCXCXLIXIXIXIVII
.(.)
.+¶$$&$¶$$&$1$¶$$&$&¶L`.{0,$+}\b¶D`¶
¶$
¶.+¶$$&$¶$$&I¶L`[A-Z]{$+}\b¶D`¶.+

Wypróbuj online! Jest to kompletne przepisanie, ponieważ źle zrozumiałem zasadę 1. oznacza to, że można użyć tylko jednego z odejmujących I, Xi C. Objaśnienie: Pierwsza część skryptu rozwija dane wejściowe w ciąg CMpar, po którym następują inne możliwe pary odejmujące. Każda para jest opcjonalna, a pierwszy znak każdej pary jest również opcjonalny w obrębie pary. Trzeci etap następnie rozszerza listę par na listę poleceń Retina, które pobierają dane wejściowe i tworzą trzy kopie z opcją drugiego lub obu znaków z pary, a następnie przycinają i deduplikują wyniki. Ostatni etap dołącza następnie kod do wykonania ostatecznych zadań: najpierw rozwiń dane wejściowe, aby ewentualnie dodać końcowyI, a następnie odfiltrować wyniki o niewłaściwej długości, następnie deduplikować wyniki i na końcu policzyć wyniki. Wynikowy skrypt Retina jest następnie oceniany.

Uwaga: Teoretycznie 15 bajtów można zapisać od końca czwartej linii, ale powoduje to, że skrypt jest zbyt wolny, aby zademonstrować na TIO nawet dla n=1.

Python 2 , 177 168 162 bajtów

import re,itertools as q
f=lambda n:sum(None!=re.match("^M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$",(''.join(m)))for m in q.product('MDCLXVI',repeat=n))

Wypróbuj online!

Jestem całkiem nowy, pomóż mi w golfa! Sprawdza to rzeczywiste cyfry rzymskie, regex należy dostosować, aby uwzględnić przypadki nieparzyste, takie jakIVI

-9 bajtów dzięki @Dead Possum!

-6 bajtów dzięki @ovs

JavaScript (ES7), 133 bajty

Edycja : Naprawiono, aby pasowało do wyników zwróconych przez kod Jonathana Allana , który został podany jako implementacja referencyjna przez PO.

n=>[...Array(m=k=7**n)].reduce(s=>s+/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test((--k+m).toString(7).replace(/0[62]|2[34]|4[51]/g,s=>s[1])),0)

Wypróbuj online!

W jaki sposób?

$N$$1$

[...Array(m = k = 7 ** n)].reduce(s => … (--k + m).toString(7) …, 0)

Odtąd każda cyfra będzie interpretowana jako symbol cyfr rzymskich:

2) Zamieniamy wszystkie poprawne pary subtraktywnymi formularza ABz B:

.replace(/0[62]|2[34]|4[51]/g, s => s[1]))  // in the code
.replace(/I[VX]|X[LC]|C[DM]/g, s => s[1]))  // with Roman symbols

Przykłady:

• XLIXIV staje się LXV
• XIIVstaje się XIV, Ico powoduje, że kolejny test zakończy się niepowodzeniem
• ICpozostaje niezmieniony, co również pozostawia nieważne Ina miejscu

3) Sprawdzamy, czy pozostałe symbole są w odpowiedniej kolejności i nie pojawiają się więcej razy, niż mogą:

/^1*5?4{0,3}3?2{0,3}6?0{0,3}$/.test(…)  // in the code
/^M*D?C{0,3}L?X{0,3}V?I{0,3}$/.test(…)  // with Roman symbols

C, 150 123 bajtów

Nie przeczytałem wystarczająco dokładnie opisu, więc daje to liczbę standardowych cyfr rzymskich (gdzie takie wyrażenia IVInie są liczone). Ponieważ włożyłem w to trochę wysiłku, pomyślałem, że i tak się podzielę.

#define F(X) for(X=10;X--;)
x[]={0,1,2,3,2,1,2,3,4,2};f(i,o,a,b,c){for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];return o;}

Oryginalny (150 bajtów):

#define F(X) for(X=10;X--;)
i,o,a,b,c,x[]={0,1,2,3,2,1,2,3,4,2};main(){scanf("%i",&i);for(i++;i--;)F(a)F(b)F(c)o+=i==x[a]+x[b]+x[c];printf("%i\n",o);}