Participando en Facebook Hacker Cup

Este año me acordé a tiempo de este evento (y la verdad que este año estuve usando por primera vez mi cuenta de Facebook :P) así que decidí probar a ver que onda.

La primer impresión : se complica rendir bien teniendo familia (o una vida de por si :P); no se puede salir apenas aparecen los problemas a lo loco a cualquier hora a resolverlos.

Desde el punto de vista técnico, los dos primeros problemas fueron muy fáciles. “Beautiful strings” fue trivial realmente, con pensar 2 o 3 min salía. El problema “Balanced Smileys” donde se buscaba determinar balanceo de () con al dificultad de que había caritas felices y tristes fue un poco mas arduo de probar, más que nada por pensar en posibilidades locas para estar seguro de tener todos los casos. En ambos problemas el primer envío de mi solución paso bien, así que realmente para estar fuera de training nada mal :).

El problema real llegó en el tercer problema, el que más puntos da. “Find the Min” es un problema conceptualmente fácil. Me complico un poco al principio entender por el idioma (“which is *not* contained in the previous *k* values of m.” no fue una frase trivial de entender para mi :D). El desafío del problema era principalmente la optimización, ya que se trabajaba mucho con arrays y en algunos casos se podía ir el tiempo al demonio.

En mi implementación (que veré de postear en algún momento cuando cierre el concurso) pude resolver los ejemplos que dan y algunos casos más que invente grandes en unos 2 a 3 min. Sin embargo no conté con casos tan complicados como los que venían cuando uno se bajaba el archivo posta para participar y lamentablemente llegué unos 5 o 6 minutos tarde, por lo que no pude subir mi solución. Facebook nos da una ventana de 6 minutos desde que bajamos el archivo de prueba hasta subir la solución. Yo pase de los 10 y ahí me quede.

Calculo que eso me elimina para la siguiente face, pero uno nunca sabe :P, tal vez me vaya mejor el año que viene :D. O en el Google Code Jam que viene dentro de poco ;).

Anuncios

Filtro de Contenido para T!

Hoy estuve leyendo este post donde los dueños de Taringa declara que “no podemos investigar el destino final de cada uno de los 20.000 post diarios”. Lejos de ser algo “colectivamente inteligente” como declaración, es una terrible boludez :). Con aplicar algunos filtros automáticos, permitir que cualquiera de forma rápida y fácil reporte los contenidos ilegales y actuando más o menos rápido en su eliminación uno se cubre el 90% del orto. El otro 10% hay que pelearlo por carta documento porque hay gente muy al pedo ahí afuera, pero ni en pedo llegamos a un juicio oral teniendo un poco de criterio :).

El problema es que filtrar a mano es caro, y además filtrar hace que nuestros usuarios bajen pues no tiene ya toda la piratería al alcance de la mano ;). Pero veamos como hacer un filtro para determinar por heurística los posts que posiblemente sean ilegales, de manera de poder revisar a mano solo los que tal ve son malos, y así bajar el trabajo necesario y por ahí bajar el costo y aumentar el profit :).

No lo voy a explicar muy en detalle, pero básicamente el programa siguiente hace un scraping de la home de T! y agarra los ‘Ultimos posts’. Para cada uno de ellos, lee el contenido y aplica una heurística muy básica para ver si es potencialmente ilegal :

require 'rubygems'
require 'net/http'
require 'hpricot'

AGENT = "Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.10) Gecko/20100915 Ubuntu/10.04 (lucid) Firefox/3.6.10"

url = URI.parse("http://www.taringa.net/")
http = Net::HTTP.new("www.taringa.net")
html = http.request_get('/', {'User-Agent' => AGENT})

doc = Hpricot(html.body)
(doc/"html/body/div[2]/div[4]/div[4]/div/div[2]/ul/li/a").each do |link|
  text = http.request_get(link.attributes['href'], {'User-Agent' => AGENT})
  doc1 = Hpricot(text.body)
  content = (doc1/"html/body/div[2]/div[4]/div[4]/div/div[2]/div[2]").first.to_s

  if (content =~ /megaupload/i) || (content =~ /free/i) || (content =~ /mediafire/i) || (content =~ /fileserve/i)
    puts "#{link.inner_html.strip} posible post ilegal"
  else
    if (content =~ /Este post es privado/i)
        puts "#{link.inner_html.strip} es privado. Al menos si es ilegal no lo ve todo el mundo :)"
    else
      puts "#{link.inner_html.strip} parece legal."
    end
  end
end

Con esto podemos saber :

  • Cuantos posts parecen legales
  • Cuantos parecen ilegales
  • Cuantos no son públicos, por lo que podemos revisarlos o no, no es tan terrible

Con un poco de bash sacamos las stats :

gazer@Max:~$ ruby tfilter.rb > post.txt
54 post.txt
gazer@Max:~$ grep 'posible post ilegal' post.txt | wc -l
2

Solo el 3.7% de los posts analizados parecería ser ilegales, por lo que en lugar de tener que revisar 20.000 posts por día solo deberia revisar 740, el número es otro. Si de esos ademas sumás el report del user, seguro no te quedan mucho más y hasta por ahí lo podés moderar mientras desayunas :).

Obviamente mi filtro se basa solamente en linksharing (que es el 90% del problema de T! y del uso que sus usuarios le dan al site). Seguramente haya servicios de upload que no puse, pero para demostrar que filtrar el contenido es una terrible pelotudez y que Taringa! no lo hace porque no le conviene, alcanza y sobra :).

Posts analizados

Procesando archivos en background con Rails

Procesar archivos en paneles de administración es un bajón, sobre todo cuando son cada vez más grande y cada vez más. En uno de nuestros proyectos tenemos ya unos cinco archivos CSV diferentes a procesar donde cada uno cumple alguna función específica. Algunos de estos archivos superan los 5 Mb por upload, por lo que se hizo necesario desacoplar el procesamiento del archivo del request que realiza el upload.

Para manejar procesos en background en rails hay muchas opciones buenas, algunas más complejas con colas de trabajo, workers distribuidos y otras cosas que nosotros no necesitamos. Lo importante para nosotros era encontrar alguno que permita :

  • Procesar en background (obvio :D)
  • Poder saber en que estado está el trabajo (% completado)
  • Al menos un proceso en background a la vez (si hay más que espere su turno, los uploads son semanales o mensuales por lo que no hay tanto solapamiento entre tareas como para justificar múltiples workers)

Y nada más. Buscando y buscando caí con BackgroundFu que cumplía con lo necesario.

Procesando los archivos

Como todos los archivos son de texto con algún separador (algunos ‘;’, otros tabs o comas) empezamos por lo básico y crear una clase base que maneje algunos parámetros comunes.

En BackgroundFu uno puede encolar cualquier clase, por lo que nuestro worker es simplemente una clase con un método process (que también es arbitrario el nombre, podría ser cualquier otro).

Como el archivo que sube el usuario está en un directorio temporal, antes de mandar al proceso en background en necesario guardarlo en algún lugar seguro, para poder saber que al momento de procesarlo va a seguir estando, para ello encapsulamos este comportamiento en un método especial para encolar.

Nuestra completa termina siendo algo como (más adelante veremos en detalle algunas cosas) :

class FileWorker
  include BackgroundFu::WorkerMonitoring

  attr_reader :total_lines

  def self.enqueue(file, *args)
    filename = "#{RAILS_ROOT}/tmp/#{self.name}-#{Time.now.to_i}"
    File.open(filename, "wb") { |f| f.write(file.read) }
    Job.enqueue!(self.name, :'process', filename, *args).id
  end

  def process(filename, *args)
    @lines = 0
    @total_lines = `wc -l #{filename}`.to_i
    record_progress(0)

    result = real_process(filename, *args)

    record_progress(100)
    File.unlink(filename)

    result
  end

  protected
  def line_processed!
    @lines += 1

    update(@lines)
  end

  def update(lines)
    record_progress(lines, @total_lines)
  end
end

Veamos un poco más en detalle algunas partes.

Encolado

  def self.enqueue(file, *args)
    filename = "#{RAILS_ROOT}/tmp/#{self.name}-#{Time.now.to_i}"
    File.open(filename, "wb") { |f| f.write(file.read) }
    Job.enqueue!(self.name, :'process', filename, *args).id
  end

Este método es quien guarda en un lugar seguro el archivo. Utilizando el nombre de la clase actual (recuerden que este método está en una clase base, de donde luego vamos a heredar) y un timestamp por las dudas que se lleguen a hacer 2 uploads (cosa que en la práctica no pasa, pero por las dudas está).

Luego de guardar el archivo se encola el trabajo pasándole el archivo (el path completo) y cualquier otro argumento que se quiera.

