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.

2008-11-09

Mirando android

Hoy estuve mirando un toque como hacer una aplicación en Android. Después de hacer el HelloWorld correspondiente, seguir parte del tutorial sobre como hacer una aplicación que sirva para guardar notas y leer bastante de la documentación, hice correr el Lunar Lander. El Lunar Lander es un port del archi-conocido juego al android.
Pensé que iba a salir de toque, pero no :(. Así que puse manos a la obra, toque las 2 tonteras que tenía mal y lo hice andar. Para que no tengan que hacer lo mismo que yo, les dejo mi proyecto de eclipse armado. Es igual al de los ejemplos de Google salvo porque como package uso aure en vez de com.android.examples.
Acá está el tar.gz.
Happy hacking,
Aureliano.

2008-11-04

Proyecto Euler: Problemas 19 a 21

Sigo avanzando con los ejercicios del proyecto Euler. Les cuento los siguientes 3 ejercicios.
EL ejercicio 19 consiste en contar la cantidad de domingos del siglo 20. Primero pensé en hacer un montón de aritmética modular para resolver esto, pero después se me ocurrió una idea mejor. Así que usé la biblioteca de fechas de ruby, iteré por todos los días de enero del siglo 20 y sumé todos los domingos. Acá abajo pongo el código:


require 'date'

sundays = 0
(1901..2000).each do
|year|
Date.civil(year,1,1).upto(Date.civil(year,1,31)) do
|d|
sundays += 1 if d.wday == 0 # is sunday
end
end

puts "# of sundays in the 20th century: #{sundays}"

El resultado de la corrida (casi instantáneo) es:

$ ruby euler19.rb
# of sundays in the 20th century: 443

El ejercicio 20 consiste en encontrar la suma de los dígitos de 100!. Usando las funciones para obtener cada dígito de un número del ejercicio 16, se hace bastante fácil. Este es el código:

class Integer
def digit(pos)
(self / (10 ** pos)) % 10
end
def digit_count
dc = 0
while self - (10 ** dc) > 0
dc += 1
end
dc += 1 if self % (10 ** dc) == 0
dc
end
end

fact100 = (1..100).inject { |prod,n| prod * n }
puts "Digits: #{fact100}"
puts "Sum: #{(0...(fact100.digit_count)).inject {|s,n| s + fact100.digit(n)}}"

Y el resultado de la ejecución (también instantánea) es:

$ ruby euler20.rb
Digits: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Sum: 648

El ejercicio 21 es el más complicado de los 3. Consiste en sumar todos los números naturales "amigables" menores a 10000. Un par de números (a,b) es amigable si la suma de los divisores de a (excluyendo a) es b y la suma de los divisores de b (excluyendo b) es a. Un número es amigable si pertenece a un par amigable. Lo que se me ocurrió fue usar el MemoFactorizator (factorizador de números que recuerda factorizaciones previas) del ejercicio 12 para calcular las factorizaciones de todos los números menores a 10000. Usando esto, calculé analíticamente las sumas de los divisores propios (hay una fórmula re-linda que sale de la factorización, pero como no puedo escribir LaTeX facilmente acá, mejor mirenla en el código). Y habiendo calculado todas las sumas de los divisores, buscar en orden n todos los números amigables. Acá está el código:

class OddPrimes
def initialize
@current = 1
@primes = []
end
attr_reader :current
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end

def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

class Primes < OddPrimes
def initialize
super
@first = true
end
def next
if @first
@first = false
2
else
super
end
end
def current
odd_super = super
odd_super == 1 ? 2 : odd_super
end
end

class MemoFactorizator
attr_reader :factored
def initialize
@factored = {1 => {} }
end
def factorize(n, pg = Primes.new)
return @factored[n] if @factored.include?( n )
p = pg.current
while n % p != 0
p = p.next
end
factorization = factorize( n / p, pg ).dup
factorization[p] = factorization.include?(p) ? factorization[p] + 1 : 1
@factored[n] = factorization
factorization
end
end

def divisor_sum(n, factorization)
acum = 1
factorization.each_pair do
|p,pow|
acum *= (0..pow).inject(0) { |s,i| s + p ** i }
end
acum - n
end

MAX = 10000

mf = MemoFactorizator.new
(2...MAX).each do
|n|
mf.factorize(n)
end

sums = {}
(2...MAX).each do
|n|
sums[n] = divisor_sum(n, mf.factored[n])
end

amicable = []

(2...MAX).each do
|n|
amicable << n if n == sums[sums[n]] and n != sums[n]
end

puts "Amicable numbers: #{amicable.inspect}"
puts "Sum: #{amicable.inject {|s,n| s+n}}"

La ejecución tardó un poquito (unos 4 segundos) y dio este resultado:

$ time ruby euler21.rb
Amicable numbers: [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
Sum: 31626

real 0m4.681s
user 0m4.560s
sys 0m0.108s

Happy hacking,
Aureliano

2008-11-01

Proyecto Euler: Problemas 16 a 18

Update: Reporto la suma en el ejercicio 18.

Sigo con mi maratón euleriana. Ahora resolví los problemas 16 a 18.
El problema 16 consiste en encontrar la suma de los dígitos de 2^1000. Para eso desenpolvé la lógica para obtener la cantidad de dígitos de un número y qué dígito es que había hecho para el problema 4 (pequeño quiz: ¿qué bug le arreglé?) calculé 2^1000 y sumé los dígitos. Este es el código:


class Integer
def digit(pos)
(self / (10 ** pos)) % 10
end
def digit_count
dc = 0
while self - (10 ** dc) > 0
dc += 1
end
dc += 1 if self % (10 ** dc) == 0
dc
end
end

n = 2 ** 1000
digits_sum = (0..(n.digit_count)).inject(0) { |sum, pos| sum += n.digit(pos) }
puts digits_sum

Y este el resultado (que sale instantáneamente):

$ ruby euler16.rb
1366

El problema 17 consiste en calcular cuantas letras (con repeticiones) hay en los números del 1 al mil en inglés. Por ejemplo "one two three" tiene 11 letras. Para eso hice una rutina que genera las palabras asociadas a cada número entre 1 y 1000, eso generó un string. Al string le saqué los espacios y conté la cantidad de caracteres. Mientras lo hacía me acordé de cuando estuve probando unos de los ejercicios que usan en ITA para contratar gente, pero lo escribí todo de 0. Acá va el código:

class Integer
UNITS = ["","one","two","three","four","five","six","seven","eight","nine"]
TEENS = ["ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"]
TENS = ["","","twenty","thirty","fourty","fifty","sixty","seventy","eighty","ninety"]
def to_words
raise Exception.new("Don't know how to say in words the number #{self}") unless (1..1000).include? self
return "one thowsand" if self == 1000
words = []
if self >= 100 then
words << UNITS[self / 100]
words << "hundred"
end
words << "and" if (self % 100) != 0
case (self % 100) / 10
when 1
words << TEENS[self%10]
else
words << TENS[(self % 100) / 10]
words << UNITS[self % 10]
end
return words.delete_if{|w| w == ""}.join(" ")
end
end

char_count = (1..1000).inject(0) { |sum,n| sum + n.to_words.gsub(" ","").length }
puts char_count

Y la corrida (también instantánea):

$ ruby euler17.rb
21521

Por último hice el ejercicio 18, que es el más interesante de los 3. El mismo consiste en navegar por un triángulo (que pongo más abajo), encontrando el camino desde arriba de todo a algún numerito de abajo de tal manera que la suma de los nodos del camino sea lo mayor posible.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23


Para resolver este problema, calculé las sumas de los mejores caminos posibles para todos los subtriangulos y después, usando eso, elegí en forma greedy el mejor camino. Acá va el código:

data_text = <<DATA_TEXT
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
DATA_TEXT

data = data_text.split("\n").map{ |row_text| row_text.split(" ").map{ |cell_text| cell_text.to_i(10) } }
sums = Array.new(data.length)
sums[-1] = data[-1].dup
(2..(data.length)).each do
|row|
sum = []
prev_sum = sums[-row+1]
data[-row].each_with_index do
|v,i|
sum[i] = v + [prev_sum[i],prev_sum[i+1]].max
end
sums[-row] = sum
end

pos = 0
path = []

(1..(data.length - 1)).each do
|row|
if sums[row][pos] > sums[row][pos+1] then
path << :left
else
path << :right
pos += 1
end
end

puts path.inspect
puts "Sum: #{sums[0][0]}"

Y este es el resultado de la ejecución (también instantáneo, ya que se hacen tantas sumas como subtriángulos no triviales (que son menos que la cantidad de números en el triángulo) y tantas elecciones como la altura del triángulo. Acá les muestro el resultado:

$ ruby euler18.rb
[:right, :right, :left, :left, :right, :left, :left, :right, :right, :right, :right, :right, :left, :right]
Sum: 1074

Happy hacking,
Aureliano.

2008-10-29

Proyecto Euler: Problemas 13 a 15

Los problemas 13 a 15 resultaron más faciles que el 12. El 13 consiste en saber los primeros 10 dígitos de una suma de 100 números re-grandes. Como ruby soporta números arbitrariamente grandes, una vez que obtuve los números lo resolví en un one-liner:


data_text = <<DATA_TEXT
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
DATA_TEXT

puts (data_text.split("\n").map { |n| n.to_i(10) }.inject(0) { |sum,n| sum + n }).to_s[0..9]

El resultado fue (solo por curiosidad):

$ ruby euler13.rb
5537376230

Y la corrida fue casi instantánea.
El problema 14 consiste en buscar el número menor a 1000000 que genera la secuencia de Collatz más grande. La secuencia de Collatz se calcula así:
  • Si n es 1, terminó
  • Si n es par, es n:collatz(n/2)
  • Si n es impar, es n:collatz(n*3 + 1)

Este problema se resuelve con un poco de memoization:

class PathLengthMemoizator
def initialize
@lengths = {1 => 0}
@max_n = 1
end
attr_reader :max_n

def max_length
@lengths[max_n]
end

def calculate_length(n)
return @lengths[n] if @lengths.include?(n)
@lengths[n] = calculate_length( n % 2 == 0 ? n/2 : 3*n + 1 ) + 1
@max_n = n if @lengths[n] > @lengths[@max_n]
@lengths[n]
end
end

plm = PathLengthMemoizator.new
(1...1000000).each do
|n|
plm.calculate_length(n)
end
puts "Longest path number: #{plm.max_n}"
puts "Length: #{plm.max_length}"

Y cuando lo corrí, dio este resultado:

$ time ruby euler14.rb
Longest path number: 837799
Length: 524

real 0m15.058s
user 0m13.609s
sys 0m1.284s

El problema 15 es el más interesante. En un cuadriculado de tamaño 20 * 20, yendo por las rayitas para abajo y a la derecha, ¿cuántas formas hay de ir desde la posición (0,0) hasta la (20,20)? En un principio, parecía un quilombo. Pero, calculando cuantos caminos hay desde (0,0) hasta (X,Y) me di cuenta que en las diagonales se armaba el Triángulo de pascal. Entonces, mirando fijo, me salió la fórmula general para calcular cuantos caminos hay hasta (X,Y) desde (0,0). Es (X*Y)! / (X! * Y!).
Aplicando la fórmula a la coordenada (20,20) queda 40! / (20! * 20!), que corriendo en el irb queda así:

$ irb
irb(main):001:0> class Integer
irb(main):002:1> def fact
irb(main):003:2> (1..self).inject(1) { |f,n| f*n }
irb(main):004:2> end
irb(main):005:1> end
=> nil
irb(main):006:0> 40.fact / (20.fact * 20.fact)
=> 137846528820

Habiéndo resuelto el problema en forma elegantísima, me voy a dormir antes que encuentre otro.
Happy hacking,
Aureliano.

2008-10-28

Proyecto Euler: Problema 12

Sigo enfermo con el proyecto Euler. Y ya hice el problema 12. El mismo consiste en encontrar el primer número triangular con más de 500 divisores. Un número triangular es de la forma 1 + 2 + 3 + ... + n. Y, se puede calcular rápidamente como n*(n+1)/2.
Mi primer intento de resolución (que anduvo pero fue lento) consistió en usar el generador de números primos del ejercicio 3 para calcular la cantidad de divisores del número, calculándolo directamente. Acá va el código:


class Integer
def triangle
(self * (self + 1)) / 2
end
def divisor_count
n = self
pg = Primes.new
count = 1
while n != 1
p = pg.next
pow = 0
while n % p == 0
pow += 1
n /= p
end
count *= (pow + 1)
end
count
end
end

class OddPrimes
def initialize
@current = 1
@primes = []
end
attr_reader :current
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end

def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

class Primes < OddPrimes
def initialize
super
@first = true
end
def next
if @first
@first = false
2
else
super
end
end
def current
odd_super = super
odd_super == 1 ? 2 : odd_super
end
end

n = 1
while n.triangle.divisor_count <= 500
n += 1
end

puts "Triangle #{n} (#{n.triangle}) is the first with over 500 divisors"

Anduvo, pero la corrida tardó como 4 minutos. Este es el resultado:

$ time ruby euler12.rb
Triangle 12375 (76576500) is the first with over 500 divisors

real 4m17.556s
user 3m57.519s
sys 0m16.117s

Así que me puse a pensar como hacer para que ande más rápido. Se me ocurrieron varias cosas:
  • Puedo calcular la factorización de n*(n+1)/2 sabiendo la factorización de n y n+1
  • Puedo calcular la factorización de cada número una sola vez (guardando factorizaciones viejas)
  • La factorización la puedo escribir recursivamente para usar las factorizaciones que ya calculé

Usando todo esto, hice una nueva implementación:

class OddPrimes
def initialize
@current = 1
@primes = []
end
attr_reader :current
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end

def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

class Primes < OddPrimes
def initialize
super
@first = true
end
def next
if @first
@first = false
2
else
super
end
end
def current
odd_super = super
odd_super == 1 ? 2 : odd_super
end
end

class MemoFactorizator
def initialize
@factored = {1 => {} }
end
def factorize(n, pg = Primes.new)
return @factored[n] if @factored.include?( n )
p = pg.current
while n % p != 0
p = p.next
end
factorization = factorize( n / p, pg ).dup
factorization[p] = factorization.include?(p) ? factorization[p] + 1 : 1
@factored[n] = factorization
factorization
end
end

n = 1
mf = MemoFactorizator.new
while true
fact_n = mf.factorize(n)
fact_nn = mf.factorize(n+1)
triangle_factorization = fact_n.merge(fact_nn) { |k,old,new| old + new }
triangle_factorization[2] -= 1

divisor_count = triangle_factorization.values.inject(1) { |c,pow| c*(pow+1) }
break if divisor_count > 500
n += 1
end

puts "First triangle: #{n} (#{n*(n+1)/2})"
puts "Factorization: #{triangle_factorization.inspect}"
puts "Divisor count: #{divisor_count}"

La nueva implementación tardó 6 segundos en correr.

$ time ruby euler12.rb
First triangle: 12375 (76576500)
Factorization: {5=>3, 11=>1, 17=>1, 7=>1, 13=>1, 2=>2, 3=>2}
Divisor count: 576

real 0m6.690s
user 0m6.568s
sys 0m0.100s

Ahora estoy contento porque dio el mismo resultado que la vez anterior pero mucho más rápido y con código más lindo.

Happy hacking,
Aureliano.

Cumplí 0x20


El 18 cumplí años de nuevo. Parece que es cada vez más rápido.

Un poquito más del proyecto Euler

Sigo enfermo resolviendo ejercicios del proyecto euler. Hoy resolví el ejercicio 11. El mismo consiste en encontrar en una matriz de 20x20 los cuatro números consecutivos en una misma línea (que puede ser horizontal, vertical o diagonal en cualquiera de sus 2 variantes) tal que su multiplicación sea lo más grande posible.
He aquí el código fuente en ruby:


require 'matrix'

RAW_DATA = <<RAW_DATA
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
RAW_DATA
data = Matrix[*RAW_DATA.split("\n").map { |row| row.split(" ").map { |n| n.to_i(10) } }]

DIRECTIONS = [[1,0],[0,1],[1,1],[1,-1]]
best_product = -1
best_row = -1
best_col = -1
best_dir = [0,0]

DIRECTIONS.each do
|dir|
(0...20).each do
|row|
(0...20).each do
|col|
product = (0...4).inject(1) do
|prod, pos|
target_row = row + pos * dir[0]
target_col = col + pos * dir[1]
(0...20).include?(target_row) && (0...20).include?(target_col) ? prod * data[target_row, target_col] : 0
end
if product > best_product then
best_product = product
best_row = row
best_col = col
best_dir = dir
end
end
end
end

puts "Product: #{best_product}"
puts "Row: #{best_row}"
puts "Col: #{best_col}"
puts "Dir: #{best_dir.inspect}"

(0...4).each do
|pos|
target_row = best_row + pos * best_dir[0]
target_col = best_col + pos * best_dir[1]
puts "Position: #{target_row}, #{target_col}"
puts "Value: #{data[target_row, target_col]}"
end

Y para que vean cuanto dio, esta es la salida de la corrida

Product: 70600674
Row: 12
Col: 6
Dir: [1, -1]
Position: 12, 6
Value: 89
Position: 13, 5
Value: 94
Position: 14, 4
Value: 97
Position: 15, 3
Value: 87

Me voy a dormir.
Happy hacking,
Aureliano.

2008-10-24

Algunas verdades y mentiras infundadas del desarrollo de software

  • Java es el nuevo Cobol
  • Eclipse es el nuevo emacs
  • Java es lento
  • Ruby es lento
  • C es rápido
  • C++ es rápido
  • PHP es una bosta
  • Las 3 virtudes de un gran programador son la pereza, la impaciencia y la soberbia
  • Haciendo test-first y refactoring se puede mantener la calidad del código
  • Los sistemas en producción tienen código fuente feo
  • Haciendo test-first y refactoring no se hacen sistemas que queden en producción
  • Los programadores tienen pocas habilidades interpersonales
  • Los programadores deben hablar con los clientes para hacer los desarrollos
  • Barato, rápido, bueno: elija 2
  • Programando en Rails un programador es 10 veces más productivo que programando en J2EE
  • Lisp es el mejor lenguaje de programación
  • Smalltalk es el mejor lenguaje de programación
  • A python hay que agregarle closures y sería un lenguaje espectacular
  • Los verdaderos programadores programan en Fortran
  • Los verdaderos programadores programan en C++
  • Los verdaderos programadores programan en Assembler
  • Los verdaderos programadores programan en código máquina
  • Los verdaderos programadores silvan en el teléfono para transmitir datos a un modem, hacer un buffer overflow y reprogramar el server
Happy hacking,
Aureliiano.

2008-10-21

Proyecto Euler - Problemas 5 a 10

Sigo a full con el Proyecto Euler. Y hoy hice 6 problemas. Les cuento como los solucioné:
El problema 5 es bastante fácil. Esencialmente se trata de encontrar el mínimo común múltiplo de los números 1..20. Lo más molesto es que ni el divisor común mayor ni el mínimo común múltiplo están en mi versión de ruby (ruby 1.8.6 patchlevel 111, ubuntu hardy), así que lo implementé:


class Integer
def gcd(other)
values = [self > 0 ? self : -self, other > 0 ? other : -other]
a = values.min
b = values.max
while (a != 0)
a, b = b % a, a
end
b
end
def lcm(other)
self * other / self.gcd(other)
end
end

puts (2..20).inject(1) {|ac, n| ac.lcm(n)}

Sólo por curiosidad, el número me dio 232792560.
El problema 6 es calcular la diferencia entre la suma de los cuadrados y el cuadrado de la suma de una secuencia 1..n (con n=100). Tampoco fue muy difícil.

class Integer
def sum_square
(1..self).inject(0) { |acum,n| acum + n * n }
end
def square_sum
((self * (self+1)) / 2) ** 2
end
end

puts 100.square_sum - 100.sum_square

También por curiosidad, el resultado es 25164150.
El problema 7 es encontrar el primo número 10001. Para eso usé la criba que definí en el post anterior e iteré hasta el primo nro 10001.Acá va el código:

class OddPrimes
def initialize
@current = 1
@primes = []
end
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end
def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

op = OddPrimes.new
p = 2
(2..10001).each {
p = op.next
}

puts p

El primo que dio es el número 104743.
El problema 8 es medio rebuscado. Lo que me resultó más difícil es entender el enunciado. Te dan un número gigante y tenés que buscar cuáles son los 5 dígitos consecutivos que multiplicados dan el número más grande. Como en el problema 4 había implementado como obtener un dígito arbitrario y la cantidad de dígitos de un número, usé eso y resolví el asunto.

class Integer
def digit(pos)
(self / (10 ** pos)) % 10
end
def digit_count
1 if self == 0
dc = 0
while self - (10 ** dc) > 0
dc += 1
end
dc
end
end

n = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

pos = -1
prod = -1
(0..995).each do
|p|
candidate = n.digit(p) * n.digit(p+1) * n.digit(p+2) * n.digit(p+3) * n.digit(p+4)
if candidate > prod
pos = p
prod = candidate
end
end
puts "Digits: #{n.digit(pos)}, #{n.digit(pos+1)}, #{n.digit(pos+2)}, #{n.digit(pos+3)}, #{n.digit(pos+4)}"
puts "Position: #{pos}"
puts "Product: #{prod}"

El resultado que dio es:

Digits: 9, 7, 8, 9, 9
Position: 631
Product: 40824

El problema 9 consiste en buscar número a,b,c tal que son enteros a+b+c=1000 y a^2+b^2=c^2 (teorema de pitágoras para triangulos rectos). Para hacer eso, busqué una tripleta (a,b,c) tal que la suma divida a 1000 y después multipliqué cada número. La verdad es que este problema me costó un ratito. Acá va el código.

#Find a triplet that fits the pitagoras formula and its components divide 1000
def primogenial_triplet
(3..100).each do
|c|
(2...c).each do
|b|
(1...b).each do
|a|
return [a,b,c] if a ** 2 + b ** 2 == c ** 2 and 1000 % (a+b+c) == 0
end
end
end
end

tr = primogenial_triplet
factor = 1000 / (tr[0] + tr[1] + tr[2])
puts tr.map {|x| x * factor}

Los a,b y c que encontré son: 200, 375 y 425 respectivamente.
El problema 10 es el más interesante hasta ahora. El mismo consiste en sumar los números primos menores a 2000000. Primero usé el generador de primos que tenía, y lo implementé, pero tardó más de un minuto. El código es:

class OddPrimes
def initialize
@current = 1
@primes = []
end
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end
def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

op = OddPrimes.new
sum = 2
while ( (p = op.next) < 2000000 )
sum += p
end

puts sum

Pero me quedé enojado porque tardaba mucho, así que googlié un toque y encontré este post que mostraba otra forma de generar números primos. Y lo implementé. La idea es ir marcando todos los múltiplos (menores a un número dado) de los números primos que voy encontrando para encontrar los primos sin hacer divisiones. Y anduvo más rápido. Igualmente, hay que notar que gasta bastante más memoria que la versión anterior. Así que tiene un trade-off distinto entre memoria y tiempo de procesamiento. El código está acá:

MAX = 2000000

class OddPrimes
def initialize(max)
@max = max
@prime_matrix = [false,true] * ((max / 2) + 1)
@prime_matrix[1] = false
@current = 1
end
def next
while not prime?(@current += 2)
throw :max_reached if @current >= @max
end
mark
@current
end

def mark
i = @current
step = @current * 2
while (i<@max)
@prime_matrix[i] = false
i += step
end
end

def prime?(n)
@prime_matrix[n]
end
end

op = OddPrimes.new(MAX)
sum = 2
catch :max_reached do
while ( (p = op.next) < MAX )
sum += p
end
end

puts sum

Esta solución corrió en 6 segundos:

$ time ruby euler10.rb
142913828922

real 0m6.179s
user 0m5.780s
sys 0m0.356s


Voy a tratar de seguir resolviendo los problemas del proyecto Euler, así que sigan sintonizados.
Happy hacking,
Aureliano.

2008-10-20

Proyecto Euler - Primeros 4 problemas resueltos en Ruby

Mirando el blog de xkcd encontré un site donde postean un montón de problemas "matematicosos" para ser resueltos mediante programas de computadora que se llama proyecto Euler. Así que me copé, me puse a resolverlos e hice los primeros 4.
El primero es calcular la suma de los múltiplos de 3 o 5 menores a 1000, que lo saqué con un one-liner en ruby:


irb(main):006:0> (1...1000).select {|x| x % 3 == 0 || x % 5 == 0}.inject(0) {|sum,num| sum + num }
=> 233168

El segundo es calcular la suma de los números de fibonacci pares menores a 4000000. Este también lo hice en el irb, pero quizás debería haberlo escrito en un archivo. Lo que escribí en el irb es:

irb(main):007:0> class Fib
irb(main):008:1> def initialize()
irb(main):009:2> @a = 0
irb(main):010:2> @b = 1
irb(main):011:2> end
irb(main):012:1> def next()
irb(main):013:2> @a, @b = @b, @a+@b
irb(main):014:2> @b
irb(main):015:2> end
irb(main):016:1> end
irb(main):027:0> sum = 0
=> 0
irb(main):028:0> f = Fib.new
=> #
irb(main):029:0> while (n = f.next) <= 4000000 irb(main):030:1> sum += n if n% 2 == 0
irb(main):031:1> end
=> nil
irb(main):032:0> sum
=> 4613732

O sea, la suma me dio 4613732, espero no haberme equivocado.
El tercer problema es encontrar el factor primo más grande de un número gigante (n=600851475143) . En este ya me puse a escribirlo en un archivo, porque me llevó más de 2 minutos. Lo que hice fue programar una criba para generar los números primos e ir dividiendo el n por los primos hasta que quede 1. Entonces el último primo por el que dividí es el factor primo más grande. El código en Ruby es así:

class OddPrimes
def initialize
@current = 1
@primes = []
end
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end
def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

n = 600851475143
max_p = 1
op = OddPrimes.new
while n>1
max_p = op.next
while n % max_p == 0
n /= max_p
end
end

puts max_p

Según mi código, el factor primo más grande es el 6857.
Y, por último porque me tengo que ir a dormir, resolví el cuarto problema. El mismo consiste en calcular el número "capicúa" más grande que resulta de multiplicar 2 números de hasta 3 dígitos. El código es medio bestia, y fue la primera vez que el resultado no se sintió "instantáneo" (tardó como 2 segundos). Pero calculó el resultado. La idea del mismo es trivial. Probar todas las posibles multiplicaciones (que son como 500000) y fijarse si el resultado es capicúa y más grande que el número más grande encontrado. El código en ruby es:

class Numeric
def digit(pos)
(self / (10 ** pos)) % 10
end
def digit_count
1 if self == 0
dc = 0
while self - (10 ** dc) > 0
dc += 1
end
dc
end
def palindromic
digit_count = self.digit_count
(0...(digit_count / 2)).each do
|pos|
return false if self.digit(pos) != self.digit(digit_count - pos - 1)
end
return true
end
end

lp = 0
f1, f2 = 0,0
(1..999).each { |x| (1..x).each { |y|
candidate = x * y
if candidate > lp and candidate.palindromic
lp = candidate
f1 = x
f2 = y
end
}}
puts "Largest Palindromic: #{lp}"
puts "Factors: #{f1}, #{f2}"

El resultado que dio es:

Largest Palindromic: 906609
Factors: 993, 913

Estoy seguro que se puede optimizar "bocha" este código.

Bueno, me voy a dormir.
Espero escribir próximamente más problemas resueltos del proyecto Euler.
Happy hacking,
Aureliano.

2008-10-11

Jugando con un proxy HTTP

El proxy transparente de Telefónica está andando mal y trae versiones viejas de un montón de páginas. Así que estuve pensando la forma de forzarlo a que traiga la última versión. Lo hablé con algunos compañeros de laburo, y lo que me sugirieron es que instale un proxy que agregue headers que fuercen el no-cacheo de las páginas. En particular, sugirieron que instalara privoxy y lo configurara con los headers que quiero agregar.
Pero, ¿para que voy a hacer algo rápida y fácilmente si me puedo meter en un quilombito? El mismísimo whytheluckystiff hizo mousehole, un proxy implementado en ruby puro. Pero mousehole está pensado para transformar las páginas a medida que van bajando, no para cambiar los headers a la ida. Así que tuve que toquetear un poquito.
Por lo que pude ver, mousehole tiene 3 capas. Una primera capa es el handler de mongrel que atiende los pedidos de http, la capa del medio es una capa que maneja los plug-ins del proxy (a los que llama apps) y una tercera capa son las apps propiamente dichas. Para agregar la funcionalidad de cambiar el request tuve que tocar estas 3 capas.
En el handler, agregué un lugar para interceptar la página antes de pedir al host la página. Este es el diff del svn:


Index: lib/mouseHole/proxyhandler.rb
===================================================================
--- lib/mouseHole/proxyhandler.rb (revision 129)
+++ lib/mouseHole/proxyhandler.rb (working copy)
@@ -46,6 +46,8 @@
choose_header(reqh, header)
set_via(header)

+ uri, header = @central.change_request(uri, header)
+
http = Net::HTTP.new(env['server-name'], env['server-port'], @central.proxy_host, @central.proxy_port)
http.open_timeout = 10
http.read_timeout = 20

En la capa que maneja los plugins (que en el código se llama central) hice que cuando llegue un pedido, intente reescribir los headers en cada app. Este es el diff del svn:

Index: lib/mouseHole/central.rb
===================================================================
--- lib/mouseHole/central.rb (revision 129)
+++ lib/mouseHole/central.rb (working copy)
@@ -95,6 +95,13 @@
end
end

+ def change_request(uri, header)
+ @apps.values.each do |app|
+ uri, header = app.change_request(uri, header)
+ end
+ [uri, header]
+ end
+
def rewrite(page, resin)
apps = find_rewrites(page)
return false if apps.empty?

Y por último, en la clase base de las apps hice que por default deje los headers y el URI original, así es todo retrocompatible (o casi). Acá está el diff del svn:

Index: lib/mouseHole/app.rb
===================================================================
--- lib/mouseHole/app.rb (revision 129)
+++ lib/mouseHole/app.rb (working copy)
@@ -58,6 +58,10 @@
end
end

+ def change_request(uri, header)
+ [uri, header]
+ end
+
def do_rewrite(page)
@document = page.document
begin

Con todo esto andando, pude hacer mi cometido, que es hacer un proxy que le agregue el header "Cache-Control: no-cache" a los requests, para que Speedy no me de versiones viejas. El código de la app que hace esto quedó resimple:

class NoCache < MouseHole::App
title "No Cache"
namespace "aure"
description %{
Forces all the request to be non cached.
Sets the Cache-Control header to no-cache.
}
version "0.1"

def change_request(uri, header)
header << ['Cache-Control', 'no-cache']
[uri, header]
end
end


Gracias Speedy y Telefónica por la inspiración y happy hacking,
Aureliano.

PD: si los headers no sirven, voy a cambiar el URI agregando parámetros aleatorios y listo, así que no me provoquen.

2008-10-05

Conferencias al cuadrado

Esta semana estuve a full. En Buenos Aires hubo 2 conferencias de seguridad informática y tuve la suerte de poder ir a las 2.

El martes y miércoles estuve en BA-Con. Ahí conocí un montón de gente interesante y tuve la suerte de que las charlas también fueron re-interesantes.
Algunas charlas que me llamaron la atención y quería comentarles son:

  • En la charla "WPA/WPA2: how long is it gonna make it" Cédric Blancher y Simon Maréchal contaron una forma interesante de generar passwords para brutforcear. La idea es que armás una cadena de markov donde cada caracter es un estado y la probabilidad de pasar de un estado "a" a un estado "b" es el porcentaje de las veces que viene una "b" después de una "a" de los passwords con los que generaste la cadena.
  • La charla "All the Crap Aircrafts Receive and Send" fue divertida. Hendrik Scholz contó cómo se enteran los aeropuertos de los tiempos de arribo de los aviones (entre otras cosas). Y cómo hizo para reversear los mensajes (incluyendo ir con un receptor de radio en el auto al aeropuerto).
  • En "LeakedOut: the Social Networks You Get Caught In", mi amigo y compañero de trabajo José Orlicki presentó sus avances de su trabajo de doctorado, donde estudia las redes sociales que se arman en los sitios Web 2.0 y sus implicancias en seguridad. A mi me pareció que fue la charla más original de las 2 conferencias.
  • En "Pass-the-hash Toolkit for Windows" mi compañero de trabajo Hernán Ochoa mostró una vez más porqué es un groso en el mundo de la seguridad informática. Esta vez contó de su proyecto "Pass-the-hash" y su implementación en Windows. El proyecto sirve para afanar tokens de autenticación de la memoria de un Windows (!) y conectarse a otros hosts. La verdad, una masa. Si quieren usarlo, pueden bajarselo de acá.
El jueves y viernes tocó Ekoparty. Y también fue re-interesante. Les cuento que charlas me llamaron más la atención:
  • En "Code injection on virtual machines", mi compañero de laburo Nicolás Economou se disfrazó de Neo y mostró como escribir memoria usada por un proceso de VM-Ware desde afuera para modificar el comportamiento de un programa corriendo adentro (!).
  • En "Atancando RSA mediante un nuevo métodos de factorización de enteros", Hugo Scolnik mostró el laburo que están haciendo para tratar de romper RSA. La verdad, pareció re-interesante. Transformó el problema de factorización de un número de la forma p*q en un árbol de decisiones y muchas formas de podar el árbol. Y mostró como, si se pudiera elegir correctamente en ese árbol (cosa que todavía no hacen), la factorización del RSA640 tomaría un par de minutos en una Pentium 3.
  • En "Smartphones (in)security" mis compañeros de laburos Alfredo Ortega y Nicolás Economou (que ya se había sacado el traje de Neo), mostraron cómo explotar un stack overflow en iPhone y Android. Fue una charla interesante y entretenida, donde también explicaron re-bien como funciona la técnica "return to libc" para escribir exploits cuándo la memoria que podemos sobreescribir no tiene derechos de ejecución.
  • Y en "Debian's OpenSSL random number generator Bug" Luciano Bello y Maximiliano Bertacchini contaron los detalles técnicos y las consecuencias de comentar una línea de código para que el valgrind no se queje. Esa línea, hacía que la entropía del generador sea tomada solamente del nro. de proceso (o sea, que si repetís el número de proceso, generás los mismos números aleatorios) y cómo usar esto para hacer ataques.
Al final, después de una semana de conferencias quedé con la cabeza que explota de conocimientos nuevos, conocí un montón de gente interesante y tengo un muchas tarjetas personales (que nunca sé que hacer con ellas).

Happy hacking,
Aureliano.

Blog de Nicolás

Cómo les había contado en un post anterior, voy a ser papá. Y hoy, junto con Agus inauguramos su propio blog. Ahí vamos a ir poniendo todas las fotos, videos y etcéteras mientras sea un proyecto o un bebé.

2008-09-28

Guerra con Telefónica

Hace un tiempo les conté que tuve problemas con Telefónica. Los problemas siguieron, y groso. En los últimos 3 meses estuve más de la mitad del tiempo sin teléfono ni ADSL. El jueves pasado, fui y pedí que me dieran un listado de incidencias impreso, al que se negaron. Pero me mostraron el registro de apertura y resolución de tickets. La verdad es que es una vergüenza. Cerraron un montón de tickets diciendo que había problemas en el consorcio pero a mi no me informaron cuál es el problema del consorcio.
Vivo en un edificio de menos de 10 años, los conductos centrales para cables de teléfono son de 20cmx20cm (o más), y el cableado de dentro del edificio lo pusieron ellos. Aparte nunca dijeron que parte del cableado del consorcio sería la que está rota y cuándo un técnico habló personalmente conmigo me dijo que el consorcio y el departamento no tienen ningún problema. En el medio de todos los tickets cerrados por "problemas en el cableado interno del consorcio" hubo uno que lo cerraron por otro motivo porque ya les daba vergüenza. Se ligó mi teléfono con un teléfono de otro edificio. ¿Cómo me enteré? Disqué 115, corté y aparte de sonar mi teléfono sonó en otro lado y atendieron, así que pude charlar con la persona con la que tenía ligado el teléfono. Así que llamé al 114 y lo avisé. Sino quizás a este ticket también lo hubieran cerrado como "problemas en el cableado interno del consorcio".

Bueno, abajo les dejo un detalle de los tickets, fechas de inicio y fin y sus resoluciones y les pregunto. ¿Saben cómo hacer para que les pongan una multa gigante?

  • Nro. de ticket: 2008027000066336
  • Inicio:28/6
  • Fin:7/7
  • Resolución: Cableado interno consorcio
  • Comentarios: ¿No será que el problema está en otro lado?
  • Nro. de ticket: 2008027000068188
  • Inicio: 3/7
  • Fin: 24/7
  • Resolución: Cableado interno consorcio
  • Comentarios: ¿No será que el problema está en otro lado?
  • Nro. de ticket: 2008027000076656
  • Inicio: 21/7
  • Fin: 1/8
  • Resolución: No permitió vigilancia
  • Comentarios: Vienen en cualquier momento, ¿saben que tenemos cosas que hacer aparte de esperar a que vengan a arreglar el TE? No vinieron en los horarios de citas concertados
  • Nro. de ticket: 2008027000080132
  • Inicio: 29/7
  • Fin: 21/8
  • Resolución: Configuración ADSL
  • Comentarios: Era hora que admitan que hay algún problema en su servicio, la configuración mala del ADSL genera interferencias en la línea (aparte de microcortes)
  • Nro. de ticket: 2008027000083451
  • Inicio: 7/8
  • Fin: 21/8
  • Resolución: Configuración ADSL
  • Comentarios: Pasó más de una semana y seguía con los mismos problemas
  • Nro. de ticket: 2008027000089423
  • Inicio: 25/8
  • Fin: 6/9
  • Resolución: Cambio de bajada
  • Comentarios: Al fin hacen algo, para algo pago el abono de mantenimiento
  • Nro. de ticket: 2008027000094576
  • Inicio: 10/9
  • Fin: 17/9
  • Resolución: Cableado interno consorcio
  • Comentarios: Nadie tocó nada, ¿se rompe y arregla solo?
  • Nro. de ticket: 2008027000098212
  • Inicio: 22/9
  • Fin: 24/9
  • Resolución: Se regenera línea ADSL
  • Comentarios: Parece que sigo con quilombo
¿Saben que tengo que hacer para que los multen? ¡Tuve tickets abiertos el 90% del tiempo de los últimos 3 meses!
Happy hacking,
Aureliano.

2008-09-14

Inauguración quilmeña - El ibérico

Quería contarles que Guillermo, el primo de mi mujer, inauguró "El ibérico", una fiambrería-rotisería en Quilmes. Más especificamente en Brandsen e Hipólito Yrigoyen (sobre Hipólito Yrigoyen). Así que si vuelven a Quilmes después de un día de laburo/joda y no saben que comer, pueden pasar por ahí y comprarse un pollo al spiedo, o un buen jamón, un buen queso y pan, y para el postre, un dulce cordobés casero que está super-re-barato ($7 el kilo, aprovechen antes que se avive). También un buen vino y tienen todo resuelto. Y no se olviden de decir que van de parte mía. Y si son unos vagonetas, también pueden llamar por teléfono al 4253-7006 y hacer su pedido.
Happy hacking,
Aureliano.

2008-09-08

¡Se reproducen!


Sí, quiero presentarles a nuestro primogénito. Esta es una imagen de la última ecografía (de cuando tenía 13 semanas de gestación). Vieron, aunque parezca increíble, ¡los geeks se reproducen!
¿Cuánto tardará en aprender a programar?

2008-09-03

Ingenieros contra la naturaleza

Los ingenieros son grosos y le ponen el pecho a las balas. Y hacen cosas grosísimas. Un ejemplo es esta foto de un dique en Nueva Orleans, que esta vez si aguantaron el paso de un huracán. Groso lo que bancan, la foto es increíble (3 metros de agua con tormenta aguantados por una pared).



Si quieren, pueden ver la nota en clarín.

2008-08-26

Jornadas Regionales de Software Libre

La semana pasada se hicieron en Buenos Aires las Jornadas Regionales de Software Libre. Las Jornadas fueron interesantes y tuve la oportunidad de charlar con un montón de gente y hacer mi presentación. Porque estoy a full con el laburo solo pude ir el jueves, que fue el día de mi charla de Rubygame como ya les había contado antes.
La charla salió medio medio porque tuve quilombos con el proyector :(. Después del ¡tercer proyector! logré que salga algo por la salida de VGA de mi notebook, pero solo booteando de un LiveCD. Por lo tanto, no pude mostrar mis jueguitos andando, pero si pude mostrar los slides que tenía preparados. Igual fue divertido, y espero poder presentar algo la próxima (que si puedo me llevo mi propio proyector y listo). Por último les dejo una foto de mi charla, que sacaron Gutes y Tenuki:


Happy hacking,
Aureliano.

2008-08-15

Torre de Agua


Ayer al mediodía, que todavía estaba en Mar del Plata, fuimos con Agus a visitar la Torre de Agua de Mar del Plata. Antes de ir estuvimos buscando el horario de apertura y cierre de la torre y no lo encontramos por ningún lado. Así que les paso horarios y coordenadas.
¿Cuándo? Días hábiles de 8:00 a 14:45hs.
¿Dónde? Falucho y Mendoza.
Si van, van a ver una vista panorámica de Mar del Plata, mirando desde arriba de la torre. Y abajo hay un museíto que no tiene demasiado interés. Pero la vista está bárbara.
Happy hacking,
Aureliano.

2008-08-12

"Vacaciones"

Esta semana estoy paseando por MDQ. Pero siempre algo de laburo tengo encima. Aparte de estar haciendo un trabajo práctico para mi doctorado, mañana miércoles a las 19hs nos encontramos con algunos de los pibes de Ruby Argentina en Piazza, que queda en Alem y la costa, y haremos un "PizzaConf" (o sea, nos juntamos a hablar de cosas de Ruby y comer pizza).
Todo rubista que quiera apropicuarse por allá será bienvenido. Si quieren traigan su notebook o alguna idea de algo que quieran presentar (hasta 1/2 hora, desde 1/2 segundo), o si quieren no traigan nada y vengan y listo. Si pinta, supongo que haré un "preview" de la presentación sobre RubyGame que voy a hacer en las Jornadas Regionales de Software Libre.
Happy hacking,
Aureliano.

2008-08-05

Cobos votó "no"

Update: Efectivamente un moderador sacó el comentario. Suerte que lo agarré a tiempo. Si quieren saquen sus propias conclusiones sobre porqué alguien quitaría un comentario como este.

A veces, y solo a veces, los foros de La Nación tienen algunas joyas increíbles. En particular, el mensaje #511 de esta nota es divertido. Acá abajo lo pongo textual (antes que lo agarre un moderador y lo saque):

COBOS POMPOSO CON PONCHO. COBOS JOCOSO. COMO TROMPO RODO POR OTROS HOYOS. COMO BOROCOTO, TROCO VOTO. COMO ORTODOXO DOCTOR, VOTO NO. VOTO CON LOS OJOS ROJOS, CON SOLLOZOS, CON SOPOR, MONOLOGO SOLO POR NO. ¿ VOTO SOLO POR LOS POROTOS ? ¿ VOTO POR SPONSOR CON FRONDOSO OBOLO ? PROMOTOR CON BOLSOS CON ORO, DOTO CON VOLVO ? COLOCO MONTOS GROSOS POR BOSTON, OSLO, TORONTO O LONDON ? COMO SOMOS !!! NO LO SOPORTO... BOROCOTO: ZORRO DOLOSO, COBOS: BOCHO HONROSO !!! FOR GOD !!! ¿ SOMOS TODOS GROSSOS ? NO. SOMOS ZONZOS, SOMOS LOCOS, SOMOS BOCHORNOSOS COMO COPPOLO. SOCORRO !!!

Mis charlas en las Jornadas Regionales de Software Libre

Hola,
Estoy muy contento de contarles que voy a participar en un par de charlas de las jornadas.
La primera es una charla introductoria a rubygame. Usando como excusa los jueguitos sobre los que estuve posteando a principio de año por acá, voy a pasar por las cosas básicas de la biblioteca. Esencialmente sprites y manejo de eventos.
La otra es una charla de mi amigo Matías Brutti sobre metaprogramación en Ruby, en la que le voy a dar una mano. Todavía no hablamos de como la vamos a organizar pero supongo que tendrá contenido parecido al del post del tema que hice acá a mediados del año pasado.
Las jornadas son el 20, 21 y 22 de agosto (sí, en 2 semanas). Mis 2 charlas son el 21 de agosto. La de Rubygame es a las 10AM (sí, bastante tempranelli) y la de metaprogramación a las 4PM. Las jornadas se hacen en la Universidad de Belgrano (Zabala 1837, Ciudad Autónoma de Buenos Aires, Argentina). Tienen que anotarse antes para poder ir. Hay más información en la página de las jornadas.
Los espero.
Happy hacking,
Aureliano.

2008-07-22

El día que Stallman apareció en infobae

Cada vez más, el software libre se hace mainstream. Y hoy pasó una vez más. Hoy entré a infobae.com y, sorpresa, sorpresa, al lado de los escándalos de la ex-novia de Ronaldo estaba una nota sobre ¡Richard Stallman! Acá les paso el link. ¡Y encima Stallman está peinado!

Hasta el premio Nobel de la Paz no para.

Happy hacking,
Aureliano.

2008-07-12

Criptografía cuántica - explicación simple.

Ayer a la tarde vino al laburo Andrés Rieznik a dar una charla sobre criptografía cuántica. Andrés es doctor en física, es especialista en fibras ópticas y actualmente está haciendo un post-doctorado en el ITBA (sí, donde yo estoy haciendo el doctorado). Y Andrés también iba a la división de al lado en la secundaria.
Bueno, volviendo al tema de la criptografía cuántica, primero nos explicó en que fenómenos de la física cuántica está basada.

Polarización, fotones y otras cosas que solo los físicos entienden


Como todos sabemos, la luz a veces es una onda. Cuando hace de onda, la onda puede oscilar en cualquier ángulo (por ejemplo: verticalmente, horizontalmente o diagonalmente). Y cuando pasa a través de un polarizador queda oscilando en la dirección que el polarizador la deja. Y si después ponemos otro a 90 grados, no pasa nada. Y más aún, si ponemos el segundo polarizador a 45 grados sale un cuarto de la luz original (se queda la mitad en cada polarizador) ¡polarizada en el ángulo del segundo polarizador!
Pero también, la luz a veces es muchas partículas. Cuándo actúa como partículas, decimos que está compuesta por fotones. Entonces ¿qué pasa cuando pasa un solo fotón por un polarizador?.
Según entendí de lo que dijo Andrés, los fotones tienen un ángulo de oscilación. Y pasan o no por un polarizador en función de ese ángulo. En particular, si el polarizador está perfectamente "alineado" con la oscilación del fotón pasa siempre y si está perfectamente cruzado con el fotón no pasa nunca. ¿Y qué pasa si está a 45 grados? Entonces pasa la mitad de las veces y, cuando pasa, cambia el ángulo de su oscilación al del polarizador por el que pasó.
Bueno, usando todo lo que está arriba, hace ya 24 años a unos cráneos se les ocurrió una idea para que 2 partes (digamos, para mantener las costumbres, Alice y Bob) compartan un "stream" de números al azar. O sea, que los 2 sepan los mismos números, pero que estos números no están definidos de antemano. Para los que sepan cripto, el resultado es muy parecido a Diffie-Hellman pero se llega por caminos muy distintos. A ese tipo de algoritmos se los llama de "intercambio secreto de claves". El primer algoritmo que hicieron se llama BB84 (son unos cráneos pero tienen menos onda para los nombres que un fotón).

El BB84


En el algoritmo BB84, cada número lo manda como un único fotón polarizado en un ángulo de 0, 45, 90 o 135 grados. 0 grados se corresponde a un 0 en base A, 45 grados a un 0 en base B, 90 grados a un 1 en base A y 135 grados a un 1 en base b.

El algoritmo consiste en lo siguiente:
Alice elige una base (entre A y B) y un nro (entre 0 y 1) y manda un fotón polarizado en el ángulo correspondiente. Bob elige una base al azar y detecta (en esa base) el número. Si los 2 eligieron la misma base, los 2 conocen el mismo número, sino hay un 50% de chances de que Bob tenga un número distinto del que tiene Alice. Este procedimiento se repite n veces.
Cuando Alice termina de mandar cada uno de los bits, Alice manda por un canal normal (no cuántico) que bases usó para mandar cada bit. Bob, con esa información, le dice cuáles de los bits leyó en la misma base que Alice transmitió (van a ser aproximadamente la mitad).
Para ver que efectivamente nadie cambió los bits en el camino se eligen algunos de los bits efectivamente transmitidos y se los manda por un canal no cuántico para verificar que la transmisión fue correcta.
Después de esto, los bits efectivamente transmitidos que no se publicaron son los que forman la clave conocida por Alice y Bob.

¿Y Eve?


¿Qué pasa si Eve interfiere un fotón? Bueno esta es LA gracia de todo el asunto. En mecánica cuántica existe una cosa que se llama "principio de incertidumbre" (lo siento, va sin link porque no me gustó el artículo de wikipedia). El principio de incertidumbre dice que es imposible obtener una medida en una partícula sin modificarla en otra aledaña. Por ejemplo, si medís la velocidad de una partícula modificás su posición, haciendo imposible saber la posición original.
Bueno, el número (0 o 1) y la base (A o B) que representa el ángulo de polarización de un fotón es como saber la posición y la velocidad. Si medís el número, como tiene que pasar por un polarizador, cambiás potencialmente la base del fotón (el 50% de los casos). O sea, que si Eve escucha un fotón, el 50% de los casos le cambia la base. De ese 50%, el 50% de los casos Bob va a escuchar el número incorrecto. Por lo tanto, en la verificación que se hace al final del algoritmo van a detectar que el 25% de los bits están mal. Entonces se detecta a Eve y no se usa esa clave para transmitir info segura.

Unas cositas más


El BB84 no es el único algoritmo conocido, hay variaciones, pero todas están basados en que para medir si un fotón pasa o no por un polarizador hay que cambiarle el ángulo de polarización.
Por último, las cosas que estén mal explicadas son culpa mía y las que estén bien culpa de Andres.

Happy hacking,
Aureliano.

2008-07-09

Problemas con el DNS de speedy

Update: Gracias a Manuel por llevar a mi atención esta vulnerabilidad del diseño del DNS. No está confirmado, pero es altamente probable que la inestabilidad de los servers de Speedy tengan que ver con esto. Les sugiero que como medida de seguridad usen los servidores DNSs que están mencionados abajo aunque tengan otro proveedor de internet, al menos por un tiempo. Estos servers aparentemente no son vulnerables.

Desde ayer que el DNS de speedy está inestable. Hoy llamé al soporte técnico y me lo confirmaron. Como no me dieron ningún servidor de DNS alternativo, me conecté a google x ip (estaba haciendoles ping para hacer troubleshooting) y leí algunos caches de páginas. Ahí encontré esta página donde sugieren usar Open DNS.

Así que configuré en mi router los servidores de nombres que dice ahí (son 208.67.222.222 y 208.67.220.220) y ahora puedo navegar nuevamente.

Happy hacking,
Aureliano.

2008-07-02

Cómo hacer que Telefónica arregle tu teléfono

Update: Incluye segundo corte de teléfono.

Según mi experiencia en reparaciones de mi línea telefónica, este es el algoritmo apropiado para lograr reparaciones medianamente rápidas:

  1. Llamar al 114 (te atiende el contestador automático)
  2. Llamar al 112. Nadie atiende.
  3. Llamar al 114 de nuevo. El contestador automático te informa que tu teléfono será reparado "en los plazos establecidos".
  4. Llamar al 112. Nadie atiende
  5. Llamar al 114 de nuevo. Poner otro número de teléfono. Te atiende el operador.
  6. El operador te corta antes de admitir que te está boludeando porque no puede abrir el ticket de la reparación del teléfono.
  7. Llamar al 112. Nadie atiende
  8. Llamar de nuevo al 114, poner de nuevo un número equivocado. Quejarse que te cortaron en la mitad de la queja anterior. Te explican que en realidad no pueden abrir tu ticket (operador buena onda, probablemente empezó a trabajar hoy).
  9. Llamar al 112. Atienden (¡milagro!). Abrís un ticket quejandote de que no hay plazos por la reparación y porque te cortaron cuando llamaste al 114.
  10. ????????????????????????????????
  11. A los 10' de la última llamada arreglan la línea.
  12. ????????????????????????????????
  13. A las 12 horas se vuelve a quedar sin tono.
  14. Habla mi suegra con Telefónica, dicen que vienen mañana antes de las 10 AM. Alegan que hay un problema en mi casa (¡pero pusieron a andar el teléfono 12 horas sin venir!).
  15. Me dejaron plantado. Segundo fin de semana sin teléfono ni internet.
  16. Llaman a mi suegra, que no está, y le dicen que van a venir cuando no haya nadie en el depto.
  17. Llamo a reparaciones de larga distancia de telefónica (al servicio técnico habitual no me puedo comunicar porque no te atienden cuando hay un arreglo en curso, seguro que esto es antirreglamentario). Por suerte toman los datos del teléfono de la oficina (o eso me hace creer la operadora.
  18. ?????????????????????????????????
  19. Llego a casa a la noche y anda todo (vamos a ver con cuanto tiempo).
Conclusión: Con Telefónica todo mal. Igual, llamen al 112 y rompan las bolas. Puntos extra si van o se quejan en Defensa del Consumidor.

Aureliano.

PD para la gente de codear: En cuanto tenga tiempo quiero hacer un post sobre mónadas en Haskell. Tenganme paciencia.

2008-06-27

Busco hogar para Amón

Estoy buscandole un nuevo hogar a Amón, mi gato. Es macho, super-juguetón, tiene 2 años y está castrado. Vivió siempre en depto, así que está acostumbrado a la compañía humana. A quién le interese ser su nuevo "papá" o "mamá" por favor comuníquese x acá o a aurelianocalvo at gmail.com (cambiando at por @).

Acá abajo pongo una foto así se van encariñando.



Muchas gracias,
Aureliano.

2008-06-22

Grandes ideas

Odio cuando se me ocurren ideas que creo "geniales" y "únicas" para después descubrir que alguien ya lo hizo antes. Esto me pasa todo el tiempo :(. Y hoy pasó de nuevo.
Cuando volvía caminando del fútbol del domingo al medio día se me ocurrió "estaría buenísima una página web que sirva para organizar los partidos de fútbol". Los quilombos de los mails solucionados. Nadie haría mucho laburo (después de todo, la página haría sola toda la coordinación). Así que me puse a hacerla, y mientras la hago chequeo el correo y veo otra página web que es para esto.
Bueno, parece que voy a tener más tiempo para estudiar para el doctorado.

Happy hacking,
Aureliano.

2008-06-18

El lock-out

A veces uno trata de explicar cómo son las cosas, pero viene un humorista y deja todo claro.

2008-06-12

Estudio de noche y Google Analytics

Ayer a la noche (u hoy a la madrugada, en función de lo que quieran pensar) fui como invitado al programa Estudio de Noche en la Radio de la Ciudad. Ahí estuvimos hablando con mi amigo Gustavo Fernandez Walker(el conductor) y mi amigo Martín Gonzalez(el otro invitado) sobre varias cosas, pero principalmente sobre el impacto de la Internet sobre la forma de generar eso a los que los abogados llaman propiedad intelectual. En particular estuvimos hablando del impacto en obras artísticas (y aún más en particular, de obras musicales). También tocamos tangencialmente el tema de los wikis y del desarrollo de software libre. Me divertí haciendo radio, así que probablemente vaya como invitado alguna otra vez.
También le mostré a Gustavo Google Analytics, que le gustó y lo puso en el blog del programa. Gustavo es filósofo y estas instrucciones le sirvieron, así que supongo que le servirán a cualquiera que tenga un blog en blogspot (y cambiandolas un poquito, cualquier página). Acá pego las instrucciones textuales:


Tenés que ir al panel de tu blog -> diseño -> Añadir un elemento de
página -> HTML/Javascript
y poner adentro de eso el cacho de código que te dicen que pongas en
google analytics. En mi caso es:
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "ACA VA UN CODIGO TUYO";
urchinTracker();
</script>
Seguramente debe ser algo parecido en el tuyo. Una vez que tenés eso
agregado, cada vez que alguien se conecte a tu blog se va a bajar ese
código, que es el que hace que google pueda saber quienes se conectan
a tu página (así es en la mía). Es solo copiar el cacho de código en
blog como dice arriba y activar el trackeo en google (si no me acuerdo
mal).

Happy hacking,
Aureliano.

2008-06-08

Buscando hosting para mis proyectos personales

Hola a tod@s,
Estoy buscando un hosting para mi. La idea es poner ahí las cosas que haga para el doctorado (así tengo acceso desde todos lados, versionado y un backup en otro lado) y algún que otro prototipo de página web que se me ocurra (tenía algunos pensados que no hice porque no tenía dónde ponerlos).

Mis requerimientos principales son que tenga svn por ssh y https (para lo del doctorado) y que pueda correr ruby para hacer la página (y seguramente alguna base de datos).

También estaría bueno acceso por ssh para poder tocar todo, que sea barato y que si me paso del ancho de banda diario/ semanal/ mensual corten el site y me manden un mail para ver que hacer (para evitar la quiebra por slashdot). No creo que, al menos al principio, tenga mucho tráfico.

Por favor, cuéntenme cómo les fue con sus proveedores de hosting. Escucho sugerencias.

Happy hacking,
Aureliano.

2008-05-24

Wireless@home

Update: Más configuración por seguridad

Hoy configuré el modem ADSL/router/access point wireless (AKA: "el coso wireless") que me compré en la semana y lo hice andar completo (wireless con WAP2). Es un hermoso ZyXEL PRESTIGE 660R-61C.
Ahora les cuento que cosas tuve que hacer para hacerlo hacer andar.

Paso 1: conexión a speedy


Conecté una notebook con fluxbuntu al "coso wireless" con el cable ethernet que viene en la caja y enchufé el cable de teléfono (que también viene en la caja) entre el coso y la boca de teléfono. Configuré eth0 para que esté en 192.168.1.23 (creo que casi cualquier IP en la red 192.168.1.x debe andar) y me dirigí con un browser a 192.168.1.1. Por suerte le pegué (de re-pedo) y entré al menú de configuración del coso vía web.
Intenté setear de una la conexión pero no funcó :(. ¿Por qué? Los seteos de VPI y VCI correctos para speedy (8 y 35 respectivamente) no los aceptaba. Después de un rato de googleo, encontré la página de speedy donde explica como configurar el coso wireless. Lo único que hice distinto es que cómo ya había cambiado el password de administración desde la parte web, puse mi password nuevo. Seguí las instrucciones, setié como name servers a200.51.211.7 y 200.51.212.7 y ¡se conectó a speedy!

Paso 2: Compartir la conexión entre varias PCs


Con esto andando, el siguiente paso fue compartir la conexión entre 2 PCs. Esto fue re-fácil. Configuré mis 2 notebooks x DHCP y las enchufé al coso wireless con sendos cables ethernet. Una vez que las PCs estuvieron andando, ya tenía conexión a internet :D

Paso 3: El coso wireless es wireless (y se supone que yo sé de seguridad informática)


Bueno, esto ya estaba andando. Entonces me puse a configurar el acceso wireless. En cuanto miré, algún vecino "extra rápido" ya se había conectado a mi coso wireless y estaba leecheando internet. Así que empecé a cerrarlo. Mirando rápido el menú me pareció que había solo WEP, y "this is unacceptable" para un investigador en seguridad informática como yo (chiste). Así que apagué el wireless para que no leecheen más y empecé a mirar la configuración. Al final encontré la parte de WAP, que está en otro menú (parece que la amigabilidad no es parte de los objetivos de diseño del menú administrativo por web del coso wireless). Y empecé a probar.
Para hacer andar la parte wireless tuve un desafío extra, que es que lo hice andar en un Kubuntu Hardy (8.04). Por suerte, cuando compré mi notebook tuve la delicadeza de comprar una placa Intel, por lo que se me hizo más fácil. Después de varias vueltas descubrí que lo mejor era configurar el coso wireless en WPA2 con PSK (pre-shared key). Y solo queda explicar que hice para hacer que ande el Kubuntu. Probé un montón de cosas que no andaban hasta que encontré por internet (no tengo el link acá) que a veces reinstalando algunos paquetes la integración de las placas wireless. Así que hice
sudo aptitude reinstall knetworkmanager wpasupplicant network-manager
y santo remedio. Cargué el KNetwork Manager y cliquié el botón derecho, me conecté a mi red, puse el password que había configurado en el párrafo anterior y anduvo todo joya.

Paso 4: Ajustes finales


Por último, quiero seguir pudiendo conectarme a bit torrent bien para "bajar ISOs de Linux". Así que configuré que la MAC de mi notebook tenga IP fija (está en la parte de LAN del menú avanzado) y forwardié los puertos correspondientes (TCP y UDP) que tengo configurados en el KTorrent.
Y para que sea más seguro (mirando los ataques que postulan en GNU Citizen) le configuré distinto el SNMP. Me conecte x telnet al coso y cambié las opciones del menú 22, que quedó algo así:

SNMP:
Get Community= [passwd nuevo]
Set Community= [otro passwd nuevo]
Trusted Host= 0.0.0.0
Trap:
Community= [y otro pass más]
Destination= 0.0.0.0

En una mirada rápida, me pareció que el resto de los ataques requieren que el atacante esté conectado en la red interna, así que los dejo para después (supongo que requerirán un cambio de firmware).

Así llegué a la configuración que quería y me dediqué a escribir este post.
Happy hacking,
Aureliano.

2008-05-03

El último pelo

Este hilarante blog habla de los calvos. Sus problemas y soluciones. Envidias y resentimientos. Gracias y tristezas. Recomiendo ampliamente a este blog, que es el único que conozco que tiene su propia canción. En fin, tómense unos minutos y ríanse un rato. Yo, como buen calvo que soy, lo recomiendo.

Happy hacking,
Aureliano.

2008-05-02

Load balancer minimalista en ruby (parte 2)

En el post anterior mostré un load balancer que implementé en ruby. Ahora le agregué algo de manejo de errores y algo de fail-over para que sea más estable.

Este es el código nuevo:


#!/usr/bin/env ruby
require 'socket'

def usage
puts "Very simple balancer"
puts "balancer.rb port host1:port1 [host2:port2 ....]"
exit
end

def build_targets(argv)
argv.map do
|param|
result = param.split(":")
result[1] = result[1].to_i
result
end
end

class Balancer
def initialize(port, *targets)
@descriptors = []
@next_step = {}

@serverSocket = TCPServer.new( "", port )
@serverSocket.setsockopt( Socket::SOL_SOCKET, Socket::SO_REUSEADDR, 1 )
puts("Balancer started on port #{port}")

@descriptors << @serverSocket

@targets = targets
@current_out = 0
end

def next_out
out_socket = nil
until out_socket
begin
@current_out = (@current_out + 1) % @targets.length
descr = @targets[@current_out]
out_socket = TCPSocket.new(descr[0], descr[1])
rescue
# do nothing on purpose
end
end
out_socket
end

def accept_new_connection

incoming = @serverSocket.accept
outgoing = next_out

@next_step[incoming] = outgoing
@next_step[outgoing] = incoming

@descriptors += [ incoming, outgoing ]
end

def propagate(sock)
next_sock = @next_step[sock]
next_sock.write(sock.read_nonblock(1000 * 1000))
end

def finish_connection(sock)
next_sock = @next_step[sock]
[sock, next_sock].each do
|s|
begin
s.close
rescue Object => e
puts "Error closing socket: #{e.inspect}"
end
@descriptors.delete(s)
@next_step.delete(s)
end
end

def run
loop do
connections = select( @descriptors )
if connections
connections[0].each do
|sock|
if sock == @serverSocket then
accept_new_connection
else
begin
if sock.eof? then
finish_connection(sock)
else
propagate(sock)
end
rescue
finish_connection(sock)
end
end
end
end
end
end
end

trap("SIGINT") do
exit
end

usage if ARGV.length < 2
port = ARGV.shift.to_i
targets = build_targets(ARGV)

Balancer.new(port, *targets).run


Me parece que ahora pueden llegar a usarlo.

Happy hacking,
Aureliano.

2008-05-01

Load balancer minimalista en ruby

Update: Puse la versión más nueva en este post.

Ayer estuve inspirado y dediqué un poquito de mi tiempo a aprender un poco más sobre cómo manejar sockets. Hacía mucho tiempo que no programaba sockets en bajo nivel y nunca había necesitado usar select para manejar muchos al mismo tiempo. De hecho, la última vez que tuve que hacer algo parecido a un server que acepte muchas conexiones TCP lo hice en java 1.3, y en java 1.3 no hay select (agregaron algo parecido en java.nio, que apareció después).
Así que puse manos a la obra e hice un minicloncito de un load balancer en ruby.
Por supuesto que no hice todo. En particular, me comí el manejo de errores. Pero si hace round robin de conexiones y tiene menos de 100 líneas de código, lo que creo que lo hace un buen ejemplo de juguete sobre como manejar sockets en ruby.
Bueno, basta de cháchara, acá va el código completo:


#!/usr/bin/env ruby
require 'socket'

def usage
puts "Very simple balancer"
puts "balancer.rb port host1:port1 [host2:port2 ....]"
exit
end

def build_targets(argv)
argv.map do
|param|
result = param.split(":")
result[1] = result[1].to_i
result
end
end

class Balancer
def initialize(port, *targets)
@descriptors = []
@next_step = {}

@serverSocket = TCPServer.new( "", port )
@serverSocket.setsockopt( Socket::SOL_SOCKET, Socket::SO_REUSEADDR, 1 )
puts("Balancer started on port #{port}")

@descriptors << @serverSocket

@targets = targets
@current_out = 0
end

def next_out
@current_out = (@current_out + 1) % @targets.length
@targets[@current_out]
end

def accept_new_connection
out_descriptor = next_out

incoming = @serverSocket.accept
outgoing = TCPSocket.new(out_descriptor[0], out_descriptor[1])

@next_step[incoming] = outgoing
@next_step[outgoing] = incoming

@descriptors += [ incoming, outgoing ]
end

def propagate(sock)
next_sock = @next_step[sock]
next_sock.write(sock.read_nonblock(1000 * 1000))
end

def finish_connection(sock)
next_sock = @next_step[sock]
[sock, next_sock].each do
|s|
s.close
@descriptors.delete(s)
@next_step.delete(s)
end
end

def run
loop do
connections = select( @descriptors )
if connections
connections[0].each do
|sock|
if sock == @serverSocket then
accept_new_connection
else
if sock.eof? then
finish_connection(sock)
else
propagate(sock)
end
end
end
end
end
end
end

trap("SIGINT") do
exit
end

usage if ARGV.length < 2
port = ARGV.shift.to_i
targets = build_targets(ARGV)

Balancer.new(port, *targets).run

Para usarlo, copien todo el codigo a un archivo (como balancer.rb) y fijense en el cartel que explica los parámetros. El primer parámetro es el puerto donde escucha y los otros son pares host:port a los que tiene que conectarse alternativamente.

Bueno, eso es todo por ahora.

Happy hacking,
Aureliano.

2008-04-20

Reconstrucción del ligamento cruzado anterior de la rodilla derecha - Epílogo

Como estuve contando hace un tiempo por acá hace un poco más de un año y medio me operaron para reconstruir el ligamento cruzado anterior de mi rodilla derecha, que fue obliterado en una de mis tantas caídas que tengo cuando esquío (en realidad fue la última). Ahora dejé de esquiar, más que nada por falta de $$$$, y me reincorporé al resto de las actividades usuales de mi vida (incluyendo volver a jugar al "fútbol" los domingos).

Aunque hace muuuucho tiempo que no escribo nada de esto, sigue habiendo gente que se interesa en estos posts de mi blog y, extrañamente, si buscan reconstrucción de ligamentos en google este blog aparece en la primera hoja, me pareció pertinente contarles como fue mi recuperación y como llegué a estar 100% activo deportivamente nuevamente.

Así que les cuento.

Septiembre 2006


Me operaron, pueden ver los detalles en este blog.

Octubre 2006-Marzo 2007


A los 20 días de la operación (aprox) el traumatólogo me dijo "ahora tenés que hacer rehabilitación". La rehabilitación es larga (dura unos 6 meses) y laboriosa (hay que ir 3 veces x semana como 2 horas) pero si hacen las cosas bien lo más probable es que queden bien. Así que me puse las pilas.
Al principio era la típica kinesiología que pensás que es medio al dope donde te ponen esos aparatos que hacen "magnetoterapia", que son como unos cilindros por donde pasas la pierna y están enchufados a un aparato con un timer, que hace ruido cuando termina. También te torturan un poquito haciendo estimulación eléctrica de los cuádriceps de la pierna operada. Media hora y despachás.
A las 2 semanas decidieron que era hora que hiciera pesas y estuve haciendo diversos ejercicios pero solo con la pierna rota, previa magnetoterapia. Todo el chiste me llevaba como 2 horas cada vez, un embole. Y encima en el gimnasio no había una mina que estuviera buena. Solamente un montón de tipos recuperandose de roturas de ligamento cruzado anterior y viejos con dolencias variadas :(.
Mientras pasaba el tiempo me fueron agregando ejercicios y subiendo el peso de los mismos hasta que idearon otra forma de torturarme: estimulación eléctrica del cuádriceps mientras hacía pesas.

¡A la mierda!

Eso si que es feo. Aparte te tiran voltajes grosos. La máquina la usaban entre ¡80 y 120 volts! (posta) y parecía que me iban a electrocutar toda la pierna. Pero cumplió su objetivo.
Al final, me agregaron ejercicios de correr de costado y haciendo secuencias raras de paso y después de un verano agotador, me dieron el alta.

Abril 2007-Presente


Me dieron el alta pero todavía no estaba bien, bien. Me faltaban los últimos detallecitos. Así que todavía me dolía la rodilla de vez en cuando y se me inflamaba cada vez que hacía movimientos raros. Aparte mi sobrepeso tampoco ayudó mucho.
En mayo entré a laburar a mi laburo actual y hubo 2 actividades que me hicieron mierda la rodilla:

  1. Día de actividades "corporativas" de la empresa. Donde nos llevaron al Club de Amigos a que nos lavaran el cerebro haciéndonos creer que la empresa es lo más importante del universo. La actividad fue una mierda, pero había un castillo inflable que estaba buenísimo, pero que fue la perdición de mi rodilla.

  2. Basket. Esa misma semana fui a jugar al basket en cancha de cemento.


El combo fue letal. Estuve rengo por 3 semanas, me asusté, fui al traumatólogo. Me dijo que me haga una radiografía y lo vea de nuevo. Cuando fui a verlo de nuevo con la radiografía, empezó a sacarle fotos porque le parecía que había hecho una obra de arte con mi rodilla y estaba muy orgulloso, me dijo que no haga más boludeces y que estaba bien y se fue a un congreso con las fotos de mi rodilla.
Así que esperé a que se terminara de desinflamar la rodilla y empecé a hacer "deporte de bajo impacto". O sea, volví a nadar. La natación me vino bárbaro y mi rodilla se terminó de mejorar. A mitad de año pusieron clases de yoga en el laburo y empecé a ir (y sigo yendo). Así estoy terminando de recuperar la flexibilidad.
Por último, hará un mes que volví a las canchas de fútbol 5. No se nota ninguna secuela de la lesión, salvo que ahora juego con una rodillera puesta. Mi habilidad está intacta y hasta estoy jugando un poquito mejor que antes. Igual eso no quiere decir mucho, era desastroso y lo sigo siendo.
O sea, si se rompieron la rodilla, no sean boludos, opérense. Es mucho laburo pero pueden volver a las cosas que hacían antes. Una cosita más. Lo que me dijeron los médicos es que si no se operan y tienen los ligamentos rotos, van a tener una artitris grosa en unos años.
Espero que les sea de utilidad a todos los googleros que llegan por acá buscando información sobre la reconstrucción de los ligamentos.

Happy hacking,
Aureliano.