Sudoku Solver

Para hacer un curso de gráficos 3D tengo que aprender C++ así que salí a buscar materiales. Lo mejor que encontré fue este curso de Stanford.

El curso es el segundo curso de computación que tienen los alumnos de Stanford, (el primero es en Java). Como tal, es interesante porque no se detiene mucho en la sintaxis de C++ (es bastante similar a Java y a C) sino en aspectos más conceptuales (el énfasis es en programar abstracciones (queues, vector, map, stack)). Sin ser un curso de algoritmos, es una buena intro.

La profe se llama Julie Zelenski y es excelente: graciosa, inteligente, casi linda… Como no pude usar las librerías que le dan a los alumnos no pude hacer los assignments. Lo que si pude hacer es tratar de hacer andar el código que tratan en clase. Un ejemplo interesante es este Sudoku Solver.

sudoku300

El algoritmo explora recursivamente el árbol de posibilidades hasta encontrar una solución. Es similar  al pset5 de MIT 6.00. El principal problema consiste en manejar correctamente la memoria del stack. Acá está el código [link al gist].

Aparte de eso implementamos varias ADTs (Queue, Stack, Map, Vector), lo que es una forma bastante interesante de conocer como funciona C++. Obviamente que me distraje un poco de los gráficos 3D.

Otra cosa totalmente nueva que estoy aprendiendo son los pointers. Creo que eso vale la pena entenderlo en detalle por lo que estoy pasando más tiempo de lo esperado en este material. También hay otro curso de Stanford en Youtube que tiene unas cuantas clases sobre pointers y como programar funciones genéricas en C.

Cómo en C no hay templates, es necesario manipular la memoria a nivel de bits para hacer funciones genéricas (un linear search que sirva para un array de ints o un array de strings). Todas esas cosas que damos por obvias los que usamos lenguajes de alto nivel como Python y Ruby, hay que hacerlas a pedal en lenguajes más rústicos como C.

En otro post entraré más en detalle sobre estas clases, porque me parecen bastante interesantes y probablemente las mire con atención.

Anuncios

MIT 6.00

Este curso es una versión en dos partes del primer curso de computación en MIT. Usan Python. El curso lo toman todos los estudiantes de carreras técnicas de MIT, por lo que no está enfocado como los típicos CS 101, sino como un panorama de como resolver problemas con computadoras en varias áreas.

 

Introduction to Computer Science and Programming Using Python

Como los deadlines son bastante estrictos y ya conozco bastante los temas no me lo tomé muy en serio, hice algunos de los ejercicios para trabajar con Emacs.

De todas formas me topé con algunas complicaciones y aprendí algunas cosas nuevas.

 

Introduction to Computational Thinking and Data Science

 

Cuando me di cuenta que este curso tenía problem sets interesantes era un poco tarde, pero lo más probable es que en la próxima iteración haga alguno más y actualice este post.  En esta iteración pude hacer solo es 5.

Pset 5 – Finding Shortest paths

Este fue bastante complicado. El problema consiste en procesar un graph con la información de una mapa del campus de MIT. Hay que encontrar el camino más corto entre un lugar  y otro, con la particularidad que hay caminos techados y caminos al aire libre, y hay una restricción de cuanto puedo recorrer al aire libre.

Esto hace que el algoritmo estándar no funcione. La solución es un algoritmo recursivo que explora el grafo y recuerda cual es mejor solución de las que ya recorrió. El bug más difícil que tuve fue por manejar mal la memoria en el stack, porque había que tener en la memoria y accesible para todo el stack cual era el camino más corto, y para cada stack tenía que tener la memoria del camino que había seguido hasta llegar ahí. Una vez que llegaba a un dead end, tenía que backtrack hasta un nodo válido, y recuperar ahí el camino. Esto fue un poco complicado. [Referencia a Sudoku Solver].

 

 

Amaestrando Emacs

Siempre quise saber usar bien un editor de texto. La mayor parte de los nerds hardcore usan Vim o Emacs. Después de leer bastante sobre las idiosincracias de cada uno, me parece que Emacs es para mi. Además, lo usé un poco en el curso de Dan Grossman sobre Programming Languages a fines de 2014 para la parte de SML.

El mejor material que encontré es el libro de Mickey Petersen Mastering Emacs. En Youtube hay bastante material, pero en general es aburridísimo. Sasha Chua tiene un montón de entrevistas donde hablan usuarios legendarios de Emacs. Además Steve Yegge tiene un montón de posts sobre Emacs.

En conclusión, Emacs es genial si ya sos un capo, pero es bastante difícil de hincarle el diente. En general siempre me vuelco por este tipo de herramientas, creo que es preferible que algo sea cada vez mejor a medida que te volvés mejor, y no al revés (se me ocurre que es el caso de MS Excel) que cuanto mejor sabés usarlo más lo odias.

Básicamente, diría que el uso básico de todo editor de texto incluye las siguientes funcionalidades:

  • Cortar y Pegar Texto
  • Moverse adentro de un archivo
  • Moverse entre archivos
  • Snippets
  • Macros
  • Autocomplete

Después de un añó de usar Emacs y un par de meses de tratar de aprenderlo activamente, creo que soy aceptable en todas menos Autocomplete.

 

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).