La Historia

Entre probetas y tubos de ensayo, el Dr. Óxido y la Dra. Reducción ultiman los preparativos para la llegada de sus trillizos.

Ya lo tienen todo: mantitas de orbitales, pañales de grafeno y… ¡hasta matraces convertidos en biberones!

Lo único que no tienen aún: sus nombres.

«¡Serán químicos de pura cepa!», se dicen, «así que los nombres tienen que formarse usando solo símbolos de la tabla periódica.»

• Co + F + Fe: «¡Un nombre más duro que el hierro!»
• P + Au: «¡No tardará en hacerse de oro!»
• Ar + Ne: «¿Brillará por su nobleza?»
• S + Al: «¿Será un pequeñín dulce o más bien salado?»

Nuestra misión: filtrar su lista de favoritos, descubrir quiénes pasan la prueba elemental… ¡y descartar los que no sean dignos de un auténtico químico!

La Primera Hipótesis

Lo primero que pensé fue: «¡Esto es trivial!» Solo hay que recorrer el nombre, letra a letra. Una a una, comprobar si corresponde a un elemento de la tabla periódica.

Por ejemplo, probemos con el nombre “Coco”. Podríamos formarlo con: carbono, oxígeno, carbono y oxígeno.

Probemos también con “Whisky”. Sí, suena más a nombre de mascota… pero nos vale como ejemplo. Podríamos formarlo con: Wolframio, hidrógeno, yodo, azufre, potasio e itrio.

Parece fácil, pero pronto nos damos cuenta de que no es tan sencillo. Por ejemplo, nombres como “Erica” no podrían formarse si solo tomamos una letra cada vez: no hay ningún elemento cuyo símbolo sea E, R o A. ¿Podríamos afirmar con seguridad que “Erica” no es elemental?

Puedes probar cualquier nombre que quieras en la siguiente caja de texto y explorar paso a paso cómo se intenta formar con símbolos de la tabla periódica de un solo carácter a la vez:

En la tabla periódica hay 14 elementos de una sola letra y 104 de dos letras. Ninguno de tres o más, eso es también un detalle importante.

Si miramos con atención, encontramos Er (erbio) y Ca (calcio). Esos dos elementos, junto con el yodo (I), nos permiten formar “Erica”.

Parece que la clave está en tomar una o dos letras a la vez. Esa es la decisión: ¿una o dos? ¿Cuándo conviene tomar una? ¿Cuándo dos? ¿Puede esa decisión afectar al resultado?

Y entonces me pregunto: ¿Habrá más de una manera de formar un nombre con elementos?

El caso de “Coco” es muy interesante. Co puede formarse de dos maneras: con carbono (C) y oxígeno (O), o con cobalto (Co):

Por lo tanto, “Coco” se puede formar de 4 maneras distintas:

Debido a que hay elementos de dos letras, hay distintos caminos para formar un nombre. El problema se vuelve más complejo, sí, pero también más interesante.

El Algoritmo Recursivo

Cada vez que intentamos formar un nombre, hay que tomar una decisión: ¿Usamos una letra o dos? Esto se repite una y otra vez.

Como hay varios caminos posibles, debemos explorarlos todos. No vaya a ser que nos saltemos una forma válida.

Podríamos imaginar este proceso como un árbol de decisiones: desde el principio, intentamos construir el nombre símbolo a símbolo, tomando uno o dos caracteres por vez.

Veámoslos visualmente, con “Erica” como ejemplo. Al principio, tenemos dos opciones: tomar E o tomar Er. El camino de la E se acaba rápido. No hay ningún elemento que empiece por E. Pero si tomamos Er, seguimos adelante, porque Erbio (Er) sí es un elemento.

Ahora el problema se reduce a formar “ica”. No importan las letras que hayamos tomado antes, solo nos queda resolver “ica”, repitiendo el proceso.

La I es yodo. Ic no existe como elemento. De nuevo, el problema se reduce a “ca”. Tenemos dos opciones: C y Ca. Si tomamos C, nos queda solo “a”. Pero no hay ningún elemento que empiece por A. Ese camino termina aquí. Si tomamos Ca, ya no quedan más letras. Hemos llegado al final. Así que sí, el nombre “Erica” es elemental.

En resumen, hemos explorado todas las posibilidades y, al menos una nos permite formar “Erica”.

Implementación

Escribamos esto en Python.

Antes de nada, necesitamos todos los símbolos de los elementos en minúscula. En Python, lo más cómodo es usar un set: así podemos comprobar rápidamente si una cadena es un elemento válido.

