Analysis and Design of Algorithms

Octubre 2015

Ahora estoy haciendo el curso de algoritmos de Tim Roughgarden
en Coursera. Me parece que estos cursos (especialmente) los
assignments son la mejor manera de mejorar como programador.

Por ahora voy viendo las clases. El material es relativamente
conocido, asi que en la primera semana voy ok. El primer assignment lo
hice en el avión desde Seoul. Se trata de contar la cantidad de inversiones
(pares de valores fuera de orden) en una lista.

Empecé en Ruby usando Rspec y no funcionó. Después me pasé a Python y
lo hice con 4 funciones en top level. Así que el diseño podría ser mejor,
pero me parece que no es el foco de los ejercicios.De todas formas me parece que puede ser interesante aplicar los paradigmas
OOP y funcional para resolver este tipo de problemas.

El algoritmo pasa todos los tests de Coursera, así que estoy conforme. Una
tarea que puede ser interesante, además de mejorar el diseño del código
es implementar todos los algoritmos que enseña. Empecé por implementar
Merge-Sort, que es la base del algoritmo para contar inversiones del
ejercicio. Por ahora me van faltando el algo para multiplicar matrice de
Strassen y para multiplica ints de Karatsuba.

Igual ya empezó la semana 2 así que vengo medio atrasado. Tampoco entregué
el problem set sobre Oh-notation.

[Final]

Quedé completamente atrasado para este curso. Lo único que logré hacer fue ver todos los videos varias veces (hasta entenderlos). El único tema que me quedó flojo es Universal Hashing. El resto de las demostraciones las podría hacer. Tendría que hacer un cuaderno e irme preparando para la parte 2 que creo que es más complicada.

Lo que faltaría sería implementar los algoritmos que vemos en el curso (y capaz que hacer algún experimento para validar la performance).

Junio el mes de Ruby on Rails

A principio de año decidí que precisaba aprender un framework y Ruby on Rails siempre me pareció muy copado. Hice el tutorial de Michael Hartl, y quedé bastante conforme, pero después me metí a estudiar algoritmos y lo dejé un tiempo.

Tenía planeado volver en Mayo y dejé pasar un tiempo, pero en Junio y Julio hice bastante con esta tecnología. Me compré este tutorial que está muy bueno. La diferencia es que me di cuenta que hacer tutoriales no alcanza, así que por cada tutorial que haga me tengo que quedar con un proyecto terminado.

Así que después de hacer el tutorial hice empecé una app que tengo en la cabeza hace como 10 años: PACPYMES. Ahora empezó de nuevo el curso de algoritmos y la tuve que volver a dejar de lado, pero avancé bastante. Estas son dos imágenes de la app como está ahora:

pacpymes_home

Pantallazo-3

 

 

Mis dos grandes fuentes son el tutorial de Pragmatic Studio (HACER REVIEW) y el de Michael Hartl. En base a eso armé lo que pude de la app de PACPYMES y anduvo bastante bien. Las features que estan listas son:

  • Log in/Log out
  • Look & Feel (en base a Bootstrap)
  • Admins y usuarios / registrar empresas
  • Administrar empresas

También me voy dando cuenta lo importante que es luchar contra tus propios problemas, pero teniendo una base de información que hay que recibir de algún lado.

Introduction to Algorithms Part 2 – Robert Sedgewick

Esta es la segunda parte del curso de Sedgewick. Esta es mi review de la primera parte. La segunda parte del curso se mete con algoritmos para procesar grafos y texto.

Sedgewick no es de esos profesores que hacen que todo parezca fácil. Ya metí bastantes horas con el libro, vi varias veces los videos, y todavía no me siento para nada cómodo con estos temas. El libro es bastante grande y tiene muchos ejercicios que no tengo ni idea de como encarar, miles de ejemplos interesantes que no pude ver con detalle.

Una cosa que aprendí mirando estos cursos es que a veces es importante cambiar las formas de estudio, y para estudiar algoritmos hay muchas formas de estudio: programar los assignments, analizar los ejemplos de código del libro, estudiar las demostraciones, correr ejemplos de los algoritmos a mano, etc.

Al principio las preguntas múltiple opción no me gustaban pero aprendí que es importante hacerlas. En general implican correr los algoritmos a mano y son buenos ejercicios para entenderlos.

Por otro lado estan los Programming Assignments. En general me parecen bastante difíciles, siempre me queda algo para corregir y nunca llegué a sacarme 100%. Ni hablar de instrumentar las optimizaciones que se sugieren en los foros.

Básicamente mis programas tienen dos problemas: mal diseño de los objetos y métodos y/o mala performance. Supongo que para ser la primera vez que los hago no están tan mal. En una segunda iteración del curso podría tratar de mejorarlos. El problema es que en general me tengo que dar por vencido porque no tengo más tiempo para seguir el ritmo del curso.

Semana 1: Undirected Graphs

Graph API: Un montón de código sencillo para procesar grafos. Breadth First Search y Depth First Search son dos formas de recorrer un grafo, son la base de los algoritmos que vienen después.

Assignment: WordNet(88.18 %) (91.89%)

En este ejercicio nos dan un Directed Edge Graph de palabras. Los edges representan relaciones tipo “es un”. Por ejemplo, hay un edge que va de pelícano a pájaro porque un pelícano es un pájaro.

Lo que hay que hacer es parsear el grafo y armar una clase para encontrar el ancestro más cercano de dos palabras. Por ejemplo, el ancestro de pinguino y pelícano es ave. Para esto hay que diseñar un algoritmo que funcione.

Después usamos este algoritmo para detectar los outcasts en una lista de palabras. Por ejemplo, en la lista: { tenedor, cuchara, cuchillo, piedra}, El outlier es piedra. Para detectarlo calculamos la distancia de cada palabra al resto y las sumamos. La que tenga una suma de distancias al resto máxima es el outcast.

[Edit Abril 2016] Para esta iteración del curso no me acordaba como había solucionado esto la vez pasada, así que empecé de cero. Mi approach fue ir recorriendo los ancestros de la fuente tirando Breadth First Searches desde cada nodo. Si bien esto funcionó bien para nodos individuales, no veo como generalizarlo para colecciones de nodos.

Así que recurrí a la solución anterior (no tenía la menor idea de cómo había resuelto esto la vez pasada). La solución es bastante elegante, hace un BFS desde la fuente y otra desde el destino, y después itera por todos los nodos para encontrar la mejor. Creo que esta iteración podría optimizarse.

Todo el resto del ejercicio es bastante sencillo. Lo único complicado es parsear los datos correctamente. Al principio parecía sencillo y lo hice a pulmón y me entreveré. Entonces empecé de nuevo escribiendo tests y quedó bien.

La clase Outcast se beneficiaría de un refactor (en el método outcast). Lo que hace es crear una array de dos dimensiones que guarda las distancias entre cada par de nouns que le pasan a la función. Después suma por columna, calcula el índice máximo y devuelve el noun correspondiente para hallar el que tiene una suma de distancias mayor al resto. Esto habría que refactorearlo, voy a tratar de hacerlo un día que esté aburrido.

 

Semana 2: Directed Graphs, Edge Weighted Graphs, Minimum Spanning Trees

Ahora los edges tienen direcciones. BFS y DFS son en realidad pensados para recorrer directed graphs, en un undirected graph toman cada edge como uno que va y otro que viene.

 

Assignment: Seam Carving (75%)(93.7%)

En este ejercico implementamos un programa que reduce el tamaño de una imagen teniendo en cuenta el contenido. Para esto, calculamos cuales son las partes de la imágen “menos importantes” y las vamos eliminando. Cada pixel tiene un valor asociado que mide su importancia. Si es muy diferente a los pixeles que lo rodena es importante, pero si es igual lo podemos borrar sin precuparnos mucho por la información perdida.

El algoritmo consiste en encontrar un hilo de  pixeles “poco importantes” que va desde el borde superior al borde inferior de la imagen. Este hilo se encuentra resolviendo un problema de Shortest Path. Luego copiamos la imágen sin esos pixels, et voilá! la imágen tiene una columna menos.

Para implementar el algoritmo armé una class (Grid) que es facilita trabajar con las coordenadas de los colores de las imágenes. Después hay un método (relax), que calcula el camino más corto entre un pixel imaginario arriba de la imágen y cada pixel en la imágen.

 

Semana 3: Min-Cut/Max-Flow

Acá la matemática se pone complicada. Hay algunas demostraciones de teoremas referidos al problema min-cut max-flow.

Assignment: BASEBALL ELIMINATION (87%)

En este ejercicio, el objetivo es determinar que equipos no tienen chance de ganar un campeonato sabiendo cuantos partidos lleva ganados, y cuantos le quedan contra cada equipo. Obviamente, si hay un equipo que ganó mas partidos que los que ganó otro más los que le restan por jugar, este equipo estará eliminado.

Pero hay una condición más complicada, que depende de contra quién son los partidos que le restan a los otros equipos.

                w[i] l[i] r[i]        g[i][j]
i  team         wins loss left   Atl Phi NY  Mon
------------------------------------------------
0  Atlanta       83   71    8     -   1   6   1
1  Philadelphia  80   79    3     1   -   0   2
2  New York      78   78    6     6   0   -   0
3  Montreal      77   82    3     1   2   0   -

En este caso, Atlanta no puede salir campéon. Este problema se puede reducir a uno de Max-Flow en una Flow Network determinada. Tengo que reconocer que no entiendo bien el algoritmo.

Sin embargo, armé un programa que lee los inputs, y después simplemente uso el código del libro para resolver el problema con Ford Fulkerson. Suficiente para llegar a una buena nota, pero debería entender mejor el problema.

Semana 4: Raddix sorts

ASSIGNMENT: Boggle
Para este problema tenemos hacer un programa que juega al Boggle. Para eso, armamos un Trie customizado.

Semana 4: Minumum spanning trees

ASSIGNMENT: Burrows-Wheeler

The Teaching Company – Discrete Math

La matemática discreta es importante para estudiar computación.

No había encontrado nada muy atractivo para estudiar esto, hasta que di con este curso de mis viejos amigos de The Teaching Company (los primeros mp3 con clases grabadas que llegaron a mis manos fueron los cursos de filosofía de Rick Roderick editados por esta empresa). 

El enfoque del material de esta empresa no es muy técnico, más bien siempre me pareció que sus cursos eran entretenimiento “high-brow”, así que nunca había pensado en usar estos cursos para estudiar algo técnico. 

Muchos de los ejercicios de los cursos de Rice de computación son aplicaciones de Matemática Discreta (Los números Fibonacci, el Triángulo de Pascal y the Fifteen Puzzle).

Tema 1: Combinatorics

Cuál es la probabilidad de sacar un full en una mano de poker? RESPUESTA!
En facultad tuve un curso de Estadística con un montón de estos problemas que nunca supe contestar. La verdad que nunca capté este tema, pero ahora creo que pude. Después de esto me tengo más fé para atacar Analytical Combinatorics en Coursera… en unos meses jeje.

Linear Recurrences and Fibonacci numbers. No sé en que tema queda esto, pero los Fibonacci Numbers son tremendamente interesantes.

Tema 2: Number Theory

Creo que este es un tema menos importante para computación, pero es saladamente interesante. La mayor parte de las pruebas del curso de Keith Devlin son de Number Theory, por lo que ya las había visto. Mind Blowing.

Tema 3: Graph Theory

Todavía no pude ver esta clases, voy a tratar de hacer ejercicios de los dos temas anteriores antes de atacar esto, aunque esta es la razón por la que hice este curso.

Miré la mayor parte de las clases de corrido sin tomar apuntes. Eso es un hábito de estudio que tengo, si el profe es suficientemente copado y yo estoy despierto sigo la clase bien, pero después necesito volver sobre los temas y ejercitarlos. Todavía no pude hacer eso, pero espero hacerlo este fin de semana!

Benjamin es un uber-nerd. Es muy entusiasta al dar la clase y va muy rápido. El curso tiene buen nivel, hace varias demostraciones y en ningún momento parece “simplificado”.

Para el recuerdo: One, One, Two, Three, Five, Eight, who do we appreciate? FIBONACCI!!!!

Programming Languages – Dan Grossman

course_logo

(2/10/2014 – 10/12/2014)

Este curso de Lenguajes de programación de Dan Grossman de la universidad de Washington. El curso hace énfasis en programación funcional y usa tres lenguajes.

El estilo de clase de Grossman está buenísimo porque los videos son de el trabajando en la computadora. Esto me parece mucho mejor que el formato “Lecture”, donde el profe tiene todo cocinado y “expone”. Me parece que ver al tipo trabajando en la máquina y “pensando en voz alta” es mucho mejor, aunque es cierto que a veces es inevitable que traiga un pedazo grande de código y pase un poco rápido.

Aparte de las clases, el curso consiste en dos exámenes y un assignment por semana. Una particularidad de este curso es que además de mandar los assignments al autograder hay un peer review para corregir la legibilidad.

 

Para justificar la elección de los lenguajes que usa, Dan ofrece una taxonomía de lenguajes de programación (estáticos vs dinámicos, funcionales vs. orientados a objetos) que hace una tabla de doble entrada. Dice que deberíamos estar familiarizados con un lenguaje en cada casillero y que los estudiantes de su curso en Washington ya conocen uno estático y orientado a objetos (Java), por lo que el enseña uno de cada uno del resto de los casilleros.

 

Parte 1: Standard ML

ML es funcional y estático pero hace type inference (de una manera bastante sofisticada, no como Java). Hay un par de assignments sobre este lenguaje que fueron bastante interesantes y no muy complicados. La principal complicación era no usar la mutabilidad de los valores, algo que alguien que viene de un lenguaje orientado a objetos puede llegar a encontrar difícil. También nos da una introducción a las principales funciones del repertorio funcional: map, fold y filter.

Assignment 1: Funciones con fechas (98%) (100%)

ASSIGNMENT 2: Mas ejercicios funcionales (81%) (99%)

ASSIGNMENT 3: Un lenguaje de programacion (80%) (96%)

Mock Exam: (100%) y Exam: (93%)

Parte 2: Racket

 

Racket es un dialecto de LISP. Viene en un programa que se llama Dr. Racket que tiene todo instalado. Si bien tuve unos problemitas al correrlo en WinXP, es bastante cómodo de usar y al estar diseñado para enseñar computación tiene un par de features muy lindas (es el entorno que usan en Introduction to Systematic Programming de Greg Kinczales).

Assignment 4: Intro a Racket (75%)

Assignment 5: Implementar un lenguaje de programación (MUPL).

Este no pude terminarlo.

El último lenguaje es Ruby. Si bien seguí las clases con bastante cuidado, no me metí a hacer los assignments (uno es extender un Tetris y el otro es portar un programa de ML a Ruby). Se ven muy interesantes y espero poder hacerlos en la próxima iteración del curso.

Fin

Este curso estuvo muy interesante, los conceptos están muy bien presentados y permite ampliar considerablemente el repertorio mental para pensar sobre programas. Todavía recuerdo esa sensación al estudiar los programas de estar en una clase de yoga mental, no como los cursos de Algoritmos que son más parecidos a boxeo mental!

Ahora que estoy revisando los programas veo que me quedaron un montón de cosas para hacer para la próxima edición del curso!

Introduction to Algorithms – Robert Sedgewick

small-icon.hover

(8/2/2015-2/4/2015)

Este curso está dividido en dos partes en la primera vemos las dos primeros capítulos del libro  (Searching, Sorting) y en la segundo los dos últimos (Graphs, Strings). Cada semana se liberan los videos de las clases, ejercicios múltiple opción para verificar que entendemos como funcionan los algoritmos y un Programming Assignment.

[UPDATE Julio/2015]: El curso se volvió a abrir y estoy aprovechando para rehacer algunas cosas. Volví a hacer Percolation y Randomized Queues and Deques. Estoy terminando Kd-Trees. Esta vez estoy usando Eclipse y escribiendo tests. También estoy tratando de usar git pero en eclipse es bastante feo. Esta vez estoy tratando de implementar los principales algoritmos que se dan en clase: QuickUnionFind, MergeSort, QuickSort, Binary Search Trees, Hash Tables (tratando de mirar el código de clase lo menos posible). También voy a usar mis implementaciones para contestar los ejercicios porque correr los algoritmos a mano es una tortura.

En general me noto un poco mejor al abordar los ejercicios. Siento que aprendí un par de cosas que me permiten mantener el proceso. El problema que sigo teniendo es trato de dedicar un día por semana a un ejercicio, y cuando no logro terminarlo en ese tiempo me empiezo a poner de mal humor.

Me subí un poco tarde porque estaba enganchado haciendo una app en Ruby on Rails, pero estoy tratando de ponerme a tiro.

El año pasado di con este curso de y me pareció que podía ser una buena manera de convertirme en un programador tout courtEsto es lo que escribí en Quora sobre esa experiencia:


Sedgewick claims that:
 
"the course doesn't go into any advanced or tricky Java syntax".

I don't agree. You'll need to understande Generics, Interfaces, 
Iterators, and a few other things to get the assignments done. 
That's pretty interesting stuff, but you'll to learn it. 
But that's fair because it was pretty interesting and sort 
of well explained in the lectures. As for the syntax, 
it's not that hard, after a day or two on CodingBat 
you should be ok.

The biggest problem was configuring an environment. 
That's where I hit a wall. You'll need a Java compiler 
and a console to run the programs from the course. 

O sea, fue un fracaso porque no pude hacer los Programming Assignments en Java. Entonces me compré el libro de Sedgewick de Java y, ya que estaba, el de Algoritmos para irme preparando para la próxima edición del curso.

Los ejercicios no requieren implementar los algoritmos que estudiamos (estan todos disponibles online), sino que plantean un problema que se puede resolver usando los algoritmos vistos en clase.

Semana 1: Introduction to algorithms

