lunes, 24 de enero de 2011

Sudoku Solver

Hace unos días, se anunció que Google Goggles para Android es capaz de resolver un Sudoku, tomando una foto del mismo. Incluso hay un video que muestra como funciona:



También hace unos días, leyendo Coders at Work (buen libro, se recomienda), en la entrevista a Peter Norvig, comenta:
It’s also important to know what you’re doing. When I wrote my Sudoku solver, some bloggers commented on that. They said, “Look at the contrast—here’s Norvig’s Sudoku thing and then there’s this other guy, whose name I’ve forgotten, one of these test-driven design gurus. He starts off and he says, “Well, I’m going to do Sudoku and I’m going to have this class and first thing I’m going to do is write a bunch of tests.” But then he never got anywhere. He had five different blog posts and in each one he wrote a little bit more and wrote lots of tests but he never got anything working because he didn’t know how to solve the problem.
Así que, me dije... ¿qué tan difícil puede ser hacer un programa que resuelva un Sudoku? (no la parte de sacar la foto e interpretarla, solo el algoritmo). Resulta que no es tan difícil...

Pueden ver el código en GitHub: https://github.com/mcrispino/sudoku-solver. Ahí están también las instrucciones para bajarlo y ejecutar el programa.

El programa está escrito en Ruby, mi nuevo lenguaje favorito :) En una próxima nota explicaré alguna parte del código y por qué me gusta como se resuelven en el lenguaje.

El algoritmo es bastante sencillo. Creo que además el código es bastante simple de leer, pero acá va una explicación:

  • se parte de un tablero (clase Board), que es una matriz de 9x9, donde cada elemento es un array con todos los valores posibles, inicialmente todos los números del 1 al 9
  • para cada valor en el tablero original, se carga ese valor en el lugar correspondiente en la matriz, y se elimina de todos los lugares donde ya no puede estar (fila, columna y sub-matriz de 3x3)
  • una vez ubicados todos los números "fijos", se buscan posiciones de la matriz que hayan quedado con un array con un solo elemento (solo hay un posible valor), y para estos se repite el proceso anterior de cambiar el array por el valor y eliminarlo de los posibles valores de las posiciones donde ya no puede estar
  • esto se repite hasta que no hayan más arrays (se encontró una solución), o hasta que no queden arrays con un solo elemento
  • si quedan arrays con más de un elemento, entonces se hace una copia del tablero, se elige uno de los valores posibles, y se intenta resolver
  • si se encuentra una solución, entonces ya está
  • si no se encuentra, se hace backtracking.
Con este algoritmo, la solución se encuentra de forma instantánea. Probé también solo con el backtracking, pero nunca llegó a terminar (tampoco le tuve demasiada paciencia).

Para los que sepan Ruby, se agradecen comentarios, correcciones y sugerencias. Es una buena forma de aprender :)

jueves, 13 de enero de 2011

Testeando aplicaciones Ruby on Rails con RSpec

Hace unos días escribí una nota sobre Ruby on Rails, contando mis primeras impresiones.

Una de las cosas que parece ser bastante común con Rails, es tener testeo automatizado. Incluso por lo que he leído se usa mucho Test Driven Development (o TDD, donde se especifican las pruebas antes de escribir el código que cumpla los requerimientos)

Todavía no llegué al nivel de TDD, cuesta un poco acostumbrarse a la metodología, pero sí empecé a escribir algunas pruebas. Para eso estoy usando RSpec, que no es el ambiente que viene por defecto, pero se integra muy bien.

RSpec define un Domain Specific Language (DSL), que hace que los casos de prueba queden muy sencillos de leer, casi como si estuvieran escritos en inglés.

Por ejemplo, supongamos que tenemos una entidad User, y queremos que solo tengan acceso los usuarios logueados, y que la página donde se listan los usuarios tenga título "Users". La especificación de los casos de prueba podría ser la siguiente:
require 'spec_helper'

describe UsersController do
  render_views

  describe "GET 'index'" do

    describe "for non-signed-in users" do
      it "redirects to login page" do
        get :index
        response.should redirect_to(signin_path)
        flash[:notice].should match(/sign in/i)
      end
    end

    describe "for signed-in users" do
      login_user

      before(:each) do
        get :index
      end

      it "is successful" do
        response.should be_success
      end

      it "has the right title" do
        response.should have_selector("title", :content => "Users")
      end
    end
  end
end
¿Simple, no? Cada vez me está gustando más Rails :)

La salida, si todos los tests pasan, sería algo así:
UsersController
  GET 'index'
    for non-signed-in users
      redirects to login page
    for signed-in users
      is successful
      has the right title
Si alguna de las pruebas falla, en el resumen aparece en rojo y al final muestra el detalle del error.

Algunos recursos interesantes: