martes, 15 de abril de 2008

Distribución de letras

Esta máquina de escribir antigua usaba, en lugar de teclado, un dial semicircular. Moviendo una aguja se señalaba la letra a escribir, y apretando un botón se imprimía dicha letra. Otro botón hacía mover el carro para poner los espacios.

No queda claro en el dibujo cuál era la distribución de las letras en el dial; por lo tanto podemos imaginar el siguiente problema:

Suponiendo que la aguja empieza en un extremo del dial, ¿Cómo deberíamos disponer las letras de manera que, al tipear el Quijote, la aguja recorra la menor distancia posible?

4 comentarios:

Jesus dijo...

Parece lógico que las letras poco frecuentes deban ir en los extremos, y las más usadas en el centro.
Pero también hay que atender a que los pares de letras más frecuentes estén juntos.
Unas pruebas con textos cortos me han resultado en:
k,x,w,z, deben estar en los extremos.
La e, entre la d y n
La o, entre la d y r
La a, entre la l y la r
La i junto a la c
La t entre n y o ( o n y u)
Algo más dificil de explicar es que la g sale junto a la p o la q.

luisito dijo...

Quizas sea una buena idea repetir algunas letras muchas veces.

Marcos dijo...

luisito: sería más extraña aún la máquina si se repitieran letras.

luisito dijo...

Pero a lo mejor es util repetir letras. Por ejemplo dado que la 'a' se usa tan frecuentemente, podriamos distribuir dos o tres 'a' alrededor de la rueda. Si bien esto haria mas grande la rueda, posiblemente se compensaria con la ventaja de que no tenemos que moverla tanto.

Obviamente podria surgir un problema de optimizacion complicado si ademas pretendieramos que la maquina elija entre todas las 'a' cada vez. El modelo greedy de ir siempre a la que este mas cerca puede ser una buen primer paso.