La Mayéutica y el problema de la recta pintada píxel a píxel

Durante la semana pasada he realizado casi todas las entrevistas a l@s jóvenes que se presentaron a la prueba de selección de las becas Talentum para Eleven Paths.  He de decir que el proceso ha sido interesante y satisfactorio, porque he visto mucho potencial en algunos de los que he entrevistado, lo que me ha encantado.

Durante los 10 a 15 minutos que tengo para entrevistar cara a cara a los que voy seleccionando, tengo que intentar descubrir lo mejor y lo peor de cada uno de los entrevistados. Eso es algo que nunca es sencillo a priori, ya que en esos minutos puedo fallar yo con las preguntas o ellos con las respuestas, así que procuro ceñirme a lo que más luzca de su currículo y preguntarles sobre ello. Por supuesto, intento saber si saben lo que dicen que saben, pero también si van a poder aprender y crecer en el tiempo que estarán en la beca.

Esto es importante, pues muchos de los jóvenes que han salido ya del programa Talentum han continuado después su andadura profesional en startups como hiyalife, en empresas como Telefónica I+D, montando su propia aventura de emprendimiento como CuaQea, ayudando a los más jóvenes en Talentum Schools o, por supuesto, en nuestra Eleven Paths donde ya hay varios.

Esta vez, la prueba que utilicé con bastantes de los llegados para ver si serían capaces de programar y de resolver problemas fue un algoritmo clásico de los inicios de la computación digital de los que se estudian en algorítmica y geometría computacional del que he discutido a ratos con mi compañero y amigo Palako: 

"Dados dos puntos de una matriz, pintar una línea recta en una pantalla de píxeles pintando punto a punto."

El problema es muy sencillo de entender, pero resolverlo en un corto espacio de tiempo y en papel no está al alcance de todos, por lo que nos sirve para sacar mucha información de los jóvenes que tenemos delante. A la hora de buscar una implementación hay que tener presente que puede haber líneas que sean diagonales perfectas con pendiente 1, pero también rectas con pendiente mayor que 1 y menor que 1, lo que da como resultado la aparición de implementaciones óptimas con distintas aproximaciones.

Ahí buscamos cosas como ver cómo hacen el tratamiento de errores - si lo hacen -, la elección de tipos de datos (¿tiene sentido usar valores enteros o es mejor con enteros sin signo?), si construyen clases y métodos para hacer el código más sostenible y, por supuesto, si son capaces de resolver el algoritmo de la forma más eficiente.

Para los que disponen de más tiempo, el problema se lo complicamos un poco más, buscando que apliquen algún filtro de antialiasing para resolver el problema de los picos en las rectas. Y para nota, si eres capaz de resolver el problema de antialiasing teniendo en cuenta la posibilidad de que el fondo sobre el que se imprime la línea recta pueda tener diferentes colores - esos para los que vayan a ser capaces de entender porque las herramientas de retoque fotográfico funcionan cómo funcionan -.

Figura 1: Tres tipos de rectas que pueden tener que pintar

La resolución sencilla, como se puede ver en la imagen, es calcular la función de la recta como f(x)=mx+n o como x=(f(x)-n)/m - que sería para dar la vuelta al eje y calcular los valores de X en función de los valores de Y - utilizando valores reales. Cómo no se pueden pintar píxeles en puntos 2.1 o 2.3, pues se aplica la función round() y listo. 

La pérdida de precisión en valores decimales es lo que después se puede utilizar para elegir una política de antialiasing, definiendo algún rango entre round(valor real) y valor real para poner un color intermedio - que podrá ser dependiente o no de los colores de fondo y los colores de paleta del pincel (en el caso de los que quieran aplicar filtros de antialiasing avanzados).

En este proceso me he encontrado con muchos jóvenes que no han sabido hacerlo, otros que pensaban que el problema era más fácil, y algunos que buscaban soluciones curiosas. Una de ellas me llamó la atención. Propuso una solución usando recursividad.

Las soluciones recursivas no suelen ser de lo más eficiente en cuanto a tiempos, por el consumo que genera solo la gestión de la pila en el sistema operativo, pero no obstante le quise escuchar para ver cómo pensaba. En su solución me planteó una implementación que se basaba en lo siguiente:

