the-game-of-life

An experiment in rule design for a cellular automata life simulator. This was my first major project in an introductory CS class at Reed College, for professor Jim Fix, fall 2014.

To learn more about Conway’s Game of Life, venture here: http://en.wikipedia.org/wiki/Conway’s_Game_of_Life.

Three files comprise this project:

Grid.py provides code for the Grid class which defines an object that performs the grid simulation. In it, the grid itself is defined, framed, and painted. Button inputs for the interact are also provided.

Life.py prints instructions for the user to navigate the demonstration of ten sequential rules on the grid.

Rules.py provides the code for ten different behavioral patterns. Rules 1 through 6 solve challenges ranging from pattern construction to image processing using the rules of the game of life, all according to the prompt of the assignment. Rules 7 through 10 are of my own devising, attempts to utilize the constraints of the game of life to render a comet, armageddon, a zombie invasion, and the growth of a weirwood tree.

Shadow, fill, glider, age, comet, zombie, and weirwood are accompanying pattern files used by the grid demo to simulate specific rule behaviors. Reed.pgm provides an image file of a photograph of Eliot Hall from Reed’s great lawn, also used in one of the image processing rules.

To run the simulation, unpack the files to your desktop. From Terminal, enter:

python3.4 life.py

A window will appear with a grid laid out and instructions at the top. Press ‘space’ to step through each evolution of the active rule set, or ‘enter’ to watch the rule evolve rapidly through to its conclusion. Press ‘q’ to close the window and open the next window with the next rule (as enumerated in life.py) activated.

Note: when grabbing the window to execute the commands, avoid placing your cursor directly over the rules text, as this will cause any commands you enter to write directly to that space. Instead, just grab the window by its task bar at the very top.

You can find all game-of-life files here.

thesis-grammar

An object-oriented design of a context-free grammar to model natural language.

Three files comprise this project. Grammar.py designs a Grammar class that has the ability to parse through a grammar file, apply a given rule set to its data, and generate a subsequent output based on those rules.

For example, this could be the beginning of a grammar file for an English sentence:

< sentence > ::= < noun_phrase > < verb >
< noun_phrase > ::= < proper_noun >
< noun_phrase > ::= < article > < noun >
< noun_phrase > ::= < article > < adjective > < noun >
< article > ::= THE
< article > ::= A
< noun > ::= COW
< noun > ::= FOX
< adjective > ::= BROWN
< adjective > ::= LAZY
< verb > ::= JUMPS
< proper_noun > ::= ZAK

A successful Grammar class could, when called to generate any of a number of statement types from this grammar list, cycle through its contents to create a randomly generated, grammatically correct sentence such as “The lazy fox jumps,” or “A brown cow jumps.”

According to my design, the Grammar class cycles through a grammar file that contains all possible elements of hundreds of different thesis statements for a freshman Humanities 110 paper, generating in its output a successful argument about ancient literature.

Here is the code for the primary Grammar class:

class Grammar:

    # init
    #
    # Initializes a grammar. If specified, 'start' is used as 
    # the start string for a derivation performed by the
    # 'generate' method below.
    #
    # This is called when the instructor is invoked, for example
    # in the code
    #
    #   Gr = Grammar('')
    #
    def __init__(self, start_string=None):
        pass
        self.start = start_string
        self.rules = { }

    # read
    #
    # Reads a grammar from a file with the given name.
    #
    def read(self, filename):
        file = open(filename,'r')
        line = file.readline()[:-1]
        while line != '':
            syms = line.split(' ')
            lhs = syms[0]
            rhs = ' '.join(syms[2:]) 
            self[lhs] = rhs
            line = file.readline()[:-1]

    # setitem
    #
    # Adds a production to the grammar, one of the form:
    #
    #    var ::= rhs
    #
    # var should be a variable string
    # rhs should be a string of variables and terminals
    #
    # This method is invoked when a 'component assignment'
    # is used in code, for example
    #
    #   Gr[''] = ' '
    #

    def __setitem__(self,var,rhs):
        
        # check to see if the left hand value (var) is already in the rules dictionary
        if var in self.rules:
            # append the new rhs to the var key
            self.rules[var].append(rhs)

        # if var is not in the dictionary...
        else:
            # create a new entry for it
            self.rules[var] = [rhs]


    # getitem
    #
    # Returns the right-hand side of a production for the variable.
    # If there are several productions whose LHS is var, then one
    # is chosen at random.
    #
    # var should be a variable string
    #
    # This method is invoked when a 'component access' is expressed
    # in code, for example
    #
    #   Gr['']
    #
    # might return the string ' '
    #

    def __getitem__(self,var):

        # check to see if the entry exists in the dictionary
        if var in self.rules:
            # then supply a random element from its list
            RHSs = self.rules[var]
            rlen = len(RHSs)
            r = int(random() * rlen)
            return RHSs[r]
        else:
            return var

    def generate(self):
        
        next = self.start
        last = None
        # repeatedly apply grammar to some expanded string
        while next != last:

            last = next
            next = self.applyTo(next)

        return next

    # applyTo
    #
    # Give back a string that results from applying some Grammar
    # production to each of the variables that occur in the 
    # string.
    #

    def applyTo(self,derived_string=None):
        
        # generates a new string extracted according to the application
        # of a given grammar rule
        new_array = derived_string.split(' ') 
        l = len(new_array)
        for i in range (l):
            new_array[i] = self[new_array[i]]

        new_string = ' '.join(new_array)
        return new_string

To test, open thesis.grm, Grammar.py, and thesis.py, and then execute thesis.py in your command line.

You can find all thesis-grammar files here.

convex-hull

An algorithm for cycling through the most exterior coordinates with respect to the area mapped by an array containing randomized points in a two-dimensional plane.

The challenge: when given a randomized series of points contained within an array, create a function that contains all coordinates by painting lines to connect only the most exterior points.

For this exercise, I use the “SwamPy” Turtles Graphics package, written by Allen Downey and found here.

My solution: I begin by creating a function for the Turtle class to compare two points within a Cartesian plane and return a numeric value that communicates the comparative position of both. I then build my primary convex hull algorithm in the form of a function, corral:

def corral(self,points):
    self.save()

    for p in points:
        self.move_to(p)
        self.mark()

    # FIND THE FIRST POINT ON THE HULL
    p0 = min(points)
    self.move_to(p0)

    self.down()

    # create two variables to compare points, with
    # p being the turtle's starting location
    p = p0
    q = 0

    # begin cycling through the hull
    while q != p0:

        # look at each point other than the turtle's current position...
        for x in points if x != p:

            # ...and compare turns from current position to find the next
            # point along the hull.
            if self.assess_turn(p,x) == -1:

                # assign q the point that is leftmost
                q = x

        # draw to that point
        self.move_to(q)

        # update the turtle's position p by changing
        # it to be q
        p = q

    self.up()
    self.restore()

You can venture here for a complete file set to run the algorithm.

drawing-with-turtles

A series of python exercises to explore constructing 2D images, iteratively and recursively. Completed in a CS class with Professor Jim Fix at Reed College, 2014.

In this assignment, I write the file turtle_draw to work through a series of drawing challenges using a Turtle object that constructs a Turtle Pen on a canvas. An instantiated Turtle can change direction (angles measured in degrees), shift its pen to be on or off the canvas, and move forward a given number of units.

Exercies 1 through 8 present challenges to create functions that draw specific images when given various parameters. As an example, below is the function for exercise 8, the Koch Snowflake (http://en.wikipedia.org/wiki/Koch_snowflake) constructed recursively.

def snowflake(turtle,n,l):

    turtle.pd()

    # ok, so I definitely need a helper function to do the work
    # of constructing one of the three legs. Each iteration of the
    # snowflake will be of variable complexity, but all versions
    # will have only three faces. I'll put the work of recursively
    # constructing increasingly complex versions of only one of the 
    # faces here, then rotate and do it again, two more times below.
    
    def snowflakeHelper(turtle,n,l):

        # base case
        if n == 0:
            turtle.fd(l)

        # call it again with increasingly tinier legs
        else:
            snowflakeHelper(turtle,n-1,l/3)
            turtle.lt(60)
            snowflakeHelper(turtle,n-1,l/3)
            turtle.rt(120)
            snowflakeHelper(turtle,n-1,l/3)
            turtle.lt(60)
            snowflakeHelper(turtle,n-1,l/3)

    # and here, do the work of building three faces total with 120
    # degree hinges
    for i in range(3):
        snowflakeHelper(turtle,n,l)
        turtle.rt(120)

You can find all drawing-with-turtles files here.

To test, un-comment out whatever line of the test cases you want to see displayed in your terminal display, and run turtle_draw.py.