ArbCamp 2007

Well, I’m headed out to ArbCamp 2007. It’s my first conference in a long while, and a first “unconference”. I think I’ve been stuck with my nose to the grindstone the last couple of months, so it’ll be nice to see what other people are doing. If any of you happen to be out in Ann Arbor or doing to ArbCamp, drop me a line, and we can meet up.

There should be some more exciting things to post after this weekend, from ArbCamp and otherwise. Til Monday.

Where do you put the rules of Monopoly?

It’s apparently a favorite interview question. I have to admit, the first response in my head wasn’t a great one, which was “everywhere”.

What are game rules? When browsing the rules of popular games like Monopoly and Scrabble, they seem to follow a similar format:

  • The initial conditions of the game (the setup)
  • Then given a condition,
    • the set of allowable actions for the player to do
    • the effects of the condition

I embarked on somewhat of the same problem, though on a much smaller scale. I wanted to implement a point system that gave points to those that participated in a Rails app. My first reaction was to make a Rule abstract class, and have different rule classes that subclass it. Something like this (variable names have been changed to protect the innocent):

class SceneRules
def initialize(model)
@scene = model
@user = @scene.submitting_user
end

def on_submit
@user.points += 1
end
end

class SceneshotRules
def initialize(model)
@sceneshot = model
@user = @sceneshot.sceneshot_uploader
end

def on_submit
@user.points += 10
@scene.submitting_user.points += 5
end

end

Then I’d be able to call it from the controllers. However, on second thought, it’s rather ugly, since I’d be updating the karma everywhere in the controllers. If I understand cross-cutting concerns correctly, scoring karma would be a good example of one. I suppose it’s a good candidate for aspect orientated programming, so I scrapped the code above.

Logging is often cited as the poster-child problem to solve with AOP. Logging needs to be done everywhere in the code, but it really has nothing to do with the responsibilities of the class that it’s performed in. So you have the same code doing the same thing, duplicated everywhere because there’s no one place to put it to make things easy to change.

By the same token, game rules and scoring are of the same nature. And because game rules involve lots of different objects at once, and scoring is interspersed throughout, I think that makes it a good candidate for AOP. However, Ruby has no such direct support for AOP. Instead, the closest thing we have are observers, before/after/around filters (in Rails), and some meta-programming.

I wanted something that allowed me to list out rules like games like Monopoly and Scrabble. I’d have a setup, and some conditions and their effects. Scoring is simplified here because the only time you can score is when one of the models is created or changes state. This is a good fit to the observers and the filters available in Rails.

class ScoringRules < ActiveRecord::Observer
observe Sceneshot, Scene
include Rules

setup { :scene => Proc.new { |sceneshot| sceneshot.scene } },
{ :sceneshot_uploader => Proc.new { |sceneshot| sceneshot.sceneshot_uploader },
:scene_submitting_user => Proc.new { |sceneshot| sceneshot.scene.submitting_user } }

rule :after_create_sceneshot do |board, players|
players[:scene_submitting_user].score += 5
end

# put more rules here

def after_create(model)
rule_dispatch(:after_create, model)
end

end

Here, the Rules module is what encapsulates the setup, rule, and rule_dispatch calls. I needed setup so that I can access different “game elements” (the board and the players) to update the scoring. It basically stores the setup as a list of lambdas that it can execute at a later time when the rule needs to be executed. Now, when a model is created, we ask the rule dispatcher to figure out which rules execute based on the rules we’ve named, and then execute the attached block. The block is passed a hash of different game pieces that it needs to update the score and the game conditions. That’s it.

I thought it was an interesting way about it and probably warranted some criticism. Is there any particular disadvantage of doing it this way? And if you can think of a way to not have to explicitly state the model relationships in the setup, that’d be nice. half-tip!

Operator for Microformats

I’ve put microformats in the stuff I’ve built before. And to be honest, I wasn’t sure if they were going to take off. The formats were there, but none of the tools to actually use them were around. For a long time, I just used the tails export add-on in firefox. You couldn’t really do anything with it, but you could at least see microformats.

The Operator takes it one step further, and adds actions to microformats. In a way, it’s a god-send, and now I’m wondering why I didn’t write it. I HATE having to cut and paste addresses into google maps. Now, if there’s a microformat of an address on a page now, all I have to do is use Operator–two clicks and I’m there. (As an aside, Humanized Enzo makes it even easier to include maps.)

