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.
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.
(a, b, c) se prueban con
n = 5?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.
Las últimas catorce combinaciones probadas. Candidatas probadas hasta aquí: 0.
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:
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.
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.