CIS 554 Haskell: Percolation
Fall 2014, David Matuszek

Purposes of this assignment

General idea of the assignment

When it rains, water soaks into the ground. When sand grains are packed tightly, water doesn't soak as far down. Your task is to write a two-dimensional model of this situation.


Construct an NxN grid, that is, a square array. Populate the grid randomly with "sand" grains, such that each location has a sand grain with probability p, or is empty with probability (1-p).

"Water" arrives at the top of this array, so that every empty location in the first row becomes filled with water.

Water will only flow down or horizontally, never up. For each succeeding row, if an empty space has water directly above it, or horizontally adjacent to it, it also fills with water. At each move, water can flow any distance horizontally.

to to to to to
to to to to  

Write at least the following functions:

ground :: Int -> Float -> [[Int]]
ground n p returns a list of lists of integer, where each list is of length n, and each integer has probability p of being a sand grain, (1-p) of being empty (and no water initially). Use the encoding 0 = empty space, 1 = sand grain, 2 = water.
seep :: [Int] -> [Int] -> [Int]
seep row1 row2 causes water to flow from row1 into row2, yielding a new value row2'. In other words, this function performs one step of the simulation.
percolate :: [[Int]] -> Bool
Returns true if, after water has "seeped" as far as it can, water has reached the bottom row, and false otherwise. For the example above, the result would be true.

Some versions of percolation theory use the "bonds" (walls) between cells to be porous or not, so that the resultant array looks like a maze. Other versions treat the cells themselves as either porous or not. I felt the latter approach would be easier to work with.

You might think that the probability of water percolating all the way to the bottom would decrease as p (probability of sand grains) increases. And it does, but in an interesting and extremely nonlinear fashion.

Due date

Turn your assignment in to Canvas before 6am Wednesday, November 5.