← Volver a los ejercicios

Ternas pitagóricas: tres generadores, un filtro y un conjunto

Una terna pitagórica es una tupla (a, b, c) de enteros positivos con a * a + b * b == c * c, como (3, 4, 5). Para encontrarlas todas hasta un tope n no hay fórmula: se generan todas las combinaciones con 1 <= a <= b <= c <= n y se descarta lo que no cumple. Los tres generadores encadenados de la expresión for hacen lo primero y el if hace lo segundo. Avance paso a paso y cuente cuántas candidatas hay que descartar por cada terna que sobrevive.

1. Cuántas candidatas se prueban

Con n = 5, los tres generadores son c <- 1 to 5, b <- 1 to c y a <- 1 to b. Cada combinación que sale de ahí se prueba contra la condición pitagórica, pase o no pase.

¿Cuántas combinaciones (a, b, c) se prueban con n = 5?

2. El código y la búsqueda

paso 0 de 0
ternas encontradas:
ninguna todavía
■ líneas 3 a 5: los tres generadores arman una combinación ■ línea 6: la condición pitagórica decide si pasa ■ línea 7: solo las que pasan llegan al yield

Los contadores de la derecha de cada línea dicen cuántas veces se evaluó cada parte. El de la línea 5 cuenta las combinaciones armadas y el de la línea 7, las que sobrevivieron.

3. Las candidatas, una por fila

Las últimas catorce combinaciones probadas. Candidatas probadas hasta aquí: 0.

4. Esto es búsqueda exhaustiva

Con n = 5 la expresión prueba 35 combinaciones y deja una. El trabajo no está en encontrar (3, 4, 5): está en descartar las otras 34, una por una, y el código no tiene ninguna forma de saltarse ese descarte. Con n = 20 el contador de candidatas se dispara y las que sobreviven son seis.

Los tres generadores reparten el trabajo de forma desigual, y los contadores lo muestran: con n = 5, la línea de c se evalúa 5 veces, la de b 15 y la de a 35. Cada generador multiplica lo que hay dentro, así que el costo lo pone el generador más interno.

Lo que imprime println al terminar:

5. Las piezas de la expresión

La misma búsqueda escrita con flatMap, map y filter, sin expresión for:

Seis preguntas sobre las dos versiones y sobre lo que aporta cada pieza. Cada opción equivocada dice en qué consiste la confusión.

6. Lo que se lleva de aquí

Los generadores encadenados hacen dos cosas a la vez. Generan las combinaciones, como lo haría cualquier recorrido anidado, y además imponen a <= b <= c sin que haga falta un filtro: el extremo de cada rango es la variable del generador de afuera. Con b <- 1 to n y a <- 1 to n el mismo triángulo aparecería como (3, 4, 5) y como (4, 3, 5), y el filtro pitagórico no los distinguiría, porque 16 + 9 da 25 igual que 9 + 16.

El if de la expresión for y el .filter de la versión con flatMap son la misma cosa escrita en dos sitios. En la primera la condición queda al lado de los generadores que la alimentan; en la segunda se aplica al final, sobre la secuencia ya armada. Las dos devuelven el mismo conjunto, y eso es lo que comprueba ternasPHOF(20) == ternasPFor(20), que imprime true.

El .toSet del final no quita nada aquí: con a <= b <= c ninguna combinación se genera dos veces. Lo que cambia es lo que la función promete devolver. Un Set[(Int, Int, Int)] dice que lo que importa es qué ternas hay, no en qué orden se encontraron ni en qué posición están, y de ahí que ternasPFor(20) imprima las seis en un orden que no es el del hallazgo.