Palabras anagramadas
En nuestra casa somos escuchantes del programa No es un día cualquiera de RNE. Nos gustan un motón de secciones: verba volant, el acabose... pero en la que participamos casi siempre es en las palabras anagramadas.
Cada hora se da una definición de palabra, y un anagrama de la misma. El anagrama puede ser de tres tipos:
- Directamente, una palabra o expresión
- El anagrama está dentro de la propia definición, y en ese caso se da el número de letras
- En último anagrama se suele formar con la primera y última letra de las soluciones anteriores.
Es un juego interesante para pensar, y a la vez es fácilmente resoluble mediante un programa de ordenador. El algoritmo es muy simple:
- Calcula el histograma de letras del anagrama. Por ejemplo, para
ANAGRAMA, el histograma es:A→4 N→1 G→1 R→1 M→1 - Compara su histograma con el de un corpus de palabras almacenadas
- Suelen quedar unas pocas palabras entre las que es fácil discriminar por la definición.
El código fuente está disponible en https://github.com/alvarogonzalezsotillo/palabras-anagramadas. Hay una segunda parte de este post en la que se migra el código a una página web.
Implementación del algoritmo
La siguiente implementación se ha realizado en lenguaje scala.
Palabra
Lo primero es una clase que encapsule una palabra y sepa calcular su histograma. También normaliza normaliza su representación, quitando espacios, acentos y mayúsculas.
El histograma se calcula de forma perezosa, ya que no es necesario calcularlo de todas las palabras (como ya se verá, basta con calcularlo de las palabras con la misma longitud que la buscada)
type Histograma = Map[Char, Int]
case class Palabra(p: String) {
import scala.concurrent.ExecutionContext.Implicits.global
private def quitaAcentosYEspacios(s: String): String = {
val acentos = Map(
'á' -> 'a',
'é' -> 'e',
'í' -> 'i',
'ó' -> 'o',
'ú' -> 'u',
'ü' -> 'u'
)
val sinAcentos = s.toLowerCase.map(c => if (acentos.isDefinedAt(c)) acentos(c) else c)
sinAcentos.replace(" ", "" )
}
lazy val size = palabra.size
lazy val palabra = quitaAcentosYEspacios(p)
lazy val histograma : Histograma = {
val ret = palabra.groupBy(c => c)
ret.map { case (c, set) => (c, set.size) }
}
}
Corpus de palabras
El programa necesita un vocabulario donde buscar las palabras. Una opción sería extraerlas de varios libros gratuitos del Proyecto Gutengberg, pero he encontrado un corpus de la Real Academia de la Lengua con 737799 palabras distintas, ordenadas por frecuencia de uso.
Orden Frec.absoluta Frec.normalizada
1. de 9,999,518 65545.55
2. la 6,277,560 41148.59
3. que 4,681,839 30688.85
4. el 4,569,652 29953.48
[...]
400040. procañasgordas 2 0.01
400041. procapellán 2 0.01
400042. procapitalista 2 0.01
[...]
Para leer las palabras utilizo una expresión regular por cada una de las líneas. Me quedo solo con las primeras 300000 palabras más frecuentes, y las agrupo por longitud.
def cronometro[T](msg: String)( proc : => T ) = {
val ini = System.currentTimeMillis()
val ret = proc
val fin = System.currentTimeMillis()
println( s"$msg: ${fin-ini} ms" )
ret
}
val palabras: Map[Int, Array[Palabra]] = cronometro("Lectura de palabras"){
val iterator = new Iterator[String] {
val palabrasFile = "./CREA_total.TXT"
val scanner = new Scanner(new FileInputStream(palabrasFile), "latin1")
val regex = """(?:\s*)(?:(\d|\.)*)(?:\s*)(\S*).*""".r
def hasNext = scanner.hasNextLine()
def next = {
val line = scanner.nextLine()
regex.findAllMatchIn(line).next.subgroups(1)
}
}
val limite = 300000
val todas = iterator.take(limite).map(p => Palabra(p)).toArray.sortBy(_.palabra)
val ret = todas.groupBy(p => p.size)
// COMO PALABRAS DE UNA SOLA LETRA, DEJAMOS SOLO a,o,y
ret.updated(1, Array("a", "o", "y").map(Palabra(_)))
}
Búsqueda de anagramas
Una vez tengo la lista de palabras, para econtrar los anagramas de una dada basta con buscar las que tienen el mismo histograma de letras. La búsqueda se realiza solo entre las que tienen la misma longitud.
def buscaCoincidenciaExacta(buscado: Palabra) = {
palabras(buscado.palabra.size).view.filter( _.histograma == buscado.histograma )
}
En algunos casos, el anagrama está formado por más de una palabra en una frase. En la pista no se dice qué palabras forman el anagrama pero se nos da su longitud. La función buscaExactoEnFrase busca entre todas las subsecuencias de palabras que sumen tantas letras como la longitud dada.
def buscaExactoEnFrase( frase: String, letras: Int ) ={
val f = frase.split("""\s+""")
val combinacionesDePalabrasConLetras = {
for (from <- (0 to f.size).view;
until <- (from to f.size).view;
slice = f.slice(from, until) if slice.map(_.size).sum == letras) yield {
slice.mkString
}
}
for (c <- combinacionesDePalabrasConLetras;
palabra = Palabra(c);
p <- buscaCoincidenciaExacta(palabra)) yield {
p
}
}
Cada palabra para adivinar tiene una definición y una pista. La pista (en los concursos que he visto) puede ser de tres tipos
- Una palabra: La palabra a adivinar es un anagrama de dicha palabra
- Una longitud: La palabra a adivinar es un anagrama de algunas palabras de la definición, con la longitud especificada
- La palabra final: Es la de la última definición. Se forma con la letra inicial y final de las tres palabras definidas con anterioridad. El concurso total es de 4 palabras, así que la cuarta siempre tiene 6 letras.
def resuelvePista( pista : (String,Any) ) = {
pista match{
// LA ULTIMA PALABRA SE CONSIGUE CON EL INICIO Y FIN DE LAS TRES PRIMERAS
case (msg, a:Array[String]) =>
val palabras = a.take(3)
println( s"${msg.toUpperCase}: Con inicio y fin de ${palabras.mkString(",")}" );
val s = palabras.map( p => p.head.toString + p.last.toString ).mkString
val p = Palabra(s);
for (c <- buscaCoincidenciaExacta(p)) {
println(" " + c)
}
// NOS DAN UNA PALABRA PARA EL ANAGRAMA
case (msg,p:Palabra) =>
println( s"${msg.toUpperCase}: Con anagrama $p" );
for (c <- buscaCoincidenciaExacta(p)) {
println(" " + c)
}
// EL ANAGRAMA ESTÁ EN LA DEFINICIÓN, NOS DAN EL NÚMERO DE LETRAS
case (frase,size:Int) =>
println( s"${frase.toUpperCase}: Anagrama en la fase, longitud $size" );
for (c <- buscaExactoEnFrase(frase, size) ) {
println(" " + c)
}
case _ =>
throw new Error("Se espera String->Palabra, String->Int o String->Array[String]" )
}
}
Solución a un día
Con estas funciones, ya es posible concursar para un día concreto. Por ejemplo, este es el código del concurso del 6/oct/2018:
def dia2018_10_06(){
println( "************ 6 octubre 2018");
val pistas = Seq(
"Vino de Francia" -> Palabra("piromántico"),
"Rediseña la licorería para poder albergar buenos recuerdos" -> 9 ,
"Vivir de administrar los remanentes de forma adecuada" -> 10,
"Trabaja de cara a la galería" -> Array("importación","relicario","mantenerse")
);
pistas.foreach( resuelvePista );
}
cronometro("Solución"){
dia2018_10_06()
}
Lo que hago es empezar con las tres primeras pistas, y deduzco las palabras entre las pocas opciones que se encuentran. Con eso, ya puedo introducir la cuarta pista en el programa. La salida del programa es la siguiente:
$ time scala palabras-afortunyadas.scala Lectura de palabras: 3334 ms ************ 6 octubre 2018 VINO DE FRANCIA: Con anagrama Palabra(piromántico) Palabra(importación) Palabra(importacion) Palabra(patronímico) REDISEÑA LA LICORERÍA PARA PODER ALBERGAR BUENOS RECUERDOS: Anagrama en la fase, longitud 9 Palabra(licorería) Palabra(relicario) Palabra(preparado) Palabra(recuerdos) VIVIR DE ADMINISTRAR LOS REMANENTES DE FORMA ADECUADA: Anagrama en la fase, longitud 10 Palabra(mantenerse) Palabra(remanentes) TRABAJA DE CARA A LA GALERÍA: Con inicio y fin de importación,relicario,mantenerse Palabra(merino) Palabra(minero) Palabra(minore) Solución: 2341 ms scala palabras-afortunyadas.scala 15,23s user 0,29s system 94% cpu 16,397 total
En cuanto al rendimiento, en mi Intel(R) Core(TM) i3-3120M CPU @ 2.50GHz el programa tarda aproximadamente:
- 11 segundos en compilarse y lanzarse
- 3 segundos en leer el corpus
- 2 segundos encontrar las soluciones
Para probar el código en tu propio ordenador, puedes descargarlo de https://github.com/alvarogonzalezsotillo/palabras-afortunyadas