ELEMENTS = {
    'h', 'he', 'li', 'be', 'b', 'c', 'n', 'o', 'f', 'ne', ...
}

Ahora sí, vamos a traducir nuestro árbol de decisiones a código. Imaginemos una función llamada is_elemental que nos dice si un nombre puede formarse usando solo símbolos de la tabla periódica.

Esta función recibe un nombre y nos devuelve True si es elemental, o False si no lo es.

def is_elemental(name: str) -> bool:

Empecemos por el caso más sencillo: si el nombre está vacío, significa que hemos conseguido formar todo el nombre con elementos. Así que devolvemos True.

if name == "":
    return True

Ahora, probamos la primera bifurcación del árbol: ¿Podemos tomar la primera letra como un elemento? Si es así, intentamos resolver el resto del nombre, quitando esa letra. Si funciona, devolvemos True.

if name[:1] in ELEMENTS and is_elemental(name[1:]):
    return True

Si no, probamos la otra bifurcación: ¿Podemos tomar las dos primeras letras como un símbolo válido? Si es así, intentamos resolver el resto del nombre, quitando esas dos letras. Si funciona, devolvemos True.

if name[:2] in ELEMENTS and is_elemental(name[2:]):
    return True

Y si ninguna de estas opciones funciona, entonces no hay manera de formar el nombre con elementos. Devolvemos False.

Así, cada llamada a la función representa una bifurcación en nuestro árbol de decisiones. Vamos probando todas las posibilidades, hasta que encontramos una que funciona… o nos quedamos sin opciones.

Problemas con la Recursión

Genial, ¿verdad? Veamos cómo se vería un árbol similar para el nombre “Coco”. Como ya vimos antes, este nombre tan corto se puede formar de hasta cuatro maneras distintas. Así que el árbol se verá un poco más complejo.

Tanto el carbono (C) como el cobalto (Co) son elementos, por lo que ambas ramas son válidas, reduciendo el problema a formar “oco” o a formar “co” respectivamente.

Sigamos un orden y vayamos por los caminos superiores primero. “Oco” podemos intentar descomponerlo en O y Oc. Rápidamente vemos que Oc no es un elemento, así que el camino se acaba ahí. Pero si tomamos O, el problema se reduce a “co”. Aquí tenemos dos opciones: C y Co. Co nos lleva al final, y si seguimos la rama del carbono llegamos a el oxígeno, que también es un elemento.

Llegados a este punto, nos toca volver a la rama que dejamos pendiente. La rama del cobalto. Al tomar Co nos queda de nuevo “co”. Tenemos dos opciones, C y Co. Si tomamos C, el problema se reduce a formar “o”, que podemos hacerlo con el oxígeno. Y si tomamos Co, llegamos al final del nombre directamente.

Pronto descubrimos algo curioso. Esta rama de aquí (la del subproblema “co”) es exáctamente igual esta de aquí abajo (la otra rama del subproblema “co”). Distintos caminos acaban llevándonos al mismo punto. Hay subproblemas que se repiten.

Para la mayoría de los nombres esto no es un problema. Por ejemplo, “Erica” solo tiene un camino válido. O nombres como “Francisco” tampoco tienen subproblemas repetidos. Pero en el peor de los casos, podríamos encontrarnos con nombres como “Cocococo”, que tienen un árbol enorme, con muchos subproblemas repetidos.

Se me ocurre pensar que ni siquiera es necesario construir el árbol entero. Podríamos dejar de construirlo en cuanto encontremos un camino válido. Pero, nos ayudaría esto en todos los casos? ¿Podríamos evitar construir el árbol entero? Con “Cocococo” desde luego que ayudaría porque con este camino ya sabríamos que sí es elemental. Pero qué pasaría si le añadimos por ejemplo una A al final? El árbol se vuelve a complicar y ya no podemos evitarlo. Al no encontrar rápidamente una rama válida, no nos queda más remedio que seguir explorando. ¿Entonces, qué podemos hacer?

Para evitar repetir trabajo, podríamos anotar los subproblemas que ya hemos resuelto en una libreta, de manera que cuando nos los volvamos a encontrar ya sepamos si se trata de un nombre elemental o no.

Pro Tip

No hace falta anotar palabras enteras. Solo índices: la posición del nombre desde donde empieza el subproblema.

Si quieres jugar con otros ejemplos puedes probar introduciendo nombres aquí debajo:

Visualizador de Programación Dinámica

Solución

A continuación, puedes ejecutar tu función contra casos de prueba y visualizar los resultados en una tabla:

Guión

Genial, ¿verdad? Veamos cómo se vería un árbol similar para el nombre “Coco”. Como ya vimos antes, este nombre tan corto se puede formar de hasta cuatro maneras distintas. Así que el árbol se verá un poco más complejo. Tanto el carbono (C) como el cobalto (Co) son elementos, por lo que ambas ramas son válidas, reduciendo el problema a formar “oco” o a formar “co” respectivamente. Sigamos un orden y vayamos por los caminos superiores primero. “Oco” podemos intentar descomponerlo en O y Oc. Rápidamente vemos que Oc no es un elemento, así que el camino se acaba ahí. Pero si tomamos O, el problema se reduce a “co”. Aquí tenemos dos opciones: C y Co. Co nos lleva al final, y si seguimos la rama del carbono llegamos a el oxígeno, que también es un elemento.

Llegados a este punto, nos toca volver a la rama que dejamos pendiente, la del cobalto. Habíamos tomado Co y nos queda de nuevo “co”. Nuevamente, tenemos dos opciones: C y Co. Si tomamos C, el problema se reduce a formar “o”, que podemos hacerlo con el oxígeno. Y si tomamos Co, llegamos al final del nombre directamente.

Pronto descubrimos algo curioso. Esta rama de aquí (la del subproblema “co”) es exáctamente igual esta de aquí abajo (la otra rama del subproblema “co”). Distintos caminos acaban llevándonos al mismo punto. Hay subproblemas que se repiten.

Para la mayoría de los nombres esto no es un problema. Por ejemplo, “Erica” solo tiene un camino válido. O nombres como “Francisco” tampoco tienen subproblemas repetidos. Pero en el peor de los casos, podríamos encontrarnos con nombres como “Cocococo”, que tienen un árbol enorme, con muchos subproblemas repetidos.

Se me ocurre pensar que ni siquiera es necesario construir el árbol entero. Podríamos dejar de construirlo en cuanto encontremos un camino válido. Pero, nos ayudaría esto en todos los casos? ¿Podríamos evitar construir el árbol entero? Con “Cocococo” desde luego que ayudaría porque con este camino ya sabríamos que sí es elemental. Pero qué pasaría si le añadimos por ejemplo una A al final? El árbol se vuelve a complicar y ya no podemos evitarlo. Al no encontrar rápidamente una rama válida, no nos queda más remedio que seguir explorando. ¿Entonces, qué podemos hacer?

Para evitar repetir trabajo, podríamos anotar los subproblemas que ya hemos resuelto en una libreta, de manera que cuando nos los volvamos a encontrar ya sepamos si se trata de un nombre elemental o no.

Pero no hace falta anotar palabras enteras.
Solo índices: la posición del nombre desde donde empieza el subproblema.

Eso ya es más eficiente.

Pero podemos ir aún más allá.

En lugar de pensar como un árbol, podemos pensar como una cinta.

Una fila de casillas.
Cada una representa una posición del nombre.

Empezamos por la primera.
La vacía.

A partir de ahí, caminamos letra a letra,
y cada vez que encontramos una posición que sabemos válida,
probamos avanzar una o dos letras más.

Cada casilla True dice:

“Hasta aquí, hemos llegado con símbolos válidos.”

Si el final del nombre también queda marcado como válido,
entonces el nombre entero se puede formar.

[🟢 Visual: dp = [True, False, True, False, True, True, True]]

El árbol desaparece.
Lo hemos aplanado.

No hay ramas.
No hay llamadas.
Solo una cinta de decisiones,
que se construye paso a paso.

Y lo más bonito es que ni siquiera necesitamos recordar toda la cinta.

En cada paso, solo nos interesa saber:

— ¿Puedo llegar aquí?
— ¿Y si tomo una letra o dos, ¿a dónde puedo ir?

Así que en realidad, bastaría con recordar las dos últimas casillas.

[🧠 Visual: círculo deslizante que solo guarda prev1 y prev2 mientras avanza.]

Avanzamos.
Olvidamos lo viejo.
Solo nos importa el presente… y un paso por delante.

Como la química bien hecha:
una reacción,
que se propaga limpia,
sin dejar residuos.

¿Y tu nombre? ¿Es elemental?

Referencias

• Worder Para buscar palabras formadas con elementos de una letra: BCFHIKNOPSUVWY
• Elemental - Codeforces Problema en el que se inspira este vídeo.