Generator angka Romawi pendek yang optimal

21

Sasaran:
Tulis fungsi yang mengambil angka sebagai input dan mengembalikan angka romawi untuk nomor tersebut sebagai output.

Simbol Angka Romawi:

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

Sebagai contoh tentang apa yang saya maksud ketika saya mengatakan "angka romawi tangan pendek", mari pertimbangkan mencari angka romawi untuk mewakili tahun 1983, karena itulah tahun saya dilahirkan. Salah satu opsi adalah melakukan ini dengan cara biasa (10 huruf):

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

Pilihan lainnya adalah melakukannya dengan cara singkat (6 karakter):

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

Tahukah Anda apa artinya ini?!? !! ?? Jika saya roman saya bisa menyelamatkan 4 karakter setiap kali saya menulis tanggal lahir saya! Woot Woot !!

Namun, sebelum saya maju dalam kegembiraan, saya memiliki pertanyaan untuk ditulis, jadi saya mungkin harus mendefinisikan aturan angka romawi tangan pendek sehingga kita semua berada di halaman yang sama:

Aturan Angka Romawi Singkat:

  1. Selalu pertimbangkan simbol dari kiri ke kanan hingga tidak ada lagi karakter yang perlu dipertimbangkan.
  2. Jika tidak ada simbol bernilai lebih tinggi di sebelah kanan simbol saat ini:
    • Tambahkan nilai simbol saat ini ke total angka romawi ini.
  3. Jika ada simbol bernilai lebih tinggi di sebelah kanan simbol yang Anda pertimbangkan:
    • Temukan simbol bernilai tertinggi paling kanan di sebelah kanan simbol saat ini
    • Pertimbangkan semua karakter hingga simbol itu sebagai satu angka romawi
    • Hitung nilai angka romawi itu menggunakan langkah-langkah ini
    • Kurangi nilai angka romawi dari total angka romawi ini.
    • Pindah ke simbol berikutnya setelah grup yang baru saja Anda pertimbangkan
  4. Setiap angka romawi harus memiliki setidaknya 1 simbol di dalamnya.
  5. Itu dia! Apa pun yang mengikuti aturan ini akan diterima!

Contoh:

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 :)

Aturan Pertanyaan:

  1. Buat fungsi yang mengambil nomor tunggal sebagai input dan mengembalikan angka romawi untuk nomor itu sebagai output menggunakan aturan di atas. Hitung codeGolfScore dari fungsi ini.

    example input: 2011
    example possible output: MMXI
    another possible output: MMVVIVV     //(2000 + 10 - 4 + 5) 
    
  2. Dengan menggunakan fungsi Anda dari aturan 1, buat angka romawi antara -1000 (benar, NEGATIF ​​seribu) dan 3.000. Kemudian jumlah panjang karakter angka romawi ini untuk mendapatkan totalCharacterCount Anda . Berikut beberapa pseudocode yang akan diklarifikasi:

    totalCharacterCount = 0;
    for(currentNumber = -1000; currentNumber <= 3000; currentNumber++){
        totalCharacterCount += getRomanNumeral(currentNumber).length;
    }
    return totalCharacterCount;
    
  3. finalScore = codeGolfScore + totalCharacterCount

  4. Final FinalScore terendah !

Catatan: Karena jumlah total Karakter adalah dalam sepuluh-ribuan +, algoritma karakter-panjang harus menjadi prioritas utama. Skor kode-golf hanyalah tie-breaker jika beberapa pengguna menemukan algoritma atau algoritma optimal yang dekat satu sama lain.

Selamat mencoba, dan bersenang-senang di perayaan MMXII Anda besok malam !!!

Briguy37
sumber
1
Tugas besar! Namun, dapatkah Anda memberikan contoh bagaimana steno tulisan tangan negatif terlihat? Apakah DDDDMberdiri untuk -1000?
pimvdb
@pimvdb Anda mengerti!
Briguy37
Sebuah pertanyaan tentang kasus khusus nol: Apakah ""diizinkan untuk nol atau apakah kita harus menggunakan VVXatau sesuatu yang setara?
Howard
@ Howard: Pertanyaan bagus, saya belum memikirkan itu! Saya telah menambahkan aturan angka romawi 4 yang mengklarifikasi kasus itu.
Briguy37
1
"Temukan simbol bernilai tertinggi paling kanan di sebelah kanan simbol saat ini" - yang menang, paling kanan atau bernilai tertinggi? yaitu, apakah IXV = -(-1 + 10) + 5 = -4(kemenangan paling kanan), atau IXV = -1 + 10 + 5 = 14(kemenangan bernilai tertinggi)?
Keith Randall

Jawaban:

5

Haskell, 25637 (= 268 + 25369) 26045 (= 222 + 25823)

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

untuk digunakan sebagai contoh

