Rango Finito

fotoscódigoobservatorioshermanocerdo temas plots

programación

Codility

Codility es una plataforma en línea para evaluar habilidades de programación. Ayer, una de las empresas a las que he enviado hojas de vida me envió allá a hacer un examen de aptitud. Todavía no me he animado a hacerlo, pero ayer mismo estuve probando la plataforma aprovechando que ofrecen algunos problemas de prueba. Son problemas típicos (y (a posteriori) sencillos) de diseño de algoritmos. Hice dos más o menos rápido. En el que quedaba me embolaté y me fui a dormir cansado y frustrado pero la ansiedad que determina el 98% de mi existencia me despertó a las cuatro de la mañana con una idea vaga de cómo escribirlo (y otros pensamientos menos agradables). Finalmente me levanté a las seis e hice el deber. Al final, después de varios intentos, logré soluciones satisfactorias a todas las preguntas. Como lenguaje elegí Python, que también está disponible como opción en la prueba que tengo que hacer. Algo bueno de Python es que me puedo desentender de problemas de desborde con números muy grandes (varios de los tests que hacían a las soluciones intentan romperlas así.) Aquí subí las soluciones sin mayor comentario. Espero que el código sea suficientemente claro.

13

Hoy leí Flash Boys, de Michael Lewis. Me gustó mucho. Como es de esperarse dado el tema (high-frequency trading), el libro es una fábula moral sin moraleja o si se quiere con moraleja en desarrollo sobre la estructura interna del sistema financiero y su propensión natural al abuso y el robo. Lewis hace un trabajo muy bueno convirtiendo un problema técnico complicado y lleno de terminachos y matices en algo digerible y hasta apasionante. Lewis tiende a sugerir que hay un beneficio social en la bolsa y que estas firmas que abusan son un síntoma de problemas de regulación más que del carácter de la bolsa en sí como institución. Esto es probablemente discutible, pero dado que el monstruo existe y no hay razones para creer que vaya a extinguirse en el mediano plazo no está de más que de vez en cuando aparezcan personas como los protagonistas del libro intentando proponer un orden alternativo que tal vez no aniquile a la bestia (en este caso ellos no tienen ni siquiera ese propósito pues comparten con Lewis la fe en el beneficio social de ese casino sublimado) pero al menos la aplaque y contenga. Independiente de sus intenciones, es fascinante el problema que enfrentan y la suma de ingenios y talentos que se requieren para doblegarlo. Envidio a esas personas (su arrojo, su capacidad para asumir riesgos, su resistencia ante fracasos, su ambición) pero creo que odiaría vivir sus vidas (la presión, el estrés, la intranquilidad, la ansiedad, la ambición). Aunque Flash Boys se siente como literatura motivacional todavía no logro aislar qué es lo que me motiva o inspira.

Tercer triángulo

Dado un triángulo y un punto arbitrario dentro del triángulo, trace las perpendiculares a los lados del triángulo que pasan por el punto elegido. Cada perpendicular corta uno de los lados en un punto. Use esos puntos para construir otro triángulo y repita el paso anterior usando el mismo punto. Así construirá un segundo triángulo. Si repite una vez más el procedimiento, obtendrá un tercer triángulo anidado. Se puede demostrar (Ejercicio: Demostrarlo) que este tercer triángulo es geométricamente semejante al triángulo inicial (es decir, el producto de transladarlo, rotarlo, reflejarlo y agrandarlo o achicarlo proporcionalmente — si sirve de algo, recuerde que dos triángulos son semejantes si tienen los mismos ángulos interiores). Aquí hay un ejemplo: Esto sale si su navegador necesita reconsiderar urgentemente su lugar en el mundo. Use Firefox o Chrome.

El triángulo rojo es semejante al triángulo negro. Con el mouse puede mover tanto los vértices del triángulo inicial como el punto interior para intentar convencerse de que la semejanza no depende ni del tipo de triángulo original ni del punto elegido.