Esto hará que luego el daemon de background instancia la clase ‘self.name’ y llame al método process pasandole nuestros parámetros.

Procesamiento

El método genérico de procesamiento hace uso de un método que la clase base no tiene ‘real_process’ que es el método que las clases hijas definarán para realizar el trabajo final :

  def process(filename, *args)
    @lines = 0
    @total_lines = `wc -l #{filename}`.to_i
    record_progress(0)

    result = real_process(filename, *args)

    record_progress(100)
    File.unlink(filename)

    result
  end

En este caso el método se encarga de saber cual es el total de lineas (de una manera tal vez no muy linda, pero que anda :P) y borrar el archivo al terminar el proceso.

Un worker real

Para que esto tenga sentido, debemos crear un worker que haga realmente algo, entonces por ejemplo podríamos tener un worker que sume puntos a los usuarios desde un archivo :

class UserPointProcessor  "t").each do |row|
         # Hacer algo con row

         line_processed!
      end
    end

    "Podemos retornar algun valor o status de exito"
  end
end

De esta forma podemos ahora en algún controller hacer el encolado del trabajo :

  def add_points
    if request.post?
      redirect_to admin_job_path(UserPointProcessor.enqueue(params[:file])) and return
    end

    render 'file_upload'
  end

En este caso el template file_upload es un form con un file field para hacer el upload, sin ningún otro campo. La ruta admin_job_path nos la provee directamente BackgroundFu, generándonos también las vistas con AJAX para actualizar el estado, una linda barra de progreso que nos muestra el tiempo estimado para terminar entre otros datos útiles (o no tanto :D).

HTML5 : Guardar el contenido de en el servidor

Hoy tenía ganas de hacer algo distinto (vamos, no quería trabajar :P) así que me puse a jugar con HTML5, entre otras cosas con el tag <canvas> para poder dibujar. Luego de bajar varios ejemplos y tener un ‘paint’ andando lo que quería era guardar la imagen, y llegué a este post donde el autor deja guardar en PNG, JPG hasta incluso en BMP el contenido del canvas.

Pero que el usuario se pueda guardar la imagen no era mi idea, era más bien guardarle en el servidor. Por ejemplo para hacer una firma digital y usarla después en el sitio para firmar los posts como si fueran documentos :P.

Al principio pensé que iba a ser super complicado, pero me encontré que todo fue mucho más fácil de lo que imaginé. Así que vamos por partes.

Vamos a empezar por el server. Como era muy poco código para este ejemplo, hice una aplicación en Sinatra que me permite mostrar un canvas y luego hacer un POST con los datos. Es ideal en este caso, ya que el server queda de tan solo unas 20 líneas de código :

require 'sinatra'
require 'RMagick'

get '/' do
   erb :index
end

post '/' do
  # Ya completaremos ...
end

Como se puede ver tenemos una vista en el root y el POST lo manejamos también en la raiz. Para procesar la imagen decidí usar la única gema que conozco, RMagick, que buscando en la documentación de ImageMagick me encontré con grata sorpresa que sale leer ‘Base64-encoded inline image’ , que resulta que es justo el formato en que se obtienen los datos desde el canvas :). La única diferencia es que hay que preceder el string con ‘inline:’ y ya estamos, nuestro método POST queda así :

post '/' do
  data = 'inline:' + request.body.read

  begin
    image = Magick::Image.read(data).first

    image.write('image.png')
    "alert('Image saved successfully')"
  rescue
    "alert('Image format not recognized')"
  end
end

Habría que revisar la documentación y bugs de ImageMagick para ver que tipos de implicancia puede llegar a tener en la seguridad del sitio o del sistema, pero son cosas que no vienen al caso :).

La vista (reducida para el ejemplo) puede resumirse en el siguiente HTML :

  
    This text is displayed if your browser does not support HTML5 Canvas.
  

  

Y un poco de javascript :


  $(function () {
    $("input").click(function () {
      // jQuery todavía no habla bien con HTML5, hack para
      // no usar un plugin.
      var c = $("#example").get(0);
      $.post('/', c.toDataURL(), null, "script");
    });

    // Un dibujito estático para probar
    var example = document.getElementById('example');
    var context = example.getContext('2d');
    context.fillStyle = "rgb(255,0,0)";
    context.fillRect(30, 30, 50, 50);
  })

