December 03, 2011

About two weeks ago reddit user AZxWildcat submitted this awesome image to the College Football subreddit.

Instantly after seeing this, I wanted to know more. How often does this happen? What year did it happen the most? When did this first happen?

Science Time

My initial hypothesis was that circles of parity occur once or twice a season. To test this statement, I needed every college football game score. Ever. Thankfully, the Internet is a wonderful place.

James Howell, College Football Data King

One Google search later and I landed on James Howell's College Football Scores page. This guy has the score of every college football game going back to 1869. Yes, 142 years of football scores. He also maintains a similar data set of conference affliations. I wrote a fabric script to save all the results locally for further processing.

Analysis

After downloading and transforming the data, it was time to start analyzing. For each year I had a JSON representation of the conference affiliations and a CSV file of football scores. The first step was to create a a directed graph for all the games that year. Each node in the graph is a team. Connections to another node inditcate victory.

Next, for each conference, I took a subset of the overall games graph involving only the teams from that conference. In the graph, a circle of parity manifests itself as a cycle which touches every node one time. In graph theory, this is called a Hamiltonian Cycle. To find these cycles, I first enumerated all paths in the graph. Since I made sure to only visit a given node once within a path, a path is a Hamiltonian cycle if and only if its length is equal to the number of nodes in the graph. With just under a hundred lines of Python my solution was complete.

Results

It turns out my initial hypothesis was correct. A circle of parity will likely form once a season. However, after 142 years of football, there are some really interesting data points.

• Total circles: 134 in 142 years
• Average per year: 0.94
• First circle: 1869 between Rutgers and Princeton
• Conference with most circles: 16 in the Big Ten
• Most in a season: 6 in 2006 with Big 12, Big East, CUSA, MAC, Pac 10, SEC
• Largest circle: 16 teams, WAC in 1997

In 1997 there was a circle of parity between all 16 teams in the WAC.

Absolutely insane.

If you're interested, the full report lists all 134 circles.

Making it Faster

It turns out that finding Hamiltonian cycles is hard. Not just hard, NP-complete hard. Thankfully, my graphs are very limited in size so the report only takes about a minute to generate on my laptop.

Even so, I thought I would give PyPy a chance to work its magic. PyPy is a "fast, compliant alternative implementation of Python" written in Python itself. They aren't lying when they say its fast.

$ time python analyze.py

real        0m52.537s
user        0m51.050s
sys         0m0.066s

$ time pypy analyze.py

real        0m22.758s
user        0m18.952s
sys         0m0.131s

Without changing a line of code, my code saw a 56.6% percent improvement in running time. If you haven't checked out PyPy yet, I suggest you head over the homepage right now and get reading.

Wrapping Up

All my data and code can be found in the circle-of-parity Github repo. Another huge thanks to AZxWildcat, James Howell, and the website where I got some of the cycle detection code (which I have now forgotton).

If you spot an error or discover something else awesome, shoot me an email or ping me on twitter.

September 20, 2010

More and more websites are popping up toolbars when you scroll down a certain distance on a page.

I can't stand these annoying bars, some of which are powered by Apture.com

I think Annoy. should be added to that list. If you want to block the Apture bar, simply add

127.0.0.1 www.apture.com

to your hosts file (usually /etc/hosts)

August 31, 2010

Just finished up hacking on my submission for the Wufoo API contest. VoiceForms 4000 takes any existing Wufoo form and turns it into a phone survey. The app is written in Python, runs on App Engine, and uses Twilio for all the phone magic.

https://voiceforms4000.appspot.com/

Go ahead and fill one of the sample forms and tell me what you think.

June 08, 2010

jQueried is a Safari 5 extension in the same vein as the jQuerify bookmarklet. jQueried adds jQuery to the current webpage, a task which can be very useful for debugging.

After finishing my first extension, simple as it is, I am impressed with the simplicity of Safari's extension API. Coupled with Firefox's Jetpack and Chrome's extension system, it looks like the future of browser extensions is all JS + CSS + HTML.

Download the extension: http://dl.dropbox.com/u/40773/jqueried.safariextz

Source is on github: http://github.com/derferman/jqueried

April 24, 2010

Currently, Apple's stock is at an all time high. A share today is worth over 40 times its value seven years ago. So, how much would you have today if you purchased stock instead of an Apple product? See for yourself in the table below. A huge thanks to everymac.com for the original prices and release dates. All values are calculated using Apple's current stock price according to http://brivierestockquotes.appspot.com.

I have also released the data set behind the calculations, which include Apple's stock price since 1997 as well as almost all Apple products released since 1997. Code at github.com/kyleconroy/apple-stock.

Big thanks to gojomo at http://news.ycombinator.com/item?id=1291809 for the idea.

December 23, 2009

The objective of StarFighter is to fly and blast through asteroids and space debris, making it to the end of the level with a high score. The ship is controlled entirely with the mouse. Lasers are fired by clicking the mouse button. The ship can also launch bombs by holding down the mouse button and releasing it after at least half a second. The longer the mouse button is held down, the further the bomb travels. Bombs are detonated by pressing the space bar.

Features

• animation and UI using OpenGL and GLUT
• detailed collision detection, optimized using object-aligned bounding boxes/spheres and kd-trees
• ray tracing technique used to fire lasers/missiles
• gravity-affected, bounce-able projectile simulation with balls
• mouse controlled x/y thrust
• level input file parsing to construct world, using OBJ output of objects designed in Maya

Libraries Used

• Eigen vector/matrix library
• kdtree (http://code.google.com/p/kdtree/)
• FreeImage for writing images
• SOIL (Simple OpenGL Image Library) for texture input

November 14, 2009

My latest CS184 project is now complete and ready for viewing. We had to take in Bezier patches and use tessellation to create triangles using OpenGL. But I know what you really want to see: videos.

October 10, 2009

We were tasked with creating a raytracer. Images are followed by the command line which produced them, as well as the scene file describing the setup. All times were calculated using the linux time program. All images on this page were output using my raytracer.