Simple pattern formation with cellular automata

A cellular automaton is a dynamical system where space, time and dynamic variable are all discrete. The system is thus composed of a lattice of cells (discrete space), each described by a state (discrete dynamic variable) which evolve into the next time step (discrete time) according to a dynamic rule.
x_i^{t+1} = f(x_i^t, \Omega_i^t, \xi)
This rule generally depends on the state of the target cell $x_i^t$, the state of its neighbors $\Omega_i^t$, and a number of auxiliary external variables $\xi$. Since all these inputs are discrete, we can enumerate them and then define the dynamic rule by a transition table. The transition table maps each possible input to the next state for the cell. As an example consider the elementary 1D cellular automaton. In this case the neighborhood consists of only the 2 nearest neighbors $\Omega_i^t = \{x_{i-1}^t, x_{i+1}^t\}$ and no external variables.

In general, there are two types of neighborhoods, commonly classified as Moore or Von Neumann. A Moore neighborhood of radius $r$ corresponds to all cells within a hypercube of size $r$ centered at the current cell. In 2D we can write it as $\Omega_{ij}^t = \{x^t_{kl}:|i-k|\leq r \wedge |j-l|\leq r\}\setminus x^t_{ij}$. The Von Neumann neighborhood is more restrictive: only cells within a manhattan distance of $r$ belong to the neighborhood. In 2D we write $\Omega_{ij}^t = \{x^t_{kl}:|i-l|+|j-k| \leq r\}\setminus x^t_{ij}$.

Finally it is worth elucidating the concept of totalistic automata. In high dimensional spaces, the number of possible configurations of the neighborhood $\Omega$ can be quite large. As a simplification, we may consider instead as an input to the transition table the sum of all neighbors in a specific state $N_k = \sum_{x \in \Omega}\delta(x = k)$. If there are only 2 states, we need only consider $N_1$, since $N_0 = r – N_1$. For an arbitrary number $m$ of states, we will obviously need to consider $m-1$ such inputs to fully characterize the neighborhood. Even then, each input $N_k$ can take $r+1$ different values, which might be too much. In such cases we may consider only the case when $N_k$ is above some threshold. Then we can define as an input the boolean variable

1& \text{if $N_k \geq T$},\\
0& \text{if $N_k < T$}.

In the simulation you can find here, I considered a cellular automaton with the following properties: number of states $m=2$; moore neighborhood with radius $r=1$; lattice size $L_x \times L_y$; and 3 inputs for the transition table:

  • Current state $x_{ij}^t$
  • Neighborhood state $P_{1,T}$ with $T$ unspecified
  • One external input $\xi$\begin{equation}
    1& \text{if $i \geq L_x/2$},\\
    0& \text{if $i < L_x/2$}.
  • Initial condition $x_{ij} = 0 \; \forall_{ij}$

For these conditions a deterministic simulation of these conditions yields only a few steady states: homogeneous 1 or 0, half the lattice 1 and the other 0, and oscillation between a combination of the previous.

One possibility would be to add noise to the cellular automaton in order to provide more interesting dynamics. There are two ways to add noise to a cellular automaton:

The most straightforward way is to perform the following procedure at each time step:

  • Apply the deterministic dynamics to the whole lattice
  • For each lattice site $ij$, invert the state $x_{ij}$ with probability $p$

This procedure only works of course for $m=2$. In the case of more states there is no obvious way to generalize the procedure and we need to use a proper monte carlo method to get the dynamics.

A second way is to implement a probabilistic cellular automaton. In this case the transition table is generalized to a markov matrix: each input is now mapped not to a specific state but rather to a set of probabilities for a transition to each state ($m$ probabilities). Naturally for each input these sum to one. In this case we have $m$ times more parameters than before.


So it was time to update the visual of this blog, as the default twenty twelve wordpress theme was starting to show its age. I started finding it visually boring a few months ago and the fact that it is not a responsive design let me to decide that a redesign was in order. My original idea was to just create a new responsive template using foundation, but after some research it turns out creating a wordpress there is quite an involved process. Not only would I have to create all the theming HTML/CSS, I’d also have to integrate them in the necessary PHP code scaffolding. As most tasks that require a significant time investment, I put this off indefinitely.

Luckily a few weeks back with a new wordpress came a new default theme, twenty thirteen. This is a nice responsive theme which places visual emphasis on the actual posts with larger fonts and no cumbersome sidebar (all that stuff is now in the footer, which is a great idea). This meant I only had to edit the CSS to get something which fulfills my requirements and has at least some identity.

The process started by creating a child theme. Since I am quite happy with the base layout, all I needed to do was to edit the colors to my heart’s content. Like all color challenged engineers I had to resort to some cheating. The usual place to cheat is to pick a pallete from colourlovers; but I find it is still an overwhelming experience. There is still simply too much to choose from. What I need is a very constrained set of good looking colors. To the rescue: flatUI colors. I picked the midnight blue as the main color for the header as a nod to the visual design my homepage had during my teenage years (nostalgia time). Then I desaturated it for the other blues I needed. For some contrasty accents, I went with the alizarin, which is also a pretty cool name for a color. Here is the pallete I built:

Midnight blue
Random blue #1
Random blue #2

Even though a real graphic designer is probably appalled by these choices, I’m pretty proud of how the visuals turned out. I have recently started paying more attention to design, which I think is an often overlooked area by scientists and engineers. It is already hard enough to communicate our work to a wide audience  and boring designs aren’t helping one bit.

Using Beautiful Soup to convert Springpad notes to Evernote

A few months back I decided to migrate all my work notes from springpad to evernote because I found evernote more robust and simpler. I still keep my recipe collection on springpad though! Looks yummy.

Anyway, surprisingly there were some scripts going from evernote to springpad but not the other way around, which is a bit suprising because both services use a sort of HTML notation to export their notes so it’s pretty simple to convert notes from one format to another. So I used the nice python library Beautiful Soup to parse the HTML and convert it to the other format.

With evernote it’s a bit tricky to get it to accept everything because any noncompliant HTML entity throws off the whole process, but after some trial and error I managed to fix it. As an aside, if you want a bit more power when editing your evernote notes, this service lets you directly edit the HTML of any note. It comes in pretty handy when you clip something from the web and it comes nested in some crazy divs. I hope evernote’s HTML format will not change too much in the near future and this script will stay helpful. In any case the header contains the evernote client version at the time, so I hope even if it changes they will recognize/honor the old version. Find the code after the jump.

Continue reading “Using Beautiful Soup to convert Springpad notes to Evernote”

SASS is awesome and you should use it

Trying to fix some bugs in the mobile layout for prospicious I realized the stylesheets had become an unmaintainable mess. So I converted the codebase to use SASS which was a bit of a pain because I had to convert well over 800 lines by hand. Luckily though there is backward compatibility so I could leave many classes untouched. However monstrosities like

can be simplified by the use of mixins, essentially the SASS version of macros:

By using mixins and variables you can avoid the annoying repetition of property blocks so common in large stylesheets. Better, by defining global variables you can iterate properties such as colors quickly, without constantly using find and replace, which is extremely useful when you’re at the prototyping stage of your app.

I found SASS via foundation, the responsive css framework I used for prospicious. They suggest the use of SASS in conjunction with compass which is a css authoring framework. I tried playing around with it but creating a new project resulted in an insane project hierarchy in the filesystem with html files and asset directories when all I wanted was one folder with sass files and one with css to integrate in my existing project.

This appears to be a problem in general with frameworks, they try to do everything for you and you end up with a bloated code base with hundreds of unused lines of code. Foundation is modular enough that you can just pick whichever parts of it you want in your code and not include the rest. Perhaps compass offers this as well but I couldn’t immediately find it so I stuck with ‘normal’ SASS and a handmade folder structure which served me well.