Y ya estamos, al presionar el botón se envían los datos de la imagen dibujada, si está todo bien ImageMagick creará el archivo en el filesystem y por último devolverá algo de javascript para informar al usuario como salió todo. Obviamente si tuviéramos un sistema de usuarios en el server podríamos guardar la imagen para cada uno, pero de nuevo, no viene al caso.

El resultado final :

$ identify -verbose image.png 
Image: image.png
  Format: PNG (Portable Network Graphics)
  Class: DirectClass
  Geometry: 200x200+0+0
  Resolution: 72x72
  Print size: 2.77778x2.77778
  Colorspace: RGB
  Depth: 8/1-bit
  Histogram:
     37500: (  0,  0,  0,  0) #00000000 none
      2500: (255,  0,  0,255) #FF0000 red
  Page geometry: 200x200+0+0
  Compression: Zip
  Properties:
    create-date: 2010-04-13T00:20:15-03:00
    modify-date: 2010-04-13T00:20:15-03:00
    signature: 0a42f3c85d6364e38f14dac554d26c62a90b84b06ac7f22264c9d964657ba8d6
  Tainted: False
  Filesize: 503b
  Number pixels: 39.1kb
  Version: ImageMagick 6.5.1-0 2009-08-27 Q16 OpenMP http://www.imagemagick.org

Probado en :

  • Chromium 5.0.372.0 (44042) Ubuntu
  • Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.9) Gecko/20100401 Ubuntu/9.10 (karmic) Firefox/3.5.9

Código completo : html5_canvas_submit

Migrando datos desde PHP a Rails

Por esas cosas de la vida me encontré todo el día de hoy migrando datos viejos de un sistema hecho en PHP a uno hecho en Rails. Las cosas venían bastante simples definiendo modelos de ActiveRecord para las tablas de la base de datos vieja y reinsertando con modelos apuntando a las tablas nuevas. Pero … siempre hay un pero.

Resulta que el hermoso sistema anterior para evitar tener muchas tablas (o vaya a saber por qué) tenía en una parte un tabla donde cada field era un gran TEXT que contenía un array de PHP serializado.

class UserTextField  user = UserTextField.find(3)
$> user.folders # => 'a:2:{i:0;s:4:"bkps";i:1;s:6:"listas";'

Justo cuando estaba por ponerme a parsear texto me encontré con php-serialize que permite serializar y deserializar estos string en cómodos tipos nativos de Ruby.

El código final queda entonces algo como :

class UserTextField  user = UserTextField.find(3)
$> user.folders # => ["bkps", "listas"]

Y la migración de datos pudo continuar sin problemas :).

Regalando cosas por Bluetooth

El año pasado Movistar había lanzado una campaña muy pedorra en el subte, en donde unos carteles en el piso te invitaban a prender tu Bluetooth y te enviaban un file. Lo que te enviaban era una simple imagen, con tanto texto que en mi celular era casi ilegible y no tenía consigna alguna.

Sin embargo esto sirvió para que me encaprichara y quisiera armar algo similar para la oficina, orientado a que un cliente que viene a una reunión se pueda llevar un regalo, que en este caso es un juego J2ME.

Hacerlo realmente es una boludez. El real problema, que no voy a tratar acá, es tener una placa Bluetooth soportada por Linux (creo que esta solución aplica Windows, pero no lo probé), lo que puede resultar complicado. Yo en mi anterior laptop fallé en cada intento. Hoy en día en mi MacBook anda todo out-of-the-box por suerte así que pude jugar un poco.

El protocolo que se utiliza para intercambiar cosas es Object Exchange (OBEX) y tenemos una excelente biblioteca llamada OpenObex. A nosotros nos interesa particularmente ObexFTP que nos da el File Transfer sobre Obex.

El primer problema que tuve es que en Jaunty no está el binding de ruby, por lo que me tuve que bajar el source y diff de Karmic y crear mis libobexftp-ruby_0.22-1_i386.deb y sus dependencias.

Salvando eso, con los ejemplos del wiki sale muy fácil. La biblioteca nos permite descubrir devices, abrir channels y enviar archivos en pocas líneas. Acá un en ruby ejemplo :

#!/usr/bin/env ruby

require 'obexftp'

puts "Scanning BT..."
intfs = Obexftp.discover(Obexftp::BLUETOOTH)
dev = intfs.first # Es un array, podríamos iterar sobre todas las encontradas

