Reto lúdico: procesadores de palabras y diccionarios

Hoy en día prácticamente todas las aplicaciones usan un diccionario de palabras, el cual funciona en tiempo real, marcando (muchas veces subrayando en rojo o pintando con algún color específico) las palabras que de acuerdo a cómo se escriben las palabras, están mal escritas. Esto lo usan muchos procesadores de palabras que añaden esta capacidad para hacer más valioso su software y ayudar al usuario a escribir con mayor corrección.

Hay que decir que los idiomas humanos muchas veces son más complicados para corregir que simplemente hacer una búsqueda en un diccionario a ver si existe una palabra o no. Hay giros idiomáticos, hay anglicismos que muchas veces no se encuentran en los diccionarios, amén de que hay palabras que tienen que ver con el contexto en el que se escriben. Pongamos un ejemplo: la palabra "solo" se escribe sin acento si es de soledad. Si es adverbio, entonces se le pone la tilde en la primera sílaba. Así, "estoy solo" está bien escrito, pero "estoy sólo" no lo está. Y sí, sé que la Rel Academia de la Lengua Española estaba quitando estos acentos diacríticos. Sin embargo, mientras no se decida cómo quedará la cosa, yo seguiré con la regla antigua.

Los elementos de una buena corrección ortográfica

En 1988 hice la maestría en Inteligencia Artificial. Mi proyecto era un corrector ortográfico inteligente. Después de analizar a detalle la problemática, llegué a la conclusión que, para tener un corrector razonablemente bueno, se requería lo siguiente:

• Ser capaz de usar reglas ortográficas: Hay más de doscientas reglas en el español. Por ejemplo, "En una palabra, después de una n va una v, después de una m va una b". Así, "enbiar" está mal escrito y "homvre" también está mal. Si usamos las reglas, podemos olvidarnos en algunos casos de consultar las palabras en el diccionario.
• Ser capaz de usar un diccionario con miles de palabras: Mientras más palabras se tengan en un diccionario, la corrección puede ser mejor.
• Ser capaz de usar diccionarios personalizados: Muchas palabras no están en los diccionarios, por ejemplo, aquellas que usan términos científicos o un lenguaje especializado. Sería pues conveniente poder agregar esta funcionalidad de tener (o crear) diccionarios especializados.
• Ser capaz de usar otras tecnologías para buscar errores, como patrones equivocados de letras: En muchas ocasiones los usuarios cambian la letras de orden y estoi hace que la palabra esté mal escrita. Si podemos detectar esto, la corrección puede hacerse sin necesidad de un diccionario.
• Ser capaz de usar de un diccionario de verbos ya conjugados: Curiosamente, los diccionarios normalmente traen los verbos en infinitivo pero no vienen conjugados. La conjugación es un proceso mecánico y por ende, bien podría añadirse a las capacidades del corrector. Cada verbo tiene, en general unas 50 conjugaciones y hay unos 10 mil verbos. Esto haría posible tener un diccionario -sólo de verbos (¿notaron la tilde?)- de 500 mil palabras.

Tres tipos de corrección: interactiva, por lotes y rápida

Normalmente los procesadores de palabras corrigen mientras el usuario está escribiendo un texto. Esto es relativamente ágil para el usuario pues puede detectar errores de inmediato. Sin embargo, hay otros escenarios. Supongamos que nos mandan un texto de muchas cuartillas. Pues bien, sería recomendable ejecutar el corrector ortográfico de manera tal que se haga automáticamente mientras hago otra cosa. Cuando termine, que guarde un reporte con las correcciones que hay que hacer en un archivo que pueda consultar. Una tercera opción es hacer una "corrección rápida", usando para ello una lista de palabras más frecuentemente usadas en el español. Estas pueden encontrarse aquí.

Con esto dicho, va el reto: hágase un editor de textos (puede ser del tipo bloc de notas, es decir, sin necesidad de tipos y tamaños diferentes de letras), que corrija un texto usando estas posibilidades, mientras más, mejor. Es decir, mientras más características puedan usarse (de las descritas), será un mejor candidato a ganar el premio del reto lúdico.

Más de uno preguntará: ¿Y de dónde saco el diccionario de palabras a usar? Buscando en el oráculo de Internet, encontré este sitio, que Giusseppe Domínguez tecleó las 91 mil palabras del diccionario de la RAE y las puso en un archivo de texto, el cual puede descargarse de este enlace. El autor de semejante esfuerzo nos da algunas estadísticas sobre las palabras:

