Older blog entries for maragato (starting at number 38)

24 Jun 2011 »

Fighting the IT overlords

Years ago, I needed an external direct Internet connection out of a lab. The first solution was to call a broadband provider and install a DSL line, but the IT department was trying to stop labs from adding more such external lines and started pushing its own solution.

Setting it up was complex because the people working on the infrastructure had never heard of this. I believe I was their Guinea Pig. As well, requesting changes was always difficult because it required second level support and the first level staff didn’t know what I was talking about.

One day I decided to document the process to help future generations. For my own amusement, I started writing it as a letter for “future occupants of the lab” where I detailed this big mistery of our ongoing, silent war against a dreadful enemy: the IT department. Later, when I was moving to a different job, I added other things to that document that I thought important in the day to day operations of a lab like that. The final document was nearly 100 pages long and had this cover page saying “To the future lurkers of Roberto’s Lair.” I did re-read the document a couple of years after I left that job and found it in some archive. It was poorly written, filled with typos and with fragrant errors. But I had fun writing it.

That was many, many moons ago.

Recently I had an exchange with someone online. The guy said he thought my name was familiar but we ended up not figuring out where he might know me from. Until today.

From:

Sent:

To:

Subject:

Robert

I knew I knew you! I had to check it to make sure I was right and I think I was. Aren’t you the guy who wrote the document about the IT overlords? We have two copies of that document here with lots of annotations bt we still use them. I need to scan and send them to you.

[REDACTED]

I’d love that.

Syndicated 2011-06-24 19:48:11 from robteix.com

21 Jun 2011 »

Anagramizer, a simple anagram solver in Go

This weekend I took the family to celebrate Father’s Day away from town. We went around getting to know parts of the province we live in and never been to.

We came back yesterday and the plan today was for a nice, calm day at home (it’s a holiday of some sort here.) Then I got engaged in a game called Hanging with Friends, a mix of the traditional hangman with a bit of Scrabble.

Since English isn’t my first language, I have a limited vocabulary, which leaves me at a disadvantage against my English-speaking friends. I can handle the “hangman” part of the game where I have to guess the word my friends come up with; but when it becomes “Scrabble” and I’ve got to form words using only a given set of letters and still make them difficult enough that a native English speaker will have problems figuring them out, then it’s tough.

An itch that needed some scratching. Enter Anagramizer.

When I woke up this morning, I decided to write a little program to help me. You call it cheating, I call it having a bit of nerd fun.

Being that I’m currently in love with Go, I decided to write in that language and it was really easy and quick to do it. It took me about half an hour to write the program that did what I needed. But then…

I succumbed to the temptation and started adding bells and whistles. Admittedly it was mostly for my own amusement and trying stuff in Go, but by the time we were leaving for lunch, the program had more options than the KDE audio volume utility (see what I did just there?)

I decided to make it available to anyone who wants to play with it. It served its purpose of entertaining me for about half a day

It’s now available on Github and released under a BSD licence.

Syndicated 2011-06-21 00:18:27 from Roberto Teixeira's blog

14 Jun 2011 »

Euler 9 in Go

This was surprising to me. For fun I picked one of the Euler algorithms I played with in the past and rewrote it in Go. The idea was to rewrite it idiomatically to see how different things might look. Nothing else. The very first thing I did was to get the exact algorithm and rewrite, no idiomatic changes.

package main
 
import "fmt"
 
func isTriplet(a, b, c int) bool {
        return a * a + b * b == c * c
}
 
func main() {
        for a := 1; a < 1000; a++ {
                for b := a + 1; b < (1000 - a) / 2; b++ {
                        c := 1000 - a - b
                        if isTriplet(a, b, c) {
                                fmt.Println(a * b * c)
                                return
                        }
                }
        }
 
}

What surprised me is that this thing runs in 0.005s, which is faster than the Python implementation and very close to the one in C. It surprised me because this wasn’t really supposed to happen. The Go compiler isn’t well optimized, especially compared to compilers with a many-years headstart.

Syndicated 2011-06-14 15:30:06 from Roberto Teixeira's blog

13 Jun 2011 »

How to set up Emacs on Windows

Just so I have it documented somewhere for future reference, here’s how to quickly set GNU Emacs up on Windows.

Download it from http://ftp.gnu.org/gnu/emacs/windows/
Unzip it to, say, C:\emacs or something like that
Set the environment variable HOME to C:\emacs and include C:\emacs\bin to the PATH
If you want to have a “Open with GNU Emacs” option on the context menu, just create a registry file (call it emacs.reg or whatever.reg) with the contents below and double-click it to import it into the registry.

REGEDIT4
[HKEY_CLASSES_ROOT\*\shell]
 
[HKEY_CLASSES_ROOT\*\shell\emacsmenu]
@="Open with &GNU Emacs"
 