"Si el punto de origen no es igual al punto final, entonces calculo el punto medio y llamo recursivamente a pintar una recta entre el punto origen y el punto medio y otra recta entre el punto medio y el punto final".

Esta solución es un ejemplo típico de un algoritmo de Divide y Vencerás (Divide & Conquer) y aunque no lo explicó correctamente verbalmente porque en su planteamiento inicial hablaba de si no es el punto medio desplazar X siempre, la solución funciona si se implementa bien. El problema es que será menos eficiente, debido a la implementación recursiva de la solución. Sin embargo, el joven me dijo que él pensaba que su solución era mucho más eficiente que la propuesta... así que le dije:

"OK, vete a casa, y hazte un programa en Java al que le pase dos puntos  por teclado y me saque  por pantalla la lista de puntos que habría que pintar, a ver qué pasa"

Por la tarde me había mandado una solución, pero me había mandado implementada la solución que yo le conté, así que volví a insistirle para que programa su método, con el objetivo de que se diera cuenta del fallo del recorrido siempre en el eje X, y de que comprobara que la implementación de una solución influye en la eficiencia de la solución.

Y me lo programó y me lo envió, resolviendo el problema y detectando el bug que tenía en el desplazamiento siempre en el eje X, que podría dar situaciones en las que para haya rectas que para X=1,Y=1, y para X=2, Y valga 5, con lo que si solo recorres en X pintando un píxel quedarían rectas discontinuas. Por supuesto, yo continúe pidiéndole cosas, que ya que él estaba dispuesto a trabajar y aprender, yo quería que le sirviera de algo la experiencia, así que le envié un correo que decía:

"Vale, ahora mídeme tiempos, con trazas y me dices cuál es más rápido."

Y lo hizo, y me contestó lo siguiente:

"Sorprendente están casi igualados, pero tu método es aproximadamente 1 milisegundo más rápido que el mío el 70% de las veces."

Llegados a este punto, era el momento de que entendiera el porqué de hacer bien el código. Él estaba analizando sus propios programas, que es algo que se ha perdido mucho, y que es fundamental en el mundo de la tecnología. De hecho, en las entrevistas técnicas de las grandes empresas tecnológicas, después de que apliques una solución te preguntan siempre: "¿Cómo lo mejorarías?".

Yo le había planteado siempre el problema a todo el mundo con un dibujo de una matriz como el que os he puesto con una tablita pequeña, así que en esta ocasión ya le contesté con un correo que desvelaba la trampa inicial del problema:

"¿Y si hubiera 1024x768 píxeles cuánto tiempo sería mucho más rápido? Haz un cálculo a ver.. Y pásame capturas de todos los resultados }:)"

Y se hizo la luz en él que me contesto con un:

"He hecho varias pruebas en cada programa para hacer media, y queda demostrado que en esas magnitudes el tuyo es un 30%-40% más eficiente. La verdad es normal, no había caído yo que las funciones recursivas consumen muchos recursos...no debí subestimar a la ecuación de la recta."

Cuando yo iba al instituto, hubo algo que me marcó de las clases de filosofía, y fue el método de enseñanza que empleaba Sócrates, el maestro de Platón. Él lo llamaba Mayéutica, y consistía en cuestionar todos los planteamientos que el alumno pensaba sólidos, para dejar que el conocimiento naciera de él y no de que alguien se lo hubiera dicho. Nunca se me olvidó aquella clase, y siempre procuro aplicármelo a mí mismo para no olvidar que lo que más nos incapacita para aprender es pensar que ya sabemos. Gran error.

En el día de hoy, la mejor forma de aprender cosas es por medio de la experimentación propia, y teniendo un sistema informático en casa tenemos una capacidad de experimentar cuasi infinita que nos puede ayudar a aprender cada día nuevas cosas. Un libro, un compilador, Internet e infinitas pruebas. Parafraseando a otro Griego que zanjó una discusión con una solemne frase que dice "el movimiento se demuestra andando", a programar se aprende programando.

Si estás intrigado por ello, he de decirte que sí, que le he dado la beca Talentum a este joven, para que continúe aprendiendo con nosotros los próximos seis meses y veamos a dónde puede llegar en el futuro. En sus manos está.

Saludos Malignos!