Older blog entries for maragato (starting at number 27)

Euler 9

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #9 statement is –

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which,

$a^2 + b^2 = c^2$

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

There exists exactly one Pythagorean triplet for which .

Find the product .

Butt ugly, super slow, brute-force solution:

 ```1 2 3 4 5 6 7 8 9 10 11 12 ``` ```from sys import exit   def is_triplet(a, b, c):         if a < b and b < c:                 return a ** 2 + b ** 2 == c ** 2   for a in range(0, 1000):         for b in range(a + 1, 1000):                 for c in range(b + 1, 1000):                         if a + b + c == 1000 and is_triplet(a, b, c):                                 print a * b * c                                 exit(0)```

I’ll have to rethink this, as it’s really inefficient. As it is, it runs in 18.034s!

Updated 2010/08/04: Gustavo Niemeyer pointed an obvious optimization to the algorithm above (written in C)–the innermost loop is unnecessary. I rewrote it in Python to see the difference:

 ```1 2 3 4 5 6 7 8 9 10 ``` ```from sys import exit   def is_triplet(a, b, c):         return (a ** 2 + b ** 2 == c ** 2)   for a in range(1, 1000):         for b in range(a + 1, (1000 - a) / 2):                 c = 1000 - a - b                 if is_triplet(a, b, c):                         print "%d * %d * %d = %d" % (a, b, c, a * b * c)```

From 18s to 0.076s. As well, following Eduardo Habkost’s suggestion, I used psyco and execution time went down to 0.023s.

Syndicated 2010-08-03 17:45:17 from Roberto Teixeira's blog

Euler 6

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #6 statement is –

The sum of the squares of the first ten natural numbers is,

The square of the sum of the first ten natural numbers is,

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is .

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Can’t be more straightforward than that, really.

 ```1 2 3 4 5 6 7 8 9 ``` ```  sqr_sum = 0 num_sum = 0 for i in range(1,100 + 1):         num_sum += i         sqr_sum += i**2   num_sum = num_sum**2 print sqr_sum - num_sum```

I’m pretty sure Niemeyer could rewrite this in one line, but whatever. This runs in 0.015s.

Syndicated 2010-08-03 17:35:28 from Roberto Teixeira's blog

Euler 5

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #5 statement is –

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

My first attempt was using brute force, but it didn’t go very well. It took a considerable amount of time, so I decided to think about the problem a bit. In the end, it boils down to the a relation between the lesser common multiplier and the greater common divisor.

 ```1 2 3 4 5 6 7 8 9 10 11 12 ``` ```def gcd(a, b):         if b== 0: return a         return gcd(b, a % b)   def lcm(a, b):         return a * b / gcd(a, b)   if __name__ == "__main__":         b = 2         for i in range(3,20):                 b = lcm(b, i)         print b```

While the original code took several seconds before I killed it, this runs in 0.015s.

Syndicated 2010-08-03 17:30:36 from Roberto Teixeira's blog

Because acme hurt my pride[1] by making fun of the still inexisting KDE interface for Apt, I've started creating KApt as a kpart last night. Quite straightforward actually. It already can query packages and update package lists. I just forgot to put it on CVS, but I'll do it tonight.

[1] it's a joke, Arnaldo :-)

We'll use a modified version of libapt in Kalypso. That's decided and I am working on it. The RPM part is working fine since the Apt version we're baseing ours on was Conectiva's Apt 0.3.19cnc55. The problem is that Debian changed its libapt at some time in the past.

Also, when porting to RPM, some of the deb code stopped working so I have to fix that. I installed a Debian system on a VMware box and now I'm working on getting our libapt working on Debian as well as RPM-based distros.

As a side note, Conectiva Apt was not ready to be compiled with gcc3 which gave me a good headache.

I've just learned that Apt's author has not integrated the rpm port into the main tree yet. This is a problem, as I will no longer be able to use libapt as a backend for the kde classes. Two bad. I'll be discussing with some people today what is the best approach right now. In the meantime I'm redoing the classes using librpm as the backend just in case.

I'm back updating Advogato. I'm now working in some classes to handle binary packages (DEP and RPM) to work on the new kde installer.

As I side note I've been thinking about Kivio for some time. It's a nice application but it's also a useless application the way it is now in KOffice. It's great for TheKompany.com but not so great for us. I'm thinking about doing some work on Kivio to make it usable in KOffice, but I'm affraid TheKompany will cry.

I give up! You win, Ark, you win...

Last night I realised I cannot defeat Ark. Seriously, Ark is so full of bugs and hacks that I can no longer fix it. When I took over Ark because the former maintainer simply disappeared from the net without a trace, I read on the TODO file "this thing is in serious need of a total reengineering" and "hacks on top of hacks on top of hacks". I knew it was going to be tough, but I did not know how much...

So, last night, I launched the kapptemplate script and began writing KArchiver from scratch. KArchiver will replace Ark as KDE archive utility. I am getting way too many bug reports on Ark. Bugs that I cannot fix without rewriting large parts of the code, so I think coding something from scratch is the best option right now.

So, that's it. If you use Ark and find a bug, please report it anyway as I will fix what is simple, and if it's not a simple fix, at least it might give me some ideas for the new code. Also, please post in Ark your wishlists for KArchiver. If you don't know it already, the Right Place(tm) to report bugs and wishes is here.

First let me tell you that Brasil Telecomm rules. They installed my ADSL connection two days ago, while the "promise" was to install early next week. Good work guys! :-)

Another milestone today was the fact that this is the first time ever that I managed to log into my advogato account on the very first attempt! (I always had to try two or three times to remember this bloody password! I'm going to change it now :)

Well, I spent most of the night porting kojima's libraptor to KDE. He insisted that I used his own library instead of porting, but the new lib is much more KDE-friendly now... also, he used a lot of STL, something that we are not very fond of in KDE.

My new box is working fine. It's a PIII 900MHz. I wish I could have afforded that juicy Athlon 1.2GHz but money is short currently :-/

The only thing that did not work was that bloody PCTel modem, but this is not a real problem since Brasil Telecomm has promissed me they'll install my ADSL connection early next week.

Meanwhile, I am back at porting Synaptic to KDE. I am also modifying it now to allow me to try an idea I have had for a KDE installer/upgrader:

Synaptic theoretically would work in any RPM- and DEP-based distribution, covering almost every big distribution in the market (Slackware would be out, I guess). When the user launches the Synaptic-base KDE installer, it will check which distro the user is running and send this information to a server (something like install.kde.org). In the server, a simple daemon responds with the appropriate Apt package source corresponding to the user distro. This would have the great advantage of freeing our bandwidth, since we would point to a source from the distro vendor. Also, it would allow distributions to more easily update their own packages everytime they need to do so.

18 older entries...