Microformats have been gaining momentum for a year now, and I think it will be important in the web to come. Not because it’s one-more-thing to have to know, but because the guys over at social network portability are using it as part of their solution to open up the walled gardens of the social network stovepipes in effect today.

Given how we’re all use to using web applications today, it’s as if we’re always ‘reborn’ every time we sign up for a new service. It’s an odd idea to be able to “take your network with you”. If you can do this, especially as mobile devices get more powerful, there can be more and more web applications that can act as mediators in social contexts of the users as they go about the world.

One nice little app would be a name-recaller. At a conference or a party, my mobile phone would detect which other mobile phones are around. It could then query the web application whether I’ve met any of these people before, and what their names are. So when I actually go to shake their hand, I can address them by name. And as we all know, the sweetest sound to a person’s ears is his/her own name.

But that’s still a long ways from now. Probably not in another 4 or 5 years, if not more. However, I’d keep an eye on this area. I’m sure you’d hear more about it soon.

Model Reduction of Complex Dynamics

Model Reduction of Complex Dynamics

Alright, for some actual news. This is something that has been hard to achieve in computer graphics–that is believable fluid mechanics like water or smoke. Traditionally, they’ve been modeled as really large particle systems, which gets to be pretty expensive computationally.

These guys have managed to reduce the amount of computation required to make these computations to simulate fluids, detailed in this paper.

I’ve only glanced at the paper, but it looks like they were able to frame the problem in such a way that they were able to use dimension reduction techniques to reduce the number of computations they need to do, but have the least noticeable effect. By noticeable, I mean not only to the eye, but also to physics. It also conserves kinetic energy in the simulation.

I don’t understand much of the math in there, as it’ll take some time to go through it, but it reminds me of lossy compression algorithms and search engines. Not every piece of information is important, or is important in the same way. If you can frame the problem so that you can throw away less important information and still have approximately the same thing. It’s kind of novel to think of it as applied to a computational process, rather than a stream of data.

First Review!

Admittedly, I submitted mobtropolis to Geekheartland, but it was nice to get a first review. You’ll probably see less and less of these self promotions, since there are only so many “firsts” you can have.

All in all, there was nothing scathing about the review, and it actually said it was interesting. In general, of everyone I’ve ever talked that got it thought it was “interesting”. Honestly, that has me puzzled. From everything I’ve read and heard about the history of innovation, great and revolutionary ideas polarize people. So far, I haven’t really had anyone that got it and was turned off by the idea or thought it could never work. Update: Probably because not enough people have heard about it. I’m sure if the bloggers at Uncov got wind of it, they’d rip it to pieces.

We’ll see what happens as I expand on Mobtropolis‘s vision.

Mergesort in Erlang was to be my redemption–alas it was not

Well, once I got started, I kinda couldn’t help myself. I really should be debugging and cleaning up Mobtropolis, but sometimes, you need a break. To add to my shame of Erlang neophytism (probably not even a word), I tried out merge sort.


mergesort([Last]) ->
[Last];
mergesort(List) ->
[Left, Right] = split(List, [], []),
io:format("~w ~w~n", [Left, Right]),
merge(mergesort(Left), mergesort(Right)).

split([Last], Acc1, Acc2)->
[ [Last | Acc1], Acc2 ];
split([First | Rest], Acc1, Acc2) when length(Acc1)
split(Rest, [First | Acc1], Acc2);
split([First | Rest], Acc1, Acc2) ->
split(Rest, Acc1, [First | Acc2]).

merge([], R) ->
R;
merge(L, []) ->
L;
merge([L_h | L_t], [R_h | R_t]) when R_h =
[R_h | merge([L_h | L_t], R_t)];
merge([L_h | L_t], [R_h | R_t]) ->
[L_h | merge(L_t, [R_h | R_t])].

Ugh. I thought mergesort would be my redemption, since in my mind, it looked shorter. But I ended up having to write split(), since I didn’t know the libraries well enough, and couldn’t think of a good list comprehension to split the list. Admittingly, it’s like deciding to forgo inventing the combustible engine and deciding to start walking–I just built it out what I little I knew. If you’re so inclined, you can also try one-liner-ing (also not a word) mergesort, as the bar I set was pretty low. 😦 Like Bryan says:

“Get back into Erlang! it’s good for you. ;)”

Speaking of Bryan, he posted a solution to bubblesort that was pretty good in the last post. It was a good lesson. Like anything worthwhile learning, languages are often easy enough to pick up, but hard to master. This was a good wakeup call to go through the examples in the book and master more Erlang before trying to write anything else on my own.

Bubblesort in Erlang

It’s amazing how if a language isn’t a part of your daily work, how rusty you get at it. Oh erlang, how I didn’t mean to neglect you! I finally convinced Ian to give Erlang a shot, and he’s been going through Joe Armstrong’s book. He decided to write bubblesort, and it took him hours. This is what he had to say:

I’m having some difficulty
getting used to the idea of a language where every variable is a const.
its interesting, though.

but I have to admit the one line erlang quicksort is one of the
prettiest code snippits I’ve ever seen.

but “=:=” for equivalence? a three character long operator? who do
they think they are?

I wrote bubble sort and merge sort in erlang last night. it took
hours. the code looks horrible. for the first time since learning
basic in high school I feel like a foreigner in a strange land. its
invigorating.

actually I find it a bit intimidating. when something takes more than a
few lines of code I wonder if I’m doing it wrong. if joe armstrong ever
saw my bubble sort he’d probably take my book away.

I decided to give it a shot. It’s certainly a far better exercise than FizzBuzz. Given that I had written a neural network in erlang before, I figured I’d be more than ok with bubblesort. Right?

Wrong.

It’s taken an embarrassingly long time to get it right, plus, I took a shortcut that isn’t very optimal. If I ever had to write this in an interview in Erlang, They’d take my keyboard away. Here’s what I came up with:

-module(bubblesort).
-export([sort/1]).

sort([First | Rest]) ->
sort_helper([First | Rest], swap(First, Rest)).

sort_helper(List, New_list) when List =:= New_list ->
List;
sort_helper(List, [First | Rest]) ->
sort_helper([First | Rest], swap(First, Rest)).

swap(Current, []) ->
[Current];
swap(Current, [First | Rest]) when Current =
[Current] ++ swap(First, Rest);
swap(Current, [First | Rest]) ->
[First] ++ swap(Current, Rest).


Notice that I use the guard “List =:= New_list” to determine if a swap took place. In a large list, this would add n comparisons on every pass. Horrible. But since it’s an exercise, I neglected to keep track of swaps.

More than half the time was wrestling with the syntax. I had forgotten a lot of it, and mixed up [First, Rest] with [First | Rest], and I kept forgetting that I needed to prefix the functions by their module names. It’s bubblesort:swap(…) when you want to call it, and I was scratching my head for 10 mins. But the other time was just thinking recursively. Unless you’re working in a language the heavily uses recursive to iteration, you don’t often use it. But defn I prefer recursive as it’s much more succinct. Can anyone come up with a one-liner Bubblesort?

For reference, “the one liner” quicksort Ian was talking about:

qsort([]) -> 
[];
qsort([Pivot | T]) ->
qsort([X || X <- T, X < Pivot]) ++ [Pivot] ++ qsort([X || X = Pivot]).

First blog mention!


It’s been a little beyond a full month since I kicked Mobtropolis, a social photo scavenger hunt to expand your world, out the door to face some beating out in the real world. Whenever you release something to the public, it’s a bit nerve racking. But you always learn something, and better to know early and fix it, than to know later and suffer.

The first major lesson is that people didn’t know what they were looking at. I had figured with the advent of Digg and Reddit, that I wouldn’t need to explain what Mobtropolis does. How wrong I was. Friends and forum readers would visit, and then leave. I spent the better part of the month refactoring the underbelly of the app, and working on a better and succinct way to communicate the value added for the user. I think this will be a constant struggle, and I’ll have to be vigilant about always communicating clearly.

The other thing that I learned is that a lot of things simply don’t matter because you’re just not at that point yet. For example, I was reluctant on putting in comments since I figured with comments comes trolls, comment spam, etc. But in truth, it’s simply not at the point yet. Though I put in some precautions, it was more prudent just to kick something simple out and start using it.

I had the first blog mention today at a spanish tech blog called Genbeta today. That was a nice milestone. While the post was neutral in tone, it did mention that Mobtropolis was:

An interesting collective game in which anyone can participate.

Hopefully, I’ll keep getting better. So for those of you out there working on your own stuff, it pays to just get things out there then just iterate. Release early and release often is something you can do with web applications, so take advantage of it. If any of you readers find Mobtropolis useful or interesting, feel free to tell your friends to join you on some wacky adventures.