2008-12-25

Traducciones hollywoodenses

Después de ir todos los mediodías a diversos restaurantes de Palermo Hollywood pude recabar información sobre el "argot" que usan para escribir las cartas. Estas son algunas de las cosas que pude entender hasta ahora:

  • colchón de verdes: ¡uy!, no compramos tomates.
  • a las finas hierbas: en una de esas le ponemos perejil.
  • papas rústicas: íbamos a hacer papas fritas pero nos dio mucha vagancia pelar las papas.
  • pezca del día: es lo más barato que había en la pezcadería.
  • menú ejecutivo: al mediodía son todos unos ratas, así que hay que darles algo barato.
  • brusquetas: nos sobró pan duro de ayer.
  • cocina gourmet: vamos a darte re-poca comida, te vas a quedar con mucha hambre y te vamos a cobrar un fangote de guita. Eso sí, cuando te llevemos el plato vas a decir "¡qué lindo! parece un cuadro"
  • spring-roll: arrolladito primavera, pero todavía más chiquito
  • explosión de vegetales: Lo que me sobró de ayer le agregué un huevo y lo cociné, AKA: "revuelto de gramajo".
Aureliano.

2008-12-09

C++ frequently questioned answers

La obra de Yossi Kreinin en su C++ Frequently questioned answers es soberbia. Cientos y cientos de Kbytes dedicados exclusivamente a explicar porqué no usar C++ para empezar proyectos nuevos de desarrollo de software (cosa que comparto) y explicar las falencias de C++ detalladamente (y, la verdad, las falencias están bien justificadas).

Con un estilo ácido, ágil y de fácil lectura, demuele carta a carta ese castillo de naipes que es C++. No puedo hacer más que recomendar la lectura de esta excelente página.

Happy hacking (pero no en C++),
Aureliano.

2008-12-03

Números de Aure

Update: Los números de Aure también se llaman A131689
Update: Los números de Aure aparecen en el último libro de Paenza, Cómo, esto también es matemática?. Mirá la página 224.

La oficina de Agustina tiene en la puerta un teclado donde hay que ingresar una clave para poder entrar. Pensando en esto (y otras cosas donde hay que ingresar claves numéricas, como los cajeros automáticos) se me ocurrió el siguiente problema:

Hay que elegir un número de 6 dígitos (en base 10, con posibles 0s
adelante) como clave para ingresar en un pinpad para ingresar a una "habitación segura".
Pero un atacante tiene la posibilidad de leer huellas digitales y por lo tanto sabe que teclas apretaste pero no en que orden ni con que repetición (o sea, no puede distinguir las claves "111112" y "122222").

¿Cómo se debe elegir la clave de tal manera que el atacante tenga la mayor dificultad posible para adivinarla?


Este problema lo postié en los news internos del laburo y Charles, un compañero de laburo, se mandó una explicación buenísima en dos mensajes. Abajo pongo textuales los mails:

Primer mail:
Con 6 digitos hay 6! = 720 posibilidades.

Con 5 digitos, una forma de contar es así: supongamos que los digitos son 1,2,3,4,5 y que el 5 está repetido dos veces, lo contamos como 1,2,3,4,5a,5b y despues dividimos por las permutaciones de 5a y 5b. Eso da 6! / 2!, y como hay 5 posibilidades para el digito repetido el
resultado es:
6! / 2! * 5 = 1800 posibilidades.

Con 4 digitos, puede haber un digito repetido tres veces, por ejemplo 1,2,3,4a,4b,4c
Posibilidades 6! / 3! * 4 = 480
Puede haber dos digitos repetidos dos veces cada uno, por ejemplo 1,2,3a,3b,4a,4b
Posibilidades 6! / (2! * 2!) * Combinatorio(4,2) = 1080 El Combinatorio(4,2) es la cantidad de formas de elegir 2 elementos entre 4, es 4! / (2!*2!) = 6
En total: 1560 posibilidades con 4 digitos

Con 3 digitos, las estructuras son 1,2,3a,3b,3c,3d da 6! / 4! * 3 = 90
1,2a,2b,3a,3b,3c da 6! / (3! * 2!) * (3*2) = 360 1a,1b,2a,2b,3a,3b da 6! / (2! * 2! * 2!) = 90
Total: 540 posibilidades con 3 digitos

Con 2 digitos, las estructuras son 1,2a,2b,2c,2d,2e da 6! / 5! * 2 = 12
1a,1b,2a,2b,2c,2d da 6! / (4! * 2!) * 2 = 30 1a,1b,1c,2a,2b,2c da 6! / (3! * 3!) = 20
Total: 62 posibilidades con 2 digitos

Con 1 digito, hay 6! / 6! = 1 posibilidad (claro ;-)

Conclusión: hay que usar 5 digitos!


Segundo mail:
Me quedé pensando en tratar de sacar una relación de recurrencia...
Llamemos "número de Aure" A(k,n) a la cantidad de claves de n digitos que usen exactamente k digitos distintos. Por ejemplo 1,2,2,3,3 es una clave de 5 digitos que usa 3 digitos distintos.

Yo lo pienso como cantidad de claves con k digitos distintos en n lugares.

Los casos faciles:
A(1,n) = 1 para todo n
A(k,n) = 0 si k > n

Ahora la recurrencia: si tengo una clave con n-1 lugares, hay dos opciones: ya se usaban los k digitos en los n-1 lugares, o solo se usaban k-1 digitos distintos y agregué el k-ésimo digito en el ultimo lugar.

Si ya se usaban k digitos en n-1 lugares, tengo k posibilidades para el n-esimo lugar (repetir uno de los k digitos).

Si se usaban exactamente k-1 digitos en n-1 lugares, entonces estoy agregando un digito nuevo en el n-ésimo lugar. Tengo k opciones para el digito nuevo.

Luego A(k,n) = k * A(k,n-1) + k * A(k-1,n-1)

A(k,n) = k * ( A(k,n-1) + A(k-1,n-1) )

Es como un triangulo de Pascal con un multiplicador k.

Las primeras filas dan:

k=1 k=2 k=3 k=4 k=5 k=6
n=1 1 0
n=2 1 2 0
n=3 1 6 6 0
n=4 1 14 36 24 0
n=5 1 30 150 240 120 0
n=6 1 62 540 1560 1800 720 0

Sorprendentemente, volvió a dar los mismos números ;-)

La problema de Aure se puede reformular como "qué k maximiza A(k,6)?"


En fin, el problema parece que dio para mucho :D, y tengo mis propios números con una serie que tiene un sentido y una "aplicación".

Happy hacking,
Aureliano.