GHCi> r 7
"VII"
GHCi> r 39
"XIL"
GHCi> r (-39)
"ICXLC"        --  "LLXILC" in my original version
GHCi> r 1983
"MXVIIM"
GHCi> r 259876
"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMCXXIVM"

Anda dapat mengevaluasi jumlah panjang dengan mudah

GHCi> sum . map(length.r) $ [-1000..3000]
25369

Yang membutuhkan sesuatu dalam urutan satu menit.

berhenti mengubah counterclockwis
sumber
5

C ++, 345 karakter kode, 25021 angka romawi = 25366

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;}}}}

Deobfuscated sedikit, dengan driver:

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;1;L++,B*=7) {
    for(int i=0;i<B;i++) {
      if(V(i,L)==n){
        for(int j=0;j<L;j++) {
          r[j]="IVXLCDM"[i%7];i/=7;
        }
        r[L]=0;
        return r;
      }
    }
  }
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
  printf("%s\n", f(atoi(argv[1])));
}

Vmenghitung nilai numerik dari string spanjang angka romawi yang diberikan L. String dikodekan basis 7 (digit pertama s% 7, digit kedua s / 7% 7, ...). Setiap digit dikodekan dengan I = 0, V = 1, ..., M = 6. fapakah enumerasi brute-force dari string angka romawi yang mungkin untuk menemukan satu yang Vmengevaluasi n.

Jumlah digit angka romawi optimal. Angka romawi terpanjang yang dibutuhkan untuk [-1000,3000] adalah 11 digit (misalnya -827 = CMDDMLXXIII), yang membutuhkan waktu sekitar 5 menit pada mesin saya.

Keith Randall
sumber
Tunggu sebentar, itu tidak berlaku seperti yang ditentukan. Program Anda memberikan mis LMCLXXIIIsebagai jawaban -777. Saya akan membacanya sebagai -50+1000-100+50+10+10+3 = 923 ≠ -777, hanya dengan "nilai paling kanan lebih tinggi " daripada " tertinggi " yang diberikannya -777. Tapi itu hanya apa yang Anda minta di komentar!
Berhenti menyalakan serangan balik pada
@leftaroundabout: tentu saja Anda benar. Saya akan memperbaikinya, tetapi tidak ada waktu sekarang ...
Keith Randall
@leftaroundabout: ok, semua sudah diperbaiki.
Keith Randall
Baiklah. Ini tidak optimal sekarang, meskipun (misalnya memberikan VVVXIuntuk -4saat IXVXini sebenarnya lebih pendek, karena saya hanya melihat) - tapi itu sangat legal.
Berhenti menyalakan serangan balik pada
@leftaroundabout: ok, diperbaiki lagi. Semoga ini benar kali ini ...
Keith Randall
2

Ruby, 25987 (= 164 + 25823)

h=->i,d,v,k{i==0?'':i<v ?(a=h[v-i,x=d[1..-1],v/k,k^7]+d[0];i<0?a:(b=h[i,x,v/k,k^7];a.size<b.size ? a :b)):d[0]+h[i-v,d,v,k]}
r=->i{i==0?'DDM':h[i,'MDCLXVI',1000,2]}

Anda dapat menelepon rlangsung untuk mendapatkan hasilnya. Jumlah di atas rentang hasil yang ditentukan

> (-1000..3000).map{|i|r[i].size}.reduce &:+
25823

yang merupakan jumlah optimal seperti solusi lainnya.

Howard
sumber
0

C # 23537 (639 karakter kode + 22898 karakter keluaran)

class M
{
    public static string R(int n, int? s = new int?())
    {
        var r = "";
        var D = new Dictionary<int, string> {{ 1000, "M"}, { 900, "CM"},{ 800, "CCM"},{ 500, "D"}, { 400, "CD"},{ 300, "CCD"},{100, "C"}, {90, "XC"},{80, "XXC"},{50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"}, {8, "IIX"}, {5, "V"}, {4, "IV"},{1, "I"}};
        if (n == 0) return "VVX";
        if (n == -1) return "IIIIIIV";
        if (n < 0) return N(n * -1);

        foreach(int k in D.Keys)
        {
            if (s.HasValue && k > s) continue;

            while(k <= n)
            {
                n -= k; 
                r += D[k];
            }
        }

        return r;
    }

    public static string N(int n)
    {
        var D = new Dictionary<int, string> {{1, "I"}, {5, "V"}, {10, "X"}, {50, "L"}, {100, "C"}, { 500, "D"}, {1000, "M"}};

        int i = D.Keys.First(v => v >= n), m = D.Keys.Where(v => v < i).Max();

        return R(n + i, m) + D[i];
    }
}

Menghitung:

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

mizer
sumber
Dan berapa skor Anda?
pengguna tidak diketahui