Zero Wind :: Jamie Wong

Immersion and Schadenfreude

2011-12-30T00:00:00-05:00

When I was in High School, I would try to absorb as much about computer science as I could from what I saw around me. I started writing competitions like CCC, dwite and ECOO-CS. I practiced for these competitions using UVa Online Judge, the USACO Training Program Gateway and by reading The Programming Contest Training Manual. I wrote word game bots and learned a lot from hacking challenge sites like hackquest and hackthissite.

But I also used to dance, draw, make abstract 3D stuff, game and play badminton (bear with me — the part of this that doesn't sound like bragging is coming).

When I got to university, I became fully immersed in computer science and software. I made the ACM team, started reading r/programming and Hacker News, started blogging about the code I was writing, started preaching the virtues of vim to my classmates and just generally increased the surface area of my CS knowledge sponge. This, in itself, was not a bad thing. Some of the things I've learned through these methods have been invaluable, but the cost was too high.

With the dramatically higher load of schoolwork from uWaterloo's Engineering program compared to high school, this influx of new activities meant the sacrifice of something. Preparing for interviews and trying to build an online presence made it easier to justify dropping off the professionally irrelevant things. I stopped drawing, stopped dancing, cut back on badminton and nearly stopped gaming. After that, I was entirely immersed in my field with little else around me.

I started realizing how bad this had become when I found myself trying to think of something to code during my free time. This is so wrong. Coding on my own time had become this obligation I had to fulfill to maintain my sense of reputation and to counter any fear of failing to complete some non-specific goal of doing something amazing. Don't get me wrong — coding on your own time is a good idea, but only do it if you're working on something that excites you.

So this seems like a relatively simple problem to fix, right? Just start doing the things you used to do. Only one problem.

Motivation

Lack of motivation is the killer of all self-improvement endeavours. Everyone has had a thing or two that they commit to doing that trails off. Whether it be eating right, going to the gym, keeping in touch with family and friends, or quitting smoking, everyone has failed to make or break a habit.

The most common pattern in my failures has been starting something, getting a rhythm going and then having one thing throw it off. Your schedule breaks down and you can't get back into it. This might be when exams start, when a project deadline is coming up or when you get sick. I can always convince myself that I'll get back to it later, but I never do.

Incentives

One method to bolster motivation is to use incentives. Self-awarded incentives have failed me for two reasons.

Internally, I know that I can give myself the reward regardless of whether I achieved my goal.
Sometimes I would rather forfeit the incentive than do the work required to get it.

Incentives that are gated by someone else are likely more successful, but if it isn't something you can give yourself, then it's probably not something you can reasonably ask of from a friend.

Disincentives

While self-awarded incentives are limited by what you might give yourself anyway, disincentives have no such restrictions. The only problem here is making sure that the punishment is unavoidable.

Self-imposed disincentives share the issue of convincing yourself that your goal was unachievable and abandoning your commitment. Luckily, certain kinds of disincentives are not only something you can reasonably ask of your friends, but something that some friends will thoroughly enjoy enforcing.

Schadenfreude

Schadenfreude is a most excellent German word that @AonTech pointed out to me meaning "pleasure derived from the misfortune of others". While serious misfortune yields sympathy from our friends — there are some undesired outcomes that are just downright funny. Whether it be someone attempting an acrobatic stunt and failing spectacularly or coming to the realization that they've just landed on Park Place and Board Walk with hotels in the same turn — sometimes it's just funny.

The Plan

This enjoyment of our friends' misfortunes is the primary motivational tool in my plan. The idea is to select a disincentive which your friends will gleefully enforce, tell everyone about it, then fight to deprive your friends of that sweet, sweet Schadenfreude.

The Bait

I couldn't think of a suitable motivating punishment, so I crowdsourced it to my beloved friends with the following post on Facebook:

The Restrictions

The bait was followed by a list of restrictions I was imposing on the punishment. #5 and up weren't included in the list I gave to my friends, but are things I would recommend if you plan to make your own pledge.

It has to only negatively affect me. This rules out punishments that would hurt my productivity on group projects or at work.
It has to have only short term negative consequences. It should be sweet sadistic joy for my friends, but shouldn't ruin my career, relationships or skeletal structure.
I can't be morally against the punishment. While I will do everything I can to avoid suffering the punishment — I have to be willing to actually go through with it.
It can't be illegal. This one is pretty self-explanatory.
It can't be charitable. One option I've seen before is to donate to a charity if you fail your goal. This seems like a poor option because you'll feel good about yourself for donating if you fail and it would make you feel crummy for celebrating the fact that you succeeded and don't have to give to charity.
It has to be all or nothing. Make success/failure boolean. If you reduce the punishment with every step you make, then you might be alright with bearing the brunt of 5% of the punishment. The last 5% of your trek should be the most motivating — not the least. The point here is not to make an effort — the point is to succeed.
It has to be impossible to fail the punishment. This rules out any punishment that requires a lot of time on the part of the person being punished, such as hours of physical labour or reading of terrible books.

The Response

I got the following recommendations for punishment upon failure:

Post all of the work you did, no matter how unfinished or terrible. This is a decent suggestion — but I don't think posting my incomplete stuff would bother me all that much.
Every day you don't draw, you have to start a company.
Chinese Water Torture.
Watch a movie with false depictions of programming for each day missed.
For every day missed, bike a kilometer.

But the winner was:

Get your legs waxed. This meets all of my criteria, and I really don't want to do this.

The Pledge

Starting January 1st, 2012, I will draw for a total of 121 hours before 11:59pm EST on May 1st, 2012. The accumulated time with be measured by me with minute accuracy using a stopwatch. If I fail to complete this goal, I will get my legs professionally waxed, and any of my friends who wish to attend will be allowed to do so.

Name your Arguments!

2011-11-28T00:00:00-05:00

"Programs should be written for people to read, and only incidentally for machines to execute." - Structure and Interpretation of Computer Programs

I've programmed enough now to start caring about the form as well as the function of my code. I can't even look at inconsistent style or naming conventions without twitching a little and wanting to fix it.

After reading and writing code full-time, I've come to appreciate the quote that starts this article. I'll explain why I support that sentiment so strongly with an example. Let's look at a very common function in JavaScript.

element.addEventListener('click', function() {
  console.log('Just got clicked!');
}, true);

So let's break down this code into components.

element - So we've got some element - alright cool. If you know a little about JavaScript and HTML, you'll guess that's an HTML element - so far so good.

addEventListener - ...and we want to listen for some event on this element. Still following, good stuff.

'click' - "click" is a word I understand as a computer user, and based on the name, I'm guessing that this means the code is listening for clicks.

function() { ... } - If you know JavaScript, you'll recognize that as a callback. It's an extremely common pattern that's well recognized and is fairly consistent across different APIs. You pass a function as a callback when you want it to be called later on. Still good.

true - ...and here's where the communication breaks down. What's true? Maybe it changes what this is in the context of the callback? Maybe it makes the callback only run once? In fact, it turns out that it fires the callback during the capture phase of the event bubbling - obvious, right?

The point is that there's absolutely no way of knowing what that true means.
Boolean flags are absolutely awful for readability. As it turns out, it's fairly important that addEventListener be extremely efficient, but let's pretend for a second that it didn't have to be - how can we make this more readable?

Option 1: Helpful variable names

var useCapture = true;
element.addEventListener('click', function() {
  console.log('Just got clicked!');
}, useCapture);

By using a variable, we've at least indicated what the flag pertains to. This is more readable, but having a one-time use variable like that is crufty. Let's assume we can change the API itself to facilitate more readable code. What can we do then?

Option 2: Namespaced constants

element.addEventListener('click', function() {
  console.log('Just got clicked!');
}, element.addEventListener.USE_CAPTURE);

This approach is better because it means that flag will be the same everywhere addEventListener is used, but it means duplicating the element.addEventListener.

Option 3: Hide the boolean arguments

If you ever have a function signature in a public API that takes a single boolean argument, you can hide it by just having two methods - one where that argument is true and another where the argument is false.

element.addCaptureEventListener('click', function() {
  console.log('Just got clicked!');
});

In the implementation, you would still have that boolean argument internally, (you weren't thinking of copy-pasting, right?) but at least the API user doesn't have to worry about it. This solution clearly doesn't scale for functions with a lot of boolean options, unless you have no problem with exponential growth in API size.

Option 4: "Named" arguments

element.addEventListener('click', function() {
  console.log('Just got clicked!');
}, {inCapturePhase: true});

Ah, there we go. Now I now what the true means! Now, there's still the matter of understanding what the "capture phase" is, but at least that's looking up concepts, not some arbitrary syntax imposed on you. Understanding event bubbling is useful - memorizing what the boolean third argument means is not.

Named Arguments

I love named arguments. Being able to tell exactly what all the arguments mean at the call site without having to look up the function signature every time is a sure way to make me happy as a developer.

JavaScript

"Named" was in quotes in Option 4 because JavaScript doesn't have real named arguments. Writing functions that take them in JavaScript is pretty kludgy, but it makes using the APIs much nicer. Take for instance, jQuery's $.ajax method.

$.ajax({
  url: "test.html",
  timeout: 1000,
  success: function(data) {
    console.log(data);
  },
  error: function(jqXHR, textStatus) {
    console.log(jxXHR);
  }
});

And compare that to another API with the same functionality but without using these named arguments:

$.ajax("test.html", 1000, function(data) {
  console.log(data);
}, function(jqXHR, textStatus) {
  console.log(jqXHR);
});

And watch the communication break down again. What's the 1000? Is the first callback the success callback or the error one? These are all questions you should never have to ask while reading code. In particular, it's an immense waste of everyone's time to have to remember what order arguments are supposed to be in.

Implementing APIs like this is unreasonable in some languages, and it's frankly somewhat of a pain in JavaScript. If you want to take options like this, you have to do silly things like this:

function fancyPrint(message, options) {
  options = options || {};

  var color = options.color;
  var bold = options.bold;
  var underline = options.underline;

  // ... implementation ...
}

fancyPrint('Hello', {color: 'red', bold: true});
fancyPrint('World', {underline: true, bold: false, color: 'blue'})

Still, if you're writing a library, please do this. I assure you the developers will appreciate it.

CoffeeScript

CoffeeScript provides an extremely nice syntax for this style exactly because it's such a pain in raw JavaScript. A translation of the above would look like this:

fancyPrint = (message, {color, bold, underline}) ->
  # ... implementation ...

print 'Hello', {color: 'red', bold: true}
print 'World', {underline: true, bold: false, color:'blue'}

Unfortunately, you lose the ability to have default arguments in CoffeeScript when using named arguments like this. Sadly, this doesn't work:

print = (message, {color='black', bold=false, underline=false}) ->
# Error: Parse error on line 2: Unexpected '='

Python

The argument system is Python is beautiful. All arguments are optionally named arguments, and you can define defaults just fine!

def fancyPrint(message, color='black', bold=True, underline=True):
  # ... implementation ...

fancyPrint('Hello', color='red', bold=True)
fancyPrint('World', underline=true, bold=false)
fancyPrint(color='black', message='!')

# You can even do this (please don't)
fancyPrint('Eugh', 'yellow', True, True)

An additional nicety of Python's argument system is that it will complain if you
pass it arguments it doesn't understand. (JavaScript just ignores them if you do this)

>>> fancyPrint('Hello', monkeys='cool')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: fancyPrint() got an unexpected keyword argument 'monkeys'

Objective C

Objective C takes a different approach here - the parameter names are part of the function signature itself. For example:

// A function invoked like this:
BOOL result = [myData writeToFile:@"/tmp/log.txt" atomically:NO];

// Will have signature like this
-(BOOL)writeToFile:(NSString *)path atomically:(BOOL)useAuxiliaryFile;

From Cocoa Dev Central's Learn Objective-C,

These are not just named arguments. The method name is actually writeToFile:atomically: in the runtime system.

Hacking It

In addition to the object literal solution I showed in the JavaScript and CoffeeScript sections above, there's another solution for C-like languages such as JavaScript, and it looks like this:

function fancyPrint(message, color, bold) {
  // ... implementation ...
}

var color, bold;
fancyPrint('Hello', color='red', bold=true);

Looks exactly like python - great, right? Well, not exactly. This is just abusing the fact that assignments return the value assigned in C-like languages.

While this does make the code more readable, it also makes it more fragile, and confusingly so. For instance, let's say we change the function signature:

function fancyPrint(message, color, underline, bold) {
  // ... implementation ...
}

var color, bold;
fancyPrint('Hello', color='red', bold=true);

Now you have the result of bold=true actually being assigned to the underline argument. So I'm not a fan of this solution for one reason:

Bad assumptions are far worse than no assumptions

Having to go look something up to see what that stupid boolean parameter does is annoying, but it's better than the code indicating it does something different than what it actually does.

This is actually a problem with options 1 & 2 above as well, but this is slightly worse because of the additional confusion created for people who might think that the assignment like this does act like Python's named arguments.

You get the same problem from commenting like this:

fancyPrint('Hello', /*color*/ 'red', /*bold*/ true);

For stable APIs, like addEventListener, these techniques are probably fine, but for your own projects' internal workings, it's probably a good idea to avoid this style.

Takeaways

Naming your arguments makes function calls more readable.
Avoid boolean arguments like the plague.
Bad assumptions are far worse than no assumptions.

If you want to hear more rambling about the minutia of good API design, you should follow me on twitter @jlfwong.

The Fifteen Puzzle - The Algorithm

2011-10-16T00:00:00-04:00

Before you read this, play with the above puzzle. You can move the blocks around yourself by clicking on one adjacent to the empty square. Click "shuffle" and the blocks will rearrange themselves using 25 randomly selected moves. Click "solve" from any configuration that isn't already ordered 1-15 and you'll see the blocks rearrange themselves.

If you hit shuffle more than 2 times, it'll take some work to solve the puzzle, so you'll see it solving for a while before it actually does anything. The version you see above is actually throttled so it doesn't freeze your browser or use hundreds of MB of memory.

As always, you can see source for the above: github.com/phleet/fifteen-puzzle.

Background

I've been going through Stanford's free online Introduction to Artificial Intelligence with my housemates and have been enjoying them. My favourite thing from the first set of lectures was the example of heuristics being applied to the Fifteen Puzzle. So I wrote up a solver and made the interactive demo you see above. Start watching at Unit 2, Topic 31, Sliding Blocks Puzzle to see a great explanation of what I'm doing.

Algorithm

The algorithm I used is pretty much exactly what's described in the video. My solution in coffeescript is an optimized and throttled version of the following:

solve = (startGrid) ->
  frontier = new PriorityQueue
  frontier.enqueue(new SolverState(startGrid, []))

  while not frontier.empty()
    curState = frontier.dequeue()

    if curState.solved
      return curState.steps

    candidateMoves = grid.validMoves()

    for move in candidateMoves
      nextGrid = grid.applyMove(move)
      nextSteps = curState.steps.concat([move])
      nextState = new SolverState(nextGrid, nextSteps)
      frontier.enqueue(nextState)

SolverState stores the current position of all the numbers in the grid and the list of steps to get there from the starting grid.

PriorityQueue is responsible for making sure we always explore the lowest cost state first. The cost of the state is the number of steps taken from the initial state plus the estimated number of steps remaining to get to the solution. This estimate (h2 from Unit 2, Topic 31) is admissible because each move can at best reduce that estimate by one.

grid.validMoves returns a list of all valid moves to make the on the grid. If the empty square is in the middle of the grid, this is all four directions. If it's in a corner, there are only two valid directions.

Optimizations

The algorithm described above will yield the optimal solution (fewest number of moves) for any valid fifteen-puzzle configuration. But it's pretty slow and can be much improved.

Tree Pruning

When looking at the search tree, there are some branches we can guarantee will not yield an optimal solution. The most obvious one here is to never go backwards. In the above algorithm, we can prevent going backwards like so:

lastStep = _.last(steps)
if lastStep?
  candidates = _(candidates).filter (x) ->
    not directionsAreOpposites x, lastStep

I'm using underscore.js for its functional goodness, so that's where _.last and _.filter come from.

Las Vegas Randomization

While the algorithm always takes the lowest cost state, there will frequently be ties. Because of of the nature of how validMoves works, this means that the algorithm will make a disproportionate number of moves in the same direction.
To fix this, we shuffle the list of valid moves before we start adding states to the priority queue. To do this, we change the candidates = ... line to be:

candidates = _.shuffle(grid.validMoves())

A Las Vegas algorithm is always right and sometimes fast. This is in contrast to a Monte Carlo algorithm, which is always fast and sometimes right.

Min-Heap Priority Queue

Once I applied the above to make the algorithm terminate in fewer iterations, it was time to optimize each iteration. By using Chrome Developer Tools, I was able to identify that the JavaScript runtime was spending most of its time in ProrityQueue::enqueue.

The first version I made of this used an O(nlogn) enqueue, O(1) dequeue method: I just appended and sorted after every enqueue and popped the element off the back of the array on dequeue.

Once I saw it was a bottleneck, I reimplemented the PriorityQueue as a min-heap to get O(logn) enqueues and dequeues, and this improved performance significantly.

You can see my implementation of a heap in coffeescript in solver.coffee.

Leveraging Known Results

After I switched to a min-heap, the next bottleneck was calculating the heuristic estimate. The observation here that made this faster is that the heuristic value can be determined for a state based on the previous state and the move used to get there. This prevents the need to recalculate the estimate for all the grids generated.

You can see this update applied on the commit: Leverage known results for lowerSolutionBound.

That's all for the algorithm. I'm planning to do two more posts about this project - one on using Chrome Developer Tools to optimize and how to not crash the browser, and another on the Jasmine test framework and literate programming with coffeescript. If you want to know when those come out, you should follow me on twitter @jlfwong.

Meet Doctor Jekyll

2011-10-03T00:00:00-04:00

My wordpress blog has lasted longer than any site I've used before, but I finally got sick of it and switched. So now I'm on Jekyll.

Wordpress is an incredible blogging-platform-turned-CMS that provides many things I wouldn't want to do myself. It's been an incredible SEO asset and worked beautifully on shared hosting. I would still recommend it to anyone who wants to write a blog and doesn't want to spend much time customizing or setting things up. There are plenty of nice looking pre-made themes and plugins to do pretty much anything you want.

Wordpress to Jekyll - Why I switched

Jekyll is "a blog-aware static site generator in Ruby". Basically what this means is that all the pages you see on this blog are generated once - not generated on demand every time they're requested. There's no DB backend, no scripting language running on the server side. These are just plain HTML pages.

I started off with a template I got off here: github.com/krisb/jekyll-template. But if you're planning on starting a blog similar to mine, don't start from scratch like I did - go check out Octopress. It provides a lot of niceties for blogging hackers that Jekyll doesn't out of the box.

So why did I switch?

Styling

While Wordpress is completely skinnable - it's a pain in the ass. I really just wanted to start from scratch and only build the things I absolutely needed. There is one unifying layout and only 2 types of page on this site: the posts list and posts. It means I can set my own structure for everything and keep it much, much simpler than it would have been on Wordpress.

Workflow

I love vim. I feel like I'm dragging a huge weight when I need to edit text - especially code - without vim. Since Jekyll just generates my site from code, it means I can edit everything including this post in vim. All I do is spawn up a local Jekyll server (WEBrick) and there's my preview. Once I'm done, all I have to do is commit the changes to git, and then I pull down the changes on my server - which is now hosted on EC2, with help from Andrew Tinits.

Novelty

I'll be honest here - I feel cooler running Jekyll than Wordpress. And having the source for my blog on github just feels right. Seriously: github.com/phleet/blog.

Plus there's nothing better to motivate you to write a blog post than redoing your entire blog. I promise I won't be another person who just writes a blog so they can write about how they set up their blog and then never write again (you know who you are.)

The Tech

Here's the part where I justify you spending the time reading this post by rambling about technology you might be interested in.

Markdown

Markdown is a content writing language for the web which compiles (primarily) down to HTML. The idea is that it enables you to write documents that are still readable in plaintext, but compile to useful HTML. This means having a nice syntax for headers, emphasis, links, images, lists and a couple of other things. It's definitely much nicer than raw HTML for writing up blog posts.

As a quick example, it takes this:

### Markdown

Markdown was written by John Gruber of [Daring Fireball][].

As a quick example, it takes this:

    Hello World
    -----------

    I am pretty awesome

and produces this:

    <h2>Hello World</h2>

    <p>I am pretty awesome</p>

[Daring Fireball]: http://daringfireball.net/

and produces this:

<h3>Markdown</h3>

<p>Markdown was written by John Gruber of <a href="http://daringfireball.net/">Daring Fireball</a>.</p>

<p>As a quick example, it takes this:</p>

<pre><code>Hello World
-----------

I am pretty awesome
</code></pre>

<p>and produces this:</p>

<pre><code>&lt;h2&gt;Hello World&lt;/h2&gt;

&lt;p&gt;I am pretty awesome&lt;/p&gt;
</code></pre>

Sass

Sass is awesome syntactic sugar for CSS. It deals with a bunch of things that are simply a giant pain in vanilla CSS. One of my favorite things it does is deal with nesting for you.

.container
  h1
    font-size: 20px
  h2
    font-size: 18px

    &:hover
      text-decoration: underline

Turns into:

.container h1 {
  font-size: 20px; }
.container h2 {
  font-size: 18px; }
  .container h2:hover {
    text-decoration: underline; }

Since it runs through a compiler before producing CSS, it lets you do some very useful things before producing the raw CSS. One of the most valuable things for me while working on this site was variables. It means you can do things like this:

$base-color: #281e17
$content-width: 500px
$sidebar-width: 150px

.container
  background-color: lighten($base-color, 50%)
  $padding: 20px
  padding: $padding
  width: $content-width + $sidebar-width - 2 * $padding

  .sidebar
    width: $sidebar-width
    background-color: lighten($base-color, 25%)

  .content
    width: $content-width
    color: $base-color

And get back this:

.container {
  background-color: #b99a85;
  padding: 20px;
  width: 610px; }
  .container .sidebar {
    width: 150px;
    background-color: #795b46; }
  .container .content {
    width: 500px;
    color: #281e17; }

The really cool thing about the color functions is that you can base your entire website off only a few colours, then make everything relative to those. This site (at time of writing) actually only has two colours specifically defined - the content font color and the body background. Everything else is relative to those.

Compass

Compass is a collection of mixins and utilities for sass. It's especially useful for CSS3 related tasks, since it does all the proprietary browser prefixes (-O-, -moz-, -webkit-) for you when you do things like +box-radius.

It also comes with Blueprint, which gives you a great starting point to have all the default styles for things (margins, typography, resets) look nice out of the box.

Pygments

Pygments is a syntax highlighter which produces HTML output which can then be styled with CSS. Github uses a wrapper around it called Albino to do all the syntax highlighting you see on the site, and it's what I'm using to make pygments work in Jekyll.

I'm actually using a custom Jekyll plugin to deal with all of this because I didn't want to have to stick liquid tags in my posts. In retrospect, this was probably really unnecessary, but it's done now.

You can see the plugin here: markdown.rb

Google Web Fonts

Google Web Fonts let you use a number of beautiful fonts that may not be available on your visitor's machine on your websites. I'm currently using it for my logo, sidebar and headers.

Using it is beautifully simple. All you have to do is drop a link tag in the head like the one I'm using:

<link href='http://fonts.googleapis.com/css?family=Questrial|Sansita+One' rel='stylesheet' type='text/css'>

And then use it like normal in a CSS rule, like so:

font-family: Questrial, "Helvetica Neue", Arial, Helvetica, sans-serif

Nginx

Since I had to set up my own web server to run this, I decided I'd try messing around with nginx since it looks much nicer to configure than apache. For the longest time, I thought it was pronounced "en-jinx". The actual pronounciation, "engine-ex" made a lot more sense once I heard it.

Setting up this server was extremely simple. Since I'm only serving static files, all I really needed was the following:

# Redirect any subdomain to the main domain
server {
  server_name *.jamie-wong.com;
  rewrite ^ http://jamie-wong.com$request_uri? permanent;
}

server {
  listen 80 default;
  server_name jamie-wong.com;
  server_name_in_redirect off;

  access_log /var/log/nginx/jamie-wong.com.log;

  index index.html index.php;

  try_files $uri $uri/ /404/ =404;

  # If it's in any of these folders I migrated from
  # my shared hosting on dreamhost, load it directly
  location ~ ^/(experiments|asciiconvert|life|Jobmine-Improved|V10|1yr)/ {
    root /var/www/jamie-wong.com/;
  }

  # Otherwise, it's probably a blog page, so load it
  # from Jekyll's generated _site directory
  location ~ / {
    root /var/www/jamie-wong.com/blog/_site/;
  }

  error_page  404  /404/;
}

This got a lot longer than I expected it to. Time for sleep - will proofread tomorrow.

Complex Asynchronous Queries in JavaScript

2011-06-25T00:00:00-04:00

Over the past couple of weeks, I finally got around to working on personal projects at an event I decided to create with the help of my housemates which we call SEHackDay. The first and only project I worked on over the 3 nights was Karma, a Facebook App which gives you statistics about your posts and how they stack up against your friends.

While it has not been remotely as successful as The Wub Machine by one of my housemates, Peter Sobot, it did make me think about how to make complex asynchronous queries in JavaScript.

While I was actually dealing with FB.api calls to the Facebook API, I'll use the example of jQuery AJAX queries for the purposes of this blog post, since they are more common. Before we delve into the complex examples, let's take a look at the basics.

Asynchronous Callbacks

If you already understand AJAX, skip to the complex queries below.

JavaScript is, by nature, an asynchronous language. A few of the language's built-in constructs use callbacks, including setTimeout and addEventListener. The basic principle of a callback is this:

When something happens, do this, but keep doing other things while you're waiting.

Here's a simple example:

window.setTimeout(function() {
  console.log("Three");
}, 1000);

console.log("One");
console.log("Two");

Run that with Firebug, Chrome Developer Tools or whatever other console logging tools you work with and you'll see that the numbers come out "One", "Two" and then finally "Three" after a one second delay.

A more useful example is retrieving data in jQuery through AJAX from the server. AJAX (for those unfamiliar) allows you to retrieve information on a web page from the server without necessitating a full page reload. A query typically looks something like this:

$.ajax({
  url: '/records.php',
  success: function(data) {
    console.log(data);
  }
});

Which says roughly: Send an HTTP GET request to the path /date. When the server responds, log the response body to the console.

For those of you reading this and unfamiliar with complex JavaScript, you should probably stop here, fiddle around with asynchronous callbacks and AJAX, and then consider continuing.

Sequential Requests with a Callback

Scenario: I want to request a series of documents, one after another, then run a callback after they've all completed. A common example is running through paginated data when you don't know how many pages there are.

Solution: Make the call recursive, keeping track of the data retrieved, then run the final callback when the last request completes.

For example, let's assume a page records.php returns the latest 10 records in a database as JSON, with a parameter offset, specifying how many records from the front to skip. We'll assume if it returns fewer than 10 results, there are no more. The coded solution will look something like this:

function allRecords(callback, offset, data) {
  if (typeof offset === 'undefined') {
    offset = 0;
  }
  if (typeof data === 'undefined') {
    data = [];
  }
  $.ajax({
    url: 'records.php',
    data: {offset: offset},
    success: function(dataChunk) {
      data = data.concat(dataChunk);
      if (dataChunk.length < 10) {
        callback(data);
      } else {
        allRecords(callback, offset + 10, data);
      }
    }
  });
}

And since there's a check for the undefined state of the second two parameters, they can be omitted when the function is actually called, like so:

allRecords(function(allData) {
  console.log(allData);
});

And this callback will be called only after the last request finishes. Assuming there are 47 records, it would make the following requests in series, then run the callback with the concatenated arrays of data.

records.php?offset=0
records.php?offset=10
records.php?offset=20
records.php?offset=30
records.php?offset=40

Note that this solution ensures that the records are returned in order.

Parallel Requests with a Callback

Scenario: I know exactly which documents I need, but I can't get them all at once, and I want to run a callback after all of them have been retrieved. A common use case is when you know exactly how many records there are, but for whatever reason (usually API limits), you can't get them all at once.

While a simple modification of the above solution would work, it's inefficient. We can send more than one AJAX response at a time, so we might as well wait on more than one at a time. Chances are we can send at least the second request while we're waiting for the first to return.

Solution: Send all the requests at once, noting how many were sent. Then count the responses as they come back. Once the count equals the number of requests sent, run the callback. Note that this does nothing to preserve order (and usually we don't care).

Assuming the same general rules as above, let's say we want to retrieve the most recent n records.

function nRecords(n, callback) {
  var nCallsNeeded = Math.ceil(n / 10);
  var nCallsFinished = 0;
  var data = [];
  for (var i = 0; i < nCallsNeeded; i++) {
    $.ajax({
      url: 'records.php',
      data: {offset : i * 10},
      success: function(dataChunk) {
        data = data.concat(dataChunk);
        nCallsFinished += 1;
        if (nCallsFinished == nCallsNeeded) {
          callback(data.slice(0,n));
        }
      }
    });
  }
}

So if I want the latest 23 records, I would get them like so:

nRecords(23, function(allData) {
  console.log(allData);
});

If you have suggestions on ways to improve these solutions, I'm all ears.

Also, if you are interested in what your highest rated post or just generally want to see your own statistics on pretty graphs, please check out Karma.

Hacker Cup Qualification Round - Solutions

2011-01-12T00:00:00-05:00

Overall, I was fairly disappointed with the organization and general structure of hacker cup qualification round. Hopefully the next round will be better, but for now - here are the solutions to the three questions. Unfortunately it seems the questions themselves have been taken down. I did manage to score 3/3, so I can be fairly sure that these are correct to the spec of the questions Facebook wrote.

Squares

Problem: For each given z, Find the # of pairs (x,y) such that x <= y and x² + y² = z.

Solution: Pre-generate the set of perfect squares. Iterate through this set. Check to see if z - x² is also in this set, where x is the current perfect square.

Implementation:

#include <iostream>
#include <set>
#include <cmath>
using namespace std;

typedef long long unsigned int llu;
set<llu> squares;

int main() {
  for (int i = 0; i < 50000; i++) {
    llu i2 = i*i;
    if (i2 > 2147483647L * 2L) {
      break;
    } else {
      squares.insert(i2);
    }
  }

  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    int num;
    cin >> num;
    int ans = 0;
    for(set<llu>::iterator it = squares.begin(); it != squares.end(); ++it) {
      llu first = *it;
      if (2 * first > num) break;
      if (squares.count(num - first)) {
        ans++;
      }
    }
    cout << ans << endl;
  }
}

Students

Problem: For a given set of words (sequences of lowercase letters), find the the lexicographically lowest string result from the concatenation of these words in any order.

Solution: I'm fairly sure simply sorting the words then concatenating them would suffice, but I was having issues string comparison yielding the same results at Facebook's output. Since the constraints were so low - maximum of 9 words per set, I simply did it exhaustively. This finishes easily within the 6 minute time limit since 9 factorial is relatively small.

Implementation:

from itertools import permutations

def doit():
    words = raw_input().split()[1:]

    best = ""

    for x in permutations(words):
        concatted = "".join(x)
        if best == "" or concatted < best:
            best = concatted

    print best

n = input()

for z in range(n):
    doit()

Pegs

Problem: Given a peg board in the format like this:

x.x.x
 x.x
x.x.x

defined by the number of rows and cols of pegs, except with a few pegs missing, like this:

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x

Determine the optimal location to drop a ball in order to maximize the probability of the ball landing in a specific slot in the bottom row. The probability of the ball going to either side of a peg is 0.5.

Solution: There's no real trick to this one - you just create an array of the probabilities that the ball reaches each available cell given which pegs are missing. This one is more of a coding problem than anything else.

I'm sure I could have written a more elegant solution to this problem, but I just wanted to get it done.

Implementation:

#include <iostream>
#include <set>
#include <cmath>
#include <utility>
using namespace std;

void doit() {
    int R, C, K, M;
    cin >> R >> C >> K >> M;
    set<pair<int,int> > missing;
    for (int i = 0; i < M; i++) {
        int ri, ci;
        cin >> ri >> ci;
        missing.insert(make_pair(ri,ci));
    }

    int best_pos = 0;
    long double best_prob = 0;
    for (int cur_pos = 0; cur_pos < C-1; cur_pos++) {
        long double probs[R][C];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                probs[r][c] = 0.00;
            }
        }
        probs[0][cur_pos] = 1.00;

        for (int r = 1; r < R; r++) {
            if (r % 2 == 1) { // odd row
                for(int peg = 0; peg < C-1; peg++) {
                    if (missing.count(make_pair(r,peg))) {
                        if (r+1 < R) probs[r+1][peg] += probs[r-1][peg];
                    } else {
                        if (peg == 0) {
                            probs[r][peg] += probs[r-1][peg];
                        } else if (peg == C-2) {
                            probs[r][peg-1] += probs[r-1][peg];
                        } else {
                            probs[r][peg]   += 0.5 * probs[r-1][peg];
                            probs[r][peg-1] += 0.5 * probs[r-1][peg];
                        }
                    }
                }
            } else { // even row
                for(int peg = 1; peg < C-1; peg++) {
                    if (missing.count(make_pair(r,peg))) {
                        if (r+1 < R) probs[r+1][peg-1] += probs[r-1][peg-1];
                    } else {
                        probs[r][peg]   += 0.5 * probs[r-1][peg-1];
                        probs[r][peg-1] += 0.5 * probs[r-1][peg-1];
                    }
                }
            }
        }

        long double cur_prob = probs[R-1][K];
        if (cur_prob > best_prob) {
            best_prob = cur_prob;
            best_pos = cur_pos;
        }
    }

    printf("%d %.6Lf\n", best_pos, best_prob);
}

int main() {
    int z;
    cin >> z;
    while(z--)doit();
}

Mechanize and UWAce Downloader

2010-11-17T00:00:00-05:00

A while ago I made something in php that would let you download things form UW-Ace (the University of Waterloo's course management system) from the command-line. Michael Chang had the excellent idea of making something that would simply download everything available to you from Ace so you could have a local copy of everything.

His solution was an extension of my php solution.

Because I wanted to make the product easier to distribute and because I wanted to make use of Mechanize, I rewrote the solution in ruby and packaged it as a gem.

UWAce Downloader

The new version looks like this:

To get it running, you'll need a copy of RubyGems, which you can get here: Download RubyGems. It's a simple package management and distribution system for ruby, which is used by more or less every ruby project you can think of.

Once you have that set up, just run

sudo gem install uwace

Wait for it to finish installing, then run

uwace

Which will prompt you for a username and password. Of course, I wouldn't release anything that asks for your password without releasing source, so here it is:

Mechanize

This version of the downloader is written in ruby with the aid of Mechanize for ruby. Mechanize is a set of tools for automating webpage interactions and retrieving data. It can identify links and forms on a page, fill them in, submit them and grab any data you want. Perfect for this task.

There's a simple guide on github here: Getting Started with Mechanize

To demonstrate how simple form interaction is, here's the method for login:

def login
  @username ||= ask("Username: ")
  @password ||= ask("Password: ") {|q| q.echo = '*'}

  say "Logging in ..."

  login_page = angel_get 'home.asp'
  form = login_page.form_with(:name => "frmLogon")
  form.username = @username
  form.password = @password

  login_submit_page = @agent.submit form

  if login_submit_page.uri.to_s.include? 'authenticate.asp'
    raise InvalidLogin
  end
rescue InvalidLogin
  say 'Invalid Username/Password'
  exit
end

While I've only used the Mechanize bindings for ruby, there bindings for many other languages:

Python's Mechanize
Perl's WWW::Mechanize - This was actually the original Mechanize

DFAs and Graphviz DOT

2010-10-16T00:00:00-04:00

As is usually the case with CS assignments, I tend to focus on reducing debugging time as much as possible by spending time coding things to make my life (and hopefully yours) easier.

On the latest assignment we are required to describe DFAs (Deterministic Finite Automatas) in a format with very low human readability, I knew immediately that I was going to write something to allow me to write my DFAs in a more human readable format so that I could sanely debug them. So instead of this:

2
0
1
5
start
zero
0mod3
1mod3
2mod3
start
2
zero
0mod3
8
start 0 zero
start 1 1mod3
1mod3 0 2mod3
1mod3 1 0mod3
2mod3 0 1mod3
2mod3 1 2mod3
0mod3 0 0mod3
0mod3 1 1mod3

I can do this in Ruby:

dfa = {
  :alphabet => %w(
    0
    1
  ),
  :states => %w(
    start
    zero
    0mod3
    1mod3
    2mod3
  ),
  :initial => 'start',
  :final => %w(
    zero
    0mod3
  ),
  :transitions => {
    'start' => [
      ['0','zero'],
      ['1','1mod3']
    ],
    '1mod3' => [
      ['0','2mod3'],
      ['1','0mod3']
    ],
    '2mod3' => [
      ['0','1mod3'],
      ['1','2mod3']
    ],
    '0mod3' => [
      ['0','0mod3'],
      ['1','1mod3']
    ]
  }
}

For those of you not familiar with ruby, %w(one two three) is equivalent to ['one','two','three']. Just a bit of syntactic sugar.

You can generate the DFA format required by Marmoset with the following function:

def dfa_output(dfa)
  lines = []
  lines << dfa[:alphabet].length.to_s
  dfa[:alphabet].each {|c| lines << c.to_s}

  lines << dfa[:states].length.to_s
  dfa[:states].each {|s| lines << s.to_s}

  lines << dfa[:initial].to_s

  lines << dfa[:final].length.to_s
  dfa[:final].each {|f| lines << f.to_s}

  transitions = []
  dfa[:transitions].each do |start,pair_array|
    pair_array.each do |(sym,targ)|
      if sym.is_a? String
        transitions << "#{start} #{sym} #{targ}"
      else
        sym.each do |s|
          transitions << "#{start} #{s} #{targ}"
        end
      end
    end
  end

  lines << transitions.length.to_s
  lines += transitions

  return lines.join("\n")
end

And then invoking with

puts dfa_output(dfa)

I designed the function with ranges and multiple transition tokens in mind, so you can do stuff like this:

'start_state' => [
  [%w(one that other),'end_state'],
  [1..9,'X']
]

Now, this makes fixing problems, once discovered, much much simpler than trying to locate the error in the DFA format, but it still doesn't help much by way of identifying problems in the DFA itself. Probably the easiest way to look at a DFA is as a picture. Thankfully, there exists a set of tools perfect for this task known as Graphviz.

Graphviz DOT

Graphviz is a collection of utilities used for visualizing graphs. The tool of interest for this post is DOT. It produces the kind of thing you can see above - which is the same graph described by the ruby code and the DFA format above.

The syntax of DOT is very simple, and is better explained by the DOT language wiki entry than by the official documentation. The DOT description of the above graph is as follows:

digraph dfa {
  "" [shape=none]
  "start" [shape=circle]
  "zero" [shape=doublecircle]
  "0mod3" [shape=doublecircle]
  "1mod3" [shape=circle]
  "2mod3" [shape=circle]

  "" -> "start"
  "1mod3" -> "2mod3" [label="0"]
  "1mod3" -> "0mod3" [label="1"]
  "0mod3" -> "0mod3" [label="0"]
  "0mod3" -> "1mod3" [label="1"]
  "2mod3" -> "1mod3" [label="0"]
  "2mod3" -> "2mod3" [label="1"]
  "start" -> "zero" [label="0"]
  "start" -> "1mod3" [label="1"]
}

And this is the ruby code to generate that output using the dfa = { ... } format at the beginning of the post.

def dot_output(dfa)
  lines = []
  lines << "digraph dfa {"

  lines << %(\t"" [shape=none])

  dfa[:states].each do |state|
    if (dfa[:final].include? state)
      lines << %(\t"#{state}" [shape=doublecircle])
    else
      lines << %(\t"#{state}" [shape=circle])
    end
  end

  lines << ''
  lines << %(\t"" -> "#{dfa[:initial]}")

  dfa[:transitions].each do |start,pair_array|
    pair_array.each do |(sym,targ)|
      if sym.is_a? String
        lines << %(\t"#{start}" -> "#{targ}" [label="#{sym}"])
      else
        lines << %(\t"#{start}" -> "#{targ}" [label="[#{sym.collect(&:to_s).join(',')}]"])
      end
    end
  end

  lines << "}"

  return lines.join("\n")
end

Once you've installed Graphviz, you can generate a PNG of the graph by running

dot -Tpng < graph.dot > graph.png

Enjoy CS241 A5.

Make your life easier with GNU Make.

2010-09-30T00:00:00-04:00

I've been trying to keep at least one post per month going, and I was sick with stomach flu today, so here goes:

As our CS assignments get more and more complex, it's starting to become time consuming to build, test, and submit each assignment. I could either do this every time I want to test:

java cs241.binasm < a2p8.asm > a2p8.mips
java mips.array a2p8.mips < a2p8.sample.in
java mips.array a2p8.mips < a2p8.onenode.in

Or I could just run make.

What is make?

GNU Make is a system for constructing executables or other non-source code files from source code. It allows you to specify dependencies for files and define rules for constructing them from source. For example, the rule to build a2p8.mips would look like this:

a2p8.mips: a2p8.asm
    java cs241.binasm < a2p8.asm > a2p8.mips

This says, to make a2p8.mips, run java cs241.binasm < a2p.asm > a2p8.mips. To use make, stick your ruleset in a file called Makefile in the same directory as your source then run make. This command will only run if a2p8.asm has changed since the last time it was run. These dependencies stack as well. For instance, say I need to join two files together before I compile them. I can define a ruleset like this:

linked.mips: linked.asm
    java cs241.binasm < linked.asm > linked.mips

linked.asm: a2p7.asm print.asm
    cat a2p7.asm print.asm > linked.asm

This will link the files together before it tries to compile them. It'll also make sure it's up to date whenever you change either a2p7.asm or print.asm. The build rule at the top of the Makefile is called the default rule. This is the one that gets run when you just run make at the command line. You can also pass a parameter to tell make to construct something specific. For instance, I could run make linked.asm here to just build the linked file without actually compiling it to machine code.

Automatic Variables in Make

One of the principles of writing good code is DRY: Don't Repeat Yourself. Make provides various ways to support this through the use of automatic variables. Automatic variables are ones that are set for you with useful values. For instance, the following rule:

linked.asm: a2p7.asm print.asm
    cat a2p7.asm print.asm > linked.asm

can be reduced to this:

linked.asm: a2p7.asm print.asm
    cat $^ > $@

The variable $^ is a space separated list of all the dependencies. $@ is the target. See GNU make - Automatic Variables for the full list and description of such variables.

Writing Implicit Rules

Another unnecessary piece of code duplication exists for compiling multiple files of the same type. For instance, the following is repetitive:

a2p8.mips: a2p8.asm
    java cs241.binasm < $< > $@

a2p7.mips: a2p7.asm
    java cs241.binasm < $< > $@

Instead, I can define my own implicit rule for building all *.mips files like so:

%.mips: %.asm
    java cs241.binasm < $*.asm > $*.mips

Testing Using Make

One of the things I took away from my co-op term at The Working Group was the benefits of test driven development. Untested code is broken code, and manual testing is tedious and annoying. As your code gets more and more complicated, there will be more and more edge cases to deal with. These cannot be dealt with a single test case. Normally, you would be forced to write multiple input files and pass them each individually to the executable to see if everything worked. I don't like having to do this. So instead, I defined my own ruleset:

ASSIGNMENT = a2p7

test: linked.mips Empty.test All.test

%.test: $(ASSIGNMENT).%.in
  @echo ----------- $* ------------------
  java mips.array linked.mips < $^

%.mips: %.asm
  java cs241.binasm < $*.asm > $*.mips

linked.asm: $(ASSIGNMENT).asm print.asm
  cat $^ > $@

This one merits a bit of explanation. The default task here is test, and it has no recipe associated with it. Instead, it just makes sure all of its dependencies are up to date. Empty.test and All.test here aren't actual files. They're simple methods of referring to another rule, in this case the %.test implicit rule.

The %.test implicit rule depends on a corresponding input file. For example, Empty.test will rely on a2p7.Empty.in, which will then be passed in as input to the executable. The result from running looks like this:

$  make
----------- Empty ------------------
java mips.array linked.mips < a2p7.Empty.in
Enter length of array: MIPS program completed normally.
$01 = 0x000001c4   $02 = 0x00000000   $03 = 0x00000000   $04 = 0x00000000
$05 = 0x00000000   $06 = 0x00000000   $07 = 0x00000000   $08 = 0x00000000
$09 = 0x00000000   $10 = 0x00000000   $11 = 0x000001c4   $12 = 0x00000000
$13 = 0x00000000   $14 = 0x00000000   $15 = 0x00000000   $16 = 0x00000000
$17 = 0x00000000   $18 = 0x00000000   $19 = 0x00000000   $20 = 0x00000000
$21 = 0x00000000   $22 = 0x00000000   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c
----------- All ------------------
java mips.array linked.mips < a2p7.All.in
Enter length of array: Enter array element 0: Enter array element 1: Enter array element 2: 123
0
-456
MIPS program completed normally.
$01 = 0xfffffe38   $02 = 0x00000003   $03 = 0x00000001   $04 = 0x00000000
$05 = 0x00000000   $06 = 0x00000000   $07 = 0x00000000   $08 = 0x00000000
$09 = 0x00000000   $10 = 0x00000000   $11 = 0x000001d0   $12 = 0x00000000
$13 = 0x00000000   $14 = 0x00000000   $15 = 0x00000000   $16 = 0x00000000
$17 = 0x00000000   $18 = 0x00000000   $19 = 0x00000000   $20 = 0x00000000
$21 = 0x00000000   $22 = 0x00000000   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c

The echo line above that simple outputs the name of the test before running it so it looks nicer on the console. The @ before the echo prevents make from displaying the command, otherwise it would look like this:

$  make
cat a2p7.asm print.asm > linked.asm
java cs241.binasm < linked.asm > linked.mips
echo ----------- Empty ------------------
----------- Empty ------------------

Submitting to Marmoset from the Commandline

Just for kicks and because I wanted to mess around with Mechanize, I built a ruby script which will submit to Marmoset for me. You can try it out yourself if you have Ruby and Rubygems by running

sudo gem install marmoset

Or you can browse the code yourself here: http://github.com/phleet/MarmosetSubmit

Here's how you can integrate the submission process into your Makefile:

submit: $(ASSIGNMENT).asm
    marmoset -u jlfwong -c cs241 -a $(ASSIGNMENT) -f $(ASSIGNMENT).asm

For now, it only submits - there's no way of checking to see if it was successful or running the release tests. I can build that if people are really interested in that, or you can fork the github repo and do it yourself.

Well, that's all for now. Time to study up for Electrodeath.

Javascript Dependency Loading – jquery.atreq

2010-08-14T00:00:00-04:00

For a project I'm working on, I have a fairly complex dependency tree and was getting fed up with manually including every single one in my haml layout file. So I started looking up other solutions and eventually decided none met my needs, so, as usual, I wrote my own.

jquery.atreq @ github

Because there's not much to say beyond what I have in the readme, and because this blog is conveniently set up to format with markdown, I'm just going to display the current state of that here.

jquery.atreq

jquery.atreq loads your javascript dependencies asynchronously.

How to use

First, include your main application file with $.atreq

<script type='text/javascript' src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script>
<script type='text/javascript' src="jquery.atreq.js"></script>
<script type='text/javascript'>
$.atreq('application.js');
</script>

Then inside your application.js and any other required files, place a require statement in the comments.

// application.js
// @require 'lib/lib1.js'
// @require 'lib/lib2.js'

Library1Function();
Library2Function();

NOTE: While //@require "blocks", $.atreq does not. This means the following will not work:

$.atreq('lib/lib1.js');
Library1Function();

Relative Require Paths

Unless the require paths begin with a /, they're assumed to be relative to the location of the file they're in.

This means, since lib1.js is in lib/, the require statement below will load lib/deb/lib1dep.js. This makes your code portable across locations.

Each of the library files can also have their own dependencies, and $.atreq will make sure they're run in the correct order.

// lib/lib1.js
// @require `dep/libdep.js`

function Library1Function() {
    alert('Awesome!");
}

Redundant or Duplicate Requires

Duplicate requires of the same file will neither request nor run the same file twice. This is true even if the relative path is different from files. This means that:

// lib/lib2.js
// @require '../shared/shared.js'

and

// lib/lib3.js
// @require '../shared/shared.js'

will only make one request out to shared/shared.js.

Alternatives and How They're Different

$.include

A jQuery plugin by Tobiasz Cudnik, this does load external files asynchronously, but these dependencies are non-blocking. He dodges this issue by delaying the document.ready event

It even has the ability to load dependencies for included scripts like so (taken from his blog post):

$.include(
    // URL
    'js/my-script.js',
    // will be loaded after this script
    $.include(baseURL+'js/my-other-script.js')
);
$.include('js/src/behaviors.js',
    // dependencies can also be an array
    [
        $.include('js/src/jquery-metadata.js'),
        $.include('js/src/jquery.form.js')
    ]
);

This is great, except that it requires all the dependencies to be loaded from the same file. This means you won't get useful behaviour if one of the files you're including has internal dependencies.

See: $.include() @ tobiasz123.wordpress.com

$.require

Another jQuery plugin, $.require doesn't have the problem of $.include: required files can require files of their own and scripts will still be parsed in the correct order.

The way it does this is it forces the scripts to be included synchronously. Functionality wise, this has no effect. However, it will result in slower load times for complex dependency trees.

The require paths in this script are relative to the inclusion point (the HTML file), not the script itself.

Comparison of load times for the following dependency tree:

application.js
|--- 1.js
|    |--- 1a.js
|    |--- 1b.js
|    \--- shared.js
\--- 2.js
     |--- 2a.js
     |--- 2b.js
     \--- shared.js

Inside each file is the required include statements, a loop iterating 10000 times, and ~4kb of lorem ipsum in comments to bloat the file size.

$.atreq:

$.require:

Note the difference in the load order - there's no reason why 1.js and 2.js shouldn't load at the same time.

See: $.require @ plugins.jquery.com

WARNING: At time of writing, the script provided on that page does not work and makes some strange assumptions about the location of your javascript files on the server. Use with caution.

JSONimal - Elegant DOM Contruction with jQuery

2010-07-16T00:00:00-04:00

EDIT There is a more complete project achieving exactly the goals I set out for called jquery-haml: http://github.com/creationix/jquery-haml

Occasionally for Javascript projects, I found myself building a lot of HTML programatically, and I wasn't satisfied with any of the techniques available, so I built JSONimal. I was originally going to just call it JSONML, but that was taken.

What's it do? This example should demonstrate my goal fairly well.

$(function() {
    $.mktag("#demo").jsonimal([
        ["h1", {text: "JSONimal!"}],
        ["table",{style: 'border: 1px solid black'},[
            ["thead",[
                ["tr",{style: 'text-transform: uppercase'},[
                    ["th", {text: "one"}],
                    ["th", {text: "two"}],
                    ["th", {text: "three"}]
                ]]
            ]],
            ["tbody", [
                ["tr",[
                    ["td", {html: "<u>a</u>"}],
                    ["td", {text: "b"}],
                    ["td", {text: "c"}]
                ]],
                ["tr",[
                    ["td",[
                        ["a", {href: "http://www.google.ca", text: "Google"}]
                    ]],
                    ["td", {text: "b"}],
                    ["td", {text: "c"}]
                ]],
                ["tr",[
                    ["td", {text: "a"}],
                    ["td", {text: "b"}],
                    ["td", {text: "c"}]
                ]]
            ]]
        ]]
    ]).appendTo("body");
});

Which will add this to the body:

JSONimal!

one	two	three
a	b	c
Google	b	c
a	b	c

For more information and examples, check out the github page: JSONimal @ github.

I also posted it as on the jQuery plugins page - but that just points to the github page anyway. JSONimal @ plugins.jquery.com

Flex/Actionscript 3: Debug Output to Console

2010-07-07T00:00:00-04:00

I recently started messing around with the Flixel framework - something built on top of Flex to make retro games. One of the first things I noticed was how difficult it is to debug things - especially complex objects.

The first problem is capturing any debug output. For whatever reason, I was unable to output traces to anywhere useful. My first success was with using De MonsterDebugger to capture the output. While this was better than nothing, I needed very little of the functionality of De MonsterDebugger and it still didn't give me what I really wanted: formatted console output.

print_r style output in actionscript

I found a good starting point here, but the output of this wasn't exactly what I wanted. I messed around with it until I got something more familiar to me.

package learning {
  import org.flixel.*;

  public class Debugger {
    public static function pr(obj:*, level:int = 0, output:String = ""):* {
      var objtype:String = typeof(obj);
      if (objtype == "boolean" || objtype == "string" || objtype == "number") {
        return obj;
      }

      var tabs:String = "";
      for(var i:int = 0; i < level; i++) {
        tabs += "\t"
      }

      output += "{\n";
      for(var child:* in obj) {
        output += tabs +"\t["+ child +"] => ";

        var childOutput:String = pr(obj[child], level+1);
        if(childOutput != '') output += childOutput

        output += "\n";
      }
      output += tabs + "}\n";

      return output;
    }

    public static function log(obj:*):void {
      FlxG.log(pr(obj));
      // This is a flixel thing. If you're not using flixel
      // Just use trace(pr(obj));
    }
  }
}

Example output

{
    [0] => {
        [tile] => 4
        [rule] => {
            [0] => xxx
            [1] => x1x
            [2] => x1x
        }
    }
    [1] => {
        [tile] => 8
        [rule] => {
            [0] => x1x
            [1] => x1x
            [2] => xxx
        }
    }
}

trace output to console

This, fortunately, was much less of a hassle for me to get working.

Reference: Configuring the debugger version of Flash Player

Step 1

Locate/create your mm.cfg file. For me this was in ~/mm.cfg. See reference.

Stick this in it: TraceOutputFileEnable=1

Or, in one command:

echo "TraceOutputFileEnable=1" > ~/mm.cfg`

Step 2

Locate the location of the log file. Mine is in

~/Library/Preferences/Macromedia/Flash Player/Logs/flashlog.txt`

See reference.

You don't want to type this in every time you want to view the log, so add a function to your .bash_profile

This is what I have:

flashlog() {
  tail -f $* ~/Library/Preferences/Macromedia/Flash\ Player/Logs/flashlog.txt;
}

Step 3

Start debugging!

$ flashlog -100
Warning: 'flash' has no property 'prototype'
Warning: 'flash' has no property 'prototype'
flixel v2.35 [debug]
----------------------------------------------------
{
    [0] => {
        [tile] => 4
        [rule] => {
            [0] => xxx
            [1] => x1x
            [2] => x1x
        }
    }
    [1] => {
        [tile] => 8
        [rule] => {
            [0] => x1x
            [1] => x1x
            [2] => xxx
        }
    }
}

Commandline Tips and Tricks

2010-06-29T00:00:00-04:00

Alas, I have been stricken with the plague of half-finished posts and projects. But, as I feel the need to have at least one post per month, here's some stuff you might find useful.

I forget where I discovered this, but commandlinefu.com is an awesome site.

It's so awesome in fact, that I think the productivity gains I've gotten from it almost outweigh the time I wasted looking through the site and testing it.

Here are some of the more useful ones from the site and a few I learned at work and elsewhere.

Change to previous working directory

From: Change to the previous working directory @ commandlinefu.com

$ pwd
/Users/jamiewong/code/stackoverflow

$ cd /usr/bin

$ pwd
/usr/bin

$ cd -
/Users/jamiewong/code/stackoverflow

$ pwd
/Users/jamiewong/code/stackoverflow

Rerun the last command

From: Run the previous command with sudo @ commandlinefu.com

$ echo hello
hello

$ !!
echo hello
hello

$ ln -s some_script.sh /usr/bin/some_script
ln: /usr/bin/some_script: Permission denied

$ sudo !!
sudo ln -s some_script.sh /usr/bin/some_script

$ ls -l /usr/bin/some_script
lrwxr-xr-x  1 root  wheel  14 30 Jun 00:44 /usr/bin/some_script -> some_script.sh

$ cat /etc/apache2/passenger_pane_vhosts/searchgraph*
<VirtualHost *:80>
  ServerName searchgraph.local
  DocumentRoot "/Users/jamiewong/Code/searchgraph/public"
  RailsEnv development
  <Directory "/Users/jamiewong/Code/searchgraph/public">
    Order allow,deny
    Allow from all
  </Directory>
</VirtualHost>

$ echo "!!"
echo "cat /etc/apache2/passenger_pane_vhosts/searchgraph*";
cat /etc/apache2/passenger_pane_vhosts/searchgraph.local.vhost.conf

Modify the last command and run it

From: Runs the previous command but replacing @ commandlinefu.com

$ echo hello world
hello world

$ ^world^friends
echo hello friends
hello friends

$ ls *.php
bolding.php shd.php     stream.php

$ ^php^rb
ls *.rb
hms.rb           split_orderby.rb
</pre><pre class="cmd">
$ cds ..
-bash: cds: command not found

$ ^s
cd ..

List your last n commands

$ history 10
 522  locate mysqld
 523  sudo /Library/StartupItems/MySQLCOM/MySQLCOM start
 524  sudo /Library/PreferencePanes/MySQL.prefPane/Contents/MacOS/MySQL
 525  sudo mysqld_safe
 526  sudo /usr/local/mysql/bin/mysqld_safe
 527  mysql
 528  history
 529  history | awk '{a[$2]++}END{for(i in a){print a[i] " " i}}' | sort -rn | head
 530  history
 531  history 10

Edit and run a previous command

From: Edit the last command line in an editor then execute @ commandlinefu.com

This one requires a bit of explanation. The fc command will, by default, open your last command in the console editor you specify (emacs by default).
If you want it to be vim, stick this in your .bash_profile to just run it when you want to use it.

export EDITOR=vim

Then run fc, and it will open up your editor with your last command in it. Save and exit (:wq) to run that command. If you just want to execute it immediately, use fc -s.

$ history 5
  86  cat /etc/apache2/passenger_pane_vhosts/searchgraph.local.vhost.conf
  87  echo "cat /etc/apache2/passenger_pane_vhosts/searchgraph.local.vhost.conf "
  88  history 10
  89  echo "cat /etc/apache2/passenger_pane_vhosts/searchgraph.local.vhost.conf "
  90  history 5

$ fc -s 87
echo "cat /etc/apache2/passenger_pane_vhosts/searchgraph.local.vhost.conf "
cat /etc/apache2/passenger_pane_vhosts/searchgraph.local.vhost.conf

If you don't care to look up the history number but happen to remember that it was the command you executed two lines ago, you can use negative history numbers

$ echo hello
hello

$ echo world
world

$ fc -s -2
echo hello
hello

Follow new output to a log

This one comes from my coworkers

$ tail -f ~/code/searchgraph/log/development.log


Processing HomeController#bp (for 127.0.0.1 at 2010-06-23 22:19:27) [GET]
Rendering home/bp
Completed in 6ms (View: 5, DB: 0) | 200 OK [http://searchgraph.local/bp]


Processing HomeController#bp (for 127.0.0.1 at 2010-06-23 22:20:46) [GET]
Rendering home/bp
Completed in 9ms (View: 7, DB: 0) | 200 OK [http://searchgraph.local/bp]

Then if I go open up searchgraph.local, my console window will get updated on its own

Copying and pasting from files

The pbcopy and pbpaste commands copy and paste from your clipboard.

$ echo test > test.txt

$ pbcopy < test.txt

$ pbpaste
test

And if you want to paste content you have in your clipboard to a file, just redirect, with

$ pbpaste > output.txt

That's all for now - I'll write more down as I find them.

Google Codejam 2010 Solutions - Qualification

2010-05-11T00:00:00-04:00

I'm happy to have qualified for Codejam for the second year running - I managed to make it to Online Round 2 last year, so let's see if I can top that this year.

The opening round was not very difficult, and were it not for a very stupid mistake on my part on the first question, I easily could have gotten perfect in under 2.5 hours. Instead I got 76 in 3.5 hours. Bah.

Read the questions here: Qualification Round 2010 @ code.google.com

Problem 1: Snapper Chain

This is the one I screwed up, because I somehow overlooked the fact that each snap was simply equivalent to an binary increment of the snappers states. Instead, I did a foolish simulation, which did actually pass me the small test case. But anyway, the real solution is O(1).

For interest, here's what the snapper chain looks like in the first 30 iterations. The left side, labeled "P:" shows which of the snappers are powered, and the right side, labeled "S:" shows the current state of the snappers, with "#" being ON and "." being OFF in both cases. I did this so it would be easier to see the pattern. The first row is the initial set up, before any snaps.

P: #.........   S: ..........
P: ##........   S: #.........
P: #.........   S: .#........
P: ###.......   S: ##........
P: #.........   S: ..#.......
P: ##........   S: #.#.......
P: #.........   S: .##.......
P: ####......   S: ###.......
P: #.........   S: ...#......
P: ##........   S: #..#......
P: #.........   S: .#.#......
P: ###.......   S: ##.#......
P: #.........   S: ..##......
P: ##........   S: #.##......
P: #.........   S: .###......
P: #####.....   S: ####......
P: #.........   S: ....#.....
P: ##........   S: #...#.....
P: #.........   S: .#..#.....
P: ###.......   S: ##..#.....
P: #.........   S: ..#.#.....
P: ##........   S: #.#.#.....
P: #.........   S: .##.#.....
P: ####......   S: ###.#.....
P: #.........   S: ...##.....
P: ##........   S: #..##.....
P: #.........   S: .#.##.....
P: ###.......   S: ##.##.....
P: #.........   S: ..###.....
P: ##........   S: #.###.....

What we're interested in is how to tell where a specific snapper is on. It turns out that this is quite simple - so long as all snappers before it are on the ON settings, it will be powered. This means that ultimately, the power column above is irrelevant. All we need to know is that the N-1 least significant bits are set. This is fairly trivial to check.

#include <iostream>
using namespace std;
int main() {
  int T,N,K;
  cin >> T;
  for(int t = 0; t < T; t++) {
    cin >> N >> K;
    int mask = (1 << N) - 1;
    printf("Case #%d: ",t+1);
    if ( (mask & K) == mask) puts("ON");
    else puts("OFF");
  }
  return 0;
}

Time for the large case:

$ time ./a.out < snapper.in > snapper.out

real    0m0.071s
user    0m0.026s
sys     0m0.040s

Problem 2: Fair Warning

This problem took me about 40 minutes to think of the solution for and about 5 minutes to code. Honour's Algebra (MATH 115) came in handy here. You can first calculate T (the optimal anniversary) by looking at the gcd (greatest common divisor) of the differences between the time elapsed since the events. This works because in order for T to divide the time elapsed since the events, it must also divide the time elapsed between the events. After that, you just need to find the first y that makes any of the numbers divisible by T. I just wrote out the congruences on my whiteboard (which I probably shouldn't have needed to do) then typed in my answer.

The only remaining problem here is dealing with the large numbers, which is hardly a problem in python. Here's my solution:

def gcd(x,y):
    while x:
        x, y = y % x, x
    return y

testcases = open("warning.in").readlines()
t = 1
for tc in testcases[1:]:
  tc = map(lambda x: int(x), tc.split(" ")[1:])
  if len(tc) == 0:
    break
  tc.sort()
  #print tc

  diff = []
  for i in range(len(tc)-1):
    diff += [tc[i+1] - tc[i]]

  T = diff[0]
  for d in diff[1:]:
    T = gcd(T,d)

  #print T
  print "Case #%d: %d" % (t, (-tc[0] % T))

  t += 1

Time for large case:

$ time python warning.py > warning.out

real    0m0.250s
user    0m0.037s
sys     0m0.021s

Problem 3: Theme Park

This is an optimization problem. There are a lot of different optimizations you can apply, but I figured "to hell with it" and decided the solution getting it down to O(R) was probably sufficient. If you want to look at a better list of optimizations, go look here: Google Codejam 2010 Qualification Round Contest Analysis.

All I figured I needed to do was make it so I didn't have to find the groups every single time the ride was loaded. To do this, I simulated using a queue until I arrived at a position where the group at the front of the line had been at the front before. While doing this, I record how many euros were made for a given start of the line, and who ends up at the front of the line while they're on the roller coaster. After this, the O(R) loop is very simple. Just add the number of euros for the run, then move on to the next front of the line.

#include <cmath>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <vector>
using namespace std;

#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define SETMIN(a,b) a = min(a,b)
#define SETMAX(a,b) a = max(a,b)
#define PB push_back
#define FORALL(i,v) for(typeof((v).end())i=(v).begin();i!=(v).end();++i)
#define CLR(x,a) memset(x,a,sizeof(x))
#define BEND(v) v.begin(),v.end()
#define MP make_pair
#define A first
#define B second

typedef unsigned long long int ull;
typedef long double ld;

int main() {
    freopen("themepark.in","r",stdin);
    freopen("themepark.out","w",stdout);

    int T;
    cin >> T;
    FOR(t,T) {
        int R,k,N;
        cin >> R >> k >> N;
        int grps[1001], done[1001], pts[1001], next[1001];
        CLR(done,0);
        queue<pair<int,int> > q;
        FOR(i,N) {
            cin >> grps[i];
            q.push(MP(i,grps[i]));
        }

        while(!done[q.front().A]) {
            int cur = 0;
            int start = q.front().A;
            done[start] = 1;

            FOR(i,N) {
                if (cur + q.front().B > k) break;

                cur += q.front().B;
                q.push(q.front());
                q.pop();
            }
            next[start] = q.front().A;
            pts[start] = cur;
        }

        while (!q.empty()) q.pop();

        int curFront = 0;
        ull ans = 0;
        FOR(i,R) {
            ans += pts[curFront];
            curFront = next[curFront];
        }

        printf("Case #%d: %lld\n", t+1, ans);
    }
    return 0;
}

Time for large test case:

$ time ./a.out

real    0m11.606s
user    0m11.542s
sys     0m0.022s

I might code up an O(N) solution later, which really isn't that difficult, but at this point in the contest, it simply didn't matter enough.

AJAX Method Callbacks and Omegle Voyeur Update

2010-04-19T00:00:00-04:00

I finally got back around to updating Omegle Voyeur with the ability to interfere, and decided to re-implement the whole thing in jQuery while I'm at it. Since jQuery doesn't come with a built-in method of building classes, I used lowpro for jQuery. It's a port of a class building scheme from Prototype. It doesn't do everything I could have hoped for, but it served most of my needs.

The other thing I implemented was a way of knowing when Omegle is blocking requests. They have a more robust form of detection now - it isn't just manual IP ban. Once you request too many things from them too fast, they start requesting a captcha. Locally, this isn't a problem - I simply embed an iframe with Omegle in it and provide instructions to the user. Hosted, this is a more troublesome problem, since the captcha is directed towards an IP, so it must be responded to from that IP. I have no solution to this problem at the moment, but I'm going to look into implementing the whole thing using Greasemonkey so this isn't an issue at all.

For now, you can see the latest version here: Omegle Voyeur. Don't be surprised if it's down, and please go grab your own copy: Omegle-Voyeur @ github.

Now on to the customary technical concept to go along with my own self promotion.

AJAX Method Callbacks

While passing functions as arguments is a pretty standard thing among almost all languages, attempting to pass methods of specific instances as arguments in JavaScript presents an interesting problem. Consider the following:

function car(price) {
    this.price = price;

    this.setPrice = function(price) {
        this.price = price;
    };
}

function pass666(func) {
    func(666);
}

var redcar = new car(2000);
alert(redcar.price);
redcar.setPrice(123);
alert(redcar.price);
pass666(redcar.setPrice);
alert(redcar.price);

As you might expect, the first two alerts will say 2000 and 123 respectively. But the last one also says 123. Why?

It all has to do with what this refers to. Both in the initialization of redcar and the modifier call redcar.setPrice, "this" refers to the instance of the function car given the identifier name redcar. In the pass666 version, this refers to the function pass666. As a result, it does nothing to modify the properties of the car because it isn't told anything about redcar.

One way to fix this is to use a placeholder variable. I used "self". Change the definition of car to the following yields the desired result.

function car(price) {
  this.price = price;

  var self = this;
  this.setPrice = function(price) {
    self.price = price;
  };
}

In this example, it's difficult to see why you would ever want to use this in the first place. The reason I encountered this problem is my need to use instance methods as callback functions for AJAX calls. Here's an excerpt of the jQuery version of Omegle Voyeur to see what I'm talking about.

sendQuery: function(target,respFunc) {
  // Send a query to the omegle server
  //log('sending');
  var self = this;
  if (respFunc == null) {
    respFunc = function(self,data) {}
  }
  $.ajax({
    url: 'omegle.php?'+target,
    type: 'GET',
    dataType: 'json',
    success: function(data) {
      respFunc(self,data);
    }
  });
},

Sending a request to the Omegle server is a very common task in Omegle Voyeur, so I wanted all the AJAX requests leaving from the same method. This means I have to accept the callback function as a parameter. I've written all the callback methods to accept a parameter self which will refer to the instance of interest.

This aspect is one of the many things that makes Prototype's class system superior to jQuery's. However, since jQuery makes a lot of other things nicer and the two libraries don't play together very well, I decided to port over to jQuery nonetheless. In Prototype, there's a function called bind (not to be confused with jQuery's bind which does something completely different,) which solves this problem elegantly.

To fix the redcar problem with the aid of Prototype without having to use a placeholder variable, you can use bind like so:

function car(price) {
    this.price = price;

    this.setPrice = function(price) {
        this.price = price;
    };
}

function pass666(func) {
    func(666);
}

var redcar = new car(2000);
alert(redcar.price);
redcar.setPrice(123);
alert(redcar.price);

pass666(redcar.setPrice.bind(redcar));

alert(redcar.price);

The line pass666(redcar.setPrice.bind(redcar)); is what makes this work out. We're explicitly saying that we want setPrice executed from the scope of the instance.

If I ever have to hire someone for a web development job, I'll be sure to ask something about this.

Learn Source Control with Git

2010-03-09T00:00:00-05:00

One of the gaps among my tech skills upon entering university was source/revision control.

For those of you unfamiliar, revision control is a method of tracking and storing the changes made to files. This is particularly useful when keeping track of all the changes made to source code being worked on in a group. This allows you to all work on the same set of files at once and merge together the changes later.

This doesn't mean it isn't useful for projects you're working on by yourself. If you've ever coded something up, then decided you have a better way of solving the problem, then finally realize your new solution doesn't work, you need to go back. Except the deleted code is one undo step beyond your history. Crap.

And no, allowing for more undo steps is not the solution to this problem. If you want to look at older versions across multiple files from weeks ago, undo won't help you. Revision control will.

After speaking with employers, it seems that the most commonly used source control system at the moment is git. I'd like to note that most of the people I interviewed with were small, fairly new, web or mobile based companies. Older companies may be using svn or possibly even cvs. Then there's the whole set of Microsoft source control systems such as Microsoft Visual Source Safe.

You can see a summary of source control options here: Comparison of revision control software @ Wikipedia

I'm posting about this now because I'm working on a collaborative project using git for the first time. Since this is a private project, I'm using Project Locker instead of Github. To be honest, I probably should have just set up my own private repository and I might look into that later.

You don't actually need to have a remote repository. You can use a git repository to control your source locally if you're the only one working on it. You might consider doing this for school projects so you don't accidentally overwrite your working code in an attempt to appease Marmoset (automated testing in CS at U Waterloo).

In order to learn how to use git, I can recommend two sources of information.

GitCasts: these are screen casts, going through git and explaining things along the way. I'm in the middle of the fourth cast right now, so I can't say for sure these are all of high quality, but I'm seeing things I didn't know before, and that's enough for me.
Visual Git Guide: Pictures are awesome, especially for those people of the tl;dr mindset. Or those attracted to colourful pictures. The picture at the top of the post is from the visual git guide. This is a fairly in depth explanation of some of the functionality of git and shows you what's actually happening behind the scenes.

For those of you more interested in learning Mercurial (Hg), Zameer Manji has recommended the following guide: Hg Init: a Mercurial tutorial by Joel Spolsky.

I would recommend you go grab an account of GitHub to help yourself learning. If you're in need of something to fool around with, fork one of my projects: phleet @ github.

Jobmine Improved (Greasemonkey & jQuery)

2010-02-05T00:00:00-05:00

I will no longer be supporting this script, there's a much better version called Jobmine Plus maintained by Matthew Ng.

I, like many (most) Waterloo Co-op students, am forced to use Jobmine and am extremely dissatisfied with its functionality. So I decided to kill three birds with one stone: improve Jobmine, learn Greasemonkey and learn jQuery all at the same time.

The result is, unsurprisingly, a Greasemonkey script written using jQuery that improves on some features of Jobmine.

Features

Table sorting - all major tables are now sortable (Interviews, Job Short List, Applications)
Improved navigation - no more Student -> Use ridiculousness
No more frames - you can refresh and it will stay on the same page!
Colour highlighting for tables - pictured above, you see the applications page with various statuses highlighted. Selected is green, not selected is red.
No more spacers - the Jobmine page is riddled with spacer images just sitting there, stealing screen real estate

How to Install You'll either need Firefox & Greasemonkey, or a recent build of Chrome (Windows only?). You can get Greasemonkey here: Greasemonkey @ addons.mozilla.org

Once you've done that, navigate to the script and click install. You can get the script here: Jobmine Upgrade @ userscripts.org

Now for the part where I explain the tech I used.

Greasemonkey

Greasemonkey is a tool for customizing the way a web page displays and interacts using javascript. More or less, it overlays javascript you write on top of pages you specify by URLs with wildcards (*). It doesn't overlay it directly, but wraps it in some way as to prevent it from messing things up in the global scope. It also seems to run once the page is done loading, not when the page head is loaded. There are plenty of tutorials out there for doing cool stuff with Greasemonkey, but I started here: Dive into Greasemonkey. I know it says it's hideously outdated, but the metadata information it provides is still good enough. If you want more up to date information, go here: GreaseSpot (Greasemonkey Wiki).

jQuery

jQuery is a javascript framework specifically designed for doing things involving the DOM tree absurdly quickly. Example: highlighting alternating rows of a table (zebra-striping).

// Standard Javascript method:
var tables = document.getElementsByTagName("table");
for (var i = 0; i < tables.length; i++) {
    var rows = tables[i].tBodies[0].rows;
    for (var j = 0; j < rows.length; j++) {
        var rowColor;
        if (j % 2 == 1) {
            rowColor = "#eef";
        } else {
            rowColor = "#fff";
        }

        var cells = rows[j].cells;
        for (var k = 0; k < cells.length; k++) {
            cells[k].style.backgroundColor = rowColor;
            cells[k].style.borderBottom = "1px solid #ccc";
        }
    }
}

// jQuery way:
$("td").css("border-bottom","1px solid #ccc");
$("tr:even > td").css("background-color","#fff");
$("tr:odd > td").css("background-color","#eef");

Now before someone says it, I know usually you can set the background-color for the whole row, and the cells will inherit it. But since, for some crazy reason, each cell is assigned a background colour on Jobmine, each cell needs to be set individually. In any case, you can see that things are made substantially easier with jQuery. I figured out jQuery mostly just using the API and looking at other people's code, but this is a decent place to start: Getting Started with jQuery.

For the table sorting functionality, I decided to use a jQuery plugin as opposed to write my own (I'd rather be able to distribute this sooner). You can read all about it here: jQuery Plugin: Tablesorter 2.0

What features do you want to see in this? By the way, the source is all available on the userscripts site, so feel free to tinker with it yourself.

EDIT: As Trevor points out, the script in its current state won't work in Chrome due to the @require. You can grab his fix to make it work in chrome here: Jobmine Improved (Chrome)

Tools: ideone, RegExr, jitouch 2, open, ditaa

2010-01-07T00:00:00-05:00

Through reading proggit and hearing about new technology from classmates, every once in a while, I build up a list of tools which I plan on checking out and see whether they're useful enough to add to my regular routine. The first four on this list fall into that category, and I may eventually find a use for the last.

ideone

ideone is an in-browser, syntax-highlighted code editor complete with interpreters and compilers. Basically, if you've ever wanted to try out a language but really didn't feel like installing it on your system, this is the perfect place to start. The site even runs Brainf**k.

There's another site which accomplishes the same task, but less elegantly: Codepad. This site is so much less elegant that I wasn't originally planning on posting it, but decided to once I saw there was a Codepad vim plugin. There's also emacs integrations.

RegExr

Regexr is an online tool, implemented in Adobe Flex, to test out regular expressions in real time. If you haven't learned about regular expressions yet, go learn right now. They're just about the most powerful text matching, user verification and error correction tool in existence. They're also implemented in nearly all languages now in some form or another. Before I saw this site, I would test out all my regular expressions just using vim, but found it frustrating when the expressions needed to be changed to be compatible with php.
So I'm likely going to start using RegExr instead.

jitouch 2

Jitouch 2 is an application expanding on the multi-touch gestures available to MacBook Pro users who want to do more with just the touch pad. The two big things that this enables me to do that I love are opening links in new tabs using only taps on the keypad, and switching tabs using a gesture equivalent to ctrl-tab to switch tabs. I actually saw this reading Randal Munroe's blag.

Mac OS X/Gnome open

open & gnome-open are terminal commands in Mac OS X and gnome respectively, but they do the same thing. Whenever you double click on a file in Finder or Nautilus, the operating system has a database of which extensions are opened by which applications. You can leverage that database by calling open. Examples:

open "Office Space.avi"

Open up Office Space in your default viewer.

open http://www.jamie-wong.com

Visit my website from the commandline, opening in your default browser

open -a "Adobe Photoshop CS3"

Launch Photoshop. open -a opens files with an application.

ditaa

ditaa is a tool for converting ASCII art diagrams into graphical diagrams. This is pretty well illustrated in the picture to the left. I haven't actually found much of a use for this yet, but some of you might.

UWAngel-CLI

2009-12-27T00:00:00-05:00

Near the end of the semester, I was getting kind of tired of navigating UW-ACE so frequently through my browsing and opening all the different tabs to grab all the files I wanted. While all the pretty graphics make for a decent user interface, it reduces the speed of the service.

But aside from that, I like being able to do as much as I possibly can from the console.

So I made a Command Line Interface (CLI) for UW-ACE in php using cUrl. I built in on my Macbook Pro in Snow Leopard, but it should work just fine on any *nix machine, and possibly in Cygwin or other emulators.

As always, source is available on github: UWAngel-CLI @ Github.

Since I always like to post snippets of code from my projects that may be universally useful, I'll do that here too.

CLI Colour in PHP

cli_colours.php included in the UWAngel-CLI source is just a collection of constants which allow you to print out colours in your CLI scripts.

<?
$COLOR_BLACK = "\033[0;30m";
$COLOR_DARKGRAY = "\033[1;30m";
$COLOR_BLUE = "\033[0;34m";
$COLOR_LIGHTBLUE = "\033[1;34m";
$COLOR_GREEN = "\033[0;32m";
$COLOR_LIGHTGREEN = "\033[1;32m";
$COLOR_CYAN = "\033[0;36m";
$COLOR_LIGHTCYAN = "\033[1;36m";
$COLOR_RED = "\033[0;31m";
$COLOR_LIGHTRED = "\033[1;31m";
$COLOR_PURPLE = "\033[0;35m";
$COLOR_LIGHTPURPLE = "\033[1;35m";
$COLOR_BROWN = "\033[0;33m";
$COLOR_YELLOW = "\033[1;33m";
$COLOR_LIGHTGRAY = "\033[0;37m";
$COLOR_WHITE = "\033[1;37m";
$COLOR_DEFAULT = "\033[0;37m";

echo <<< EOT
One fish,
two fish,
{$COLOR_RED}red{$COLOR_DEFAULT} fish,
{$COLOR_BLUE}blue{$COLOR_DEFAULT} fish.

EOT;

The only gripe I have about this is that COLOR_DEFAULT it's the same colour as I have on by default in iTerm. Anyone know the escape code to make it actually revert to what it was before instead of just making an assumption about what color is being used?

Hide Commandline Input

One of the first things I looked up when I started this project today was how to hide user input from the command line. I sure as hell didn't want people typing their passwords for UWACE on screen and having it actually display.

It turns out you can do this by temporarily telling your TTY to stop echoing what you type. The command for this is stty -echo and can be re-enabled using stty echo. Below is how I implemented as part of the AngelAccess class to meet my needs.

<?
function Prompt($prompt_text,$hide = false) {
    echo $prompt_text;
    $input = "";
    if ($hide) {
        $input = trim(`stty -echo;head -n1;stty echo`);
        echo "\n";
    } else {
        $input = trim(fgets(STDIN));
    }
    return $input;
}
?>

As a complete side note, thanks to a boot-camped installation of Windows 7 (or at least I'm fairly sure that's the culprit,) my Macbook Pro is now stuck on Digital Out. This means I can't use the internal speakers on my computer under Mac OS X. Well... what I should say is that I can't use them without some annoying tricks. If I plug in my headphones, then tell my mac to use the input jack for audio input, then my internal speakers appear under the output options and let me use them. The speakers then work perfectly fine. They also work fine under Windows 7. A direct side effect of digital out being stuck on is a read light emanating from the audio jack.

The problem is apparently fairly common, unfortunately the only confirmed fixes for it are sending it back to Apple or wiggling a toothpick around in the audio jack. I had absolutely no luck with the toothpick, or precision screwdriver, or pen cartridge, or paintbrush handle. If anyone knows how to fix this problem, I would love to know. Otherwise, I'm just going to take it into the Apple store in Rideau some time this week and hope they can fix the problem. I really don't want to have to send my Mac in during my first week at Velocity.

Manual Sorting

2009-12-12T00:00:00-05:00

The basis for this post is the following question: what is the fastest algorithm for sorting a deck of cards by hand?

TL:DR advisor - skip to the end of the post for a challenge.

In terms of algorithmic complexity, merge sort and quick sort are two of the fastest widely used sorting algorithms - both running at an average case of O(n log n). But if you've ever sorted a deck of cards, ordering primarily by suit and secondly by number, I doubt you used either of these algorithms. You might unknowingly be doing bucket sort, dividing the cards into 4 "buckets" - one for each suit, then sorting each suit using a different algorithm and joining all the suits together at the end.

If I had a deck of cards in my room right now, I would be inclined to take videos of me sorting them using various different algorithms and comparing the time required. I have a feeling that the fastest algorithm would involve drawing out a 4x13 grid on a big piece of paper with each cell labeled with the exact card that fits there, then running through the deck, placing all the cards on their grid cell and just picking them up in order at the end. Of course, this could be accomplished without the grid but requires a spacial sense which I simply do not possess.

As a followup, I have another question: what if the cards were labeled with a number system you've never seen before? Assume you have some visual reference allowing you to understand the system, but also assume that the number system is not intuitive. Does your approach change? Of course, the fastest approach here depends on what I'm really asking by "fastest". Given enough time and practice, you would be able to become familiar enough with the numeral system to use any approach you would with regular cards or regular decimal numbers. When I say "fastest", I'm asking how you would minimize the time between receiving the cards and the visual reference and the cards being sorted. In terms of computation, the introduction of this numeral system has drastically increased the time for a comparison or enumeration while not affecting the time for movement or swapping at all. The reverse would be to use the standard deck of cards but make them orders of magnitude larger - say 1 meter wide each. In this case a move or a swap is extremely costly, but a comparison is very cheap.

A more realistic scenario in which the cost of comparison is drastically increased comes about when the criteria used for sorting is not an absolute. Example: sort these pictures by aesthetic appeal. Even by yourself this may be a long process, as you second guess your original decision about the relative appeal of a picture. In the world of web 2.0 though, it's a much much longer process. Sorting by crowd-sourced opinion is the basis of many websites, such as bash.org and reddit. Most of these systems work by providing users with the ability or increase or decrease the item's value by small amounts. Is there some better way of ensuring that the articles which will be the most valuable to the readers will show up at the top?

Returning to the point of manual sorting, I have 2 more things to say.

The first is an idea - competitive sorting. I'm sure this sounds nerdy as hell, but I think I'd still find it fairly entertaining. Groups of people would be given sets of objects and told to sort by some criteria, the fastest group being the victor, with penalties dished out for people falsely claiming their list is sorted. The criteria could be size, weight, volume, buoyancy, color saturation, retail price, alcohol content, power consumption or even something as obscure as average salary of a worker for the company manufacturing the product. Given that I'm at Waterloo, I feel that organizing such a competition isn't all that unlikely. Anyone feel like coming up with a plan for making this actually happen?

The second is a challenge. I challenge everyone reading this to make a video of them sorting a deck of 52 cards (no jokers) as fast as they can, then post the video in the comment section. As soon as I actually get a deck of cards, I'll take part in this challenge myself.

Rules.

The video must be all in one take
The deck must be shuffled thoroughly on screen, then fanned towards the camera to demonstrate the randomized order of the cards.
Once the cards have been fanned towards the camera, you can have a maximum of 10 seconds of review time looking through the cards before the sorting starts. All cards must stay in contact and in order during this review time.
The timer starts the second a card is separated from the rest of the deck.
The timer stops when the deck has been reassembled into a single sorted deck.
A deck is considered sorted if the cards are primarily ordered by suit in the order diamonds, clubs, hearts, spades, and secondarily ascending numerically.
You must fan the deck towards the camera after it is sorted.
You are allowed any setup you want before starting to sort (e.g. the grid I talked about above,) provided that the setup does not contain moving parts - no robots.
You must be the only one handling the cards - no team efforts.

That's all. I fully expect to receive no responses to this challenge, but would love to see the things people come up with if someone does try it.

EDIT: Woohoo! Someone attempted! Timothy Armstrong Sorting

Also, the claimed record according to this page is 36.1 seconds.

Lambda Functions

2009-12-06T00:00:00-05:00

One day, a friend of mine called me up asking for help with his CS assignment. It was about lambda functions in scheme. Lambda functions had always been something confusing both in theory and practice for me. Why do you need them? Before I explain what they are, I'll start with a simple probably justifying why they are.

All code in this post is going to be in python, but most of it can be applied to other high level languages. I've only used lambda functions in python and scheme, but I'm sure the functionality exists in many, many other languages.

Sorting

Sorting in python is very straight forward. If I have a list of strings in python and want to sort them, I do this:

a = ["banana","apple","pear","elephant","zebra","mango"]
a.sort()
print a
# OUT: ['apple', 'banana', 'elephant', 'mango', 'pear', 'zebra']

But what happens when you try to sort a list of words containing capital letters?

a = ["pear","Police","apple","Airplane","banana","Bear"]
a.sort()
print a
# OUT: ['Airplane', 'Bear', 'Police', 'apple', 'banana', 'pear']

The sorting is done purely based on the byte values of the characters. Since 'P' (ASCII 80) < 'a' (ASCII 97), "Police" is placed before "apple" in the list of words. Normally when you're trying to sort a list of words, you want to do it alphabetically. So how do you fix this? You make a comparator function. Here's python's definition of the sort function.

L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
cmp(x, y) -> -1, 0, 1

For those of you who have used qsort in the standard C library, this isn't such an arcane concept. In python however, it is much easier (no void* madness).

def alphacmp(x,y):
    return cmp(x.lower(),y.lower())

a = ["pear","Police","apple","Airplane","banana","Bear"]
a.sort(alphacmp)
print a
# OUT: ['Airplane', 'apple', 'banana', 'Bear', 'pear', 'Police']

Okay, great! We now have our list sorted in the intuitive way. The lower() function will ensure that the lowercase version of the strings are being compared, removing the issues of the byte comparisons. But this code seems a little longer than it could be. Normally, you wouldn't create a function for task you do only once if it was just as readable within the code body. But the sort function needs a comparator function. So how can you give sort a comparator function without having to actually declare a function? The answer is lambda functions.

Lambda Functions

Lambda functions are anonymous functions. What does that mean? They're functions without a declared name. Let's look at an example so you can see what I mean. In the above example, we can sort alphabetically without defining the alphacmp function like so:

a = ["pear","Police","apple","Airplane","banana","Bear"]
a.sort(lambda x,y: cmp(x.lower(),y.lower()))
print a
# OUT: ['Airplane', 'apple', 'banana', 'Bear', 'pear', 'Police']

So what does lambda x,y: cmp(x.lower(),y.lower()) mean? "lambda" says that the statements following define an anonymous function. "x,y:" defines the parameter list accepted by the anonymous function. "cmp(x.lower(),y.lower())" defines the return value for the lambda function. If you're still a little bit confused, read on for many many more examples. At some point, it will likely click and you'll see how valuable lambda really is.

Another sorting example: what if I want to sort by length of the strings instead of alphabetically? Easily done with lambda.

a = ["pencil","pen","cap","zebra","Blizzard","0xB4DC0DE","!"]
a.sort(lambda x,y: len(x) - len(y))
print a
# OUT: ['!', 'pen', 'cap', 'zebra', 'pencil', 'Blizzard', '0xB4DC0DE']

The use of lambda functions makes the use of many higher level functions much nicer. I'll be outlining a few of them here.

map

map(function, sequence[, sequence, ...]) -> list

Return a list of the results of applying the function to the items of the argument sequence(s). If more than one sequence is given, the function is called with an argument list consisting of the corresponding item of each sequence, substituting None for missing values when not all sequences have the same length. If the function is None, return a list of the items of the sequence (or a list of tuples if more than one sequence).

More or less, what map does is apply a function on every element of an array then return an array of the corresponding return values.

A very simple use for map would be making every word in a list upper case.

a = ["abc","cattle","not even if there's a FIRE","Jeymi!?"]
b = map(lambda x: x.upper(),a)
print b
# OUT: ['ABC', 'CATTLE', "NOT EVEN IF THERE'S A FIRE", 'JEYMI!?']

A more useful example involves printing out grids. Say I have a matrix of numbers, represented as a list of lists in python. The default output formatting for this in python is extremely difficult to look at.

a = [
    [1,212,-13],
    [41,5,614],
    [7,8,91]
]
print a
# OUT: [[1, 212, -13], [41, 5, 614], [7, 8, 91]]

What would be better is to output one row per line.

a = [
    [1,212,-13],
    [41,5,614],
    [7,8,91]
]
print "\n".join(map(lambda x: str(x), a))
#OUT:
# [1, 212, -13]
# [41, 5, 614]
# [7, 8, 91]

The join function concatenates a list of string, separating the elements with the separator character - in this case: "\n"

Much better! But what would be even better would be to print out the numbers in columns that line up nicely too.

a = [
    [1,212,-13],
    [41,5,614],
    [7,8,91]
]
print "\n".join(
    map(
        lambda row:
            " ".join(map(
                lambda y: "%4d" % y,
                row
            )),
        a
    )
)
# OUT:
#   1  212  -13
#  41    5  614
#   7    8   91

"%4d" % y is applying the formatting string %4d to y, much the same way that printf in C and php do

Now, using a lambda function inside of a lambda function is less than readable, so I'll write out what this function does first without the maps and lambdas.

a = [
    [1,212,-13],
    [41,5,614],
    [7,8,91]
]

def rowformat(row):
    formatted_cells = []
    for element in row:
        formatted_cells.append("%4d" % element)
    return " ".join(formatted_cells)

formatted_rows = []
for row in a:
    formatted_rows.append(rowformat(row))

print "\n".join(formatted_rows)
# OUT:
#   1  212  -13
#  41    5  614
#   7    8   91

In this case, rowformat(row) plays the exact same roles as lambda row:.

filter

filter(function or None, sequence) -> list, tuple, or string

Return those items of sequence for which function(item) is true. If function is None, return the items that are true. If sequence is a tuple or string, return the same type, else return a list.

The filter function does just what it's name suggests: filters out items that don't meet certain requirements. Specifically, any element which does not evaluate to true when passed to the provided function will be discarded. Note that this is not in place - it returns the filtered list.

Example: remove all odd numbers from a list of numbers

a = [1,2,5,0,-15,100,1400,-1337,135]
a = filter(lambda x: x % 2 == 0, a)
print a
# OUT: [2, 0, 100, 1400]

Example: remove all vowels from a string

a = "Hello there! My name is Jamie, not to be confused with Jeymi."
a = "".join(filter(lambda x: "aeiou".find(x) == -1, list(a)))
print a
# OUT: Hll thr! My nm s Jm, nt t b cnfsd wth Jym.

Example: build a list of all prime numbers between 0 and 100 inclusive

# NOTE: This prime test is inefficient - used for readability)
def isprime(x):
    if (x < 2):
        return False
    for i in range(2,x):
        if (x % i == 0):
            return False
    return True

print filter(isprime,range(101))
# OUT (placed on multiple lines for readability)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
# 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

reduce

reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). If initial is present, it is placed before the items of the sequence in the calculation, and serves as a default when the sequence is empty.

Example: Calculate 30 factorial without using local variables

# Note that range(2,n) -> [2,3,...,n-1]
print reduce(lambda x,y: x*y, range(2,31))
# OUT: 265252859812191058636308480000000

Example: Find the longest word in a list of words

a = ["pencil","pen","cap","zebra","Blizzard","0xB4DC0DE","!"]
print reduce(lambda x,y: y if len(y) > len(x) else x, a)
# OUT: 0xB4DC0DE

And that's all for now. If you're in SE 2014 reading this and don't think you need to know how to use lambda functions - have fun with scheme.

Game of Life

2009-12-01T00:00:00-05:00

For my latest project, I'm implementing Conway's Game of Life in python into animated GIFs.

Before I even explain what Conway's Game of Life is, be amused by the below, generated animation:

As always, the code I'm using here is open source: Game Of Life @ Github. In addition to the source code, there's also a few animation demos such as the one above.

Conway's Game of Life is a cellular automaton following very simple rules, as outlined in the Wikipedia article. It is a zero player game played on a 2 dimensional grid of squares, each holding either a state of dead or alive. The state of any cell is dependent on the state of the 8 cells neighbouring it in the previous generation. There are only 4 rules.

From the Wikipedia article Conway's Game of Life:

Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.

Any live cell with more than three live neighbours dies, as if by overcrowding.

Any live cell with two or three live neighbours lives on to the next generation.

Any dead cell with exactly three live neighbours becomes a live cell.

The colours you see in the above animation represent the alive status of each cell and also how many neighbours that cell has if it's alive.

This project is my first time making use of two utilities: optparse in python, and gifsicle.

optparse is a python library designed to make the creation of command line application much simpler. Specifically it's targeted towards making application with many possible flags easy to maintain. lifeImage.py falls into this category. From the commandline, you can control the source of input, the colour scheme, the number of generations to output, the scaling of the image and various other things to produce the exact animation or image you want.

You can take a look at optparse here: optparse @ docs.python.org. The tutorial included there was enough for me to create this application.

gifsicle is a command line application for the creation and modification of animated gifs. It can create gifs out of a sequence of images, convert an image into a sequence of images, or even modify replace a single frame of an animated gif with an external image.

You can see and download gifsicle here: Official Gifsicle Page

Why did I use gifsicle instead of the much more universal convert in ImageMagick? Simply put: gifsicle is faster. If someone would like to do a benchmark to (dis)prove this, I'd be happy to post the results, but from simple experimentation, it seemed obvious to me that gifsicle took less time to make the animation.

What's Next?

Now that I have a working command line utility, my next goal is to make an AJAX powered web interface for the thing. This might explain why I have ProcMonitor in the github for Game of Life. The web interface was another key motivator behind using gifs for the output medium. People may want to use these things for avatar, and they're simply easier to share and move around than a java applet, or a flash swf, or some database stored simulation. It also helps that gifs are designed for palette based images, which works out nicely for optimizing the file size of these animations. The first 1000 generations of acorn is 2.5 MB as it is.

Another thing I want to do is make lifeImage.py read the .cells format from the Life Lexicon. This would save me a lot of time having to code all the states myself. This will be a very straightforward process, as the .cells files are simply plaintext with 2 lines of header.

Suggestions/bug fixes for my implementation of Game of Life are welcomed.

I'm almost 100% sure that some combination of the command line flags of lifeImage.py don't work nicely together, and would like to know what they are.

Omegle Voyeur - Multiple Connections

2009-11-14T00:00:00-05:00

In case you haven't read the post about all my projects, here's a description of what Omegle Voyeur is:

Omegle is a website where you are connected to a stranger for a chat. It is dominated mostly by trolls whose primary purpose is to coerce you into a cyber session and then switch genders or to make you lose the game. Talking to these people is a rather tiresome endeavour, but seeing exactly what happens in these conversations is interesting. Omegle Voyeur is a way of watching a conversation which you aren't part of. What Voyeur does is form two simultaneous connections and then pass the input of one to the output of the other. This sets you up as a conversation proxy, allowing you to watch. Currently, this is exclusively a "sit and watch" program. Later I intend to add functionality to add more than 2 people into a conversation, automatically name the participants so it will be obvious that there are more than 2 people in the conversation, and allow the ability to interfere (mute participants/say things yourself) with a conversation. This concept was spawned during discussion (read: boredom) at CCC Stage 2, 2009.

In terms of technology, Omegle Voyeur is primarily one big Javascript Prototype class. Prototype is a Javascript Framework which makes the creation and maintenance of classes, conversion of data into JSON for transfer, and sending AJAX requests much, much easier.

There's also a very small bit of code in php which is able to be so short because it uses the incredible program cUrl. cUrl is a command line utility for grabbing data from websites using their URL. libcurl facilititates the use of curl in php without having to write your own wrapper.

Below is some php code I use to make curl even easier than it already is. simple_get($url) will return the HTTP GET result from the url specified. simple_post works similarly, but delivers data using the payload.

<?
// Simple cUrl
// Simple get and post requests
function simple_get($url) {
    $c = curl_init();
    curl_setopt($c, CURLOPT_URL, $url);
    curl_setopt($c, CURLOPT_RETURNTRANSFER, 1);
    $result = curl_exec($c);
    curl_close($c);
    return $result;
}

function simple_post($url,$payload) {
    $c = curl_init();
    curl_setopt($c, CURLOPT_URL, $url);
    curl_setopt($c, CURLOPT_POST, true);
    curl_setopt($c, CURLOPT_POSTFIELDS, $payload);
    curl_setopt($c, CURLOPT_RETURNTRANSFER, 1);
    $result = curl_exec($c);
    curl_close($c);
    return $result;
}
?>

When I started working on this project today (well, I suppose that would be last night now... wonder if I'll see the sunrise) I figured it would be a good time to get used to using git, so I made a repository using github. So far I'm enjoying git. Everything seems to act pretty much the way you'd expect to, and I already had to do a revert once I realized my logic was wrong for the way I was structuring my code.

You can see the github for Omegle Voyeur here: http://github.com/phleet/Omegle-Voyeur Feel free to design your own stuff with the all the code there - just be sure to link back here, or to the github page.

In any case, the thing the majority of the people reading this are probably interested in are the result. Things I've updated since last time are primarily aesthetic and behind the scenes, but I did add the ability to connect one person to more than one other person, and the connections don't have to be mutual. In the first 3 way conversation example, 1 can only speak to 2, 2 can only speak to 3 and 3 can only speak to 1. It leads to some rather confused people.

~~You can see the current running version here: Omegle Voyeur.~~ EDIT: It seems that after being posted on reddit, omegle has (manually?) IP blocked me. The source should still work, so feel free to try it out yourself. You can go grab XAMPP to run it locally. For the time being, you can view it here: Omegle Voyeur

A quick note on how I figured out the Omegle communication protocol. The entire code governing the process is conveniently kept here: http://omegle.com/static/omegle.js?27 Unless you enjoy reading 1000s of characters on a single line, you can use the JS Beautifier to clean it up to a readable state.

SPOJ Problem 2: Prime Generator (PRIME1)

2009-11-12T00:00:00-05:00

Problem: Prime Generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Concept The idea behind every solution here (with some variation) is to generate all the prime numbers that could be factors of numbers up to the maximum endpoint 1 billion. That square root happens to be around 32000. Using this array, do a bounded Sieve of Eratosthenes only in the range requested. In languages like php and python, it turns out that it's more efficient to build an associative array and check if the index is set than it is to generate a huge boolean array.

Code

C++

/// PRIME1 - C++ (g++)
// AC Time: 2.52s
// NOTE: I am aware that the use of vector and set actually
//  makes this code run _slower_
// I used vector and set simply as a way of practicing STL
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

int main() {
    vector<int> primes;
    primes.push_back(2);

    for (int i = 3; i <= 32000; i+=2) {
        bool isprime = true;
        int cap = sqrt(i) + 1;

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {
            if (*p >= cap) break;
            if (i % *p == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) primes.push_back(i);
    }

    int T,N,M;

    cin >> T;

    for (int t = 0; t < T; t++) {
        if (t) cout << endl;

        cin >> M >> N;
        if (M < 2) M = 2;

        int cap = sqrt(N) + 1;

        set<int> notprime;
        notprime.clear();

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {

            if (*p >= cap) break;
            int start;

            if (*p >= M) start = (*p)*2;
            else start = M + ((*p - M % *p) % *p);

            for (int j = start; j <= N; j += *p) {
                notprime.insert(j);
            }
        }

        for (int i = M; i <= N; i++) {
            if (notprime.count(i) == 0) {
                cout << i << endl;
            }
        }

    }
    return 0;
}

C99

// PRIME1 - C99 (gcc)
// AC Time: 0.07s
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main() {
    int primes[4000];
    int numprimes = 0;

    primes[numprimes++] = 2;
    for (int i = 3; i <= 32000; i+=2) {
        bool isprime = true;
        int cap = sqrt(i)+1;
        for (int j = 0; j < numprimes; j++) {
            if (primes[j] >= cap) break;
            if (i % primes[j] == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) primes[numprimes++] = i;
    }

    int T,N,M;
    scanf("%d",&T);

    for (int t = 0; t < T; t++) {
        if (t) printf("\n");
        scanf("%d %d",&M,&N);
        if (M < 2) M = 2;

        int cap = sqrt(N) + 1;

        bool isprime[100001];
        memset(isprime,true,sizeof(isprime));

        for (int i = 0; i < numprimes; i++) {
            int p = primes[i];

            if(p >= cap) break;

            int start;

            if (p >= M) start = p*2;
            else start = M + ((p - M % p) % p);

            for (int j = start; j <= N; j += p) {
                isprime[j - M] = false;
            }
        }

        int start = (M % 2)?M:M+1;

        if (M == 2) {
            printf("2\n");
        }
        for (int i = start; i <= N; i+=2) {
            if (isprime[i-M]) printf("%d\n",i);
        }
    }
    return 0;
}

PHP

<?
// PRIME1 - PHP
// AC Time: 5.73

$primes = array(2);
$numprimes = 1;

for ($i = 3; $i <= 32000; $i+=2) {
    $isprime = true;
    $cap = sqrt($i)+1;

    for ($j = 0; $j < $numprimes; ++$j) {
        if ($j >= $cap) break;
        if (!($i % $primes[$j])) {
            $isprime = false;
            break;
        }
    }
    if ($isprime) $primes[$numprimes++] = $i;
}

fscanf(STDIN,"%d",$T);

$output = "";

for ($t = 0; $t < $T; $t++) {
    if ($t) $output .= "\n";

    fscanf(STDIN,"%d %d",$M,$N);
    if ($M < 2) $M = 2;

    $isprime = array();

    $cap = sqrt($N)+1;

    $i = 0;
    while($i < $numprimes) {
        $p = $primes[$i];

        if ($p >= $cap) break;

        if ($p >= $M) {
            $start = $p*2;
        } else {
            $start = $M + (($p - $M % $p) % $p);
        }

        for ($j = $start; $j <= $N; $j += $p) {
            $isprime[$j - $M] = false;
        }

        ++$i;
    }

    for ($i = $M; $i <= $N; ++$i) {
        if (!isset($isprime[$i-$M])) {
            $output .= "$i\n";
        }
    }
}

echo $output;
?>

Python

# PRIME1 - Python
# AC Time: 3.10s
from math import sqrt
primes = [2]

for i in range(3,32000,2):
    isprime = True

    cap = sqrt(i)+1

    for j in primes:
        if (j >= cap):
            break
        if (i % j == 0):
            isprime = False
            break
    if (isprime):
        primes.append(i)

T = input()
output = ""
for t in range(T):

    if (t > 0):
        output += "\n"

    M,N = raw_input().split(' ')
    M = int(M)
    N = int(N)
    cap = sqrt(N)+1

    if (M < 2):
        M = 2

    isprime = [True]*100001

    for i in primes:
        if (i >= cap):
            break

        if (i >= M):
            start = i*2
        else:
            start = M + ((i - M % i)%i)

        # The two below, obscure lines create a continuous
        #  block of false elements in order to set all
        #  elements correspnding to numbers divisible by i
        #  in isprime to be false
        # In turns out that this runs substantially faster
        #  than setting the elements individually using loops
        falseblock = [False] * len(isprime[start-M:N+1-M:i]);
        isprime[start-M:N+1-M:i] = falseblock

    for i in range(M,N+1):
        if (isprime[i-M] == True):
            output += str(i) + "\n"

print output[:-1]

Bash

# PRIME1 Incomplete - BASH
# This is not a complete solution
# The speed of bash parsing makes getting an
#  AC submission infeasible

# The following code is a working prime generator
# Giving enough time, it will output all prime
#  numbers from 0 to 32000
# ..which is the first step in the solution to PRIME1

let PRIMES[0]=2
let NUMPRIMES=1
for i in {3..32000}; do
    let ISPRIME=1

    #for j in {0..$NUMPRIMES}; do
    for (( j = 0;j<$NUMPRIMES;j++ )); do
        let CURPRIME=${PRIMES[$j]}
        if [[ $CURPRIME*$CURPRIME -gt $i ]]; then
            break
        fi

        let MOD=$[$i % $CURPRIME]
        if [ $MOD -eq 0 ]; then
            let ISPRIME=0
            break
        fi
    done

    if [ $ISPRIME -eq 1 ]; then
        echo $i
        let PRIMES[NUMPRIMES]=$i
        let NUMPRIMES=NUMPRIMES+1
    fi
done
</pre>

Ruby

# PRIME1 - Ruby
# AC Time: 4.65s
#
# While I would have liked to use more
# Ruby idioms such as for p in primes
# or primes.each do |p| (used once),
# the difference in runtime between
# the use of loops like these and while
# loops was non-negligible

primes = [2]

3.step(32000,2) do |i|
    isprime = true
    cap = Math.sqrt(i) + 1

    primes.each do |p|
        if (p >= cap)
            break
        end

        if (i % p == 0)
            isprime = false
            break
        end
    end

    if isprime
        primes << i
    end
end
numprimes = primes.length

T = gets.to_i


output = ""
t = 0
while t < T
    print "\n" if t > 0
    line = gets.split(" ")
    m = line[0].to_i
    n = line[1].to_i

    m = 2 if m < 2

    cap = Math.sqrt(n) + 1

    notprime = {}

    i = 0
    while i < numprimes
        p = primes[i]
        i+=1
        if (p >= cap)
            break
        end

        if (p >= m)
            start = p*2
        else
            start = m + ((p - m % p)%p)
        end

        j = start
        while j <= n
            notprime[j] = true
            j += p
        end
    end

    i = m
    while (i <= n)
        if (notprime[i] == nil)
            print i,"\n"
        end
        i+=1
    end
    t += 1
end

Java

// PRIME1 - Java
// AC Time: 2.20

import java.io.*;
import java.util.*;
import java.lang.Math.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int[] primes = new int[4000];
        int numprimes = 0;

        primes[numprimes++] = 2;
        for (int i = 3; i <= 32000; i+=2) {
            boolean isprime = true;
            double cap = Math.sqrt(i) + 1.0;

            for (int j = 0; j < numprimes; j++) {
                if (j >= cap) break;
                if (i % primes[j] == 0) {
                    isprime = false;
                    break;
                }
            }
            if (isprime) primes[numprimes++] = i;
        }


        int T,N,M;

        T = in.nextInt();

        for (int t = 0; t < T; t++) {
            if (t > 0) System.out.println("");

            M = in.nextInt();
            N = in.nextInt();

            if (M < 2) M = 2;

            boolean[] isprime = new boolean[100001];
            for (int j = 0; j < 100001; j++) {
                isprime[j] = true;
            }

            for (int i = 0; i < numprimes; i++) {
                int p = primes[i];
                int start;

                if (p >= M) start = p*2;
                else start = M + ((p - M % p)%p);

                for (int j = start; j <= N; j += p) {
                    isprime[j - M] = false;
                }
            }

            for (int i = M; i <= N; i++) {
                if (isprime[i-M]) System.out.println(i);
            }
        }
    }
}

Perl

# PRIME1 - Perl
# AC Time: 4.28s
@primes = (2);

for ($i = 3; $i <= 32000; $i+=2) {
    $isprime = 1;
    $cap = sqrt($i) + 1;
    foreach $p (@primes) {
        if ($p >= $cap) {
            last;
        }
        if ($i % $p == 0) {
            $isprime = 0;
            last;
        }
    }
    if ($isprime == 1) {
        push(@primes,$i)
    }
}


$T = <STDIN>;

for ($t = 0; $t < $T; $t++) {
    if ($t > 0) {
        print "";
    }

    $in = <STDIN>;
    @line = split(/ /,$in);
    $M = $line[0];
    $N = $line[1];

    if ($M < 2) {
        $M = 2;
    }

    $cap = sqrt($N) + 1;

    @isprime = ((1) x 100001);

    foreach $p (@primes) {
        if ($p >= $cap) {
            last;
        }

        if ($p >= $M) {
            $start = $p*2;
        } else {
            $start = $M + (($p - $M % $p) % $p);
        }

        for ($j = $start; $j <= $N; $j += $p) {
            $isprime[$j-$M] = 0;
        }
    }

    for ($i = $M; $i <= $N; $i++) {
        if ($isprime[$i-$M] == 1) {
            print "$i\n";
        }
    }
}

// PRIME1 - C# (gmcs)
// AC Time: 1.50s

using System;
class PRIME1 {
    static void Main() {

        int[] primes = new int[4000];
        int numprimes = 0;

        primes[numprimes++] = 2;
        for (int i = 3; i <= 32000; i+=2) {
            bool isprime = true;
            double cap = Math.Sqrt(i) + 1.0;
            for (int j = 0; j < numprimes; j++) {
                if (j >= cap) break;
                if (i % primes[j] == 0) {
                    isprime = false;
                    break;
                }
            }
            if (isprime) primes[numprimes++] = i;
        }

        int T,N,M;
        T = int.Parse(Console.ReadLine());

        for (int t = 0; t < T; t++) {
            if (t > 0) Console.WriteLine("");

            string[] parts = Console.ReadLine().Split(' ');
            M = int.Parse(parts[0]);
            N = int.Parse(parts[1]);


            if (M < 2) M = 2;
            double cap = Math.Sqrt(N)+1;

            bool[] isprime = new bool[100001];
            for (int i = 0; i < 100001; i++) isprime[i] = true;

            for (int i = 0; i < numprimes; i++) {
                int p = primes[i];
                if (p >= cap) break;
                int start;

                if (p >= M) start = p*2;
                else start = M + ((p - M % p)%p);

                for (int j = start; j <= N; j+= p) {
                    isprime[j - M] = false;
                }
            }

            for (int i = M; i <= N; i++) {
                if (isprime[i-M] == true) Console.WriteLine(i);
            }
        }
    }
}

GNU Pascal

{
    PRIME1 - GNU Pascal
    AC Time: 0.54
}

program PRIME1;
var
    primes: array[1..4000] of integer;
    numprimes: integer;
    i,j: integer;
    cap: double;
    isprime: boolean;
    T,N,M: integer;
    isp: array[0..100001] of boolean;
    p,start: integer;


begin
    primes[1] := 2;
    numprimes := 1;
    for i := 3 to 32000 do
    begin
        isprime := true;
        cap := sqrt(i) + 1;
        for j := 1 to numprimes do
        begin
            if primes[j] >= cap then
                    break;

            if (i MOD primes[j] = 0) then
            begin
                isprime := false;
                break;
            end
        end;

        if isprime = true then
        begin
            numprimes := numprimes + 1;
            primes[numprimes] := i
        end
    end;

    read(T);

    for t := 1 to T do
    begin
        if t > 0 then
            writeln('');

        read(M);
        read(N);

        if M < 2 then
            M := 2;

        cap := sqrt(N) + 1;

        for i := 0 to 100001 do
            isp[i] := true;


        for i := 1 to numprimes do
        begin
            p := primes[i];
            if p >= cap then
                break;

            if p >= M then
                start := (p * 2);

            if p < M then
                start := M + ((p - (M MOD p)) MOD p);

            j := start;

            while j <= N do
            begin
                isp[j - M] := false;
                j := j + p;
            end;
        end;

        for i := M to N do
        begin
            if isp[i-M] = true then
                writeln(i);
        end;
    end;
end.

SPOJ Problem 1

2009-11-08T00:00:00-05:00

When I saw that Thor had done solutions to the first few problems of Project Euler in many many languages, I thought "Hey! That's a good idea!" but didn't want to copy exactly.

So instead I'm doing solutions to some problems on SPOJ. SPOJ is an online judge system full of algorithmic problems. This is one of the things that Hanson Wang did to get as good as he is. The solutions I'll be providing here are going to be very simple problems, so don't expect any magic. The beautiful thing about SPOJ is the sheer number of languages it will judge. I figured this was the perfect playground to make sure my code worked in all the languages I try.

Problem: Life, the Universe, and Everything

Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely... rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

Solutions - In order of frequency that I use the language

C++

//TEST AC - CPP (g++)
#include <iostream>
using namespace std;

int main() {
  int n;
  while(1) {
    cin >> n;
    if (n == 42) break;
    cout << n << endl;
  }
  return 0;
}

C99

//TEST AC - (gcc C99)
#include <stdio.h>
int main() {
  int n;
  while(1) {
    scanf("%d",&n);
    if (n == 42) break;
    printf("%d\n",n);
  }
  return 0;
}

php

<?
//TEST AC - PHP
while(1) {
  fscanf(STDIN,"%d",$n);
  if ($n == 42) break;
  print "$n\n";
}
?>

Python

#TEST AC - Python
while 1:
  num = input()
  if (num == 42):
    break
  print num

Bash

#!/bin/bash
# TEST AC - BASH

while true; do
  read n
  if [ $n -eq 42 ]; then
    break
  fi
  echo "$n"
done

Ruby

#TEST AC - Ruby
while 1
  n = gets.to_i
  if n == 42
    break
  end
  puts n
end

Java

//TEST AC - Java
import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    while(true) {
      int n = in.nextInt();
      if (n == 42) break;
      System.out.println(n);
    }
  }
}

Perl

#TEST AC - Perl
while (1)
{
  $n = <STDIN>;
  if ($n == 42) {
    last;
  }
  print $n
}

//TEST AC - C# (gmcs + Mono)
using System;
class WelcomeCSS {
  static void Main() {
    while(true) {
      int n;
      n = int.Parse(Console.ReadLine());
      if (n == 42) break;
      Console.WriteLine(n);
    }
  }
}

GNU Pascal

{TEST AC - GPC Pascal}

program TEST;

var n:integer;

begin
  while true do
    begin
      readln(n);
      if n = 42 then begin
        break;
      end;
      writeln(n);
    end;
end.

You can see Thor's Project Euler solutions here: Derek Thurn's Website - Project Euler