Esto es una intro al tema. Hay un módulo describiendo el enfoque de Sedegewick (por que está en contra de la Big-O notation, etc.). Otro módulo es de análisis de algoritmos, donde habla de como estimar el exponente de un algoritmo cuadrático usando la doubling-rule y una regresión log-log. Otro es sobre el uso de memoria en Java.

El cuarto es el primer algoritmo propiamente dicho, es Union-Find, un algoritmo que permite encontrar strong components en una red en tiempo logarítmico. El enfoque es interesante porque va refinando una solución básica poco a poco.

Assignment: Percolation(100 %)

Este es el primer problema del curso, es bastante interesante. EXPLICAR PROBLEMA Y PONER IMAGEN.

Para resolverlo usamos el algoritmo Quick-Union Find, para calcluar los strong components de una matriz de puntos. La solución es interesante porque demuestra un efecto llamado phase transition. El objetivo es estimar que proporción de celdas debe estar abierta para que el agua llegue desde el techo al piso de la matriz.

Para eso hacemos un experimento Monte Carlo en el que abirmos una posición y chequeamos si la matriz percola o no iterativamente hasta que percola. Esto nos permite estimar un “umbral” para la proporción de sitios que debe haber abiertos para que la matriz percole.

Semana 2:  Stacks & queues

Estas son estructuras de datos bastante básicas. Se usan como base para implementar otros algoritmos.

Assignment: Randomized Queues and Deques (98%)

Este problema fue relativamente sencillo.

Una Randomized Queue tiene la API de una Queue normal, pero además permite extraer un ítem al azar. Parece fácil pero los requerimientos de performance para el iterador complicaban un poquito las cosas. Un Deque es como una Queue de la que se pueden sacar items de adelante y de atrás. Relativamente sencillo, pero hay un detalle que nunca pude sacar, y me quedé en 98%.

Semana 3: Sorting Algorithms: Mergesort & Quicksort

Estos algoritmos son de los grandes éxitos de la historia de la computación. La segunda vuelta del curso los voy a intentar implementar. PONER LINK A PUBLIC REPO.

Dificil: Quicksort.

Assignment: Collinear Points (84%)(93.78%)

Acá empecé a decaer. El problema es detectar líneas de cuatro o más puntos en una nube de puntos. Implementamos una solución por fuerza bruta y después un algoritmo basado en ordenar los puntos.

La solución final tenía algunos problemas de performance, y el diseño me quedó bastante desastroso. Creo que esto es lo que más me falta, aprender a planificar los objetos y los métodos que tiene cada uno antes de implementarlos.

En vez de hacer esto, mi forma de trabajo es pensar una posible solución, implementarla y ver que falla. Lo más normal es que la primera solución no sea viable, y creo que debería ser posible anticiparse a esto. Otra cosa que pasa es que la solución no es suficiente, entonces la empezás a emparchar, lo que resulta en implementaciones y APIs espantosas. Esto es lo que me pasó con este problema (y otros tantos…).

Una feature de Java importante para este assignment fue implementar la Interfaz Comparable para los Puntos y las líneas, pero, como decía antes, no me quedó del todo bien.

[Julio] Esta vez levanté un poquito la nota pero no quedé conforme con el código principal. La nota que perdí es por Brute.java, Fast.java pasa todos los tests, pero la lógica del algoritmo debería mejorarse. Descubrí algunos casos límites (cuando los puntos colineales quedan al final). Probablemente lo mejore en estos días.

 

Semana 4: Priority Queues

En este módulo estudiamos las Binary Heaps, el último algoritmo para ordenar (Heapsort) y una estructura de datos super útil: Priority Queue.

DIFICIL:

Sacar 100% en el assignment.

Assignment: 8 Puzzle (70%)(92.07%)

Este problema está en Principles Of Computing de Rice. Es un juego en el que hay que ordenar 15 fichas numeradas del 1 al 15 en una grilla de 16 piezas (una en blanco).

El análisis matemático es interesante. La solución es usar el algoritmo de búsqueda A*, que genera todos los movimientos posibles a partir de una posición inicial y explora todos los escenarios posibles a partir de cada movimiento usando “Best First Search”.

Best first search se sirve de una Priority Queue para “priorizar” los mejores nodos y procesarlos antes que los primeros. Para decidir que nodos son mejores que otros, usamos una herurística (en este caso la suma de las distancias de los bloques a sus posiciones finales).

[Marzo 2015] Creo que la nota que me dieron por este problema es injusta. Mi programa andaba bien con todos los casos salvo uno, que tenía una grilla de 14 * 14. No supe como debugear a mano un caso tan grande así que entregué así.

[Julio 2015] Esta vez me fue mejor, el código es mucho más limpio pero no llegué a 100% porque estoy insertando demasiados nodos en la queue. Este es de los assignments donde más ideas hay para optimizar la performance. Hay una que es obligatoria de implementar, que es no poner el nodo previo en la Queue cuando calculo los vecinos.

Traté de cachear los cálculos de hamming() y manhattan() pero el resultado fue peor. Otra que parece prometedora es representar las tiles como un char[] en vez de un int[][]. También hay que refactorear el código que enqueues los neighbors.

 

Semana 5: Symbol Tables

dificil:

Implementación recursiva de get() e insert() en un BST.

Assignment: KD-Trees (100%)

La primera vez que tomé el curso, el fracaso en el problema 4 me desanimó y no pude juntar el valor para empezar este Assignment. La segunda vez lo hice y salió bastante bien.

Los K-dimensional Trees son árboles binarios en varias dimensiones. En 2 dimensiones, los nodos se pueden usar para almacenar puntos en el plano. Cada nivel del árbol particiona una dimensión, en el caso de ser binarios el root particiona el eje x, los dos hijos del root particionan el eje Y.

Esto permite implementar rápidamente operaciones como encontrar el punto más cercano en una nube de puntos a un punto exterior y encontrar todos los puntos de un conjuntos que caen adentro de un rectángulo.

El único problema que tuve fue algo que era relativamente sencillo pero era totalmente clave para que el resto saliera bien. Pensé que lo tenía bien pero en realidad había dos errores que hicieron que pareciera que andaba bien al dibujar el árbol:

kdtree

Para implementarlos hay que adaptar un BST. El ejercicio requiere implementar las dos operaciones anteriores. Para hacerlas rápido, hay que implementar dos optimizaciones que se pueden poner un tanto complejas.

Fin

Bueno, ahora terminó y tengo una semana libre para empezar la segunda parte (ver mi review de como me fue en la segunda parte acá). En el medio me fui de vacaciones con el libro y aproveché para estudiar algo. Una cosa que aprendí de pasar tiempo con el libro es lo importante de “correr” los algoritmos a mano para entender como funcionan. Los ejemplos del libro están muy bien para hacer eso, de manera que estoy aprendiendo los algoritmos un poco mejor esta vez.

La segunda vez que hice el curso también valió totalmente la pena. No solo porque aprendo más cosas sino porque los programas que hago son mejores. Esto se debe a que al tener más familiaridad con las features de Java es más sencillo implementar las soluciones mas idiomáticas.

También resuelvo los problemas más rápido, aunque es probable que esto se deba a que ya los hice hace unos meses. En todo caso el proceso es más agradable, lo que resulta en mejor aprendizaje.

También estoy más cómodo con las herramientas (que no son las que se recomiendan en el curso). Estoy usando Eclipse, Junit y Git. (Aunque Git me sigue dando problemas). El código que escribí para el curso está repos privados en Bitbucket.

Quedan pendientes los ejercicios. Probablemente los haga programando en vez de a mano.

Otra cosa interesante es escribir los programas que Sedgewick muestra en clase. Si bien esto es más natural en otro estilo de curso, es una actividad que vale bastante la pena.

 

Ruby on Rails Tutorial – Michael Hartl

imagesEste el estándar de facto para aprender Ruby on Rails. . Me bajé una versión vieja y me pareció bastante copado, así que le pedí a mi esposa la última versión para nuestro primer aniversario.

La idea es hacer un clon de Twitter usando Ruby y Rails. La versión final tiene un sistema de autenticación casero que permite subir fotos, seguir usuarios y tiene un feed con la info de tus usuarios.

Hartl hace bastante énfasis en que todo lo que enseña es “industrial strenght”, así que funciona y está en la web: https://morning-ridge-1269.herokuapp.com/ (Ahora no se pueden subir imágenes para evitar que me cobren en AWS…).

Es un tutorial (paso a paso) muy disfrutable, así que en principio no es complicado (lo único que hay que hacer es seguir los pasos). Habiendo aclarado esto, recomendaría aprender Ruby antes de esto, e idealmente algo de Rails (yo aprendí con el curso de Lynda). Esta base va a hacer mucho más llevaderos los videos (algunos llegan hasta 3 horas).

Creo que la mejora forma de usar los videos es mirar una hora o dos y luego lanzarse a programar lo que viste. Si no te acordás de algo volvés a mirar el video o el pdf del libro.

1) Configuración del entorno.

Como siempre que uno se mete en algo nuevo es el setup del environment. La versión 2 que empecé es vieja, y hace todo local en una Mac. Así que instalé todo y empecé. Entonces todo se fue cayendo a pedazos lentamente. Eso fue lo que me decidió a comprarme la versión actualizada.

La versión 3 usa una Cloud IDE (cloud9), que viene preconfigurada (solo hay que agregar unos pequeños extras opcionales). Me hice una cuenta gratis, pero no le da la memoria (512 MB) para correr los tests automáticos. Así que me compré la básica que sale 9 dólares. Ahora la uso para otras cosas y me parece muy útil (aunque es un poquito lenta).

2) Cosas nuevas:

Estoy escribiendo esto un dos meses después de haberlo hecho así que mi memoria puede fallar un poco. Lo más complicado es aprender el Framework y que va en donde. Por ejemplo, cuando creamos el sistema de autenticación, hay que usar un montón de helpers que van todos en archivos distintos, no termino de entender que va en donde no que está en scope cuando.

Además están los helpers de los tests, que complican todo, porque siguen unas reglas diferentes… Toda la parte de autenticación me resultó un poco confusa. Espero poder volver a escribir la aplicación de 0 y que quede más claro cuando vuelva a tener tiempo para Ruby on Rails.

3) Sobre aprender un craft.

Está muy copado ver a un tipo experimentado trabajar (Hartl es programador web pero tiene un Phd en Física de Harvard así que es bastante listo). Ya escribí de esto en otros lados, me parece una forma mucho más efectiva de aprender que el formato “lecture”.

Esto se aplica a la mayoría de los cursos online que he hecho, debería escribir algo sobre esto.

4) Conclusión

Creo que esto es un recurso imprescindible para alguien que le interesa el desarrollo Web  (es excelente incluso si tenés la duda de si te interesa y estás dispuesto a probar).

 

Mas Java: super

Este es otro ejercicio para el curso de Coursera. Lo más interesante es el uso de super para llamar métodos over-rideados en sub-clases y una abstract class. Si te parás a pensarlo, el uso de Dynamic Dispatch es bastante complicado.

Por ejemplo, cuando definimos el método afficher() en la super clase Item, este se fija si el courrier es válido.


// PROGRAMME PRINCIPAL (A NE PAS MODIFIER)
class Poste {

 public static void  main(String args[]) {
  //Cr'eation d'une boite-aux-lettres
  // 30  est la capacit'e maximale de la
  // boite aux lettres
  // (pas necessaire si vous dêcidez d'utiliser
  // un ArrayList).
  Boite boite = new Boite();

  //Creation de divers courriers/colis..
  Lettre lettre1 = new Lettre(200, true, 
                             "Chemin des Acacias 28, 1009 Pully", "A3");
  Lettre lettre2 = new Lettre(800, false, "", "A4"); // invalide
  
  Publicite pub1 = new Publicite(1500, true, 
                                  "Les Moilles  13A, 1913 Saillon");
  Publicite pub2 = new Publicite(3000, false, ""); // invalide

  Colis colis1 = new Colis(5000, true, "Grand rue 18, 1950 Sion", 30);
  Colis colis2 = new Colis(3000, true, 
                           "Chemin des fleurs 48, 2800 Delemont", 70); 
  boite.ajouterCourrier(lettre1);
  boite.ajouterCourrier(lettre2);
  boite.ajouterCourrier(pub1);
  boite.ajouterCourrier(pub2);
  boite.ajouterCourrier(colis1);
  boite.ajouterCourrier(colis2);
  boite.afficher();

  /*
  System.out.println("Le montant total d'affranchissement est de " +
         boite.affranchir());
  boite.afficher();
  
  System.out.println("La boite contient " + boite.courriersInvalides()
         + " courriers invalides");
 */
 }
}


class Boite {
  Item[] items = new Item[30];
  int head = 0;
  
  public void ajouterCourrier(Item item) {
     items[head] = item;
     head++;
  }
  
  public void afficher() {
    for (int i = 0; i<head; i++) {
     items[i].afficher();
     System.out.println("\n");
    }    
  }
}

abstract class Item {
  
    int poids;
    boolean express;
    String address;
    
  Item(int poids, boolean express, String address) {
    
   this.poids = poids;
   this.express = express;
   this.address = address;
  }
  
  public double getMontant() {
    return 0.0;
  }
   public void afficher() {
     
     if (!isValid()) {
   System.out.println("(Courrier  invalide)");
     }
   System.out.println("Poids :  " + poids + " grammes");
   if (express) { System.out.println("Express :  oui"); }
   else System.out.println("Express :  non");
   System.out.println("Destination :  " + address);
   System.out.println("Prix : " + affranchir() + " CHF");
  }
   
   public boolean isValid() {
       return !address.equals("");
   }
   
