Skip to content

Solución: Hawking

by en 13/04/2014

¡Hola!

Esta semana os proponíamos un acertijo en el que había que colocar las letras en un “tablero” de modo que se minimizara el coste de referenciar las letras de una determinada frase sabiendo que el coste de cada referencia era la suma de la posición x y la posición y de cada letra dentro del tablero. Dicho así suena muy confuso, de modo que os poníamos el siguiente ejemplo. En el tablero:

1 2 3 4 5 6
1 A B C D 1 2
2 E F G H 3 4
3 I J K L M N
4 O P Q R S T
5 U V W X Y Z
6 5 6 7 8 9 0

la palabra “COSMOS” tiene un coste de:

(3 + 1) + (1 + 4) + (5 + 4) + (5 + 3) + (1 + 4) + (5 + 3) = 39

Os preguntábamos el menor coste posible para las frases “COSMOS”, “PROGRAMAME”, “ACEPTA EL RETO” y “MUCHO POR PROGRAMAR”, sabiendo que en cada frase recolocamos las letras a voluntad, y que un espacio no supone coste alguno.

Por desgracia, esta semana ¡nadie se ha animado con la solución! 😦 De primeras puede que impusiera… pero era cuestión de pensarlo un poco y resulta bastante sencillo. Para cada frase, si queremos minimizar el coste tenemos que conseguir que las letras más frecuentes cuesten lo menos posible. Como el coste de cada casilla es la suma de la x y de la y podemos saber los costes de cada celda antes de colocar las letras:

1 2 3 4 5 6
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 4 5 6 7 8 9
4 5 6 7 8 9 10
5 6 7 8 9 10 11
6 7 8 9 10 11 12

Ordenando los costes de las celdas y poniéndolos todos seguidos tenemos:

2 3 3 4 4 4 5 5 5 5 6

que salen de recorrer el tablero original por diagonales.

Ahora, para cada frase lo que queremos, como hemos dicho, es que las letras más frecuentes nos cuesten lo menos posible. Lo que tenemos que hacer es contar el número de apariciones de cada letra, ordenarlas por número de apariciones y darles a cada una el siguiente coste de la lista anterior.

Así, para “COSMOS”, la O y la S aparecen dos veces (da igual en qué orden las coloquemos), y la C y la M sólo una. Por tanto, los costes que queremos tener son:

Coste 2 3 3 4 4 4 5 5 5 5 6
Letra O S C M
Nº aparic. 2 2 1 1

Si multiplicáis el número de apariciones de cada letra por el coste (en la fila superior) obtendréis el resultado para “COSMOS”, que resulta ser 17.

Con “PROGRAMAME” la tabla queda:

Coste 2 3 3 4 4 4 5 5 5 5 6
Letra R A M P O G E
Nº aparic. 2 2 2 1 1 1 1

y el coste es 33.

Si hacéis lo mismo con “ACEPTA EL RETO” llegaréis al coste 40, y con “MUCHO POR PROGRAMAR” a 58.

Como siempre, si os animáis a programarlo y queréis probar vuestra solución, podéis hacerlo aquí.

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: