Round and round the robin goes

Recently I found it useful to implement a round-robin tournament. Here’s a little Python generator that produces schedules for you, for your enjoyment.

from collections import deque
def round_robin(size):
  if size < 2:
    yield []
    raise StopIteration

  teams = range(1, size)
  rounds = size - 1
  if size % 2:
    teams.append(None)
    rounds = rounds + 1
  roster = deque(teams)
  half = (len(roster) + 1)/2
  for round in range(rounds):
    positions = [0] + list(roster)
    backwards = positions[::-1]
    yield [(positions[i], backwards[i]) for i in range(half)]
    roster.rotate()

Render D3.js-driven SVG server-side!

Recently I’ve been working on a congressional tweet aggregator to get a handle on what our legislators are saying. To make that easier to see, I figured I’d start adding some charts and lists and other snazzy dataviz gizmos that are so hot these days.

I like D3.js as a graphing library. It makes clean, interactive, data-driven charts a snap to make in just a few lines of Javascript. Then it does its magic to render the data in crisp SVG, which I am quite fond of. On my site, I wanted to turn the crank on the back-end for charts that don’t update all that frequently, inject them into my templates, and spare the viewers of my site the heavy-lifting required for multiple charts—not to mention my poor server that has to execute several complicated queries to do the appropriate counting to generate the data to back the charts.

After a little poking around on the internet, I stumbled on to PhantomJS, which bills itself as a full-stack headless WebKit. Perfect. It can ping my website periodically, load the chart pages, and extract the SVG, I thought.

Not so fast. The Phantom is excellent at reading SVG, and it’s even good at rendering it to PDF or PNG. But that’s not what I wanted! I just wanted it to spit out the SVG for me after D3 was finished making it, untouched. And since SVG elements don’t have an innerHTML property, I needed to think harder to find a solution; i.e., ask Google. But Google didn’t seem to know, either. So I wrote a tiny script to extract page elements by ID. Maybe one of you will find it useful, too.

var system = require('system');

if (system.args.length != 3) {
    console.log("Usage: extract.js  ");
    phantom.exit(1);
}

var address = system.args[1];
var elementID = system.args[2];
var page = require('webpage').create();

function serialize(elementID) {
    var serializer = new XMLSerializer();
    var element = document.getElementById(elementID);
    return serializer.serializeToString(element);
}

function extract(elementID) {
  return function(status) {
    if (status != 'success') {
      console.log("Failed to open the page.");
    } else {
      var output = page.evaluate(serialize, elementID);
      console.log(output);
    }
  phantom.exit();
  };
}

page.open(address, extract(elementID));

A little birdie told Congress

Since I couldn’t find a list of twitter feeds from the US Congress, I made one today.

Now you can get a snap-shot of our legislators highest priorities, as captured in 140 characters at a time, at twitter.com/CongressBirdie/legislators.

In case you’re curious how I did it without painstakingly searching each congressperson’s name and username to add to my list by hand, I’ll let you in on my little my secret: I relied heavily on a few open source projects to automate the process. To find the Twitter IDs, I simply looked them up from the very excellent Github project unitedstates/congress-legislators. Then I used the Python Twitter Tools module to chat with the Twitter API to create the list and add all the legislators in bulk.

Life wasn’t exactly as easy as all that, though. I had to make a little tweaks in order to gather all the tweets. First, there is an easy-to-fix bug in the Python Twitter Tools package. You need to make sure it knows how to POST to lists/members/create_all command. Right now employs a GET request—and that doesn’t work. It looks like at least one other person has run into the same problem. If you run into the problem, you can read how I fixed it.

But Twitter didn’t handle my create_all request as they promised. The documentation claims you can add up to 100 users to your list at a time, but that wasn’t my experience. Instead, I could only get the API to add legislators 25 at a time. But that’s a small price to pay for democracy.

And this list is active! In the time it took me to write this post, the list reported 13 new tweets. Your tax dollars hard at work.

Populate URLs in Your Javascript with Django

All this Olympics has inspired me. I’ve decided to train for the summer games in Rio and to pursue my hobbies in full force. The former requires me to learn to kayak; the latter, to program, program, program.

I’m building a fun web-app game on top of Django. And I want to make it dance with a little Javascript. I really like that I can look up the URLs of my pages by an internal name in templates using the {% url %} tag, but unfortunately that functionality isn’t available to me inside my static media—particularly, I’d like to be able to reverse look-up URLs in my site’s javascript, but I don’t want to have to render the file each time it gets served.

After hunting around for a while, I figured, “Why not just render to Javascript once, fill in all the links, and be done with it?” So that’s what I did. And it doesn’t take much.

I wrote a custom command called populate_urls that consumes a template (in this case, my Javascript) and spits out the finished product with all the holes filled in by Django and its handy URL resolvers. Then I stash its output in my static directory and pretend the whole thing never happened.

from __future__ import print_function

import sys

from django.core.management.base import BaseCommand
from django.template import Template, Context

class Command(BaseCommand):
from __future__ import print_function

import sys

from django.core.management.base import BaseCommand, CommandError
from django.template import Template, Context

class Command(BaseCommand):
args = ‘
help = ‘Populates the URLs in the template. If no output filename is supplied, renders the template to standard out.’
traceback = True

def handle(self, *args, **options):
if len(args) < 1: raise CommandError("You must supply a template.") with open(args[0], 'r') as templatefile: template = Template(templatefile.read()) context = Context() with sys.stdout if len(args) < 2 else open(args[1], 'w') as output: print(template.render(context), file=output) [/sourcecode]

Geotools, WFS-T Update Request

A pet project of mine has flung me into the exciting though less-than-firm territory of web-backed geographical information systems. Since I don’t have the thousands of dollars it costs to get a commercial server like those provided by ESRI, I’ve had to check out the open-source alternatives. And there are some out there. I’m using GeoServer, and it works great! I can send all the web-feature service transactions (WFS-T) in XML I want and it works every time. Not bad if you want to make a GoogleMap of your house on your own—so long as you’re content to hard-code everything by hand. Should you want to jazz things up a bit (i.e., make minimally useful dynamic maps), like me, then you have to do a little more work. Actually, you need to do a lot more work.

GeoServer is built on top of a gargantuan set of Java libraries, collectively packaged under the name GeoTools. Now I appreciate that this thing exists, all two hundred and fifty megs of source code and all the functionality that comes with it. However, navigating the mountain of documentation for this thing is, at least for me, a little daunting. It took me a few days (and some serious help from my friend Matt) to figure out how to write a simple update transaction using their API. (Compare that to the forty-two seconds it takes me to type up the XML.)

Since other people might want to know what they have to do update an attribute field using WFS with GeoTools, and since I couldn’t easily find out how to do it elsewhere, I’ve decided to post a short snippet of code right here on my blog. That’s right: my charity knows no bounds.

In this example I’m going to update the value of all the features (polygons, lines, points, whatever) that match a simple filter. Here I’m going to change the value of propertyToUpdate to updatedValue using a filter to get all the features with the attribute called constraintProperty with a value of constraintValue. I’ve marked them in red, so that it’s as easy as possible to customize this example to fit your needs. Let’s start with the XML that the Open Geospatial Consortium standards expects to see.

<wfs:Transaction service=”WFS” version=”1.0.0″
     xmlns:myns=”http://www.domain.com/ns
     xmlns:ogc=”http://www.opengis.net/ogc”
     xmlns:wfs=”http://www.opengis.net/wfs”>
  <wfs:Update typeName=”myns:LayerToUpdate“>
    <wfs:Property>
        <wfs:Name>propertyToUpdate</wfs:Name>
        <wfs:Value>updatedValue</wfs:Value>
    </wfs:Property>
    <ogc:Filter>
        <ogc:PropertyIsEqualTo>
            <ogc:PropertyName>constraintProperty</ogc:PropertyName>
            <ogc:Literal>constraintValue</ogc:Literal>
        </ogc:PropertyIsEqualTo>
    </ogc:Filter>
  </wfs:Update>
</wfs:Transaction>

Now let’s rock out the Java.

Like I said, GeoTools is mammoth. To make life easy, we’re going to import a whole bunch of classes for this example. So many, in fact, that their number really warrants my displaying them here in their own list. What’s more, the names of some of classes (like Filter) show up in more than one package, and you need to keep track of which is used where. So keep an eye out for things from org.opengis.

import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.HashMap;
import java.util.Map;
import java.util.logging.Level;

import org.geotools.data.DataStore;
import org.geotools.data.DefaultTransaction;
import org.geotools.data.FeatureStore;
import org.geotools.data.Transaction;
import org.geotools.data.wfs.WFSDataStoreFactory;
import org.geotools.feature.AttributeType;
import org.geotools.feature.FeatureType;
import org.geotools.filter.FilterFactoryFinder;
import org.geotools.xml.XMLSAXHandler;

import org.opengis.filter.Filter;
import org.opengis.filter.FilterFactory;
import org.opengis.filter.expression.Expression;

In our constructor we’ll set up a connection to the WFS server using a URL. If you’re tinkering with GeoServer, then that URL you’re looking for probably looks something like http://localhost:8080/geoserver/wfs. Since we know that we’ll want to filter our responses, it’s not a terrible idea to make a filter factory now and save it for later. In GeoTools everything is made using a factory. For filters, we need to make a factory using the new keyword, though. Here goes.

public class WFSUpdater {

    private DataStore wfs;
    private FilterFactory filterFactory;