[HKEY_CLASSES_ROOT\*\shell\emacsmenu\command]
@="C:\\emacs\\bin\\runemacs.exe \"%1\""

Et voilà! As well, for my preferred colour scheme, we need to use color-theme from http://www.nongnu.org/color-theme/ and set it up in your .emacs file:

(add-to-list 'load-path "c:/emacs/.emacs.d")
(require 'color-theme)
(color-theme-initialize)
(when (display-graphic-p)
  (color-theme-subtle-hacker)

Syndicated 2011-06-13 18:38:49 from Roberto Teixeira's blog

11 Jun 2011 »

Best closing line ever

I didn’t get to watch the Golden Globes ceremony. To be honest, it’s not really the kind of show I enjoy. But completely by chance I tuned in right at the very end, when host Ricky Gervais said the show was over and started his own thanks. And he closed with –

And thank you god for making me an atheist.

While my facial muscles were still working of forming the smile, my head was already wondering how the quote would sit with some of the theists who would be watching. I immediately started a search on Twitter and the very first tweet I found was –

“TY God for making me an atheist” now that was just bad taste!

The tweets that followed were more or less equally divided between those very similar to the one above and others agreeing with me that this was the best closing line ever.

I wonder how you can possibly consider it bad taste though. I mean, if you’re an atheist, the quote is just funny. If, however, you believe in a god, then he’s just thanking it for something. He might as well have said, “thank you god for making me a comedian.”

You can’t really have it both ways. Either god doesn’t exist or god exists and made Ricky Gervais an atheist. Actually, there are other alternatives, but the people who would be offended belong to the team that believes in a personal god who does this kind of things.

Syndicated 2011-01-17 17:30:18 from Roberto Teixeira's blog

11 Jun 2011 »

That’s how you make atheists

A recent Pew poll in the US shows that agnostics and atheists seem to know more about religion than the rest of the population. That’s not really a big surprise as previous similar polls shows similar results.

But even if it’s not a big surprise, it can still seem strange to many. To me, the best explanation I’ve been able to come to is beautifully summarized by American Atheists’ president Dave Silverman, for the New York Times:

I have heard many times that atheists know more about religion than religious people. Atheism is an effect of that knowledge, not a lack of knowledge. I gave a Bible to my daughter. That’s how you make atheists.

CNN has a test with 10 questions from the survey. I can’t tell if those are the easiest ones or randomly picked, but I found it extremely easy. Got 10 out of 10 right.

Syndicated 2010-09-28 15:44:26 from Roberto Teixeira's blog

11 Jun 2011 »

Euler 15 in Python

This one isn’t even funny…

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

Your first thought would be to generate the routes, but for a 20×20 grid, those amount to BILLIONS and you’d try to do it recursively too! Forget it.

But if you have some CompSci-level math background, though, you’ll remember this one–reading The Art of Computer Programming, Vol. 4 also helps. It’s a matter of combinatorics and if we take w for the width and h for the height, all we need to do is calculate,

$\frac{(w + h)!}{w!h!}$

and that’s it. I didn’t even write a program for this, instead using Python’s interactive shell, but just for the same of completeness, here’s a “program” to calculate the possibles paths in a 20×20 grid.

1
2
3

import math
w = h = 20
print math.factorial(w + h) / (math.factorial(w) * math.factorial(h))

That’s it.

Syndicated 2010-08-07 22:39:27 from Roberto Teixeira's blog

11 Jun 2011 »

Euler 11 in Python

Project Euler’s problem #11 statement goes:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is .

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

This one is remarkably easy but also was quite fun. I think it’s because it reminds me of the kind of work we’d do during our Algorithms classes during my first year in college. And so this one goes to my Algorithms teacher, Ricardo Vargas Dornelles—best teacher I’ve ever had too.

import operator
numbers = [[8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8],
[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0],
[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65],
[52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,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,3,45,2,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,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],
[24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
[21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95],
[78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92],
[16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57],
[86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58],
[19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40],
[4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66],
[88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69],
[4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],
[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16],
[20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54],
[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]
 
maxp = 0
for row in range(0,16):
        for col in range(0,16):
                maxp = max(maxp, reduce(lambda x,y: x*y, \
                                        [n for n in numbers[row][col:col+4]]))
                maxp = max(maxp, numbers[row][col] * numbers[row + 1][col + 1] * \
                                 numbers[row+2][col+2] * numbers[row+3][col+3])
                maxp = max(maxp, reduce(lambda x,y: x*y, \
                                        [n[col] for n in numbers[row:row+4]]))
                if col > 3:
                        maxp = max(maxp, numbers[row][col] * \
                                         numbers[row + 1][col - 1] * \
                                         numbers[row+2][col-2] * \
                                         numbers[row+3][col-3])
 
print maxp

As well, this runs in 0.020s, so not bad at all.

Syndicated 2010-08-06 17:19:56 from Roberto Teixeira's blog

11 Jun 2011 »

Euler 10 in C++

The other night I took on Project Euler’s problem #10. The problem statement went like this:

The sum of the primes below 10 is .

Find the sum of all the primes below two million.

I went with Python and you can find the result here. I just rewrote the exact same algorithm using C++ and Boost, just for fun.

#include <iostream>
#include <cmath>
#include <boost/dynamic_bitset.hpp>
using namespace std;
 
unsigned long long prime_sum(int limit)
{
        if (limit < 2) return 0;
 
        long sieve_size = ceil(limit / 2);
        boost::dynamic_bitset<> sieve(sieve_size);
        unsigned long long sum = 2;
 
        sieve.flip();
 
        for (unsigned int i = 0; i < floor(sqrt(limit) / 2); i++) {
                if (!sieve[i])
                        continue;
                for (int j = (i * (i + 3) * 2) + 3; j < sieve_size; j += (i * 2) + 3)
                        sieve[j] = 0;
        }
 
        for (unsigned int i = 0; i < sieve_size; i++)
                if (sieve[i])
                        sum += (i * 2) + 3;
 
        return sum;
}
 
 
int main(void)
{
        cout << prime_sum(2000000) << endl;
        return 0;
}

Runs in 0.019s.

Syndicated 2010-08-06 15:46:32 from Roberto Teixeira's blog

11 Jun 2011 »

Euler 10 in Python

I decided to take on Project Euler’s problem #10. Its statement goes like this:

The sum of the primes below 10 is .

Find the sum of all the primes below two million.

My first attempt used brute force and testing primality using only previously found primes:

primes = []
 
def is_prime(n):
        if not (n < 2 or any(n % x == 0 
           for x in filter(lambda x: x < math.ceil(n ** 2), primes))):
                primes.append(n)
                return True
        return False
 
sum_primes = 0
n = 1   
while n < 2000000:
    if (is_prime(n)):
        sum_primes += n
    n += 1  
print sum_primes

It worked if you consider an execution time of over 7 minutes reasonable. Clearly a bad solution. So I decided to rethink it a bit and tried again. This time, I decided to use a little creative thinking. For every number I tested for primality, I took the time to mark its multiples as not primes (when I first test, say, 3, I already know that 6, 9, 12, ... n * 3 < 2000000 will not be a prime numbers, so I don’t have to test their primality later.)

max_primes = 2000000
numbers = [0] * max_primes
 
def is_prime(n):
        if n <= 2:
                return True
        if numbers[n] == 1:
                return False
        c = 2
        m = 0
        while True:
                m = n * c
                if m < max_primes:
                        numbers[m] = 1
                else:
                        break
                c+= 1
 
        #if any(n % x == 0 for x in xrange(2, int(n ** 0.5) + 1)):
        i = 2
        while i < int(n** 0.5 + 1):
                if n % i == 0:
                        return False
                i += 1
 
        numbers[n] = 1
        return True
 
def sum_primes():
        soma = 0
        for i in range (2, max_primes):
                if is_prime(i):
                        soma += i
        return soma
 
print sum_primes()

This is a much better algorithm and it gave the correct result in 54 seconds. Project Euler has a “one-minute rule”, which state that all its problems should be solvable “on a modestly powered computer in less than one minute,” which means the solution applies. Still, it’s a brute force solution and I wanted a better one.

So today I picked my copy of Concrete Mathematics and read about primes. Honestly, I’ve been reading more about primes lately than I even thought I would.

Anyways, Knuth—yes, I know the book has three authors, but I can’t help thinking of it as a Knuth book—talks about several strategies to test primality, but it also mentions sieve algorithms that are used to generate lists of prime numbers. Exactly what I wanted!

def prime_list(limit):
        if limit < 2:
                return []
        sieve_size = limit / 2
        sieve = [True] * sieve_size
 
        for i in range(0, int(limit ** 0.5) / 2):
                if not sieve[i]:
                        continue
                for j in range((i * (i + 3) * 2) + 3, sieve_size, (i * 2) + 3):
                        sieve[j] = False
 
        primes = [2]
        primes.extend([(i * 2) + 3 for i in range(0, sieve_size) if sieve[i]])
 
        return primes
 
print reduce(lambda x,y: x+y, prime_list(2000000))

Et voilà! Correct result in 0.456s! The code is based on the description of the Sieve of Eratosthenes found in Concrete Mathematics. Also interesting to note, my idea in the second algorithm above is actually the basis of this sieve algorithm, I was just thinking “backwards.”

Syndicated 2010-08-06 01:07:00 from Roberto Teixeira's blog

29 older entries...