• A Django site. •
• •
October 4, 2008

Cesar Villegas
slayer
Slayer_X homepage
» The Big Bang Theory: 1ra temporada

Siguiendo con mi maraton de series, tengo en mis manos los 3 DVDs que conforman la 1ra temporada de The Big Bang Theory que es una serie cómica con demasiado contenido NERD; la mejor forma de resumir esta serie es que es una serie de nerds para nerds, de otra forma veo muy complicado que gente “normal” pueda entenderla. En realidad exagero un poco, la verdad es que esta serie tiene muchísimos elementos considerados geeks/nerds/freaks.

The Big Bang Theory

Imagen a 2 genios con sendos doctorados en física viviendo juntos, ambos comparten las típicas aficiones de los nerds como coleccionar comics, figuras de acción, ser fans de star wars, jugar Halo, World of Warcraft, Warhammer, etc etc. Sheldon (Jim Parsons) es el mas nerd y antisocial (en la imagen es el de la izquierda) es de lejos el mejor personaje, su forma de interactuar con la gente es increible, el tipo tiene paranoia con el orden, con su salud y en que la gente diga las cosas correctamente, ponerse a discutir con el es terrible porque es una enciclopedia para poder dar datos y refutar cualquier argumento en contra de su posición. Leonard (Johnny Galecki) es también nerd pero a diferencia de Sheldon tiene interés en las mujeres y esta perdidamente enamorado de Penny (Kaley Cuoco) que es la rubia que vemos en la foto, lastimosamente para Leonard sus habilidades para interactuar con las chicas no estan a la par con sus conocimientos de Física.

Pero ellos no estan solos, tienen 2 amigos: Howard (Simon Helberg) un nerd de ascendencia judia que vive con su madre y que esta obsesionado con las mujeres a quiénes trata de conquistar hablandoles en distintos idiomas. Finalmente tenemos a Rajesh Koothrappali (Kunal Nayyar) un joven hindu que sufre de incapacidad para poder hablar con las mujeres, si una mujer le habla el simplemente se queda mudo y no puede articular palabra, ademas odia la comida hindu y se anda quejando de que es discriminado por su origen.

Cualquiera pensaría que todo gira en torno a Penny, que por cierto viene de un pueblo a la gran ciudad a probar fortuna y es un poco tonta (felizmente no la hicieron exageradamente tonta) realmente lo mejor de la serie es la interacción entre estos 4 nerds, los chistes son muy buenos aunque claro hacen muchas referencias a la cultura “pop” de los nerd de hoy en dia, asi que hay ocasiones en las que uno se puede perder un poco.

Para que se hagan una idea de como es la serie les dejo un par de videos, en el primero se ve a los protagonistas jugando World of Warcraft:

The Swordmaster ^_^

Y en esta otra escena estan jugando Halo y reciben una sorpresiva visita

Si les parecio divertido entonces no pueden perderse esta serie por nada del mundo, descarguenla de su sitio de torrents preferido ^_^

Como bonus encontré una web que recopila las camisetas usadas en la serie y donde comprarlas: http://www.sheldonshirts.com/

by Slayer_X at 4:37 AM under geek , humor , nerd , series , television , the big bang theory , tv (Comments)
November 18, 2007

Gustavo Picón
tabo
tabo :: para todos y para nadie
» Optimizando solución a problema de edificio de Google

Hace una semana publicaba la solución a un problema de entrevista tipo que hacen en google, la pregunta era la siguiente:



La solución que publiqué no solo daba la solución si no que brindaba los pisos desde los que se debía arrojar los objetos. Antonio Ognio complementó mi solución con una muy buena explicación del problema.

Ya había dado por cerrado el tema, hasta que Eduardo Morales, el ingeniero de Google que presentó el problema, dejó unos comentarios interesantes.

El principal reparo de Eduardo con mi solución es que no es eficiente. Es un algoritmo "O(n^2)". Como le comentaba a Eduardo, no era mi propósito hacer una solución eficiente, solo necesitaba una solución y nada más. La optimización prematura es la raiz de todos los males mencioné parafraseando a Knuth, y en este caso no necesitaba de ninguna optimización, ya que el enunciado del problema no pide un algoritmo óptimo (solo pide hayar una solución rompiendo el menor número de objetos). Para este problema, en mi opinión, optimizar representaba un costo (mi tiempo) y ningún beneficio.

