The Roberto Selbach Chronicles

About |  Blog |  Archive

Category: Programming

FOR is evil or something

Have you ever wondered how FORs impact your code? How they are limiting your design and more important how they are transforming your code into an amount of lines without any human meaning?

How can you not want to read an article that starts like that? I had to steal the intro from the original. Seriously, I have used FOR since I learned BASIC back in the day. I never thought about how it was limiting my design. I. Must. Learn. How.

The article I am referring to is, Avoiding FORs – Anti-If Campaign. Eager learner I, I could not not read it.

After the resplendent intro, Avoiding FOR goes on to show “how to transform a simple example of a for […], to something more readable and well designed.”

It takes this unreadable piece of code — that I now recognize as unreadable:

[java]
public class Department {

private List resources = new ArrayList();

public void addResource(Resource resource) {
    this.resources.add(resource);
}

public void printSlips() {

    for (Resource resource : resources) {
        if(resource.lastContract().deadline().after(new Date())) {

            System.out.println(resource.name());
            System.out.println(resource.salary());
        }
    }
}

}[/java]

My eyes hurt already. Thankfully the author transforms the aberration above into this clean, much more readable snippet:

[java]public class ResourceOrderedCollection {

    private Collection<Resource> resources = new ArrayList<Resource>();



public ResourceOrderedCollection() {
    super();
}

public ResourceOrderedCollection(Collection<Resource> resources) {
    this.resources = resources;
}

public void add(Resource resource) {
    this.resources.add(resource);
}

public void forEachDo(Block block) {
    Iterator<Resource> iterator = resources.iterator();

    while(iterator.hasNext()) {
        block.evaluate(iterator.next());
    }

}

public ResourceOrderedCollection select(Predicate predicate) {

    ResourceOrderedCollection resourceOrderedCollection = new ResourceOrderedCollection();

    Iterator<Resource> iterator = resources.iterator();

    while(iterator.hasNext()) {
        Resource resource = iterator.next();
        if(predicate.is(resource)) {
            resourceOrderedCollection.add(resource);
        }
    }

    return resourceOrderedCollection;
}

}

public class Department {

private List<Resource> resources = new ArrayList<Resource>();

public void addResource(Resource resource) {
    this.resources.add(resource);
}

public void printSlips() {
    new ResourceOrderedCollection(this.resources).select(new InForcePredicate()).forEachDo(new PrintSlip());
}

}[/java]

Wait, what? Is this an Onion article?

Snarky Mode Off.

I understand what the author wanted to do, but really, the example used is so off the left field that it’s not even funny.

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.

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.

[go]
package main

import "fmt"

func isTriplet(a, b, c int) bool {
return a * a + b * b == c * c
}

func main() {
for a := 1; a &lt; 1000; a++ {
for b := a + 1; b &lt; (1000 – a) / 2; b++ {
c := 1000 – a – b
if isTriplet(a, b, c) {
fmt.Println(a * b * c)
return
}
}
}

}
[/go]

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.

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,

[latex size=“3”]frac{(w + h)!}{w!h!}[/latex]

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.

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

That’s it.

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 [pmath]26 * 63 * 78 * 14 = 1788696[/pmath].

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.

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 [pmath]2 + 3 + 5 + 7 = 17[/pmath].

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 [pmath]6, 9, 12, … n * 3 < 2000000[/pmath] 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.”

Euler 9 in C

So I recently wrote an ugly solution to Project Euler’s problem #9. It was written in Python and even though every other Project Euler solution I wrote ran in less than one second, this one took over 18 seconds to get to the answer. Obviously it’s my fault for using a purely brute force algorithm.

Anyway, boredom is a great motivator and I just rewrote the exact same algorithm in C, just to see how much faster it would be.

#include <stdio.h>

int is_triplet(int a, int b, int c)
{
        return (((a < b) && (b < c)) && ((a * a + b * b) == (c * c)));
}

int main(void)
{
        for (int a = 0; a < 1000; a++)
                for (int b = a + 1; b < 1000; b++)
                        for (int c = b + 1; c < 1000; c++)
                                if ((a + b + c == 1000) && is_triplet(a, b, c)) {
                                        printf("%d %d %d = %dn", a, b, c,
                                               a * b * c);
                                        return 0;
                                }
}

It’s the exact same algorithm, but instead of 18 seconds, it ran in 0.072s.

Update: And here’s the version suggested by Gustavo Niemeyer:

#include <stdio.h>

int is_triplet(int a, int b, int c)
{
        return ((a * a + b * b) == (c * c));
}

int main(void)
{
        for (int a = 1; a < 1000; a++)
                for (int b = a + 1; b < (1000 - a) / 2; b++) {
                        int c = 1000 - a - b;
                        if (is_triplet(a, b, c)) {
                                printf("%d %d %d = %dn", a, b, c,
                                       a * b * c);
                                return 0;
                        }
                }
}

It now runs in 0.002s :–)

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, $latex a < b < c$, for which,

[latex]a2 + b2 = c2[/latex]

For example, $latex 32 + 42 = 9 + 16 = 25 = 52$.

There exists exactly one Pythagorean triplet for which [pmath]a + b + c = 1000[/pmath].

Find the product [pmath]abc[/pmath].

Butt ugly, super slow, brute-force solution:

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: take a look at another take at this problem and algorithm.

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:

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.

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,

[pmath]12 + 22 + … + 102 = 385[/pmath]

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

pmath2 = 552 = 3025[/pmath]

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is [pmath]3025 – 385 = 2640[/pmath].

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.

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.

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.

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.