Como mi javascript (aquí el código) es torpe, no he logrado encontrar una forma buena de evitar que el punto elegido quede fuera del triángulo (por cierto: si el punto se sale del marco, recargue (Ejercicio/Duda: ¿Cómo evitar que el punto abandone el marco?)). Sin embargo, jugando con él, noté que realmente el resultado es cierto incluso si el punto está afuera del triángulo inicial y la construcción se replantea usando las líneas que generan los lados del triángulo en lugar de los lados en sí (que es como lo había calculado, de cualquier modo). Haga la prueba: saque el punto del triángulo. Afuera del triángulo original el triángulo rojo crece aunque las limitaciones de espacio me impiden constatar si alcanza un tamaño máximo (o si sigue creciendo hasta obtener el tamaño del triángulo original en el límite, por ejemplo (o si crece ilimitadamente)). Si el punto se restringe de nuevo al triángulo original, hay un tamaño máximo posible para el tercer triángulo (Ejercicio: ¿Dónde se obtiene? ¿De qué depende? ¿Pasa lo mismo afuera?). Otra duda/ejercicio: ¿En qué puntos se logra que el tercer triángulo tenga exactamente la misma posición que el triángulo original (es decir, sólo transladado y escalado, sin rotarlo ni reflejarlo)?

Aparentemente, este fenómeno es cierto también para polígonos (asumo convexos (?)) de cualquier número de lados: con un polígono de N lados se requiere repetir el procedimiento N veces para obtener un polígono semejante al original. (Ejercicio: ¿Cuál es la demostración general?)

Encontré este resultado en Futility Closet, donde transcriben un poema de una tal Mary Pedoe que usa la construcción como inspiración:

Begin with any point called P
(That all-too-common name for points),
Whence, on three-sided ABC
We drop, to make right-angled joints,
Three several plumb-lines, whence ’tis clear
A new triangle should appear.

A ghostly Phoenix on its nest
Brooding a chick among the ashes,
ABC bears within its breast
A younger ABC (with dashes):
A figure destined, not to burn,
But to be dropped on in its turn.

By going through these motions thrice
We fashion two triangles more,
And call them ABC (dashed twice)
And thrice bedashed, but now we score
A chick indeed! Cry gully, gully!
(One moment! I’ll explain more fully.)

The fourth triangle ABC,
Though decadently small in size,
Presents a form that perfectly
Resembles, e’en to casual eyes
Its first progenitor. They are
In strict proportion similar.

Ejercicio: traducirlo.

Diagrams

Una librería para hacer diagramas en Haskell.

Hackers & Developers

Hackers & Developers es una revista de temas informáticos editada por un equipo de programadoras hispanohablantes (mayoritariamente peruanas) distribuída en PDF. Parece bien producida aunque algo árida para mi gusto. La mayoría de los artículos son repasos veloces del uso de librerías o manuales express de lenguajes de programación. Me gustaría ver artículos con más sustancia y opinión que contrasten el contenido técnico.

De paso: Pybonacci es un blog en español muy bueno dedicado a Python y sus misterios.

Quién manda a quién

La columna de hoy trata sobre la transformación del computador en una máquina de entretenimiento con capacidades limitadas para ser programada por su usuario. Esta transformación está convirtiendo a los usuarios en espectadores. Aunque todavía es posible instalar compiladores e intérpretes de lenguajes de programación en los computadores actuales, esta posibilidad no es promovida por sus productores ni impulsada por establecimiento educativo. En un sistema económico consumido por el software semejante tendencia debería ser por lo menos cuestionable. Pero incluso sin entrar en discusiones económicas, dada la ubicuidad de los computadores y la digitalización progresiva de buena parte de las actividades humanas, la capacidad para programar ofrece a los usuarios una relación menos pasiva con las máquinas que administran sus vidas. Al final es un problema casi político: estamos permitiendo, por pura ignorancia, que los computadores personales se conviertan en otro medio de opresión y control.

*

Aquí veintisiete formas de aprender a programar en línea todas muy razonables (Codeacademy tiene hasta versión en español (dudoso, eso sí)). De paso recomiendo este manual de programación para Processing. Está muy bien escrito. También está este video log cheverísimo de desarrolo de una aplicación animada en Javascript.

La educación de un programador

En este artículo de (creo) 1978, E. W. Dijkstra habla de la relación íntima entre programación y matemática y de paso explica las razones por las que un programador competente debe tener bases matemáticas sólidas y amplias.

In reaction to the recognition that we did not know how to program well enough, people began to ask themselves how a really competent programmer would look like. What would we have to teach if we wanted to educate a next generation of really competent programmers? This became the central question of the study that later would become known as “programming methodology”. A careful analysis of the programmer’s task was made, and programming emerged as a task with a strong mathematical flavour. As I have once put it “Programming is one of the hardest branches of applied mathematics because it is also one of the hardest branches of engineering, and vice versa”. Why the programming task has such a strong mathematical flavour is something I shall indicate later.

A lower bound for what the adequate education of a really competent programmer should comprise was very convincingly established, but it was not an easy message to sell, because it demonstrated by necessity the total inadequacy of the education of what is known as “the average programmer”. The world today has about a million “average programmers”, and it is frightening to be forced to conclude that most of them are the victims of an earlier underestimation of the intrinsic difficulty of the programmer’s task and now find themselves lured into a profession beyond their intellectual capabilities. It is a horrible conclusion to draw, but I am afraid that it is unavoidable.

Creo que Dijkstra sobreestima el papel de los formalismos incluso dentro de la matemática. Buena parte de la labor de los matemáticos se funda sobre exploraciones erráticas no particularmente asentadas en la lógica (este asentamiento (sin duda necesario) hace parte de una etapa posterior del juego para blindar y presentar los resultados). De todas maneras es evidente que un cierto nivel de cultura matemática general (y comodidad para aplicarla) fortalece la capacidad de un programador para resolver problemas intrínsecos de su trabajo.

Cañón-Aspiradora Cíclica

James Paterson está haciendo un video-diario y tutorial de programación muy detallado del desarrollo de un juguetito en HTML5/CSS/JS. Perfecto para programadores eternamente principiantes como yo. (Vía Creative Applications.)

Hay otros mundos

Diez diferencias entre los terroristas blancos y los otros ¶ Cromatoforas (?) de calamar al ritmo de Cypress Hill ¶ Los cambios recientes en twitter ilustran bien el problema principal de las “redes sociales” centralizadas ¶ Un catálogo de técnicas para atrapar en imágenes estáticas (o casi estáticas) el paso del tiempo ¶ Es lindo el diario ilustrado de Gemma Correll ¶ Las vacas de Narayana se reproducen musicalmente (aquí un artículo al respecto (en alcanforado postscript) escrito por el compositor (Tom Johnson) y su amigo matemático) ¶ En tiempo de caudillos la política de ideas colapsaSiete problemas (pdf) que tal vez nunca oyó correctamente (con soluciones) ¶ Y un graficador tipográfico de flujos o algo así.

I went through a sudden period where I couldn’t read

Llevo meses postergando este ejercicio. Hace un par de semanas le dediqué una tarde, pero con la muerte del computador perdí el trabajo (entre muchas otras cosas), así que ayer por la noche lo volví a hacer. El resultado final es más oscuro que iluminador pero qué más da. Su génesis se encuentra en el largo monólogo de Chris Fogle que ocupa el capítulo §22 de The Pale King, la (pseudo)novela póstuma de David Wallace:

[I]nstead of reading something I’d count the words in it, as though reading was the same as just counting the words. [En lugar de leer algo contaba sus palabras, como si leer fuera lo mismo que sólo contar palabras.]

The Pale King (en español El rey pálido, traducción de Javier Calvo) es el esqueleto escueto de una novela que, estimo, rondaría las 1500 páginas (i.e., apenas un tercio de la novela fue concluída). Está estructurada (al menos en su primera edición) en 50 capítulos que, tras la muerte de Wallace, fueron dispuestos en orden lineal por su editor (Wallace no dejó mayores directivas al respecto). Mi pregunta inicial, intencionalmente ingenua, era cómo automatizar ese trabajo o al menos facilitarlo mediante un procesamiento automático del texto que involucrara, cómo no, conteos de palabras.

Gráfico del logaritmo de la extensión en carácteres de cada uno de los capítulos de The Pale King

Con el tiempo, sin embargo, me decanté por un ejercicio alternativo más a mi alcance: (1) Calcular una distancia léxica entre los capítulos, y (2) Disponerlos como puntos en un plano de manera que respetaran (dentro de lo posible) la distancia propuesta. Mi teoría era que un gráfico de ese estilo sería una herramienta útil (un criterio más) para facilitar la organización del texto. Ya no estoy tan seguro.

*

El primer componente del ejercicio es la distancia. La aproximación más intuitiva al cálculo de distancias entre documentos (este artículo de Anna Huang ofrece un sobrevuelo por varios métodos) se basa en recolectar una lista de palabras presentes en los documentos (más detalles adelante) y utilizarlas como base de un espacio vectorial. Bajo este esquema, a cada documento le corresponde una combinación lineal de la base con escalares elegidos de acuerdo al número de apariciones (frecuencia) de la palabra en el documento. Así, si la lista de palabras es $\{v_i\colon 1 \leq i \leq M\}$, entonces un documento $d$ es representado por el vector $M$-dimensional $$\sum_{i=1}^M f_i(d) v_i,$$ donde $f_i(d)$ es igual al número de apariciones de la palabra $v_i$ en el documento $d$. Una vez representados de esta manera, calcular distancias entre documentos se reduce a aplicar el teorema de Pitágoras.

Una versión sólo un poco más sofisticada de lo anterior se basa en la siguiente observación: si una palabra $v_i$ es muy frecuente en un documento $d$ pero también está presente en la mayoría de los documentos disponibles (supongamos que tenemos $N$ documentos) entonces probablemente no sea tan representativa del documento $d$ como cabría esperar inicialmente. Para tomar en cuenta esto, reescribimos la representación vectorial del documento $d$ como $$\sum_{i=1}^M f_i(d) \log\left (\frac{N}{P_i}\right ) v_i,$$ donde $P_i$ es igual al número de documentos que contienen la palabra $v_i$. De esta manera, la frecuencia de la palabra $v_i$ en cada documento es penalizada multiplicándola por un número ($\log(\frac{N}{P_i})$) que se acerca a cero entre más documentos la mencionen.

Así, al final el problema del cálculo de distancias se reduce a decidir cuál debe ser la lista de palabras que se utilicen como base del espacio vectorial de documentos. Siguiendo (a mano alzada) el artículo de Huang, tras una serie de filtros sencillos que removieran diferencias innecesarias y contenido irrelevante busqué (usando NLTK, la navaja suiza del análisis automatizado de texto) todas las palabras que aparecieran más de siete veces en todo el libro. 2060 palabras (aproximadamente un décimo de las que contiene el libro) cumplían con esta condición. Esto en particular implica que los capítulos del libro son representados por puntos en un espacio de dos mil y tantas dimensiones. Calcular distancias entre ellos, ya lo dije, es sencillo. Verlos en un plano es otra historia.

*

Había sobrestimado seriamente la incomprensibilidad del texto. Un conteo burdo de nombres propios en páginas 12-21 ofrece 38, 28, 17, 28, 40, 32, 31, 31, 18, 22. Número medio por página, 28,2, desviación estándar de 6,9, 70% de los datos a s de la media. Número promedio de palabras por página basado en una muestra de 2, 302. O sea 9% de comprensibilidad. Alto.

— H. DeWitt, Ese oscuro objeto del deseo

*

No sé por qué pensaba que el problema de aplanar dimensiones debía estar completa y contundentemente resuelto desde hace décadas. Fue difícil dar por mi cuenta con soluciones convincentes. Finalmente, Juan Manuel me sugirió revisar los métodos de manifold learning implementados en scikit-learn. Para mi sorpresa, varios de los algoritmos disponibles son bastante recientes y provienen de laboratorios de ciencias cognitivas interesados en visión. El que elegí para mi ejercicio, Isomap, fue desarrollado por Josh Tenenbaum (y amigos) cuando trabajaba en Stanford.

La conexión entre visión y reducción de dimensiones se basa en el hecho, permítome ser burdo, de que el ojo cuenta con (muchísimos) sensores que registran el estímulo (imaginen cada sensor como un vector independiente) y luego el cerebro toma esas (combinaciones lineales de) señales y compone una imagen bidimensional (o tal vez un par). ¿Cómo lo hace? Ni idea. Los métodos de manifold analysis intentan simularlo. La idea es asumir que un conjunto de puntos en un espacio de dimensión alta yacen sobre una superficie (de ahí el término manifold) y luego aplanarla preservando en lo posible distancias locales. En el caso particular de Isomap primero se construye un grafo que captura, mediante la imposición de vértices, el sabor local de la colección de puntos, luego se define una distancia optimizada sobre el grafo y finalmente se soluciona un problema de optimización para encontrar los puntos de baja dimensión correspondientes (para el interesado en por qué y cómo funciona, aquí hay detalles y aquí todavía más detalles). Como es de esperarse, entre más puntos, mejor el resultado.

*

Tal vez cincuenta puntos no sean suficientes. (Aquí más grande.)

Este de arriba es el resultado de aplicar Isomap a una versión normalizada (para evitar desequilibrios por diferencias de extensión) de los 50 puntos 2060-dimensionales que representan, de acuerdo a la lista de palabras elegidas, los 50 capítulos de The Pale King. Así se ve. Con Javier discutimos una noche los posibles significados de varios gráficos similares a este pero no logramos decidir si se conectaban de alguna manera con la sustancia del libro, lo que quiera que eso signifique. La verdad, prefiero que sea así. El anticlímax tiene naturaleza de Buda.

*

Anoche, antes de acostarme, se me ocurrió un posible orden lineal que se desprendería de estos cálculos: organizar los capítulos de acuerdo a la distancia al centro de masa (Isomap lo clava en $(0,0)$). El orden sería: §20, §6, §9, §22, §2, §14, §13, §7, §15, §16, §35, §32, §21, §46, §31, §17, §43, §26, §29, §45, §4, §8, §42, §19, §39, §10, §38, §33, §24, §50, §36, §27, §44, §47, §49, §12, §34, §23, §5, §1, §18, §11, §28, §30, §41, §48, §37, §3, §40 y §25. Ya puestos, calculé directamente sobre los puntos originales (en el espacio de dimensión 2060) y en ese caso (cambia, obviamente) el orden es: §22, §24, §2, §27, §42, §30, §7, §19, §33, §9, §5, §14, §47, §6, §49, §16, §8, §46, §43, §15, §13, §23, §36, §32, §26, §45, §39, §3, §12, §18, §29, §20, §17, §48, §38, §37, §50, §21, §31, §4, §35, §44, §1, §11, §41, §40, §28, §34, §10 y §25. En ambos, el recorrido se cierra en ese capítulo neurótico a dos columnas (Devils are actually angels) que describe la tediosa cotidianidad diaria de la oficina de impuestos (casi todos los personajes son mencionados), y se inicia (o casi) con el soliloquio de Chris Fogle (§22) sobre, entre otras cosas, su tendencia a contar palabras en lugar de leer. También podrían organizarse en sentido inverso, como en una espiral hacia el origen. Tal vez eso tenga más sentido.

Direcciones desde el infierno

London a 33 grados centígrados. FedEx dice que mi computador llega mañana por la tarde. Mientras tanto leo The Scar de Miéville. A continuación algunos enlaces que he recopilado durante la última semana cuando Mónica me suelta su computador:

  • Ojo a los cortos documentales de Sean Dunne disponibles en Vimeo. Mención especial merece American Juggalo, sobre la comunidad de fanáticos de la banda Insane Clown Posse (aquí una introducción a la banda publicada hace un par de años en Wired). La estética sucia de Donne y sus temas, lugares y tratamientos me recuerdan lo mejor de los hermanos Coen. Todavía quedan algunos días para apoyar Oxyana su proyecto de documental financiado vía Kickstarter.
  • La colombiana Diana Beltrán Herrera hace pájaros de papel (y estructuras geométricas).
  • Cultvana es una nueva revista digital en español. La diagramación de los artículos (aquí por ejemplo uno sobre la obra de Todd Solondz) es novedosa y trabajada. Me gusta muchísimo (aunque apreciaría una tipografía principal más grande). En el primer número la oferta es diversa pero se nota el ánimo tan juvenil y español por popularizar el análisis cultural académico (que nunca me ha entusiasmado mucho). Creo que al formato que proponen le convendrían números temáticos ocasionales. De resto la veo muy bien encaminada.
  • Robert Hodgin hace simulaciones de creación, exploración y destrucción utilizando la librería Cinder, una especie de Processing de alto desempeño en C++.
  • Educación Prohibida, un documental y proyecto argentino para sacar a la educación pública de su inercia perniciosa. Las reflexiones y críticas aplican sin dificultad al panorama educativo global.
  • Iñigo Quilez explica los fundamentos del warping. Aquí algunos experimentos básicos de Amnon Owed usando Processing. Intentaré algo parecido.
  • El Toronto Star compiló los artículos que escribió Ernest Hemingway entre 1920 y 1924 y los publicó en formato periódico, página a página, tal y como aparecieron originalmente. Aquí hay un pequeño abrebocas en línea (otro sitio de artículos con diagramación novedosa, por cierto). Me impresiona la fuerza de la redacción del joven Hemingway (que atribuyo en parte a la exigencia editorial que tenían los periódicos de entonces) pero sobre todo su seguridad al abordar los temas que trata. Cuesta creer que tenga sólo veinte años.
  • Retratos de Kumi Yamashita hechos con clavos e hilo. Ver para no creer.
On Juggalo Island we can be one.

Chiste

A raíz del relato de DeWitt, Jaime me hizo caer en cuenta de lo siguiente: en tanto que el Test de Turing es relativo a la inteligencia del ser humano promedio (o sus capacidades cognitivas, o lo que sea), si esta medida se reduce lo suficiente puede llegar un momento cuando el Test de Turing se torne trivial. ¿Qué nos garantiza que la inteligencia humana es más o menos estable en el tiempo o por lo menos no decreciente?

Alan Turing cuando era feliz.

Otra posibilidad, más aterradora: es posible que aunque la inteligencia humana no decrezca sustancialmente, la civilización avance en una dirección en la que los protocolos sociales se normaticen tanto como para que sea sencillo programarlos en máquinas.

Al principio pensé que era un chiste pero ya no estoy tan seguro de que sea un chiste. Si es un chiste es uno bien-bien oscuro. Seguro que Turing se pondría triste. Yo también me pongo triste a veces por cosas así.

Arduino

(Dentro de mi proyecto de renovación de distracciones me compré un Arduino Uno de regalo de cumpleaños. Nunca había jugado con electrónica. Demasiado práctico para mí. Además mi motricidad fina no es la mejor. Todavía no entiendo bien la lógica de los circuítos pero la sencillez del lenguaje de programación (una versión minimal de C, parecería) facilita mucho las cosas. Quiero hacer juguetitos tontos con ánimo decorativo. Mi primer pequeño proyecto fue un contador de segundos en binario utilizando ocho lucecitas. El segundo es un medidor primitivo de intensidad luminosa utilizando una pantalla de cuatro dígitos y una fotoresistencia. Tengo todavía varios sensores y actuores (?) por probar. A los once años un juguete como este hubiera sido el paraíso. A los treinta y cinco es un pasatiempo más que digno.)