Letras para escribir números entre un rango dado.

Esta es una cuestión que me tope una ocasión a traves de internet, se trata de lo siguiente: hay que crear un algorítmo que reciba un número, mayor o igual a cero y menor a mil, el algorítmo debe determinar cuales son las letras que se necesitan para escribir los números [en español] desde el cero hasta el número especificado.

Ejemplo: si recibe el número tres, tenemos que dado el valor habrá que procesar los siguientes numeros:

0, 1, 2 y 3

Dicho en palabras:

cero, uno, dos y tres

=> Analicemos.

Las letras necesarias (viendo lo anterior) para escribirlos son:

c,e,r,o,u,n,o,d,o,s,t,r,e,s

Si quitamos las repetidas nos queda:

c,e,r,o,u,n,d,s,t

Y ordenandolas:

c,d,e,n,o,r,s,t,u

Y esa es la idea, si la entrada es el número 28 hay que procesar hasta el 28, si es el 67 hasta el 67 y así para cada caso hasta el 999 (<1000)

Ahora, como se podrán imaginar sería muy tedioso y costoso estar examinando uno por uno cada valor/palabra hasta (posiblemente) el 999...

Claro que programaticamente, con el uso de ciclos, no sería tan complejo, podríamos crear un ciclo desde el cero hasta el valor recibido y usando algún algorítmo de convertir numeros a letras obtener las letras necesarias, luego retirar las repetidas y finalmente ordenarlas y tenemos nuestro resultado si estar nosotros valor por valor y palabra por palabra. Tal solución es valida y funcional pero... habrá otra forma ¿quizas más optima?

Sin entrar a cosas de programación pensemos en la naturaleza de los numeros, del 0 al 999 parecen muchos, pero si los vemos desde el punto de vista del lenguage (humano no de programación), 0, 1, 2, 3 ... 9, 10, 11, 12, 13, 14 ... 109, 110, 111, 112, 113, 114... sabemos que son sólo diez digitos y para formar valores grandes se repiten, y con palabras pasa lo mismo uno, dos, tres ... veinte, veintyuno, veintydos, veintytres ... ciento-veintydos...

Si usamos lo anterior a nuestro favor no será necesario estar recorriendo todos los posibles valores, dado que se repiten, sólo será necesario recorrer valores significativos, es decir valores con nuevas palabras (no repetidas) y que por lo tanto aporten nuevos caracteres, así podremos descartar los valores cuyos caracteres ya se encuentran incluidos previamente y con ello disminuir el tiempo de proceso.

Ahora analicemos cuales seran nuetros valores significativos, para los primeros diez números cada palabra es diferente por lo tanto todos encajan en la categoria de 'significativos'

[cero, uno, dos, tres, cuatro, cinco, seis, siete, ocho y nueve]

En los siguientes diez valores (11-19)

[diez, once, doce, trece, catorce, quince, diezyseis, diezysiete, diezyocho, diezynueve]

Podemos observar que a partir del 16 se comienzan a repetir las palabras (marcadas en colores iguales) y por lo tanto podemos prescindir del 17 al 19, el 16 aún se incluye por que aporta la letra 'y'

Antes de continuar recordemos que los numeros ahora se formaran concatenando las decenas + el numero unitario, ejemplos: treinta+y+uno, cuarenta+y+uno, cincuenta+y+uno ... noventa+y+uno, por ello podemos prescindir de los numeros terminados entre 1 y 9 y analizar sólo las decenas de la siguiente forma:

[veinte, treinta, cuarenta, cincuenta, sesenta, setenta, ochenta, noventa y cien]

Hasta este momento de 101 valores (del 0 al 100) se han reducido a sólo 26 valores significativos, o dicho de otra forma a numeros cuyas palabras no son repeticiones de numeros anteriores:

[cero, uno, dos, tres, cuatro, cinco, seis, siete, ocho, nueve, diez, once, doce, trece, catorce, quince, diezyseis, veinte, treinta, cuarenta, cincuenta, sesenta, setenta, ochenta, noventa y cien]

Ahora recordemos que para los numeros de centenas pasará algo similar a las decenas y los numeros se forman concatenado centena + unitario (para los primeros quince valores de la centena), o bien centena + decena + unitario para el resto. Por ello pasa que los valores entre c01 hasta c99 (siendo c la centena: cien, doscientos...) ya estan incluidos, entonces nos limitaremos a considerar ahora sólo las palabras de las centenas, es decir:

