Category Archives: Uncategorized

  • 0

Random Invaders!

Category : Uncategorized

Last night at the Coder School in San Mateo a student and I found a cool site that showed how to create random Space Invaders-like graphics:

The 5×3 “invader array” would be filled in at random and then columns 1 and 2 would be copied or reflected across the center so invaders will all have lateral symmetry.

We had already done the “Atticus Clone” Random Art exploration so my student easily recognized the similarities. He made a class for an Invader and he already had the functionality for randomly filling in all 15 elements in the 3×5 array.

Those Awful Reflections

It wasn’t hard to get a list of 15 random 0’s and 1’s but how were we going to copy the terms and reflect them across the center? As a math guy, I was looking for patterns in the indices of the items to reflect and where to insert, but my lazy mind came up with an elegant solution!

Instead of trying to reflect elements of lists, I decided to flip the 5×3 grid into a 3×5 grid, with 3 lists of 5 elements each. That would make it a cinch to copy the lists and add the copies to another part of the array. Now if the array looked something like this:

blockList = [[1,0,0,1,1],
             [0,1,0,0,1],
             [0,0,1,1,1]]

I could easily add the second list to the end of the array, then add the first list. I’m copying each of those rows to the “gridList” which will be the 5×5 array. Then I’m copying/reflecting the first two lists starting with the second list and working backwards.

gridList = [[1,0,0,1,1],
            [0,1,0,0,1],
            [0,0,1,1,1],
            [0,1,0,0,1],
            [1,0,0,1,1]]

Notice the gridList has up-down symmetry. Here’s the code:

self.blockList = []
for i in range(2):
    self.blockList.append([])
        for j in range(5):
            self.blockList[i].append(choice([0,1]))
 #now copy the rows at the end to the beginning
 #rows 0,1,2,1,0
 for rownum in range(3): #for 0,1,2
     self.gridList.append(self.blockList[rownum])
 for rownum in range(1,-1,-1): #for 1,0
     self.gridList.append(self.blockList[rownum])

My next student wanted to make larger Invaders, so I generalized the code to make a grid of any size (“dim”).

