Generador óptimo de números romanos de mano corta

21

Objetivo:
escribir una función que tome un número como entrada y devuelva un número romano de mano corta para ese número como salida.

Símbolos de números romanos:

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

Para un ejemplo de lo que quiero decir cuando digo "números romanos abreviados", consideremos encontrar un número romano para representar 1983, porque ese es el año en que nací. Una opción es hacer esto de la manera normal (10 letras):

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

La otra opción es hacerlo de forma abreviada (6 caracteres):

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

¿¿¡¡¿¡¿Sabes qué significa esto?!?!!?? ¡Si fuera romano, podría haber guardado 4 caracteres cada vez que escribiera mi fecha de nacimiento! Woot Woot !!

Sin embargo, antes de adelantarme en la emoción, tengo una pregunta que escribir, por lo que probablemente debería definir las reglas de números romanos abreviados para que todos estemos en la misma página:

Reglas de números romanos de mano corta:

  1. Siempre considere los símbolos de izquierda a derecha hasta que no haya más caracteres para considerar.
  2. Si no hay símbolos de mayor valor a la derecha del símbolo actual:
    • Agregue el valor del símbolo actual al total acumulado de este número romano.
  3. Si hay símbolos de mayor valor a la derecha del símbolo que está considerando:
    • Ubique el símbolo de mayor valor más a la derecha a la derecha del símbolo actual
    • Considere todos los caracteres hasta ese símbolo como un número romano
    • Calcule el valor de ese número romano usando estos pasos
    • Reste el valor de ese número romano del total acumulado de este número romano.
    • Pasa al siguiente símbolo después del grupo que acabas de considerar
  4. Cada número romano debe tener al menos 1 símbolo.
  5. ¡Eso es! ¡Todo lo que siga estas reglas será aceptado!

Ejemplos:

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

Reglas de preguntas:

  1. Realice una función que tome un solo número como entrada y devuelva un número romano para ese número como salida utilizando las reglas anteriores. Calcule el codeGolfScore de esta función.

    example input: 2011
    example possible output: MMXI
    another possible output: MMVVIVV     //(2000 + 10 - 4 + 5) 
    
  2. Usando su función de la regla 1, genere los números romanos entre -1000 (es cierto, NEGATIVO mil) y 3000. Luego, sume la longitud de los caracteres de estos números romanos para obtener su totalCharacterCount . Aquí hay un pseudocódigo para aclarar:

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

  4. ¡El puntaje final más bajo gana!

Nota: Como el recuento total de caracteres estará en más de diez mil, el algoritmo de longitud de caracteres debe ser la máxima prioridad. Los puntajes de código de golf son solo el factor decisivo en caso de que varios usuarios encuentren el algoritmo o algoritmos óptimos que están cerca uno del otro.

Buena suerte y diviértete en tus celebraciones MMXII mañana por la noche.

Briguy37
fuente
1
Gran tarea! Sin embargo, ¿podría dar un ejemplo de cómo se ve una taquigrafía romana negativa? ¿ Qué DDDDMsignifica -1000?
pimvdb
@pimvdb ¡Lo tienes!
Briguy37
Una pregunta con respecto al caso especial cero: ¿Está ""permitido cero o tenemos que usar VVXo algo equivalente?
Howard
@Howard: Gran pregunta, ¡no había pensado en eso! He agregado la regla 4 del número romano para aclarar ese caso.
Briguy37
1
"Localice el símbolo de mayor valor más a la derecha del símbolo actual": ¿cuál gana, el de mayor valor o el más a la derecha? es decir, ¿es IXV = -(-1 + 10) + 5 = -4(victorias más a la derecha) o IXV = -1 + 10 + 5 = 14(victorias de mayor valor)?
Keith Randall

Respuestas:

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

para ser utilizado como por ejemplo

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"

Puede evaluar la suma de la longitud con el sencillo

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

Lo cual toma algo del orden de un minuto.

dejó de girar en sentido antihorario
fuente
5

C ++, 345 caracteres de código, 25021 dígitos de números romanos = 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;}}}}

desobuscado un poco, con un controlador:

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

Vcalcula el valor numérico de una cadena sde longitud de un número romano dado L. Las cadenas están codificadas en base 7 (el primer dígito es s% 7, el segundo dígito es s / 7% 7, ...). Cada dígito está codificado con I = 0, V = 1, ..., M = 6. fhace una enumeración de fuerza bruta de posibles cadenas de números romanos para encontrar una que Vevalúe n.

El número total de dígitos de números romanos es óptimo. El número romano más largo necesario para [-1000,3000] es de 11 dígitos (por ejemplo, -827 = CMDDMLXXIII), lo que demora aproximadamente 5 minutos en mi máquina.

Keith Randall
fuente
Espera un momento, eso no se comporta de la manera especificada. Su programa da, por ejemplo, LMCLXXIIIcomo la respuesta a -777. Lo había leído como -50+1000-100+50+10+10+3 = 923 ≠ -777, solo con "el más alto valor " en lugar de " más alto " da -777. ¡Pero eso fue justo lo que pediste en los comentarios!
dejó de girar en sentido antihorario el
@leftaroundabout: por supuesto que tienes razón. Lo arreglaré, pero no hay tiempo ahora ...
Keith Randall
@leftaroundabout: ok, todo arreglado.
Keith Randall el
Todo bien. Es no óptima ahora, sin embargo (por ejemplo, da VVVXIpara -4cuando IXVXen realidad es más corto, como acabo de notar) - pero eso es perfectamente legal.
dejó de girar en sentido antihorario el
@leftaroundabout: ok, arreglado nuevamente. Esperemos que sea correcto esta vez ...
Keith Randall
2

Rubí, 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]}

Puede llamar rdirectamente para obtener los resultados. La suma sobre el rango especificado rinde

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

cuál es la suma óptima como con las otras soluciones.

Howard
fuente
0

C # 23537 (639 caracteres de código + 22898 caracteres de salida)

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

Calcular:

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

mizer
fuente
¿Y cuál es tu puntaje?
Usuario desconocido el