lunes, noviembre 11, 2013

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!

12 comentarios:

Anónimo dijo...

Me ha gustado esta entrada, lo de la mayéutica es algo que muchos adultos anclados en costumbres del pasado deberían aplicar en su vida antes de abrir la boca en los tiempos que corren y quedar en ridículo (mi padre -y seguramente el de muchos otros-, es ejemplo claro, siempre dando lecciones de boca en boca sin conocimiento de causa, hasta de los temas que ignora).

Nunca te acostarás sin saber algo más, me guardo la publicación para futuras consultas. Y para el de la beca, ojalá le sirva y le pueda servir para un futuro, le deseo lo mejor, el esfuerzo por pasión es de las cosas que más valoro.

Anónimo dijo...

Una de las mejores entradas que he leido en tiempo en los diversos blogs que sigo. Tiene de todo, caso real de experiencia propia y una muy buena "moraleja"

Muy buena historia chema, me quedo con esta frase: "no olvidar que lo que más nos incapacita para aprender es pensar que ya sabemos."

Saludos

Curro dijo...

Pues yo voy a discrepar, nunca me han convencido esas entrevistas de trabajo donde te piden programar. Por varias razones, pero principalmente porque te arriesgas a contratar a alguien que sólo se ha aprendido de memoria los típicos programas que piden (el de unir puntos de tu ejemplo es uno de ellos) y que en realidad no tiene ni idea de programar. Siempre he creído mejor hacer preguntas más personales para saber si la persona estudió informática por las salidas o por vocación. Esta forma es más difícil claro puesto que tienes que saber "psicoanalizar" pero haciendo analogía con tu ejemplo de código es la manera más eficaz de unir los dos puntos (el del candidato y el del trabajo).

P.D. Lo de pedir que haga un filtro antialiasing a un candidato a analista de seguridad me parece un poco surrealista :)

Maligno dijo...

@Curro, las becas son para desarrolladores.

Saludos!

Curro dijo...

Ok, pero eso solo responde a lo de pedir un filtro antialiasing :)
De verdad que creo que pedir una prueba de programación no es la manera más eficaz de buscar buenos candidatos, me recuerda demasiado a las típicas de preguntas de "¿con qué animal se identifica?". Al final de lo que se trata es de buscar gente que disfrute con el trabajo que va a realizar.
Saludos!

Anónimo dijo...

Pues qué quieres que te diga Chema, yo coincido con algunas de las personas que han comentado esta entrada del blog: pedir a los candidatos que programen un ejemplillo tonto de algoritmia no es la mejor forma de buscar un candidato ideal.

Maligno dijo...

@Anónimo, en las becas Talentum buscamos gente que pueda programar tecnología. Este tipo de pruebas es habitual en todas las empresas tecnológicas, como en Tuenti, Facebook, Google, Microsoft o Yahoo!. En mi caso, que busco ver cómo piensan y razonan para solucionar problemas me parece una manera perfecta para en el poco tiempo que hay disponible sacar el máximo de información.

Saludos!

Curro dijo...

No sé si quitaron este tipo de preguntas pero al menos Google sí reconoció que su manera de hacer entrevistas era ineficaz http://www.deathandtaxesmag.com/200732/google-admits-its-famous-job-interview-questions-were-a-complete-waste-of-time/
De todas formas está claro que lo importante es no agarrarse a la prueba como si fuera infalible, si a pesar de "fallar" ves algo interesante en el candidato pues no deberías dejar de contratarlo. Que es al fin y al cabo lo que hiciste.
Yo es que como soy de pensármelo mucho todo, igual es que le tengo un poco de manía a esas pruebas :)

Anónimo dijo...

solo bastaba con preguntarle:

si en un bosque cae un arbol y no hay nadie para escucharle. hace ruido?

xD! saludos

Anónimo dijo...

Esta entrada me ha recordado mis clases de Algorítmica, donde se decia a menudo: No se debe usar una solución recursiva si existe una solución iterativa clara.

Darwin Reencarnado dijo...

elladodelmal.Chema, Saludos desde Argentina! Me encantó la anécdota. Si bien se argumenta que habría que usar técnicas más "psicológicas", creo que esta técnica es lo más “psicológicamente efectivo”. Porque lo importante no es lo que “sabe de memoria”, y ni tampoco que dé una respuesta “correcta”. Lo que se analiza son las reacciones del entrevistado ante problemas.
Mi conclusión es que el entrevistado tiene las siguientes características: ambición, responsabilidad, resiliencia, y una de las características que más importantes (desde mi punto de vista), es la humildad. También destaco actitudes de intentar resolver los problemas desconocidos, buscar alternativas, reconocer errores, aprender de ellos y convertirlos en fortalezas. Todas estas cualidades, son propias de la persona, y no pueden “actuarse”, o mentirse en una entrevista. Como dice el refrán: “En la carrera se ven los pingos” (pingos=caballos de carrera).
Gracias por compartir tanto conocimiento en el blog!
Saludos!

Matu - Ontinet dijo...

Mas allá de si es útil o no pedirle a alguien en una entrevista que haga un pequeño ejercicio para poder evaluar su capacidad de resolución de problemas, me gusto mucho como lo hiciste porque fuiste mas lejos que eso y evaluaste a la persona detrás del código y su capacidad de adaptación a los cambios y a las criticas. Seguramente fue mas importante como reaccionó después que lo que pasó en la entrevista en si misma.
Ademas le diste la oportunidad de que se autoevalue y en el camino, aprender. Magistral!
Es algo que hecho mucho de menos en algunos "profesores" copy&paste.

Abrazos @Maligno!

Entrada destacada

Navaja Negra: La CON de Albacete el 29 de Septiembre @navajanegra_ab @elevenpaths @0xWord

Es la sexta edición de esta CON que comenzó hace ya más de un lustro en la ciudad de Albacete , reúne el próximo 29 de Septiembre a una b...

Entradas populares