self.blockList = []
for i in range(dim//2+1):
    self.blockList.append([])
        for j in range(dim):
            self.blockList[i].append(choice([0,1]))
 #now copy the rows at the end to the beginning
 #rows 0,1,2,3, ... n, ...,3,2,1,0
 for rownum in range(dim//2+1):
     self.gridList.append(self.blockList[rownum])
 for rownum in range(dim//2-1,-1,-1):
     self.gridList.append(self.blockList[rownum])

Now the reflection is fairly easy, and all I had to do was rotate the Invader so the copied rows became columns before drawing it. Just like the Atticus Clone sketch, I made a grid of randomly drawn Invaders:

All the code is on github. Have fun!


  • 0

Substitute Me for Him

Category : Uncategorized

I’ve been listening to a lot of songs by The Who lately, and even heard them play at the Outside Lands festival on Sunday night! They didn’t do “Substitute,” an early hit and one of my favorites, but the idea of substituting comes up a lot in Math. Sometimes you’re substituting a letter for a number or the value of a letter in one equation where you see the letter in another equation.

Today’s math challenge from the Center of Math’s Twitter post can be solved using substitution:

So there are two mystery numbers, represented by the letters x and y, which make the two equations work:

x + 1/y = 10

and

y + 1/x = 5/12

First we’ll solve for y:

y = 5/12 – 1/x

And we’ll substitute that value for y where we see y in the first equation:

x + 1/(5/12 – 1/x) = 10

To subtract 5/12 – 1/x we’ll need to get them over a common denominator, 12x:

x + 1/(5x – 12)/12x = 10

The reciprocal of (5x – 12)/12x is 12x/(5x – 12):

x + 12x/(5x – 12) = 10

Now we’ll add the terms on the left side by getting them both over a common denominator:

x(5x – 12) /(5x – 12) + 12x/(5x – 12) = 10

Multiply x by (5x – 12) and you get 5x2 – 12x.

(5x2 – 12x + 12x) /(5x – 12) = 10

Simplify the numerator and you’re left with

5x2 /(5x – 12) = 10

Multiply both sides by (5x – 12):

5x2 = 10(5x – 12)

Distribute the 10:

5x2 = 50x – 120

You’re left with a quadratic equation.

5x2 – 50x + 120 = 0

We can factor a five out of all three terms.

5(x2 – 10x + 24) = 0

5 times something is equal to zero so that “something” must be zero:

x2 – 10x + 24 = 0

The quadratic factors into

(x – 6)(x – 4) = 0

The solutions for x are

x = 6, 4

Remember y = 5/12 – 1/x, so we’ll plug in each value of x to get its corresponding value for y:

y = 5/12 – 1/(6) = 5/12 – 2/12

y = 3/12 or 1/4

When x = 4, y = 5/12 – 1/(4) = 5/12 – 3/12 = 2/12 = 1/6.

We check that both of those pairs work in the equations and they do. The values for x are 6 and 4.

Check by Graphing

But the problem asks for “all the possible values of x.” How do we know there are no other possible values? We could graph the original equations and see where they cross. I used the online grapher at geogebra.org. The first equation is in blue and the second is in pink:

This region is the only place where the blue and pink curves even get close to one another. We know they cross where x is 4 and 6. Let’s zoom in to those points:

There are our solutions: (4, 1/6) and (6, 1/4).

The Pythonic Way

I figured there had to be a way to use programming to come up with answers, so I created a couple of functions to return True if the two parameters, x and y, work in the equations:

def eq1(x,y):
    '''Returns True if x + 1/y = 10'''
    return x + 1/y == 10

def eq2(x,y):
    '''Returns True if y + 1/x = 5/12'''
    return y + 1/x == 5/12

Python 3 has no issues dividing integers like Python 2 did, so I checked a solution I knew would work in equation 1: x = 8 and y = 1/2.

>>> eq1(8,1/2)
True

But when I tried a similar one in the second equation, I was surprised to find it didn’t work:

>> eq2(1,-12/7)
False

Why is this? Let’s print out 1 – 7/12:

>>> 1 - 7/12
0.41666666666666663

Now let’s print out 5/12:

>> 5/12
0.4166666666666667

There’s a tiny rounding difference at the end of the decimals that will mean they’ll never be technically equal. But we can call them equal if they’re close enough to each other. We’ll use the absolute value of the left side minus the right side:

def eq1(x,y):
    '''Returns True if x + 1/y
    gets close to 10'''
    return abs(x + 1/y - 10) < 0.0001

def eq2(x,y):
 '''Returns True if y + 1/x
 gets close to 5/12'''
 return abs(y + 1/x - 5/12) < 0.0001

This works. Now we just need to go through a bunch of values between, say, -20 and 20. x will be the integers, and y will be the reciprocals, like 1/20, 1/19 and so on.

#try the numbers between -20 and 20
for x in range(-20,20):
    for z in range(-20,20):
        y = 1/z
        if eq1(x,y) and eq2(x,y):
            print(x,y)

However, this produces an error:

ZeroDivisionError: division by zero

We need to make sure we don’t use z = 0 because that makes y = 1/0 and you can’t divide by zero. A good thing to learn in Python is exception handling. We’ll “try” the process above, and if we run into the Zero Division Error, just go on to the next number.

#try the numbers between -20 and 20
for x in range(-20,20):
    for z in range(-20,20):
        #let y be the reciprocal of z
        try:
            y = 1/z
            if eq1(x,y) and eq2(x,y):
                print(x,y)
 #if we run into a dividing by zero
 #error, never mind and go on to the
 #next number
        except ZeroDivisionError:
            continue

Run this and it quickly prints out our solutions:

4 0.16666666666666666
6 0.25

I’m sure there are other ways to solve this problem, too!

Here’s a video of The Who singing Substitute at the Monterey Pop Festival in 1967:


  • 0

Coding for Encoding and Decoding

Category : Uncategorized

I read a quora answer from a grown up who learned about matrices years ago and even though he got through it he still doesn’t know what matrices are used for. In one word: Transformation. I’ve done videos on using matrices to transform points into other points and create 2D and 3D animations:

There’s another important field that concerns transforming letters into numbers and then transforming them back: cryptography (or is it cryptology? Or cryptanalysis?) You know: writing secret codes so others can’t read your message. The “Caesar Cipher” is the one we learned as kids: changing every letter to the letter before or after it, or if you’re really fancy, the letter 3 letters before it:

Cryptography has advanced somewhat in 2,000 years, and breaking the “replace every S with a Q and every E with an X” code has become a popular pastime in the puzzle section of the newspaper.

There’s a way to replace every letter with a corresponding number, but that doesn’t make the code any more complicated to break than the cryptoquote above.

That’s where matrices come in. You can put the numbers into a matrix and transform them into other numbers by multiplying them by a transformation matrix. Here’s how you multiply two 2×2 matrices together. The rows in the first matrix are multiplied by the columns in the second:

The first matrix can have as many rows as you want:

Here’s how to multiply two matrices, where the first one has two columns and the second one is a 2×2 matrix:

def multMatrix(a,b):
    '''Multiplies two matrices.
    b is a 2x2 matrix'''
    newmatrix = []
    for i in range(len(a)): # repeat for every row in matrix a
        newmatrix.append([])
        for j in range(2): #because b only has two columns
            newmatrix[i].append(a[i][0]*b[0][j]+a[i][1]*b[1][j])
    return newmatrix

The new numbers won’t make any sense until the designated recipient undoes the transformation with the inverse of your transformation matrix.

First we define our alphabet with a string.

alpha = ' abcdefghijklmnopqrstuvwxyz'

Every element in a string has an index, so that’s how we’ll replace a letter with a number:

nummat = []
msg = 'the kids are alright'
for n in msg: #go through every letter
    numlet = alpha.index(n) #replace the letter with its index
    nummat.append(numlet) #put the numbers in a list
    print(nummat) #print the list

It prints out a list of numbers:

[20, 8, 5, 0, 11, 9, 4, 19, 0, 1, 18, 5, 0, 1, 12, 18, 9, 7, 8, 20]

We want there to be only two columns, so if the length of the message is an odd number of letters, we’ll add a zero on the end (which is a space in our code). We can find the number of rows by dividing by 2, and fill that many rows with two numbers:

if len(nummat) % 2 != 0:
    nummat.append(0)
rows = len(nummat) / 2
letter_count = 0 #which letter are we on?
x = []
for i in range(int(rows)):
    x.append([])
    for j in range(2):
        x[i].append(nummat[letter_count])
        letter_count += 1

Finally, we multiply by our transformation matrix, which we’ll call ‘y.’

y = [[1,2],[-3,4]]
z = multMatrix(x,y)

This is the matrix we get out:

[[-4, 72],
[5, 10],
[-16, 58],
[-53, 84],
[-3, 4],
[3, 56],
[-3, 4],
[-42, 96],
[-12, 46],
[-52, 96]]

But we don’t want our enemies to suspect we’re using matrices, so we’ll “flatten” the list and print it all on one line:

output_list = []
for row in z:
    for thing in row:
        output_list.append(thing)
print(output_list)

Now it prints out our list of numbers:

[-4, 72, 5, 10, -16, 58, -53, 84, -3, 4, 3, 56, -3, 4, -42, 96, -12, 46, -52, 96]

The numbers look pretty random: some negative, some positive, and not many repeated numbers. To show you how well this mixes letters up, let’s encrypt the message “blah blah blah blah blah blah blah”

[-34, 52, -23, 34, -6, 8, 9, 28, 8, 16, -34, 52, -23, 34, -6, 8, 9, 28, 8, 16, -34, 52, -23, 34, -6, 8, 9, 28, 8, 16, -34, 52, -23, 34]

Interesting! A repetition of a 5-character word (including the space) seven times is transformed into a 10-character “word” repeated three and a half times.

A similar function decrypts the message:

>> decryptMat()
Enter the numeric message separated by commas:-4, 72, 5, 10, -16, 58, -53, 84, -3, 4, 3, 56, -3, 4, -42, 96, -12, 46, -52, 96
the kids are alright

Ramping up the Mystery (even without Matrices!)

A few years ago a student of mine suggested we really hide the numbers by converting them to binary:

1010001000001010000001011010010010010011000000000110010001010000000001011001001001001001110100010100

Your enemies would easily guess you were using binary. So my student suggested we convert every 1 into a random odd number, and every zero into a random even number:

7690829846223890060687071234476610416219820420808390252623234862864607637207407087283641336366634580

Now this looks mysterious! The enemy will never suspect that “76908” is really just “10100” which is 20, and the 20th letter in the alphabet is “T.”

Cryptography is a great way to teach string manipulation in any programming language, not to mention matrix multiplication and binary numbers!

 


  • 0

Random + Symmetry = Art

Category : Uncategorized

I have the nerdiest, artsiest Twitter feed. Every day I’m blown away by some creation by techy artists Saskia Freeke, Jessica “Nervous System” Rosenkrantz, Anders “Inconvergent” Hoff or somebody with the handle “Atticus Bones.” Atticus Bones often posts grids of randomly generated designs, and today’s really caught my attention:

I was inspired to clone these figures today. But how? There’s no way Atticus writes out the code for 484 designs; it must be done with random generation. I looked more closely at the individual designs for clues. I noticed every design has rotation symmetry. For instance, this design can be broken up into four identical quadrants.

I zoomed in on the top right quadrant:

Looking more closely at this quadrant, I could tell there’s more symmetry, reflectional symmetry about the diagonal. So we could chop it down even further to this:

So it’s just a matter of creating a random collection of segments, and reflecting them over the diagonal and then rotating them to the other quadrants. Some of Atticus’ figures give me a clue as to how many points would be needed to connect the segments. It seems to me there are “nodes” forming squares at a 45 degree angle. So in our example, here’s where I think we need nodes:

So we need 9 nodes, all with their own location. This is a job for a Node class, where each node has an x- and y-value and a distinguishing number “num.” I fired up the Python mode of the Processing graphics software:

I created a “nodes” list to store all the nodes, and a Grid class to draw a whole quadrant of nodes. Here are the first four nodes:

The vertical and horizontal distance between the nodes is “sz” (since “size” is already a keyword in Processing), so the x- and y-values of the nodes are easy to calculate.

Ready to Reflect

The nodes on the other side of the diagonal line needed their own locations. Was this going to be a mess? Not really. 5 out of the nine nodes are on the diagonal, so their locations don’t change. The other 4 took a little thinking and a little “back of the envelope” calculating. I didn’t have an envelope but I had a whiteboard. I drew a point (1, 2) and its reflection, which turned out to be (2,1):

So the pattern is the node at (x,y) is reflected to a node at (y, x). I easily made those changes after copying and pasting!

The next challenge was how to randomly draw a segment between two nodes (or not to). I wrote a list of the nodes and all the possible connections between them:

Now I created a list of randomly generated 0’s and 1’s that would determine whether each connection would be drawn or not:

self.connectChoice = [choice([0,1]) for x in range(16)]

Now a simple “if” statement would tell the program to draw the segment if the number in that spot is a 1.

 def connect(self):
     #for every node that's connecting:
     for i,c in enumerate(self.connectChoice):
         if c == 1: #if the connection is active
             #connect the first node in the 2-list with the second
             nodes[connections[i][0]].connect(nodes[connections[i][1]])
             #also connect the reflections of those nodes
             mirrornodes[connections[i][0]].\
             connect(mirrornodes[connections[i][1]])

The “mirrornodes” part makes sure the reflection happens with the reflections of the nodes, too. So the quadrant is done! This code rotates the grid 90 degrees four times so we get our whole design:

 def display(self):
     #copy the upper right quadrant 
     # to all 4 quadrants by rotating
     for i in range(4):
         rotate(radians(90*i))
         self.connect()

Now we need to scale down the size of each design and arrange a bunch of them in rows and columns. Sounds like we need a few loops!

#add the grid to rows and columns
for j in range(22):
    for k in range(22):
        pushMatrix()
        #go to the location
        translate(j*6*sz, k*6*sz)
        #display 1 grid
        grids[k+22*j].display()
        popMatrix()

It took a little trial and error to get the right amount of spacing, but I finally had my “Atticus Clone:”

I posted it on Twitter and only got one like. But guess who it was from?

All my code is available on github. Have fun making Art!


  • 0

Art with Complex Numbers!

Category : Uncategorized

Complex numbers are numbers made up of a real part and an imaginary part containing i, the square root of negative 1. They’re usually expressed as z = a + bi, where a and b are real numbers, as in z = 2 + 3i. In fact, every number you’ve used is a complex number, but a real number like 5 is expressed as 5 + 0i, meaning it has no imaginary part. It reminds me of the character in the Moliere play who was tickled to learn he had been speaking prose his entire life without knowing it.

When you learn about complex numbers in a traditional math class you seldom get to do much with them, because it takes a lot of algebra to multiply them together (think FOIL) and forget dividing them. Your textbook says they’re used in such fractals as the Mandelbrot set but it never tells you how.

The great thing about using computers in math class is you can write functions to operate on complex numbers and (once you’ve ensured your code works) easily transform them. Every point on the plane is given a coordinate, not unlike the (x,y) coordinate system you see in Algebra class. In fact each point (x,y) in the traditional Cartesian coordinate system can be expressed as a complex number in the complex coordinate system, as z = x + iy:

 Here’s where you start learning about transformations. Obviously, adding and subtracting complex numbers corresponds to translating a point. Multiplying complex numbers corresponds to rotating. Squaring complex numbers is particularly interesting, because of the patterns that result. In the figure below I created a grid inside a tiny part of the coordinate grid. The blue lines are one unit apart, so we’re really just dealing with the points between 0 and 1 horizontally and 0 and i vertically.

The black grid in the lower right is composed of a bunch of points, and when they’re put into a function they’re transformed into the red points. In this case, I created a function to square a complex number like this:

def cMult(a,b):
    '''Returns the product of two complex numbers'''
    return [a[0]*b[0]-a[1]*b[1],a[1]*b[0]+a[0]*b[1]]

Of course, multiplying a number by itself is squaring, so this will square the complex number a:

>> a = [1.0,1.0]
>>> cMult(a,a)
[0.0, 2.0]

In the graph, the complex number a = 1.0 + 1.0 i is the top right corner of the black grid. In the red grid, you can see it maps to the point 2i, at the top of the screen. The complex version is 0 + 2i, and that’s why the output says “[0.0, 2.0]”

 Santa Clara University Professor Frank Farris took this visualization one step further in his book Creating Symmetry. Instead of transforming a list of points, he transformed the pixels in pictures he took of flowers, fruit and other food. He took pictures like the one below at left, and transformed each pixel (which has a position on the screen just like points do) to another position using more and more complicated functions, resulting in surprisingly beautiful patterns like the one below at right:

The formula Farris used to map the pixels of the picture of the dahlia is

Once you’ve written the code for “take the coordinates of a pixel, run it through this function and place the color of that pixel at the new location” the rest is just giving the program new functions. I wanted to copy Farris’ beautiful wallpaper pictures and found this formula in Chapter 10:

Which leads to mapping the example color wheel to this fantastic rotation/translation design:

The equation looks ugly but once we’ve written the code for “e to the power something” and declared what the variables m and n are, the computer will do the rest. This is the output I got putting my dahlia into that function:

 Lavender’s nice, too:

Like I always say, Math is art!

My code is on github.


  • 1

Thinking About Neural Nets

Category : Uncategorized

In the spirit of tackling real-world problems we don’t know the answer to, the newest focus of the data science world is “Machine Learning.” It’s a pretty general term that applies to just about anything that deals with teaching computers to do something in an indirect way. When I teach students how to create a Tic Tac Toe game, for example, they have to tell it how to make a move and so on, and there’s a lot of “if this, then that” kind of code:

for i in range(1,10):  # Check if computer can win on next turn
    if board2[i] == ' ':        # if a space is open
        board2[i] = computer    #fill it with computer's letter
        if isWinner(board2, computer): # if it's a win
            return i                # return that move
            else:                   # Otherwise
                board2[i] = ' '     # open that space again

With Machine Learning, the computer (eventually) learns the best move through repeated training trials, like thousands of them. The Go-playing AI  from Google that just defeated the World Champion learned by being shown tens of millions of board positions from hundreds of thousands of games. The idea is good moves are reinforced while bad moves are weeded out. An Artificial Neural Net is designed to work like a human brain, where input neurons are connected to a bunch of neurons, eventually leading to output neurons. Here’s a simple view:

The idea for such a network originated in the late ’50s, but its progress had hit a brick wall before Paul Werbos came up with the idea of backpropagation in the ’70s. That means the weights and values of the paths and neurons in the network are recalculated after a trial and the network gets feedback. The mathematical methods of minimizing error are the subject of many books and Doctoral theses, but suffice it to say they involve linear algebra, statistics and calculus.

Simple nets can be made with a surprisingly few lines of Python code. I worked with a few students at the Coder School last night, and even though none of them were ready to tackle a real net yet, we made sketches of how an impulse travels from the input neurons to the output. This is what it looks like so far. Click the nodes on the left to activate a random path through the network. Notice even when no longer activated this strengthens those paths a bit each time.

See the Pen Neural Net by Peter Farrell (@peterfarrell66) on CodePen.


The next step would be to use the numbers from the weights and values of the paths and nodes to realistically depict the forward- and back-propagation until it settles on the best path through the network!


  • 0

Into the Unknown

Category : Uncategorized

One of my (grown-up) students at JobTrain wasn’t impressed with my Shakespeare-writing organisms since we knew the phrase we were trying to make it write. He has a point, and that’s what’s wrong with a lot of problems we assign in Math: we already know the answer. It reminded me of the Simpson’s episode where Lisa steals all the Teachers’ Editions of the schoolbooks. Without the answers, the teachers panic!

Making sure a formula or a program works is important and that’s why we test it with something we know the answer to. But once we know it works correctly, we should be extending it and using it on questions we don’t know the answer to!

There’s a famous problem in math and programming called the Traveling Salesman Problem (TSP), in which a salesperson has to travel to a bunch of cities and is of course looking for the shortest route. Even introducing it is a terrific math problem: how many routes are there between 3 cities? 4 cities? 10 cities? It really starts to add up!

Between n cities there are (n-1)! routes, and you need to divide that by 2 because half of them are duplicates, just in the opposite direction.

So between 10 cities there are 181,440 unique routes, and between 20 cities there are 60,822,550,204,416,000 routes! If you could check a million routes randomly every second, that would still take you 1,928 years.

In programming it’s challenging enough to draw the routes between the cities randomly and test their total distance. That’s what I did, following one of Dan Shiffman’s excellent Code Challenges on YouTube. But then you leave it running and it just chooses random routes. The best route improves a little now and then. To apply the genetic algorithm, I gave each organism a score, a length, and a list of numbers signifying a route through the cities. If there were 10 cities, the “cities” list would just be the numbers 0 through 9, shuffled randomly:

class Organism:
    def __init__(self):
        self.score = 0
        self.length = 0
        self.cities = nums[:]
        random.shuffle(self.cities)

Just like the Shakespeare program, but with numbers instead of letters. But how do you score the organism if you don’t know the answer? You give the highest score to the route with the lowest distance.

 def calcScore(self):
     #calculate the length of the route:
     myLength = self.calculateLength()
     #give a score. Lower distance --> higher score
     self.score = 1000000.0/myLength
  
     return self.score

Those organisms with “better genes” get more copies put into the mating pool and little by little the surviving routes improve. I added in some helpful mutations, where a random number of genes get switched.

It isn’t a foolproof system, though: the pool of genes could get stuck in a non-optimal route, but it does a great job for 10,000 organisms (in this model) starting with random routes. In this GIF you can see the process of improving the route in increments of 100 generations per frame. The white number is the best distance in the first generation: 13,537 units. By the end of 1000 generations or so of the organisms evolving better and better genes (which are just lists of numbers), we’ve improved the distance to 3,808 units.

My entire code is on Github.

Your students might be fascinated to know they (and their virtual helpers) are solving problems that have never been solved before! Is their solution the best one? There’s no answer in the back of the book!

Have fun and Go Organisms!


-Peter Farrell
May 15, 2017


  • 0

I Do Have a Point – in fact, I have a list of them!

Category : Uncategorized

A student found a page on Code Golf – using the least number of characters to do a task in code. It’s a popular sport:

The designs they made interested me. It was really just a bunch of points spaced out around the circumference of a circle, and each point was connected to each other point by a segment. What a great mathematical exercise! It’s simple to space points out around a circle using rotate and translate in Processing:

Unfortunately, when you transform points in Processing, they don’t have absolute coordinates you can use anymore. If you want to keep their coordinates intact, you have to use sines and cosines. Here’s the position of a point r units away from the origin and rotated a certain angle:

You have to convert degrees to radians, or even better, have the computer do it. In Processing it’s as easy as putting the degrees into a function called “radians” and it will convert it for you.

 points = [] #empty points list
 for i in range(12):
     x = 250*cos(radians(360.0*i/12))
     y = 250*sin(radians(360.0*i/12))
     #put point in a list
     points.append([x,y])

In the above code I created a list to put points in, then started a for loop that would space the points evenly around the circle. Now I just had to go over every point and draw a line between it and every other point. That’s done with this nested loop:

for p in points: #from every point
    for other in points: #to every "other" point
        stroke(255,0,0) #red
        line(p[0],p[1],other[0],other[1])

“[0]” means the x-value, and “[1]” means the y-value. Now I can see the outcome with 12 points:

Of course I wanted to make it fancy and interactive, so I connected the number of points to the x-value of the mouse. Now if the user moves their mouse left and right the number of points increases and decreases.

I like the interactivity. You get to choose how crazy it gets.


-Peter Farrell
May 10, 2017


  • 0

Solving Problems with Genetic Algorithms

Category : Uncategorized

Talk about an all-around STEM topic! If you’re interested in exploring genetics through modeling, Genetic Algorithms are a great start! I followed Chapter 9 in Dan Shiffman’s excellent book The Nature of Code (you can order it or read it for free here), where he creates a population of organisms to work out a target phrase:

target = "wherefore art thou romeo"

In Python, I created an Organism class so each organism would have a set of “genes,” or randomly generated letters to guess the target string.

characters = 'abcdefghijklmnopqrstuvwxyz '

class Organism(object):
   def __init__(self):
       self.score = 0
       self.genes = ''
       for i in range(len(target)):
           self.genes += choice(characters)

Each organism would get a score based on matched letters divided by the length of the target phrase. The score would be multiplied by 100 so it would be a whole number and that number of copies of the organism would be added to a mating pool to reproduce.

“Reproduction” would consist of splicing together two organisms’ genes at a random point so the result would still be the length of the target phrase. A certain number of the child’s genes would be replaced by random characters according to a mutation rate. Then the child organism would take one parent’s place in the population. Repeat for the next generation, and the next and the next…

It doesn’t sound particularly promising with all the randomness factored in. We kept track of the best fit phrase among the organisms and it didn’t start off well:

But in a few dozen generations there was success:

This may not be so miraculous, since we knew the target phrase, but just imagine applying this method to a problem where we don’t know the answer. In the Traveling Salesperson’s Problem (TSP), for example, you don’t know the shortest path between the cities but you can score the attempts by length and use the genetic algorithm to evolve a pretty good approximation!


-Peter Farrell
April 26, 2017


  • 0

Programming the Environment

Category : Uncategorized

If STEM is really all about linking Science and Technology, for example biology, the environment and programming, how do your students explore sustainability? If only there were a way to have students create their own virtual environment model with grass that grows and sheep that eat, reproduce and die. It would really help them to appreciate the complex interaction of elements in the environment with every new organism they add.

Years ago I was introduced to the grass-eating colony of turtles exploration on the NetLogo site and it’s a great programming challenge. Unfortunately, the Logo programming language isn’t of much use outside of the classroom. But Python is definitely a useful skill and by using the Processing graphics library we can make a visual, dynamic, interactive (and memorable!) model in maybe a couple of class periods.

We’ll start with a “sheep,” which my students and I simplified to a circle, but you can draw it as realistically as you like. Sheep need an x-y position, a color, a size, an age, and an energy level. When they’re “born” they’re added to the sheep list. So in Python the Sheep object is created like this:

class Sheep:
    def __init__(self,x,y,sList,col):
        self.x = x #x-position
        self.y = y #y-position
        self.col = col #color
        self.age = 0
        self.sz = 10 #size
        self.energy = 20 #energy level
        #add it to the sheep list
        sList.append(self)


Then you have to tell the program how to update the sheep, to make it walk around (which costs it energy points) and “eat” the grass to increase its energy points. If its energy gets down to 0, it dies and is removed from the sheep list. Every loop the Sheep’s age is incremented, and if it reaches a certain age it dies. Finally you draw the Sheep. That code looks like this:

def update(self):
    #make sheep walk randomly
    move = 10 #the distance they can move
    self.x += random(-move, move)
    self.y += random(-move, move)
    self.energy -= 1
    self.age += 1
 
    #if the sheep gets enough energy, reproduce
    if self.energy > 50:
        #create another Sheep on the same spot
        Sheep(self.x,self.y,
              sheepList,self.col)
        self.energy -= 30 #this costs energy!
 
    #draw sheep
    fill(self.col)
    ellipse(self.x,
            self.y,
            self.sz, self.sz)

Compared to Sheep, the patches of grass are pretty simple. They just need an x-y position, a size, an energy content, and an “eaten” property which can be True or False:

class Patch:
    def __init__(self,x,y):
        self.x = x #x-position
        self.y = y #y-position
        self.energy = 2 #energy from eating this patch
        self.eaten = False #hasn't been eaten yet
        self.sz = 10 #size
 
    def update(self):
        if self.eaten: #if it's been eaten
                       #it can randomly "regrow"
            if random(100)<5:
                self.eaten = False
            else:
                fill(BROWN) #eaten grass is brown
        else:
            fill(GREEN) #un-eaten grass is green
        #draw the square patch of grass:
        rect(self.x, self.y, self.sz,self.sz)

Now it’s just a matter of creating a field of grass and a bunch of sheep at random locations. I’ve put the entire code on Github. You let the model run and see how it turns out. You can change the rate at which the grass grows, the energy content of the grass, the sheep’s maximum age and many other factors, to see the changes in the environment:

Evolution

My favorite thing to do with this model is give one species of Sheep a small Evolutionary advantage, like being able to walk just a bit further, like this:

if self.col == PURPLE: 
    move = 12

Students can come up with other advantages, like giving birth to more offspring or getting more energy out of the grass. When you run the model, does the advantage matter? Here’s a screenshot from a model where the advantage certainly did matter and the purple Sheep ended up dominating the environment:

Students love to watch the model run and will come up with all kinds of interesting ideas for expanding on this template. Have fun and Go Sheep!

-Peter Farrell
April 16, 2017


Recent Posts