Pero al mencionar Eduardo que el problema se puede optimizar hasta O(1), pues me pareció un buen ejercicio, y la optimización de código, cuando es estrictamente necesaria, puede ser bastante gratificante. Tenía entonces ahora un beneficio para optimizar: podía publicar el proceso de optimización, dedicado especialmente para aquellos que mostraron interés en mi solución original (y varios al parecer, según me comentan por privado, están leyendo a Knuth :-)

Así que veamos el proceso de optimización, si no lo han hecho, pediría que lean primero mi (ineficiente) solución original y la explicación detallada de Antonio.

Comencemos entonces por la primera optimización:

Problema edificio google: O(n)

Gracias a este algoritmo tenemos esta solución en Python:

def findworst(num):
for res in range(1, num+1):
    if res*(res+1)/2 >= num:
        break
return res
que es una solución O(n)

Pero esto se puede optimizar aún mas, como podemos apreciar:

Problema edificio google: O(1)

Lo que nos deja con este código en Python:

def findworst_o1(num):
    return math.ceil((math.sqrt(num*8+1)-1)/2)



que es una solución O(1), constante, y en una línea de código.

Podemos sacar algunas lecciones con todo esto:

  1. La optimización prematura no es necesaria. El algoritmo original, a pesar de no ser óptimo, nos daba una solución correcta. El costo de optimizar (tiempo) era mas alto que los beneficios (nulos). Esto cambió con los comentarios de Eduardo ya que apareció un beneficio: mostrar el proceso de optimización para los lectores.
  2. Tener una base matemática es muy importante. De no haber aplicado matemáticas la solución se hubiera hallado con "fuerza bruta" pero no con eficiencia.
Muchas gracias Eduardo por tus comentarios, espero que estos posts despierten el interés de mis lectores técnicos para investigar estos temas. Y para mis lectores no técnicos (se supone que este es mi blog no-nerd), mil disculpas, prometo volver pronto a la normalidad ;-)

Comentarios?

tags: , , , , , , , , ,

by tabo at 4:08 AM under algoritmos , edificio , entrevista , google , knuth , nerd , optimizacion , python , solucion , taocp
» Solucion a quiz de google

Para hacer la historia corta:

Soplín fue a una charla de Google y publicó un slide con una pregunta típica de las entrevistas laborales en Google:



Este quiz provocó un total alboroto chichero solucionando el problemita. Yo había publicado ya un rudimento del algoritmo y la respuesta, pero había dejado pendiente detallar la solución, asi que aqui va:

Algoritmo de solucion a problema de entrevista de google (edificio)

Y la solución programada y lista para usar:

#!/usr/bin/env python

def findsteps(numpisos):
   res = 1
   while True:
       l = []
       val = 0
       for step in range(res, 0, -1):
           val += step
           if val >= numpisos:
               l.append(numpisos)
               break
           l.append(val)
       if val >= numpisos:
           break
       res += 1
   return l
  
if __name__ == '__main__':
   import sys
   if len(sys.argv) > 1:
       try:
           numpisos = int(sys.argv[1])
       except ValueError, errmsg:
           sys.stdout.write('ERROR: num de pisos debe ser un entero\n')
           sys.exit(-1)
   else:  
       numpisos = 100
   if numpisos < 1:
       sys.stdout.write('ERROR: num de pisos debe ser un >= 1\n')
       sys.exit(-1)
   print '# Pisos-intervalo para edificio de %d pisos: \n' % (numpisos,)
   res = findsteps(numpisos)
   print res
   print '# %d intentos en el peor escenario' % (res[0],)



Con este programita pueden encontrar la solución óptima para un edificio de cualquier altura, pero veamos los pasos necesarios para el edificio de 100 pisos del problema original:


# Pisos-intervalo para edificio de 100 pisos:
[14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100]
# 14 intentos en el peor escenario


Cumplido mis queridos chicheros, ahora espero que Soplín cumpla su promesa de publicar las otras preguntas!

(y creo que es aparente que si las empresas locales hicieran este tipo de preguntas en vez de "tiene un mcse?", el nivel de empleo local sería CERO!)

Por cierto: GRACIAS TIO KNUTH! No hubiera podido resolver esto sin ti!

Actualización: Antonio Ognio, demostrando sus capacidades de docente, hace una explicación for dummies del algoritmo del problema. Denle una mirada si no la captaron con mi dibujito y el código en Python ;-)

Actualización2: Optimizaciones, algoritmo O(n^2) es ahora O(1)

tags: , , , , , ,

by tabo at 3:58 AM under edificio , entrevista , google , knuth , nerd , solucion , taocp