    public WFSUpdater(String url) {
      try {
        URL endPoint = new URL(url);

        XMLSAXHandler.setLogLevel(Level.OFF); // turns off logging for XML parsing.

        // Parameters to connect to the WFS server, namely the URL.
        // You could have others, say if you had to authenticate your connection with a username and password.

        Map params = new HashMap();
        params.put(WFSDataStoreFactory.URL.key, endPoint);

        wfs = (new WFSDataStoreFactory()).createNewDataStore(params);
        filterFactory = FilterFactoryFinder.createFilterFactory();

      } catch (MalformedURLException e) {
        e.printStackTrace();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }

Now that we have a connection, it’s time to make the transaction. As a first timer to GeoTools, I found it difficult to crawl through the documentation. Lots of their classes and methods have been deprecated with no clear hints about what to use instead. I had a hard time finding the right constructors. In what follows everything is hard-wired into the code, but it shouldn’t be all that bad to tweak things so that it works the way you like.

public void updateProperty(String propertyToUpdate, String updatedValue) {
    // This is the layer name on the server.
    String layer = “myns:LayerToUpdate“;
    Transaction update = new DefaultTransaction(“update”); // The handle/ID of this transaction is called “update.” It’s required.

    try {
      // Make the filter.
      Expression property = filterFactory.property(“constraintProperty“);
      Expression value = filterFactory.literal(“constraintValue“);
      Filter filter = filterFactory.equals(property, value); // This is an org.opengis.filter.Filter.

      FeatureStore features = (FeatureStore) wfs.getFeatureSource(layer);

      // Set the transaction. Otherwise, we can’t commit our changes later on.
      features.setTransaction(update);

      // Fetch the property from the FeatureType schema so that we can update it with the new value.
      FeatureType schema = features.getSchema();
      AttributeType atrributeToUpdate = schema.getAttributeType(propertyToUpdate);

      features.modifyFeatures(atrributeToUpdate, updatedValue, (org.geotools.filter.Filter) filter); // There’s that casting again.

      // Record the modifications.
      update.commit();

      } catch (IOException e) {
        e.printStackTrace();
      }
    }
}

Anyway, I hope this saves some people the hassle of tearing through the Javadocs for GeoTools. Also, if there’s a better way to do what I did, please let me know. Happy GIS-ing.

Technorati Tags: , , , , , , , , , , , , ,

Genetics by the Poolside

Happy Independence Day! To celebrate our nation’s founding, my family and I often hit up the Cape. This year was no exception, there’s little to report. The weather has been spotty: a little rain here, a few showers there, but nothing substantial. Someone was playing bagpipes the other night. And I witnessed a gruesome car accident a few feet from my balcony during the fireworks spectacular. A mass of people immediately sprang up to help the man, direct traffic, and call 911 repeatedly until emergency vehicles could make their way here. I was genuinely impressed by the response, professional and make-shift alike. Within seconds the response team had the guy off to the hospital in no time flat. I think it prudent not to speculate on the cyclist’s health. I don’t want to jinx anything, you know.

And since it’s vacation time, I’m here, at the kitchen table, on my laptop, implementing genetic algorithms. Maybe later I’ll describe what I did. Maybe if I do, someone will be able to tell me if my results make any sense. Whether or not my programs reproduce the classical results isn’t really the point, though. Look at the evolution of strategies for playing the iterated prisoner’s dilemma: they make perfect modern art tile mosaics! I bet someone’d love to have this pattern on their pool floor or garden wall. (Don’t be alarmed that they don’t appear all that related. Each row in black represents the fittest individual from one of a number of independent runs. That is, they probably never had the chance to meet each other.) Imagine the graphic tastefully obscured by flowering vines. (Click on it for a larger image.)

I can see an upside-down raccoon in it. What can you find?

Crab Canon

This week we had to create a sound collage for my computational media class. I didn’t set aside a lot of time to work on it, so it became something of a last-minute project. Today I spent most of my day meeting with bioinformatics folk to discuss herberia and taxa and distributed architectures. I may end up working in a CS research group playing with this (or other) stuff. Anyway, by the time I got home, I only had a few hours to start and finish my project. Luckily, I’ve been toying around with MIDI on my own. So I took a line from J.S. Bach and tried to reconstruct part of his crab canon. (This amounts to reversing, compositing, and normalizing a small bit of data.)

Here’s what I started with.

Two hours later, here’s what I ended up with. True it’s not precisely a crab canon—I prefixed a short introduction before the canon starts proper. But if you played from then on backwards, it would sound exactly the same. That’s right: I one-upped Bach. He thought he was writing a musical palindrome. Unfortunately, he couldn’t reverse the attack and decay of each note. He needed me to come along and help him out with the minor, technical details. There’s no shame in that.

You can even download my project in spiffy MP3 format if you like. I’m just that sort of guy. Giving, courteous, clean.

Crab Canon.mp3

Technorati Tags:, , , , , , ,

Games: a Ludic Structure for Problem-Solving

Today I’ve decided to post a journal together with a longer paper about games. You hear all the time that we need to inject more play into education, that we need to return to childhood, etc. But why? You don’t as frequently hear why play is useful in education. People claim things like “If learning is fun, children will learn better.” I’m not sure of the connection. I suppose that if kids are engaged in learning, then they have a better chance of actually picking something new up than if they’re not trying to learn at all. That’s like saying if you look for something you have a better chance of finding it then if you don’t look at all. Sure, I buy that. But why play? By the same argument, we could just as easily pay kids to go to school and do their homework.

Of course some people do give reasons why play is useful. In these two papers, I’m building on some insights found in a 1933 paper by Lev Vygotsky entitled Play and its role in the Mental Development of the Child. (Vygotsky, you may well know, is one of my current heroes.) I remind the reader that in play, you can find all sorts of higher-order thinking skills taking place. Imaginary play is a very natural, distilled, abstractly difficult thing to do. Yet kids seem to do it on their own anyway, and before they even step foot in a classroom. If taught effectively, I think play is a useful vehicle for transfer of skills and tons of that ever-so-hot interdisciplinary work that goes on nowadays. (Wait until I get my genetic algorithmic music up and running.)

Journal 4 Journal 4: Methodological Doubt, Belief, and the Structure of Play

Paper 2 Reflection Paper 2: Decision-making as Game: A Mode of Prediction and Solution

Peter Elbow introduced concepts of methodological doubt and belief in his book Embracing Contraries: Explorations in Learning and Teaching. They’re central to his believing game and doubting game. Traditionally, doubt has been used as the primary tool in critical thinking. This unbalanced attention really makes a lot of analysis blind to new insights that can be gleaned from a moment of pure, suspended disbelief. (My ego won’t let me pass up an opportunity to say that both games show up automatically in my coffee mug model of classroom education.)

In my first paper I remark that all games require its participants to engage in the believing game—they have to believe that the rules imposed by the game are real and that the game itself is real. There are no consequences in any game if you don’t except them. You can always pick up the ball with your hands in soccer, unless you firmly believe that you can’t. For this reason, we might frame any situation as a game.

In the second paper, I extend my ideas to show that framing a situation as a game can greatly improve your power to predict behavior and arrive at winning strategies by simply considering the acceptable moves in your game. To illustrate my point, I work through a problem of the type sometimes given in consulting or computer science job interviews. The example shows, additionally, how mathematical reasoning (which I believe is no different than plain, old, vanilla reasoning) can be used to solve a problem without once using “math.”

As always, please comment freely. I’d love to get some feedback on this stuff.

Technorati Tags: , , , , , , , , , , , , , , , , , , , , , ,

I’ve Landed.

Today I was reverse-stalking the links pointing to my site when I discovered that Planet 02138 uses my RSS feed to fill their content. To be honest, I’m a little touched. At first I thought it might be associated with that magazine I don’t read with the same zip code. Fortunately, it’s not. If I were to guess, it’s another service offered by the kind folks at the Berkman Center.

Anyway, here’s how the Planet explains itself:

Planet 02138 is a collection of Harvard blogs. It is a sample of opinions and ramblings by Harvard students, faculty, and alumni.

From what I saw, they nailed it head-on.

You can make your own feed reader with the software from Planet Planet. Gosh, that’s fun to say.

Trolling their blogroll inspired me to update my own. Sure, my RSS reader knows what I’m currently reading—somehow my blog got left behind, though. After all, how are you going to know what I’m [likely to be] reading?

Technorati Tags:, , , , , , ,

Grassy Field

Since all I do these days is post my school projects to my blog, here’s another one for you. This week we had to create a collage. The requirements were pretty bare: at least five instances of the picture, one rotation, one rescaling, and at least one color modification. Try to spot each of the requirements in the final product below. (Maybe you’ve seen the original image before.) I had planned on using longer strips than the squares I ended up implementing, but I got lazy. The checkered effect is a little busy for my tastes; hopefully it’ll make the grade.

I tried for freakin’ ever to get the sky to soft clip to the hill top. I was able to adapt the intermediate image technique described in this article to create a tacky sun (not shown for art’s sake), but not for much more. Instead, I used the built-in, jagged setClip() method native to the java.awt.Graphics2D class. In case you were wondering, the clip was made with about six straight lines. I hate spline fitting, and try never to use curves—especially if line segments will do just fine. File that little tidbit away, it could be useful someday.

But convolutions rock. I’ve always thought so. Ever since I started using them to do signal processing in astronomy class. Our professor made us do a lot of convolutions using a visual calculus that really changed the way I thought about calculation in general. Drawing it out refined my sense of geometric interaction and avoided a lot of messy integrals. Here’s to qualitative methods: hurrah!

A field in collage

Technorati Tags:, , , , , ,