Travelling salesman
I’m selling this fine leather jackets
One classic computation problem, the travelling salesman. Even if it’s quite simple to describe, it’s one of those hideous NP complete problems, the ones that are quite difficult to resolve, as the computation time needed grows greatly with the length of the data. On Programming Praxis they have proposed to resolve the problem using brute force, and using the closest neighbor (a simplification of the problem).
I’ve created this program, in Python.
import random
import itertools
import operator
import datetime
MAX_X = 100
MAX_Y = 100
def random_cities(number):
''' Generate a number of cities located on random places '''
cities = [ (random.randrange(0, MAX_X),
random.randrange(0, MAX_Y))
for i in range(number) ]
return cities
def path_lenght(path):
''' Get the lenght of a path '''
lenght = 0
for i in xrange(len(path) - 1):
# Add the distance between two cities
lenght += abs(complex(path[i][0], path[i][1])
- complex(path[i + 1][0], path[i + 1][1]))
return lenght
def find_path_bruteforce(cities):
''' Find the smallest path using brute force '''
lenghts = []
for path in itertools.permutations(cities, len(cities)):
# Get the length of the path, adding the returning point
total_path = path + (path[0],)
lenght = path_lenght(total_path)
lenghts.append((total_path, lenght))
# Get minimum
lenghts.sort(key=operator.itemgetter(1))
return lenghts[0]
def find_path_nearest(cities):
''' Find the closest neibour '''
lenghts = []
for city in cities:
lenght = 0
actual_cities = cities[:]
actual_city = actual_cities.pop(actual_cities.index(city))
path = [actual_city, ]
# Find nearest neibour
while actual_cities:
min_lenght = []
for next_city in actual_cities:
min_lenght.append((next_city, abs(complex(city[0], city[1])
- complex(next_city[0], next_city[1]))))
# Get closest neibor
min_lenght.sort(key=operator.itemgetter(1))
actual_city = min_lenght[0][0]
lenght += min_lenght[0][1]
actual_cities.pop(actual_cities.index(actual_city))
path.append(actual_city)
# Complete the trip with the first city
path.append(city)
lenghts.append((tuple(path), path_lenght(path)))
# Get minimum
lenghts.sort(key=operator.itemgetter(1))
return lenghts[0]
if __name__ == '__main__':
for i in range(3, 10):
print 'Number of cities: ', i
cities = random_cities(i)
time1 = datetime.datetime.now()
path2, lenght_neighbor = find_path_nearest(cities)
time2 = datetime.datetime.now()
print path2, lenght_neighbor
time_neighbor = time2 - time1
print 'Time neighbor: ', time_neighbor
time1 = datetime.datetime.now()
path1, lenght_brute = find_path_bruteforce(cities)
time2 = datetime.datetime.now()
print path1, lenght_brute
time_brute = time2 - time1
print 'Time brute force: ', time_brute
print 'Diff: ', float(lenght_neighbor - lenght_brute) / lenght_brute * 100, '%'
The time spend on each is brutally different, specially as the number of cities grow. With more than 9 cities, the time grows at some point when my computer has to take more than minutes to compute the brute force approach, while the neighbor approach will still be below the 1/100 of a second. The error also grows, being the same on small number of cities, but getting afar fast when the number of cities grow. At 9 cities, the error is about a 20-30%
Crítica despiadada de “Todo va a cambiar” de E. Dans
Influido y presionado desde Twitter, he decidido leerme el libro “Todo va cambiar”, de Enrique Dans. Sinceramente, ha sido un suplicio, y la idea es hacer un resumen para que nadie más tenga que hacerlo… 😀
Primero, unas ideas preconcebidas. No me gusta nada Enrique Dans. Lo encuentro el paradigma del gurú de Internet que simplemente habla sin tener mucha idea, que intenta comunicar a base de repetir las mismas ideas que hacen otros, y con un sobramiento de sí mismo desmesurado. Hay un lugar para “los comunicadores”, gente que se encarga de recopilar ideas y darles un tratamiento único. Hacerlo bien es difícil y hay que reconocerlo. Hay otros que se dedican a poco menos que copipegar todas las ideas que pueden, y encima lo cuentan peor que el original. Eso sí, parece que es una especie de gurú del 2.0 y que tiene muchos seguidores. Pues vale. El que espere una crítica amable, puede dejar de leer 😀
Dicho mis ideas generales sobre Enrique Dans, vamos a lo que es el libro. En general, me resulta un libro prescindible e infumable (que es todavía peor). Principalmente se dedica a recopilar ideas muy manidas, a saber: Web 2.0 bueno. Derechos de autor, malo. Nuevos paradigmas. Compañías que no evolucionan. Google bueno, Microsoft, malo.Todo esto aderezado con un estilo de escribir aburrido y pagado de sí mismo, con contínuas referencias personales un poco metidas con calzador.
Creo que lo peor que tiene el libro es que su concepto debería ser algo que inspirase, que te animase a hacer algo, pero el 90% del tiempo está comentando los mismo ejemplos de siempre (Amazon, eBay, Google, Microsoft, etc), y no resulta inspirador. Comparado con, por ejemplo, Seth Godin, se le ven las carencias. Por ejemplo Brainwashed (traducido al español en el blog Desencadenado) o Bootstrapper Bible son buenos textos que te impulsan a pensar, a cargar las pilas, a intentar hacer algo… El que Enrique Dans te cuente sus batallitas de pionero internauta, pues no te da el mismo impulso… Así que tenemos dos opciones: O bien lo que dice el libro te lo sabes y ya lo has hecho (ya has cambiado) o bien, si no lo sabes, le falta la parte de verdaderamente animar a hacer algo. Por eso digo que es prescindible.
Aun así, hay libros prescindibles y animados de leer, que aumentan tus conocimientos. No es el caso, el estilo (al menos a mí) me resulta soporífero y cada pocas páginas tengo que darme de cabezazos por alguna metedura de pata o algunas de sus “perlas”. Además, se hace difícil para el profano al ahondar en términos excesivamente técnicos, y los pocos que se explican se hacen de manera bastante farragosa. Curiosamente, para ser un “libro 2.0”, es raro que no incluya enlaces y referencias a muchas páginas para apreder más. Si me da por pensar mal, será para que no se noten las carencias.
Para los que no tienen ganas de leerse el libro (y, desde aquí, no se lo recomiendo a nadie), he decidido hacer un resumen, capítulo por capítulo con las cosas más cargantes que aparecen…
- Después de un prólogo firmado por Vint Cerf, con sobreabundancia de términos técnicos en inglés y entiendo que fuera de lugar para un libro “generalista” (sospecho que se escribió en inglés), viene la introducción. sin duda, una de las joyas del libro, que relata las maravillosas aventuras de un pionero, un visionario en esto de los ordenadores, un gurú. Claro que sus “visiones” producen más risa que otra cosa a cualquiera que haya estado relacionado con ordenadores los últimos 15 años, pero bueno. Al tratarse de un tema “cercano”, el estilo es menos “plomizo” (comparado con el resto del libro), pero mucho más “sobrado”.
- Música, películas, mentiras e Internet. El primer capítulo es una sucesión de topicazos, argumentos mil veces repetidos ya hace años, y aderezados con una serie de pedantes referencias históricas. Los argumentos son los de siempre sobre el tema copyright, y es un tema taaaan manido. David Bravo explica lo mismo de manera muchísimo más amena (y hace 5 años) en “Copia este libro”
- Las evidencias del cambio. Explicando las bondades del software libre y cómo la Wikipedia es mucho mejor que la Enciclopedia Británica (entre otros ejemplos de cómo la tecnología mejora nuestras vidas, con ejemplos). Tampoco escatima en poner por las nubes a su padre y abuelo, pero incluso ellos tendrían problemas con los cambios. Y pensar que mi abuelo usaba un ordenador e Internet, siendo una de las personas más negadas para temas técnicos que he conocido… Pero el gran descubrimiento del capítulo es el hecho de que la palabra “Viagra” se puede deletrear de 600.426.974.379.824.381.952 (son 21 cifras) de manera que sea reconocible por los humanos. Viene de este artículo, que obviamente, es más una broma que otra cosa… Entre otras cosas, porque acepta cosas como “aVbIPARGIRNam” como una forma de deletrear “Viagra” de manera (perfectamente) reconocible por los humanos… Sin embargo, creo que es un gran número para definir el ego de Enrique Dans en relación al ego de una persona normal, es decir, su ego es 600.426.974.379.824.381.952 veces superior al de una persona normal, o 1 edans veces…
- La disrupción tecnológica (cuando lo vemos venir). Habla de lo rápido que pueden darse procesos de cambio. También tiene “detalles”, “los productos bit” y “los productos átomo”, que viene siendo “información” y “cosas físicas”, claro que dicho así resulta menos lioso y Enrique Dans dice textualmente: “Pero nadie le dijo que la lectura de este libro iba a ser fácil”. Creo que debería ir en la contraportada, a modo de advertencia. Otro detalle: “cuando llegué en 1996 a los Estados Unidos tras haber recibido durante toda mi vida una educación en inglés británico, el acento californiano me suponía ciertos problemas de comprensión”. Si escribe eso, o no ha hablado con un británico en su vida (supongo que con algún californiano sí) o se las da de que sabía inglés británico mejor que la Reina antes de llegar a California.
- La evolución de la comunicación. Básicamente una evolución, desde nuestros ancestros comunicándose a base de aullidos, hasta los blogs. Curiosamente, no comenta nada específico de Twitter o Facebook.
- Introducción a la red. La neutralidad de la red. Resume la idea de la neutralidad de la web y cómo “oscuros intereses” pueden interferir, junto a ideas como que es un derecho, etc…
- Los costes de transacción y comunicación. O cómo las empresas “antiguas” tendían a crecer verticalmente (llevando el control de producto desde la materia prima hasta la venta al por menor) y ahora se tiende a especializarse y a poder trabajar repartidos por el mundo. Deja claro que conoce bien cómo funciona Weblogs SL.
- La generación perdida: La resistencia a la tecnología. Los típicos comentarios de que Internet es fabulosa y en España tiene muy mala prensa. Que hay sitios peligrosos, pero no es para tanto, y que las empresas tienen que adaptarse y no rechazar los cambios tecnológicos, o serán aparcadas. Otra vez, nada nuevo.
- Una nueva generación. Lecciones sobre cómo educar a tus hijos en la tecnología. Me parece un capítulo especialmente peligroso (y posiblemente polémico), ya que diserta sobre el uso de las tecnologías en niños y adolescentes, resumido en “los niños utilizan de manera más natural las redes sociales y saber usarla mejor” y critica cosas como el uso de filtros o restricciones el uso de los ordenadores en niños. Me parece peligroso porque entra en un terreno sumamente resbaladizo, como es la educación de los hijos, y evita el siguiente problema. Si el padre sabe poco o nada de Internet, ¿cómo debe educar a su hijo al respecto? No es nada fácil responder a estas preguntas, incluso por (verdaderos) expertos, pero Enrique Dans sienta cátedra con una rotundidad bestial.
- La red y el neohumanismo. Aparentemente, vivimos en sociedades en las que la identidad individual ha sido cercenada. Y sólo lo recuperaremos por Intenné. O eso dice. A mí me parece una tontería como un castillo, será que no soy un gurú que marca tendencias. Y volvemos a la idea de que no eres nadie si no estás en Google posicionado como un experto. Chorrisandeces de esas que Andrés, en Marca Propia, se encarga de desmontar todos los días. El mundo no es sólo Internet (y lo dice alguien que trabaja en el ramo y para quien Internet es MUY importante).
- Un caso práctico: Microsoft. Hacer leña del arbol caído siempre es interesante, y Microsoft es una compañía que se presta como pocas a calificarla como “el Mal Absoluto”. Pero de ahí a contar la historia de Microsoft como se cuenta en este capítulo, hay un mundo. Porque se dedica, básicamente, a ponerlos a caer de unburro, relativizar sus éxitos y ahondar en sus fracasos. Además, nos volvemos a encontrar “perlas” de las que me llama la atención esta: “Los mejores lenguajes de programación son PHP, Perl o Python.” Vamos, que nos tomamos muy a pecho las arquitecturas LAMP (también hace referencia a Apache) 😀 Resultado, “Microsoft es la historia de una falta de adaptación”. Y mira que Python es mi lenguaje de programación favorito 😉
- La evolución de la web. Varios ejemplos de empresas exitosas en Internet, como Google, Amazon, YouTube o eBay. Los ejemplos de siempre, vamos.
- Un caso práctico: Google. En comparación con el anterior, todo loas a Google. Algunas explicaciones de cómo funciona su buscador (aunque pasa de puntillas frente a otras alternativas que había, en su momento y califica a Yahoo de “directorio”), y, curiosamente, una reseña sobre el tema de la privacidad, que se salda diciendo que Google “es muy transparente” y que en cualquier momento podemos borrar las cookies del navegador…
- La evolución de la tecnología: del ordenador a la nube. Cambiar de un procesador de textos con datos en local, a “la nube”, ese concepto etéreo que parece que las cosas no se guardan en ningún sitio, pero están muy seguras. Aviso a navegantes, procurad tener copia de las cosas realmente importantes que tengais en la nube. Ningún sistema es seguro al 100%
- Nuevas herramientas para nuevos escenarios. ¿Slashdot es un blog? Este capítulo trata sobre lo guays que son los blogs y lo fácil que es escribir en uno y hacerse un reputado experto y gurú. Además de algunas reseñas a Twitter y a Digg.
- La sociedad hiperconectada. Blogs (de nuevo), comentarios, twitter, respuestas de las empresas a usuarios que se quejan en Internet, comunidades, trolls interneteros… Tiene pinta de repetición de otras fuentes, a veces está deslavazado y repite machaconamente ideas de otros capítulos como “El efecto Streissan”.
- Revisando los papeles: Participación y comunidades. ¡Móntese un blog si no lo tiene! Es muy importante, pero si lo abandona, nadie le echará de menos…
- El futuro. Aquí Enrique Dans nos obsequia con lo guay que es su vida con el uso de la tecnología y cómo podremos disfrutar de parte de ella si nos conectamos a Internet, participamos, compramos y hacemos nuestra vida más tecnológica… Las gestoras de derechos seguirán luchando por conservar el poder e impedir el libre intercambio de archivos. Las telefónicas querrán no ser neutrales. Los “viejos poderes” intentarán impedir los derechos digitales, pero no podrán. Todos podremos ser creadores y se democratizará la creación. Se eliminarán intermediarios. El mercado se fragmentará aún más y habrá un nuevo modelo económico. Todo ha cambiado ya. Si no has oído música de violines al leer esta parte y has aplaudido al final, es que ya has oído lo mismo desde hace unos 10 años mil y una veces… Yo al menos, exijo que se narre con garra…
En resumen, me ha parecido infumable. No sólo habla de los mismos (y típicos) ejemplos una y otra vez, sino que lo plaga de referencia que oscilan entre lo irrelevante y lo pedante, y el autobombo más descarado. El libro es aburrido, lleno de términos desconocidos para el que no está pendiente de la informática e irrelevancias para el que está pendiente.
Interesting Project Euler problem
There is one interesting problem to solve from the guys on Project Euler.
I think that maybe there are some problems running a naive approach to the problem on the 2002, but right now, even a inefficient approach can give you results in not much time. I’ve made the following program in Python to measure the differences between a straight approach, and one using recursion and memoization. Looking carefully at the sequences, we realize that each time we get to a previous calculated number, we don’t have to recalculate the sequence again. So, doing it by hand, for the numbers from 1 to 5:
1 : 1 step 2 --> 1 : 2 steps 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1 : 8 steps 4 --> 2 --> 1: 3 steps (note that is repeated from below) 5 --> 16 --> 8 --> 4 --> 2 --> 1 : 6 steps (again, is repeated)
So, by memoization, we can store the length of previous results, so we don’t have to calculate them again.
from datetime import datetime
import operator
def inneficient(number):
''' Find the number of steps to 1, inefficiently '''
steps = 1
while number != 1:
if number % 2 == 0:
number = number / 2
else:
number = number * 3 + 1
steps += 1
return steps
numbers = {1:1}
def efficient(number):
''' Find the number of steps to 1, nefficiently '''
if number in numbers:
return numbers[number]
else:
if number % 2 == 0:
result = efficient(number / 2) + 1
else:
result = efficient(number * 3 + 1) + 1
numbers[number] = result
return result
def inefficient_search(times):
return max(((number, inneficient(number)) for number in xrange(1, times + 1)), key=operator.itemgetter(1))
def efficient_search(times):
return max(((number, efficient(number)) for number in xrange(1, times + 1)), key=operator.itemgetter(1))
def execute(function, times):
time1 = datetime.now()
result = function(times)
time2 = datetime.now()
total_time = time2 - time1
print '{0:18}: {1:9} times, time {2}. Result: {3}'.format(function.__name__, times,
total_time, result)
def main():
''' Find the longest secuence of numbers '''
SMALL_NUM = 1000
BIG_NUM = 1000000
execute(inefficient_search, SMALL_NUM)
execute(efficient_search, SMALL_NUM)
execute(inefficient_search, BIG_NUM)
execute(efficient_search, BIG_NUM)
# Add another result, even bigger, to show that the complexity of the problem is not linear
execute(efficient_search, BIG_NUM * 10)
if __name__ == '__main__':
main()
And the results on my computer:
inefficient_search: 1000 times, time 0:00:00.022727. Result: (871, 179)efficient_search : 1000 times, time 0:00:00.002074. Result: (871, 179)inefficient_search: 1000000 times, time 0:00:31.148715. Result: (837799, 525)efficient_search : 1000000 times, time 0:00:01.822361. Result: (837799, 525)efficient_search : 10000000 times, time 0:00:18.398862. Result: (8400511, 686)
So even the first option doesn’t take too long to run on a modern computer, although, of course, the second one is much faster.
PD: I get to this problem after this post from the blog of S. Lott. Includes a funny cartoon!
Deployment of Django project using CherryPy and Cherokee
Recently, we have deployed into a test production our latest Django project. Choosing which deployment to use it’s not easy, as there are a lot of different tools for the job, but as we expect some load on the system, we have been spending some time in getting a good deployment that will allow us to be confident on the grow of the system.
After some research, we decided to use CherryPy and Cherokee.
- It’s pure Python, and easily integrated with Django. You can do it by yourself (it’s not very difficult), or you can take the easy way and use the django-cpserver tool. Anyway, we probably will end up customizing django-server to suit your needs, as there are some things that seems to be lacking (like logging support)
- It’s fast! Also it’s mature and stable. All three are must-have characteristics for any web server.
Why Cherokee?
- Its admin system. It’s really easy to use (instead of the usual .conf file, which can be a headache) and also quite safe, as it will only be active when a command is called, with a one-time-only password. It’s a great feature!
- It allows us to make our deployment. It’s described bellow. Basically, we are using it as a HTTP reverse proxy that will balance the load between several CherryPy instances. It will also serve our static files.
- Low memory footprint.
- Cherokee is able to manage all the CherryPy processes, so you don have to worry about launching and controlling them. You don’t have to daemonize the CherryPy processes also, making all the process much easier.
- It’s blazingly fast! It’s specially good serving static files. The speed is in the same league than ngix.
Not everything is great. We have also some problems, already solved or that will be solved in the future.
- As I said, django-cpserver doesn’t allow you to specify logging parameters to CherryPy. We will have to tweak it, although this is not difficult.
- We have a problem with this configuration with CherryPy 3.1 Ocasionally, when you ask for a page in Chrome or IE (but not in Firefox), you’ll get a blank page and a 408 error (request timeout). This will indicate that the connection between the client and the server has been lost, and it’s happening only when the option Keep Alive in the Cherokee server is activated. Asking for the page again will reload the data, as a new connection will be open. Apparently, this was due a bug in CherryPy that has been corrected in version 3.2 (which is now on Release Candidate state). Version 3.2.0RC1 seems to work perfectly fine.
Our deployment configuration is described in the following diagram.
Architecture
The static data is directly served by Cherokee, while the Django application is supported by CherryPy. There are several processes of Django-CherryPy working, one of each core the server has, to increase the response avoiding problems with the GIL working over multiple cores, as well as making the architecture much scalable. Cherokee is conecting to the CherryPy instances over TCP/IP, so it gives quite flexibility. It’s also possible to use a Unix domain socket path, which could be even (a little) faster. As Cherokee allow to define an Information Source as a local interpreter command, you just write an script creating a new CherryPy instance, and Cherokee will manage to set up the processes and to kill everything when you stop the server. Cool.
We have also used memcached to increase the response of Django. It’s quite easy to use. Just install memcached on the machine, python-memcached to allow Python access it, and with a few configuration touches on your settings.py file, you’re ready. At the moment, as our views won’t change often, our approach is to use the @cache_page decorator, to cache completely the view. We’re not caching the complete site as that will not cache everything that gets URL parameters, which we’ve been using for generic_views.
All the architecture is highly scalable. Right now everything is on the same machine, but can be spread on different machines. Each process (Cherokee, CherryPy instances and Database) can be separated without much effort. Also, more instances of Django+CherryPy can be created. The only part that can be difficult to duplicate is the Cherokee server, but it’s difficult it will come to be the bottleneck of the system, unless the system grows REALLY big.
The system seems to be really fast and we’re having great testing results for the moment. In a couple of weeks the system is supposed to be public, and we expect quite a lot of hits, so performance it’s quite important, but, for the moment, we are quite satisfied with our deployment.
PD: For a tutorial on configuring Cherokee and CherryPy, you could check this great post.
Store standard output on a variable in Python
This is a great, hacky trick to get the standard output ( and others like standard error and standard input) in Python
You can “redirect” the standard error changing the sys.stdout module with your own StringIO object. So, you can do something like
from StringIO import StringIO # Python2 from io import StringIO # Python3 import sys # Store the reference, in case you want to show things again in standard output old_stdout = sys.stdout # This variable will store everything that is sent to the standard output result = StringIO() sys.stdout = result # Here we can call anything we like, like external modules, and everything that they will send to standard output will be stored on "result" do_fancy_stuff() # Redirect again the std output to screen sys.stdout = old_stdout # Then, get the stdout like a string and process it! result_string = result.getvalue() process_string(result_string)
Easy and very useful!
EDITED: Updated to make it work for Python 3.4
Casi un mes de trabajo en Irlanda
A lo tonto a lo tonto, llevo ya más de tres semanas trabajando y viviendo en Irlanda… A veces me parece que llevo ya mucho tiempo, y a veces me parece que acabo de llegar hace dos días. Algunos pensamientos intentado resumir algunas cosas.
Estoy MUY contento con el trabajo en Jolt Online. Es todavía un poco pronto para hacer balances, pero, por ahora, creo que ha sido un acierto en lo referente a profesionalmente, por varios motivos. El primero de todos, porque creo que es una gran experiencia curricular el hecho de trabajar en otro país, y en este tipo de empresa. Además, el trabajo en sí me está gustando mucho, estoy trabajando con herramientas que me gustan, como son Python y Django. Siento también que mi opinión es tenida en cuenta (cosa importante, al menos para mí) y que tengo mucha libertad para tanto proponer ideas como para hacer las cosas un poco como yo quiera, o, al menos, debatiendo sobre ello. Además, creo que mis compañeros de trabajo saben mucho y que puedo aprender de ellos, que es también interesante… Y, además, hay muy buen ambiente de trabajo y todo el mundo parece ser simpático y agradable. Otra cosa que me encanta, aunque no sé si es más debido al tipo de empresa o a la cultura por aquí, es que la gente realmente dice cosas como “good work”, “great job” y ánimos por el estilo, agradeciendo y valorando tu trabajo. Creo que en España funcionamos más en el lado contrario, echando la bronca si algo está mal, y no diciendo nada si está bien. Y la verdad es que sienta muy bien que te digan que has hecho algo bien.
El tema del inglés cuesta. Cuesta horrores. Aunque la verdad es que no he tenido en ningún momento problemas, es un esfuerzo contínuo el tener que hacer tu vida en otro idioma. Especialmente en situaciones como cuando se está hablando en grupo, es muy fácil perder la concentración y perderse. Ayer mismo tuve mi primera demostración/presentación para un grupo de gente de la empresa, y te caen goterones del esfuerzo. Supongo que irá mejorando con el tiempo, y esta parte es inevitable, pero el caso es que cuesta…
Intentaré también actualizar el blog de manera más frecuente, a ver si si me esfuerzo, que escribir es algo que también tarda uno su tiempo…
Bicicletas
Me encanta ver tantas bicicletas por las calles de Dublín. Estuve echándole un ojo al sistema de transporte de bicicletas público y es ridículamente barato…
Primeros pasos en Irlanda
Bueno, pues llevo ya dos días completos en Irlanda (esta será mi tercera noche), pero para algunas cosas, parece que llevo por lo menos un mes…
Obviamente, el cambiar de país lleva un montón de cambios y de puntos de comienzo, que uno no sabe bien por donde empezar… Hay algunas cosas que todavía no tengo terminadas, la principal es conseguir el PPS, que es el número de la seguridad social de aquí, que parece que es algo bastante primordial. Mañana mismo por la mañana tengo que acercarme a las oficinas, ya que, aunque lo han intentado en mi empresa, tengo que ser yo personalmente el que vaya a pedirlo. Otro detalle importante es el abrir una cuenta bancaria, que por lo que he leído, puede llegar a ser complicado porque se ponen bastante exigentes. Ya que parece que mi jefe tiene buena mano con los bancos, me han concertado una cita para el jueves por la mañana, donde sólo tengo que llevar el pasaporte y una carta firmada de mi jefe.
¿Cosas conseguidas? La principal de todas, ya tengo apartamento. Hoy mismo he firmado el contrato y me tengo que acercar esta tarde para comprobar que las llaves abren correctamente y para “tomar posesión” de todo. De todas formas, hoy no dormiré allí, ya que todavía tengo noches en el hostal, que me viene mejor para mañana acercarme a la oficina de la seguridad social. Mi idea es dormir ya mañana allí.
Otro punto importante es el estar en la oficina, firmar el contrato (por supuesto), preparar mi ordenador, y recibir algo de instrucción. Todavía estamos un poco en ello, pero parece que vamos avanzando, lo que es importante. No me está costando horrores el tema del inglés, aunque obviamente todavía voy despacito y hay muchas veces que no me entero. Cuesta bastante, aunque, bueno, espero que vaya mejorando con el tiempo… Se nota mucho especialmente con el acento, hay gente que se le entiende bastante bien, y hay otra que parece que hablan un idioma distinto.Al final del día uno llega con dolor de cabeza, pero supono que es normal… Otra cosa que tengo es un dolor horrible de pies, de estarme pateando la ciudad.. Espero que mejore en breve, ayer fue un día que me tiré todo el día andando, y el ir y venir del trabajo andando todos los días es una gozada, en lugar de conducir durante hora y media como solía…
En estos primeros días hay cosas que me resultan “raras”. Una es el tema de conducir por la izquierda. A la hora de cruzar la calle me pone en un estado de estrés constante, tengo que mirar a derecha y a izquierda y nunca sé de donde van a salir los coches. También ayuda el hecho de que los irlandeses cruzan la calle bastante al tuntún, quizá animados por el hecho de que no hay realmente pasos de cebra, y que los semáforos funcionan de forma extraña, poniéndose en rojo para todo el mundo por unos 3-4 minutos. Otro tema que se me hace extraño es el silencio que hay en la oficina, aunque eso puede ser más achacable a la oficina en sí que al país. Es realmente silencioso.
En fin, mis siguientes pasos son:
– Todo lo relativo a la casa. Dar de alta la luz, el teléfono, etc… Ayudará mucho el tema de la cuenta en el banco.
– Pillarme un teléfono.engo que enterarme de los requisitos, pero el hecho de tener una cuenta hará bastante también…
– Comprarme un puñetero adaptador para poder cargar el móvil, que está casi sin batería…
Seguiremos contando lo que pasa…
Vente para Irlanda, Pepe
La principal razón por la que me he decidido a retomar un blog es el contar mi nueva experiencia de trabajo, y es el hecho de que, en una semana, vuelo hacia Irlanda para comenzar un nuevo trabajo.
Obviamente es un gran cambio en la vida de cualquiera. No es sólo mudarte a una nueva ciudad y cmabiar de trabajo. Además, cambiar de idioma, y empezar de nuevo en un país distinto. La verdad sea dicha, es un reto importante que me atrae. Mirando con un poco de retrospectiva, en estos últimos 10 años, el mundo se ha hecho mucho más pequeño, y es bastante frecuente tener familiares y amigos que viven desperdigados por el mundo. Así que mudarse a otro país ya no es visto como una excentricidad, sino que es algo relativamente habitual.
Además, el nuevo trabajo me lo ha puesto muy fácil. Al menos sobre el papel, el puesto es interesantísimo y emocionante desde el punto de vista profesional.
Cuando llegue a Irlanda comenzaré una serie de posts sobre los distintos pasos que iré dando y cosas que me llamen la atención.
$7.11 in four prices and the Decimal type
There’s an fun and not very difficult programming exercise, presented on Programming Praxis . The problem is easy to describe:
“A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.”
Ok, the problem is easy to get on a brute force approach. Just try all the combinations, see their sum and multiplication, and find the one that gets it. Well, easy, but a lot of work to do for a modern computer. Get all the possible combination will be an amazingly great number of combinations (711 possible prices to the power of 4 gives 255,551,481,441 possibilities).
To simplify the calculations, we change the domain from 7.11 to 711, so get get the prices multiplied has to be equal to 711,000,000.
The proposed solution is to consider only the prices that are divisors of 711,000,000, reducing drastically the combinations.
I’ve tried a solution using a Python code, as follows. I added some “generic” touch and the Decimal type to avoid problems with float comparison:
def solve(dec_number, step, number_of_numbers):
integer_range = int(dec_number * 100)
all_numbers = [ Decimal(i) * step for i in range(1, integer_range) ]
multiples = 1 / reduce(operator.mul, [step] * (number_of_numbers))
correct_numbers = [ i for i in all_numbers if (dec_number * multiples % i) == 0 ]
def check(numbers):
"""Check the numbers added and multiplied are the same"""
return sum(numbers) == dec_number == reduce(operator.mul, numbers)
#it's naive to get only the combinations, but it's faster
posibilities = combinations(correct_numbers, number_of_numbers)
filter_mul = ifilter(check, posibilities)
return list(filter_mul)
t1 = time.time()
print solve(dec_number=Decimal('7.11'), step=Decimal('0.01'), number_of_numbers=4)
t2 = time.time()
print "time 7.11: ", ((t2 - t1))
and that gives an amazing time of 96 seconds! That’s clearly a lot. After that, I tried a completely different approach, just a not-so-brute solution, making a big loop with some tweaks to avoid all the combinations.
def calc():
for w in range(711):
for x in range(711 - w):
for y in range(711 - w - x):
z = 711 - x - y - w;
if (w * x * y * z == 711000000):
print "w: %d x: %d y: %d z: %d" % (w, x, y, z)
#Measuring time
t1 = time.time()
calc()
t2 = time.time()
print "time loop: ", ((t2 - t1))
For a total time of 34 seconds! And all the solutions! (which, BTW are the same, just reordered)
After some profiling, I’ve get the solution to this strange behavior. The use of the Decimal type.
LESSONS LEARNED:
– Decimal seems to be a “little” unefficient.
– Try to use basic types when making a lot of calculations.
– Don’t understimate the power of brute force, combined with low level languages. I’ve tried the same loop on C, and takes about 1/3 seconds.
Wrong Side of Memphis 