• Palabras en a.txt = 11135
• Palabras en b.txt = 3861
• Palabras en c.txt = 12697
• Palabras en d.txt = 5880
• Palabras en e.txt = 7332
• Palabras en f.txt = 2966
• Palabras en g.txt = 3000
• Palabras en h.txt = 2215
• Palabras en i.txt = 3308
• Palabras en j.txt = 982
• Palabras en k.txt = 117
• Palabras en l.txt = 2531
• Palabras en m.txt = 5598
• Palabras en n.txt = 1351
• Palabras en ñ.txt = 82
• Palabras en o.txt = 1468
• Palabras en p.txt = 7951
• Palabras en q.txt = 521
• Palabras en r.txt = 4603
• Palabras en s.txt = 4713
• Palabras en t.txt = 4980
• Palabras en u.txt = 500
• Palabras en v.txt = 2031
• Palabras en w.txt = 28
• Palabras en x.txt = 48
• Palabras en y.txt = 267
• Palabras en z.txt = 774

Palabras en total = 90939

Con esto todo está en la mesa. ¡A programar!

El ganador (si es de la Ciudad de México), se hará acreedor a una taza con el logotipo de la Morsa. Si es de otro país o de provincia, le mandaremos un USB de al menos 16 GB.

Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas satisfactorias, ganará quien la haya mandado primero.

El ganador cede su código fuente a la comunidad. Los que estén interesados deberán mandar sus programas a morsa@la-morsa.com. Quien resulte ganador deberá entregar el código fuente para compartirlo con la comunidad.

Digamos que la idea es promover la creación de software y además, hacer que ésta sea de código abierto. Si el autor decide no poner su código accesible, perderá su premio.

Reto lúdico: Números palindrómicos, el problema del número 196

Un nuevo reto de la programación lúdica: Sabemos que el número 196 no se ha podido demostrar que es palindrómico. Hállese la mayor cantidad de iteraciones y el mayor número al que se pueda llegar sin que el programa falle. Ése es el reto.

Aún en esta era de la computación masiva, no se ha hallado que la conjetura sobre los números capicúas, que fue el reto de programación lúdica pasado, funcione para el número 196, la cual sigue siendo un problema matemático sin resolver. Se sabe que los números, entre el 100 a 999, 13 no llevan a ningún palíndromo. Estos son: 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986. El 196 es el primero de ellos y evidentemente su retrógrado el 691 tampoco llega a ser capicúa.

Podemos entonces considerar dos grupos, el primero, conteniendo 196, 295, 394, 493, 592, 689, 691, 788, 790, 887 y el 986, y un segundo grupo compuesto por el 879 y el 978. A los números 196 y 879 se les llama “números generadores” o “semillas”. La razón de esto es que el 691 es el retrógrado del 196 por lo que son parte del mismo grupo: 196 + 691 = 691 + 196 = 887. El número 295 y el 592 llevan al mismo número, 887, después de una primera iteración, por lo que se consideran parte del mismo grupo.

En abril de 1984 apareció en la columna de Scientific American “Computer Recreations”, un artículo sobre estos patrones matemáticos   y los esfuerzos para probar la conjetura han sido extraordinarios. Por ejemplo, John Walker indica que el 12 de agosto de 1987 puso su estación de trabajo Sun 3/260 para tratar de resolver si el 196 era un número palindrómico. El programa tenía algunos controles, que se guardaban en un archivo cada dos horas y en caso necesario el sistema reiniciaba la tarea desde los últimos datos hallados en dicho archivo. Así, si algo fallaba (por ejemplo, se cortaba la energía eléctrica), podía reanudarse el proceso sin problemas. Entonces el programa corría día y noche sin intervención humana.

Dice Walker que finalmente, casi cuando se cumplían tres años de ejecución ininterrumpida del software, cinco minutos antes de la media noche, el programa mandó el siguiente mensaje:

Stop point reached on pass 2415836.
Number contains 1000000 digits.

(El número contiene 1000000 de dígitos)
(Punto de detención en la iteración 2415836)

Así entonces, el número 196 había crecido hasta un millón de cifras sin que fuese palindrómico.

Esto podría quizás considerarse el final de la historia, pero sorpresivamente en 1995, Tim Irvin retomó el trabajo de Walker usando una supercomputadora, empezando en el número de un millón de cifras y cuando el sistema llegó a un número con dos millones de cifras, encontró también que no había sido localizado ningún número palindrómico.

Irvin inició su búsqueda el 5 de julio de 1995 y después de una semana de pruebas y corrección de errores, el programa trabajó casi ininterrumpidamente, a excepción de las horas de respaldo diario del sistema. En la mañana del 22 de agosto de ese mismo año, el programa se detuvo en los dos millones de cifras, de nuevo, sin encontrar el ansiado número capicúa.

Irvin terminó su búsqueda y aunque ha jugado con la idea de seguirla, considerando que el sistema de súper cómputo se ha renovado, parece decidido a no continuar por diversas razones. Por una parte, el tiempo de súper cómputo no es barato y por otra parte, hay muchos problemas más importantes que atacar que el resolver la conjetura. No obstante esto, Irvin pone a la disposición el programa y los controles para que el sistema se detenga cuando se llegue a 3 millones de cifras.

Pero Jason Doucette, en 1999 decidió retomar el trabajo de Irvin y usando una computadora casera, entró a esta gran búsqueda. En este caso, el programador desarrolló software en ensamblador (buscando optimizar los recursos), y en 1999, el 9 de agosto, se inicio la ejecución del software, en una máquina Pentium II, a 266 Mhz. El sistema alcanzó la marca de un millón de cifras en 1 día y 18 horas, lo cual es notable si consideramos que Walker tardó 3 años casi en llegar a esa cantidad de cifras.  5 días y 10 horas después, Doucette llegó a la marca de los 2 millones de cifras. Se compararon los resultados y no se hallaron divergencias, por lo que se asume que el software no tiene errores.

La marca de los tres millones de cifras se alcanzó 8 días y 7 horas después. Desde luego, mientras mayor es el número más sumas tendrá que hacer. 13 días y 8 horas después se alcanzó la cifra de 5 millones de dígitos. Al llegar a este resultado, Doucette cambio de hardware y el programa reinició su búsqueda en una máquina Celeron, con un procesador de 400 Mhz (lejos, muy lejos, del estándar actual).

Eventualmente Doucette llegó a más de 13 millones de cifras y ahí decidió detenerse aparentemente  . Sin embargo, Ian Peter logró la cifra de 10 millones de dígitos en poco más de cinco horas. Esto lo hizo en una máquina de 500 Mhz Athlon.

El trabajo de Ian Peter es además interesante porque encontró algunos números palindrómicos que tardan más que las 24 iteraciones que la mayoría de los números necesita. En la siguiente tabla se observan estos números palindrómicos, con sus respectivas iteraciones y el palíndroma generado:

Finalmente Wade van Landingham entró a la búsqueda y a partir de casi 14 millones de cifras de Doucette, llegó a un número de 300 millones de dígitos, lo cual son casi 725 millones de iteraciones y de nuevo, parece no encontrarse el capicúa que se inicia con 196. Sin embargo, hay que hacer énfasis en que hasta el momento lo único que podemos concluir es que no se sabe si el 196 es número palindrómico. Esto sigue siendo indecidible  .
El hecho de que no todos los números sean capicúas podría hacernos pensar que existe una asimetría en la conjetura, aunque en términos reales, no es el único número que no cumple con ello. Los matemáticos se preguntan, sin embargo, ¿Qué tiene de especial el número 196?

Todo lo anterior es simplemente el preludio del nuevo reto de programación lúdica. Se trata de procesar el número 196 para ver si es palindrómico (lo cual no sabemos a pesar de que se han hecho millones de iteraciones) y entregar el número más grande al que el programa del concursante pueda llegar. Por ejemplo, si pusiésemos a trabajar el 89 y llegásemos a la iteración 24 que da 8813200023188, éste sería el valor más grande que podríamos encontrar del número con el que partimos. Pero en el caso del 196 no parece haber un límite de iteraciones y de lo que se trata es que el concursante entregue el mayor número con la mayor cantidad de iteraciones.

Cabe señalar que si hay más de un programa que llega al máximo valor, ganará quien lo haya enviado primero. El resultado es inapelable.

Al ganador (si es de la Ciudad de México), le daré una taza con el logotipo de la Morsa. Si es de otro país o de provincia, le mandaré un USB de al menos 8 GB. La razón de esto es que mandar una taza por mensajería es estúpidamente caro.

Las soluciones me las pueden mandar a morsa@la-morsa.com.

Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas que den el mismo tiempo al procesar la lista de 10 mil números, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto.

En este caso no hay restricción en qué lenguaje usar. El concursante tiene que mandar su código fuente, el ejecutable (si aplica) y los resultados obtenidos. El concurso tendrá una vigencia de unas tres semanas, aproximadamente. Así que manos a la obra, digo, dedos al teclado…

Ps. El concurso anterior (sobre la conjetura palindrómica) se ha cerrado y en unos días pondré quién fue el ganador. Estén atentos.