I have a new garden. You can visit it at my “homepage” (how long since I’ve used that word!) on http://dealmeida.net/. And when visiting the page you will plant a flower.

The garden is actually inspired in an old project I did back in 2004, when I moved to Holland. I was impressed by the weather in Utrecht, so I wrote a Python script that grabbed the local temperature and used it to evolve a garden of cellular automata flowers:

The idea was based on James Lovelock’s Daisyworld model, and it had two interesting consequences: first that it acted as a fuzzy thermometers, since darker flowers would dominate in cold weather, and lighter flowers would prevail in warmer weather; second, it had the emergent property of acting like a greenhouse, stabilizing the temperature so that it was warmer in the garden in winter, and colder during summer.

This week I created a new garden for my homepage. Instead of using Python I create a page-sized canvas element, and I draw the flowers using Javascript. The flowers are stored in a JSONStore database, which stores the flowers' DNA and their location on the canvas. The DNA has 7 genes, stored as 8 bytes, that describe each flower’s shape and color.

When a person visits the page a new flower is added. The new flower is created by randomly selecting two parents, weighting the selection by the efficiency of each flower. The efficiency is a function of the temperature and humidity at Cachoeira Paulista, where I live. As in my old model, darker flowers do better in colder weather, while the opposite is true for lighter flowers. This time I also use humidity: drier weather favors “spikier” flowers, inspired by how leaves tend to become pointier in drier regions in order to avoid losing too much water. I’m not sure of how scientific this is, but it gives more variability to the evolution of the garden.

The new flower is drawn first with a white outline, so you can see it. It should stay there for a while; flowers are only killed when their efficiency is below zero, which happens for temperatures outside the range of 5 and 40 degrees C. There’s also a limit of 200 flowers. When the limit is exceeded flowers are randomly removed based on their efficiency. This means your flower should stay for a while.

PythonBrasil [7]

I just left São Paulo today, after 3 days at the PythonBrasil [7] meeting (which should really be called PythonBrasil [6], since it's the seventh event!). The meeting was great, as always — I met good friends, made some new ones, talked to *very* smart people, showed my JSONStore module and even made a presentation of the Spanish Inquisition sketch! =D

I also wanted to visit the Garoa Hacker Club, but today I had lunch with my formed PhD advisor, Rein, and his wife Claudia. After that I got a ride to Ubatuba, where we start a Summer School Continent–Ocean interaction tomorrow.

This is a solution to this problem:

A drunken sailor returns to his ship via a plank 15 paces long and 7 paces wide. With each step he has an equal chance of stepping forward, left, right, or standing still. What is the probability that he returns safely to his ship?

The article shows two different solutions, one using a Monte Carlo approach and the other, Markov chains. The Monte Carlo approach is pretty trivial; here’s how I did it using Python:

def walk():
    pos = array([4, 0])
    while 1:
        if pos[1] == 16:
            return True
        elif not 0 < pos[0] < 8:
            return False

        pos += choice([
                array([ 0, 1]),  # forward
                array([ 1, 0]),  # right
                array([-1, 0]),  # left
                array([ 0, 0]),  # still
                ])

This is our random walk. We keep updating the position of the sailor until he either reaches the ship of falls into water. We can estimate the chance that the sailor will reach the boat by running this function several times and counting the percentage that returns True:

REALIZATIONS = 10000
successes = 0
for i in range(REALIZATIONS):
    if walk(): successes += 1
print float(successes)/REALIZATIONS

For 10 thousand realizations I get a probability of 12% that the sailor can cross the plank. But I’m more interested in the Markov chain solution. The idea behind this solution is to create a matrix of the probabilities of going from a place A to a point B. In order to do this I create an array of shape (7+2, 15+1, 7+2, 15+1). This array includes two additional side points, for water, and one additional point along the plank, representing the boat. In this array, the value at the position (i0, j0, i1, j1) represents the probability of a person at point (i0, j0) going to the position (i1, j1). We start with an empty arrays of zeros:

WIDTH = 7
LENGTH = 15
markov = zeros((WIDTH+2, LENGTH+1, WIDTH+2, LENGTH+1), 'f')

Now let’s set the probabilities for the plank:

for i in range(1, WIDTH+1):
    for j in range(LENGTH):
        markov[i, j, i, j+1] = 0.25  # forward
        markov[i, j, i+1, j] = 0.25  # right
        markov[i, j, i-1, j] = 0.25  # left
        markov[i, j, i, j]   = 0.25  # still

So, if the sailor is in the point (i, j) inside the plank it has a 25% chance of moving to point (i+1, j), ie, to the right. We also set the probabilities for when the sailor is on the water; in this case, he will stay there:

# when in water, stay
for j in range(LENGTH+1):
    markov[0, j, 0, j] = 1
    markov[WIDTH+1, j, WIDTH+1, j] = 1

And we do the same when he reaches the boat:

# when in the ship, stay
for i in range(WIDTH+2):
    markov[i, LENGTH, i, LENGTH] = 1

We also reshape our array, making it 2D. It will still keep the probabilistic correspondence between point A and B, but now our space dimension has been turned into 1D:

markov.shape = ((WIDTH+2)*(LENGTH+1), (WIDTH+2)*(LENGTH+1))

The rest now is easy. The transition matrix we just built has the nice property that it represents the chance of going from one point to the other, and if we keep multiplying it by itself n times we have the chance of reaching point B after n steps from point A. So we just need to convert our array into a matrix (there’s a difference in Numpy) and take the power to a resonable number of steps:

MAXSTEPS = 200
result = matrix(markov)**MAXSTEPS
result = array(result).reshape(WIDTH+2, LENGTH+1, WIDTH+2, LENGTH+1)

What we want is the chance of a sailor leaving from point (4, 0) to reach the boat at any point in (i, 15). We can get this easily:

print sum(result[4, 0, :, 15])

And the result is 15%. Pretty cool.