Générateur optimal de chiffres romains à main courte

21

Objectif:
écrire une fonction qui prend un nombre en entrée et renvoie un chiffre romain abrégé pour ce nombre en sortie.

Symboles des chiffres romains:

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

Pour un exemple de ce que je veux dire quand je dis "chiffres romains à main courte", considérons la recherche d'un chiffre romain pour représenter 1983, car c'est l'année de ma naissance. Une option consiste à le faire de manière normale (10 lettres):

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

L'autre option est de le faire de manière abrégée (6 caractères):

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

Savez-vous ce que cela signifie?!?!!?? Si j'étais romain, j'aurais pu enregistrer 4 caractères à chaque fois que j'écrivais ma date de naissance! Woot Woot !!

Cependant, avant de prendre de l'avance sur moi-même dans l'excitation, j'ai une question à écrire, je devrais donc probablement définir les règles abrégées des chiffres romains afin que nous soyons tous sur la même page:

Règles des chiffres romains à main courte:

  1. Considérez toujours les symboles de gauche à droite jusqu'à ce qu'il n'y ait plus de caractères à considérer.
  2. S'il n'y a pas de symboles de valeur supérieure à droite du symbole actuel:
    • Ajoutez la valeur du symbole actuel au total cumulé de ce chiffre romain.
  3. S'il y a des symboles de valeur supérieure à droite du symbole que vous envisagez:
    • Localisez le symbole de valeur la plus à droite à droite du symbole actuel
    • Considérez tous les caractères jusqu'à ce symbole comme un chiffre romain
    • Calculez la valeur de ce chiffre romain en utilisant ces étapes
    • Soustrayez la valeur de ce chiffre romain du total cumulé de ce chiffre romain.
    • Passez au symbole suivant après le groupe que vous venez de considérer
  4. Chaque chiffre romain doit contenir au moins 1 symbole.
  5. C'est ça! Tout ce qui suit ces règles sera accepté!

Exemples:

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

Règles des questions:

  1. Créez une fonction qui prend un seul nombre en entrée et renvoie un chiffre romain pour ce nombre en sortie en utilisant les règles ci-dessus. Calculez le codeGolfScore de cette fonction.

    example input: 2011
    example possible output: MMXI
    another possible output: MMVVIVV     //(2000 + 10 - 4 + 5) 
    
  2. En utilisant votre fonction de la règle 1, générez les chiffres romains entre -1000 (c'est-à-dire NÉGATIF ​​mille) et 3000. Résumez ensuite la longueur des caractères de ces chiffres romains pour obtenir votre totalCharacterCount . Voici un pseudocode pour clarifier:

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

  4. Le score final le plus bas gagne!

Remarque: Comme le nombre total de caractères sera dans les dix mille +, l'algorithme de longueur de caractère doit être la priorité absolue. Les scores de code-golf ne sont que le bris d'égalité au cas où plusieurs utilisateurs trouveraient l'algorithme optimal ou des algorithmes proches les uns des autres.

Bonne chance et amusez-vous lors de vos célébrations MMXII demain soir !!!

Briguy37
la source
1
Grande tâche! Cependant, pourriez-vous donner un exemple de l'apparence d'une sténographie romaine négative? Cela DDDDMsignifie- t-il -1000?
pimvdb
@pimvdb Vous l'avez compris!
Briguy37
Une question concernant le cas spécial zéro: est-il ""autorisé pour zéro ou devons-nous utiliser VVXou quelque chose d'équivalent?
Howard
@Howard: Excellente question, je n'y avais pas pensé! J'ai ajouté la règle de chiffre romain 4 pour clarifier ce cas.
Briguy37
1
"Localisez le symbole le plus à droite à droite du symbole actuel" - qui gagne, à droite ou à valeur la plus élevée? c.-à-d. est IXV = -(-1 + 10) + 5 = -4(victoires les plus à droite), ou IXV = -1 + 10 + 5 = 14(victoires les plus appréciées)?
Keith Randall

Réponses:

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

à utiliser par exemple

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"

Vous pouvez évaluer la somme de la longueur avec le simple

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

Ce qui prend quelque chose en une minute.

a cessé de tourner dans le sens antihoraire
la source
5

C ++, 345 caractères de code, 25021 chiffres romains = 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;}}}}

désobfusqué un peu, avec un pilote:

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

Vcalcule la valeur numérique d'une chaîne numérique sde longueur donnée L. Les chaînes sont codées en base 7 (le premier chiffre est s% 7, le deuxième chiffre est s / 7% 7, ...). Chaque chiffre est codé avec I = 0, V = 1, ..., M = 6. feffectue une énumération par force brute des chaînes de chiffres romains possibles pour en trouver une qui Vévalue n.

Le nombre total de chiffres romains est optimal. Le chiffre romain le plus long requis pour [-1000,3000] est de 11 chiffres (par exemple -827 = CMDDMLXXIII), ce qui prend environ 5 minutes sur ma machine.

Keith Randall
la source
Attendez un instant, cela ne se comporte pas comme indiqué. Votre programme donne par exemple LMCLXXIIIcomme réponse à -777. Je lirais cela comme -50+1000-100+50+10+10+3 = 923 ≠ -777, seulement avec "le plus haut à droite " au lieu de "le plus élevé " -777. Mais c'est exactement ce que vous avez demandé dans les commentaires!
cessé de tourner dans le sens inverse des aiguilles d'une montre le
@leftaroundabout: bien sûr, vous avez raison. Je vais le réparer, mais pas de temps pour le moment ...
Keith Randall
@leftaroundabout: ok, tout est réparé.
Keith Randall
D'accord. Ce n'est pas optimal maintenant, cependant (par exemple donne VVVXIpour -4quand IXVXest en fait plus court, comme je viens de le remarquer) - mais c'est parfaitement légal.
cessé de tourner dans le sens inverse des aiguilles d'une montre le
@leftaroundabout: ok, corrigé à nouveau. J'espère que c'est correct cette fois ...
Keith Randall
2

Rubis, 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]}

Vous pouvez appeler rdirectement pour obtenir les résultats. La somme sur la plage spécifiée donne

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

qui est la somme optimale comme pour les autres solutions.

Howard
la source
0

C # 23537 (639 caractères de code + 22898 caractères de sortie)

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

Calculer:

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

mizer
la source
Et quel est votre score?
utilisateur inconnu