[unciento (o cien), doscientos, trescientos, cuatrocientos, quinientos, seiscientos, sietecientos, ochocientos y nuevecientos]

Por ello a nuestros anteriores 26 valores significativos se agregan otros 9 y tenemos que en 35 palabras podemos considerar incluida toda la posible escritura de los numeros desde el 0 hasta el 999, así en vez de hacer un ciclo (considerando el valor más grande) de 999 iteraciones se ha reducido a 35 iteraciones, esto significa una reducion a menos del 5% de haber procesado el total de valores.

Y aún no se termina esto.... recordando el ejemplo inicial donde se consideró sólo hasta el numero 3, recordemos que una vez obtenidas las letras de cada palabra tuvimos que quitar varias repetidas, si observamos nuestras 35 palabras significativas obviamente salta a la vista que, aunque las palabras en sí son diferentes, muchas de las letras se repiten, por ello podemos reducir aún más nuestro conjunto de procesamiento, veamos, marcando en azul la primera aparición de una letra y en rojo las repeticiones obtenemos:

[cero, uno ,dos, tres, cuatro, ci nco, seis, siete, ocho, nue ve, diez, once, doce, trece, catorce, quince, diez yseis, veinte, treinta, cuarenta, cincuenta, sesenta, setenta, ochenta, noventa, unciento (o cien), doscientos, trescientos, cuatrocientos, quinientos, seiscientos, sietecientos (o setecientos), ochocientos y nuevecientos (o novecientos)]

Simplificando obtenemos:

[cero, uno ,dos, tres, cuatro, ci nco, ocho, nue ve, diez, q uince, diezyseis]

De treinta y cinco palabras se reduce a sólo once, y en esas once sabemos que estan incluidas todas las letras necesarias para escribir cualquier numero desde el 0 hasta el 999. Así que la primer idea para un algorítmo usando un ciclo que mayoritariamente haría cientos de iteraciones se puede reducir drasticamente usando unicamente nuestro conjunto de valores significativos.

Con todo el analisis previo podemos crear un sencillo código incluso sin utilizar ciclos, usando sólo el condicional if:

   // sintaxis utilizada: java
   int val; // nuestro valor de entrada
   String tx=""; // aca se guardara el resultado
   if(val>=16) tx="a,c,d,e,h,i,n,o,q,r,s,t,u,v,y,z";
   else if(val==15) tx="a,c,d,e,h,i,n,o,q,r,s,t,u,v,z";
   else if(val>=10) tx="a,c,d,e,h,i,n,o,r,s,t,u,v,z";
   else if(val==9) tx="a,c,d,e,h,i,n,o,r,s,t,u,v";
   else if(val==8) tx="a,c,d,e,h,i,n,o,r,s,t,u";
   else if(val>=5) tx="a,c,d,e,i,n,o,r,s,t,u";
   else if(val==4) tx="a,c,d,e,n,o,r,s,t,u";
   else if(val==3) tx="c,d,e,n,o,r,s,t,u";
   else if(val==2) tx="c,d,e,n,o,r,s,u";
   else if(val==1) tx="c,e,n,o,r,u";
   else tx="c,e,o,r";

Como pueden observar de una vez ordene las letras y ya ni siquiera analice palabras, solo el valor recibido y obtenia automaticamente las letras respectivas.

Otra forma diferente usando un ciclo y un array:

   // sintaxis utilizada: java
   int val; // nuestro valor de entrada
   String tx="";  // aca se guardara el resultado
   Object[][] matriz= { {4,"a"}, {0,"c"}, {2,"d"}, {0,"e"},
      {8,"h"}, {5,"i"}, {1,"n"}, {0,"o"}, {15,"q"}, {0,"r"},
      {2,"s"}, {3,"t"}, {1,"u"}, {9,"v"}, {16,"y"}, {10,"z"} };
   for(int i=0;i<matriz.length;i++){
     if(val>=Integer.parseInt(matriz[i][0].toString()))
       tx+=(tx.equals("")?"":",")+matriz[i][1];
   }

Y con esto me dí cuenta de la importancia de hacer un buen analisís antes de codificar (como caballo desbocado) la primer idea que se me ocurra para solucionar un problema.