channel = Obexftp.browsebt(dev, Obexftp::PUSH)

cli = Obexftp::Client.new(Obexftp::BLUETOOTH)
puts cli.connectpush(dev, channel)
puts cli.put_file('ver.jpg')
puts cli.disconnect

Hacer lo mismo en Python, Perl o cualqueir otro lenguaje soportado es igual de simple.

Obviamente es muy minimalista: agarra el primer device encontrado, abre un channel para hacer un PUSH (si el device no soporta PUSH retorna -1 según creo), luego abre la conexión y le envía el archivo.

Desde el celular vemos un mensaje de que se está abriendo una conexión y luego el detalle de lo que se quiere enviar, nombre del archivo, tipo de archivo, tamaño, etc. Podemos aceptarlo o rechazarlo. De aceptarlo se descarga pero no se guarda ni se instala, es un paso extra que debemos decidir si lo hacemos o no.

Un problema que encontramos para enviar juegos es que algunos celulares están bloqueados para esa función (para así vendértelos por el portal WAP oficial de tu carrier). Ya lo pudimos probar con varios celulares Nokia, Motorola y Samsung y funciona razonablemente bien.

Sobre este ejemplo nosotros tenés un poco más de trabajo, ya que guardamos los device ID y el contenido enviado, así cuando volvés te damos un contenido diferente :). Si además no podés recibir el juego, te pasamos una imágen simpática :P.

Sitemaps vía crawling

Hoy me pidieron agregar un Sitemap para uno de los trabajos que hicimos para el gobierno y me encontré con que los plugins que uso para esta tarea no me cerraban de forma cómoda. El problema es que este sitio tiene, además del contenido dinámico, muchas páginas estáticas que no puedo referenciar desde un modelo, por lo que debía forzarlas y era bastante molesto.

Buscando encontré una solución práctica para este caso (donde hay pocas páginas, menos de 1k) que usa un crawler para recorrer todo el sitio y obtener las URLs a agregar al sitemap. El script que presentan me sirvió, aunque tuve que hacerle algunos cambios menores.

El primer problema que tenía era que me agregaba páginas que no deben ir en un sitemap (ni ser indexadas) como las de login, recuperar clave, form de registración, etc. Por lo que tuve que modificar ligeramente el código para no seguir los enlaces que estuvieran marcados con rel="nofollow" y para eso modifiqué en el método extract_and_call_urls la última línea como sigue :

links.each{ |link|
   extract_and_call_urls(link.href) unless
      !can_follow?(link) || ignore_url?(link.href) || 
      @visited_pages.include?(link.href) 
}

Y definiendo el nuevo método :

 def can_follow?(link)
   return false if link.nil? ||
   (link.attributes["rel"] && link.attributes["rel"].include?("nofollow"))
   
   true
 end

Entonces, cuando el crawler encuentra un enlace que el developer marcó que no debe seguirse en una indexación (esto es principalmente para los crawlers de los search engines) se ignora y no se agrega al sitemap.

El otro cambio menor fue que tenía algunas URLs con el path completo y por default siempre me agregaba al inicio el domain name, por lo que me quedaban URLs inválidas, por lo que hice la siguiente modificación :

# Antes
xml.loc(@starting_url + url)

# Después
xml.loc(url.include?(@starting_url) ? url : (@starting_url + url))

Una vez probado el script hice una tarea rake para poder correrla fácil desde un cronjob :

# lib/tasks/sitemap.rake
require 'lib/crawler'

desc "Generate the sitemap file"
task :sitemap => :environment do
  start_url = ENV["URL"] || "http://localhost:3000"
  Crawler.new(start_url, (ENV["CREDS"] if ENV["CREDS"]), ENV["QUIET"] || false, ENV["SITEMAP"] || false, ENV["DEBUG"] || false)
end

Y listo, lo último fue hacer un deploy y configurar un cron.dayli para que cree el sitemap actualizado :

rake sitemap URL=http://www.haciendoelcolon.buenosaires.gob.ar SITEMAP=true

Así una vez por día se actualiza el sitemap y se hace un ping a google para que sepa que debe pasar a reindexar el contenido.

Esto tiene varias desventajas (pero aún así para este sitio sirve a su propópito) :

  • No se puede priorizar cada tipo de contenido fácilmente
  • La fecha de última modificación es inexacta
  • Carga el webserver para generar el sitemap

Código completo : crawler.rb