   abstract double affranchir();
}



class Colis extends Item {
  int volumen;
  
  Colis(int poids, boolean express, String address, int volumen) {
   super(poids, express, address);
   this.volumen = volumen;
  }
  
  public void afficher() {
   System.out.println("Colis");
   super.afficher();
   
  }
  
  public double affranchir() {
   // montant = 0.25 * volume (litres) + poids (kilos) * 1.0; 
   if (isValid()) return 0.25 * volumen  + poids * 1.0; 
   else return 0.0;
  }
  
  public boolean isValid() {
   return super.isValid() && volumen <=50; 
  }
}

class Publicite extends Item {
    
  Publicite(int poids, boolean express, String address) {
    super(poids, express, address);
  }
   public void afficher() {
   System.out.println("Publicité");
   super.afficher();

  }
   
   public double affranchir() {
    double result = 5.0 * poids/1000;
    if (express)  result *= 2.0;
    
    if(isValid()) return result;
    else          return 0.0;
   }
  
}

class Lettre extends Item {
  
  String format;
  
  Lettre(int poids, boolean express, String address, String format) {  
   super(poids, express, address);
   this.format = format;
  }
   public void afficher() {
   System.out.println("Lettre");
   super.afficher();
   System.out.println("Format : " + format);
  }
   
   public double affranchir() {
    // tarif de base + 1.0 * poids (kilos), 
    // où le tarif de base pour une lettre "A4" est de 2.50, et 3.50 pour une lettre "A3" 
     
   double base;
   if (format == "A4") base = 2.5;
   else                base = 3.5;
 
   double result = base + 1.0 * (poids / 1000.0);
   if (express) result *= 2.0;
   if(isValid()) return result;
   else          return 0.0;
   }
}

Esto de aprender java tiene momentos dolorosos!!!!

Dibujando en Java: StdDraw

Este es un ejemplo sencillo del libro de Sedgewick. Es un programa que dibuja H’s recursivas (una en el centro y una en cada punta de la H central) y usa la clase StdDraw que viene con el libro para dibujar. Es bastante fácil, StdDraw.line(x0, y0, x1, y1)  es un método estático para dibujar una recta entre (x0, y0) y (x1, y1).

public class Htree {

  public static void draw(int n, double sz, double x, double y) {
   if (n == 0) return;
   double x0 = x - sz/2, x1 = x + sz/2;
   double y0 = y - sz/2, y1 = y + sz/2;
   StdDraw.line(x0,y, x1,y);
   StdDraw.line(x0, y0, x0, y1);
   StdDraw.line(x1, y0, x1, y1);
   draw(n-1, sz/2, x0, y1);
   draw(n-1, sz/2, x0, y0);
   draw(n-1, sz/2, x1, y1);
   draw(n-1, sz/2, x1, y0);
  }

  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    draw(n, .5, .5, .5);
  }

}

N son los niveles de recursión (cuántas H’s arriba de H’s dibujamos). Este es el resultado con H = 5:

 

htree

Dos Fractales

El tema de hoy son los fractales. Vienen a ser objetos (imágenes en este caso) que son “self-similar”. Otra forma de verlo es que son iguales vistos a diferentes escalas.

Por ejemplo, una persona vista a un metro de distancia se ve de una forma. Pero si cambiamos la escala y vemos sus células, ya es bien distinta. Si vamos un paso más y vemos los átomos de los que se componen las células, vemos estructuras totalmente distintas.

No es así con los objetos fractales. Hacé un zoom de 500% en un fractal, y se va a ver muy similar a si mismo. Sinceramente no se de ninguna aplicación seria de este principio. Pero, Timewave Zero, la teoría del tiempo de Terence Mckenna está basada en esta idea.

Así que en este post tengo dos programas para producir fractales. El primero es del libro de Sedgewick de Java. Primero desarrollamos la clase de los números complejos:

[codigo]

Luego, usamos esta clase para dibujar un Mandelbrot set. Para saber si un punto en el plano complejo pertenece a este conjunto, tengo que computar la serie
z(t+1) = z(t)
y verificar si diverge a infinito o no. Acá es donde mis conocimientos matemáticos empiezan a hacer agua, pero si la parte real del número complejo llega a ser mayor que 2 en algún momento, estamos seguros de que la serie diverge.

Entonces lo que hace el programa es tomar todos los puntos de un rectángulo de 256 x 256 y estimar los primeros 500 términos de la serie. Por ejemplo:

Entonces, si diverge sabemos que está afuera, sino no. No entiendo que carajo hace con los grises.

Esta es la imágen del set: