Good morning, and welcome to the first Software Carpentry lecture on program design. This episode will introduce our sample problem, invasion percolation.

Our goal in this lecture is to talk about program design…

…by which of course we mean the *principles* of program design.

Unfortunately, principles are very difficult to teach in the abstract…

…so instead, we're going to give you a few examples of program design.

And our first is called *invasion percolation*.

Suppose that you've got a fractured piece of rock…

…and you're interested in finding out how far pollution will spread through it.

One simple way to model this with a computer program is to create a two-dimensional grid of square cells…

…and fill those cells with random values.

Mark the center cell as being filled with pollutant…

…and then look at its four neighbors. The neighbor with the lowest value is the one that has the least resistance to the spread of the pollutant—in our case, the most highly fractured rock.

Mark that one as being filled…

…and look at the neighbors of the new filled region.

Find the one with the lowest value, and repeat the process over and over again.

If you have two cells on the boundary that are tied equal for the lowest value, pick one of them at random…

…and fill it in.

Continue this process until you reach the edge of the grid.

The fractal that results from this simulation will tell you about how far and how fast the pollutant would spread through the rock.

Of course, if you want to look at the statistical properties of these fractals, you need to do lots of simulation…

…on large grids.

That means your program has to be fast.

So in this lecture we will look at three questions. First, how do we do this at all?

Second, how do we tell that it's correct?

And third, how do we make it fast?

Thank you.