Writing code for multiple platforms is a challenge. It not only increases the complexity of your code and tests, but it also increases the complexity of your build process. The build process is what I have had trouble with as of late. So, I'm logging my struggles so that I, and you, might have some place to go the next time multi-platform deployment causes headaches.

So, here is my problem. I have a plug-in that has a little bit of platform-specific code in it. The code works on both windows and linux, and I have precompiled binaries for them. In other words, the build of the (C++) native code doesn't need to be part of my build process. I do that separately just because it is easier. Setting up cross-compilers is a nightmare, and takes more time than I have.

So, here is what I do: I separate my native code into plug-in fragments for windows and for linux. After that, I have to go through all of my different manifests to make sure that P2 knows what to do with the the fragments. First, a p2.inf file has to be made for each fragment and the host plug-in, so that P2 knows the fragments are installable units that should be downloaded. OK, that's fine. Then, I have to the feature.xml for the feature that contains my plugins and fragments to make sure that I specify the supporting environments:



OK, then I have to set up my fragments to make sure that the platform filters match their target environment:



Platform filters are basically read as a functional notation, where sets of attributes are bound to operators. For example, (|(osgi.arch=x86)(osgi.arch=x86_64)) binds the selection of the attributes (osgi.arch=x86 and osgi.arch=x86_64) to the logical OR operator (|), so that it reads, "the osgi architecture can be either x86 or x86_64." So, I've got that down. I also had to set up the Bundle-NativeCode attribute in the manifest for the fragment so that my application knows where to find the binaries, but I'll get back to that later.

OK, now one might expect that everything is ready to export. After all, the binaries don't depend on any native Eclipse fragments (they don't reference SWT or anything). So, it seems that my fragments should be able to be packaged up just like anything else.

That's not the case however. When you run a build in PDE, and you put a platform filter on a fragment, Eclipse checks your current target platform and builds only for what you currently have. I, for example, have a machine with Windows XP on it, and that is the version of Eclipse that I downloaded. So, Eclipse will build only the windows fragment for me. There is no option to build for other platforms. If I use the Export Deployable Features wizard, this is what I get:



Even though my fragments don't have any dependencies on any other platform-specific code and all I really need is a jar with my binaries in it, the PDE says, "No! I can't build that for you." OK, that's fine. I know that it is possible to build for multiple platforms (the SWT guys do it), so I did some searching.

It turns out that what I need is something called the Eclipse Delta Pack. The Delta Pack is basically a bunch of fragments for different platforms which include native code for user interfaces and other i/o such as file manipulation. Getting the Delta Pack can transform your Eclipse workbench into a catch-all platform which targets everything that Eclipse can manage.

The unfortunate thing is that the Delta Pack isn't that easy to find. If you go to the Eclipse Download page, you won't find any reference to it. You have to go down to the bottom of the page, and find the Classic Eclipse distribution. And select Other Downloads:



Once there, you will want to get the release that you are targeting (probably somewhere in the 3.5.1 stream or later), and look to the left-hand menu. You will find the Delta Pack there:



Or, you can follow this link for the 3.5.1 drop.

When you download the Delta Pack, you have to unpack it. Make sure that you don't unpack it over your current Eclipse install. That could make things go bad. Instead, unpack it somewhere else and you can tell Eclipse to add it to your target platform.

To do that, go to your Eclipse Preferences, and find the page for Target Platform, select the running platform, and Add the Delta Pack to it as an Eclipse Install:



After that's done, you will have a new magic option in your Export Deployable Features wizard called Export for multiple platforms. That's exactly what I was looking for!



So, one would think at this point that one could simply export all of the features, upload them to a P2 repository, and release the new version. Not so fast. If you are me and you do that, you get this bug report.

It was silly of me. I shouldn't have assumed that the build would work flawlessly without testing. So, I checked my P2 repository, and low-and-behold, the Linux fragment was missing. That seemed strange. After all I did export for Linux. There's no rocket science here. It's just a pre-compiled binary after all.

So, after hours of fighting with trying different combinations of platform filters, and different ways of building, there were no warnings and no errors in the build. Unfortunately, there was also no Linux fragment. It just would not get created on my windows box. I was about to go and file a bug on P2, when I decided that maybe I should just try to get the build on Linux. So, I went through all the above steps again on a fresh install of Eclipse on a Linux machine. What I expected to happen was that it would build fine on the Linux machine, but instead of not having a Linux fragment, I would be left without a windows fragment.

That isn't what happened. I did get a windows fragment. What was missing? You guessed it: the Linux fragment! My Linux machine failed to build the Linux fragment. But, at least I got an error this time:



It looks like there was something about my Bundle-NativeCode property in the Linux fragment which the PDE build system didn't like. So, I went to investigate it.

I had used native code previously in an RCP toy application in which I was experimenting with OpenGL. When I looked up how to do it at that time, I learnt that I was supposed to use various keys such as processor= and os= to tell the plug-in when to use different compiled libraries. In fact, that is what I used in previous versions of Diver. When both the Windows and Linux binaries were in one fragment, it worked fine. But apparently, now that I had them in two fragments, that was very, very wrong:



I didn't really know what to do, though since this is what I had read was correct, and it was previously working. In fact it still works for the different Windows versions. Not for Linux, though. I don't know why. So, after another hour or so on Google, I learned about the key selection-filter which works in the same way that the Eclipse-PlatformFilter does. So, I copied my platform filter into the Bundle-NativeCode like this:



And it works! So, I learned a few things from this whole process:

1. You Need The Delta Pack. Why you need it for all multi-platform builds, I don't know. In my example, all I needed was to package up pre-compiled binaries into jar files. There doesn't need to be any dependency resolution for that, but the PDE needs the Delta Pack to do the build. That is relatively painless, so I don't mind.


2. Pay Attention to the Bundle-NativeCode Format. Eclipse won't necessarily tell you what is wrong. It might just fail to build a fragment or two without you even noticing. The safest way to get it to work just seems to be to copy your Eclipse-PlatformFilter directly into the Bundle-NativeCode property. At least you don't have to manage multiple different syntaxes that way.

Anyway, that is all for now. I hope this can be helpful to anyone who is doing builds for multiple platforms. It isn't an easy problem to solve, so there are bound to be pain points. This post will hopefully get you (and me) through them quickly next time.

If anyone tried to download Diver 0.1.0 last week on their Linux boxes, you may have had a little trouble. It turns out that I didn't have everything set up correctly for a multi-platform build, and the Linux plugins weren't getting created. I'm going to blog about my experience in a minute, to keep it for posterity so that I can remember how to do it. Hopefully it will be useful for others as well. For now, here is a pretty picture to prove to you that things are good to go for you Linux users.



If you downloaded for Windows last week, I think that you should be fine. But, there won't be any harm in updating.

Eclipse 3.6 M5 is now available for download. There are lots of new and exciting features, like the ability to open and file directly from the command line.  You can also use the synchronize view to compare patches:

Debug also introduced a few new features (like instance counts):

Check out all the new features in the New and Noteworthy.

Download the milestone:
http://download.eclipse.org/eclipse/downloads/drops/S-3.6M5-201001291300/index.php

or use p2 to upgrade to it:

http://download.eclipse.org/eclipse/updates/3.6milestones/

The ActionScript Graphics class supports drawing solid lines and quadratic curves. But there isn't native support for dashed lines or cubic (Bezier) curves.

I've created a sample application that shows the three line types: straight, quadratic curve and cubic curve. It also lets you choose between showing a solid line, a dashed line, or both. The line thickness can also be adjusted.



I also got a little carried away and added the quadratic and cubic control points as buttons that you can drag around the canvas to change the curve.

Most of the drawing functionality for these examples is in the GraphicsUtils.as class that contains the following static functions:

• drawLine() - draws a straight line, either solid (using Graphics.lineTo() function) or dashed
• drawQuadCurve() - draws a quadratic curve, either solid (using Graphics.curveTo() function) or dashed
• drawCubicCurve() - draws a cubic curve (two control points), either solid or dashed. The curve is an approximation done by dividing the curve into many small segments and drawing straight lines
• drawCircle() - draws a circle, either solid (using Graphics. drawCircle() function) or dashed
• drawArc() - draws an arc, either solid or dashed

The dashed lines are drawn by dividing the line into many small segments to draw the dashes. By default a dash length of 10 pixels is used, but that is customizable.

The equations used to calculate the values at any point along the line for the three cases were found on the Wikipedia entry for Bézier curves.

There is a new version of Diver out, with a few new features which should make reverse engineering easier in Eclipse. A couple of highlights are the new "Notes" feature which can be accessed using Eclipse's Properties View, and the new Trace Search Page which helps you to find things in your traces. Diver is also a lot smaller in terms of its memory footprint now. For more information on what's new, check out the New To Diver 0.1.0 Page. To get Diver, just point your P2 "Available Software Sites" to https://diver.svn.sourceforge.net/svnroot/diver/Release. Diver works on Windows and Linux.

Some fancy pictures of the new features:

The new Diver Trace Search






Finding all the activations of methods that start with get*






Finding all personalized notes stored in a trace

I've had some frustration with Flex ContextMenus, so I thought I'd write an entry about the basics of creating context menus, adding items, listening for context menu events, and a few restrictions on context menus.

Every InteractiveObject (e.g. Application, Panel, Button, etc) contains a contextMenu property. For most components it will be null and you'll have to create a new menu and assign it to that property. So you can have different context menus for different components.

Here is a simple example of a context menu set on the application:


Here is a short snippet from the above example showing you have to create a ContextMenu, hide the built-in menu items, and listen for menu events.

There are many restrictions to Flex ContextMenus, some of which will drive you crazy. Read carefully, it will save you time later.

• Maximum of 15 custom menu items in the menu
• No sub-menus allowed
• No icons in menus
• Menu items must be 100 characters or less
• Control characters, newlines, and other white space characters are ignored
• MANY reserved words including (but not limited to):
  • Save
  • Zoom In
  • Zoom Out
  • 100%
  • Show All
  • Quality
  • Play
  • Loop
  • Rewind
  • Forward
  • Back
  • Movie not loaded
  • About
  • Print
  • Show Redraw Regions
  • Debugger
  • Undo
  • Cut
  • Copy
  • Paste
  • Delete
  • Select All
  • Open
  • Open in new window
  • Copy link
  • Copy Link Location
  • Del

I'm not quite sure why there are so many restrictions, but I'm sure Adobe has a good reason for it!

More details about the restrictions can be found on the ContextMenuItem page.

There are a few other solutions for people who want more control over the menus. These usually involve adding right click listeners in JavaScript on top of the Flex application and passing that event into Flex to position and show a custom menu instead of the usual Flex context menu.
Here is one such solution: Custom Context Menu.
These solutions can work quite effectively, but since they depend on the browser they can be quite buggy.

Though I'm really a coder at heart, I am a researcher by day. I've been working hard on the Diver project to try and figure out ways that reverse engineering can be used to aid coders like you and me. If you've downloaded it and used it, please fill out my survey.

If you haven't tried Diver yet, please try it. I'm really hopeful that it can help you Java developers out.

The BC Winter Programming Contest took place this past weekend, January 16th. You can check out the scoreboard here. It was an excellent competition, only one student, Jaehyun Park from Stanford, solved all 7 problems, and almost all students solved at least one. Brad Bart from SFU did most of the work to write problems, solutions, and organize everything. Sonny Chan (coach of Stanford) and myself made small contributions with some solution validation, test case generation and I wrote one of the problems.

There were 5 pairs of UVic students competing and one UVicer competing remotely while on co-op with Research in Motion in Waterloo, ON. The top UVic team was Dan Sanders and John Hawthorn with 4 problems solved. They finished 6th overall and were the 2nd overall amongst BC students. They were in 3rd or 4th about half way through the competition, but got stuck trying to debug wrong answers on problems C, D and F for the second half of the competition. In the last half hour, students from SFU solved their 5th problem and jumped ahead of them. Scott Porter, competing remotely by himself, was the second top UVic student, placing 20th overall.

Many of the UVic students that participated were completely new to competitive programming. They had really no idea what to expect, so I would like to congratulate all UVic students that came out and gave it a try. These competitions can be very intimidating and stressful the first few times, so I'm really proud of everyone that stuck it out for the full 3 hours. Hopefully you'll keep practicing and compete in the ACM competitions next Fall.

Problems:
A - This was the simplest problem in the set. You had to read in words and determine whether they were writable in Hawaiian. This amounted to determining whether the word contained only letters from the Hawaiian alphabet. The catch for some solutions was not properly handling the stopping condition. The problem states that the last test case ends with the exact string "Ahuihou". Some students matched against this word ignoring case, which is wrong.

B - In this problem you have to read in a number, up to 30 digits in length, and determine what bases it can be rewritten in such that it is evenly divisible by 7. If the number is never divisible by 7, you have to print "Always unlucky.". It turns out that you only need to test bases up to base 16. All other valid bases will be one of these bases plus Y*7 (Y >= 1). For example, if base 9 works, then base 16 works, 23, 30, etc. You can easily do this in Java using the BigInteger class. Python probably also has something equivalent.

C - This was the hardest problem in the set, and only one student managed to successfully solve it. You are given a grid of diamond shaped cells. You are also given a metal detector that can probe a gridsquare and give you one of 8 compass directions. Compass directions North, East, South, and West are only valid responses if the treasure you are hunting is located along that exact path. Otherwise, you get a direction like Northwest that simply narrows your search to a region of the grid.

You can solve this problem using dynamic programming or memoization. A sub-problem can be described by the grid size, m and n. However, there are some tricky conditions for the recursion for certain values of m and n.

D - This is the problem I wrote. The problem describes a game with colored marbles on two tracks, one horizontal and one vaertical. You can rotate either track to move marbles from one track to the other. You are given an initial configuration of the tracks and you have to figure out the minimum number of moves (i.e. rotations) such that you get all the blue marbles into the middle square. It turns out that there's not that many valid starting configurations.

One approach to solve the problem is to start by representing the winning condition as two bit strings of length 18, "111100000111100000" and "100000111100000111". Then using these strings as a representation of state, you can breadth-first-search across all possible valid moves to generate any potential starting position that takes one move to reach the winning state. Continue to do this for all of these states to get all configurations 2 moves away. Do this until you can't find any new states and store everything in a table. You can now simply look-up the answer based on the read in configuration. If the given starting configuration does not exist in the table, then it is impossible.

E - In this problem, you are told that two flat oranges rest at the bottom of a fruit bowl shaped like a parabola. You have to determine at what value of y the fruit's centers are located at. Applying some geometry, you can work out an equation to calculate y given some "guessed" value for x. To guess a value for x, we can use binary search and terminate when the high and low value become significantly close.

F - This problem describes a bad measuring device that is only precise within 1 foot. So any measurement has value V feet plus or minus 1 foot. The distance between floors in a building are measured with this device and you have to determine whether these measurements are consistent or inconsistent. Consistent means that the measurements are possible, inconsistent means that there's no way they could be right, there is some sort of conflict between two or more floor distances.

We can represent this problem as a graph. All floors represent nodes in a graph and two floors, a and b, have directed edges between them if there is some measurement d given in the problem input. The edge from a to b can be assigned weight 1-d (the minimum possible value) and b to a has weight 1+d (the maximum possible value). Once the graph is constructed, the measurements are consistent provided there are no negative cycles in the graph. To detect negative cycles, you can apply the Bellman-Ford algorithm.

G - This was the second easiest problem in the set. You are given numbers that represent the values of odd-indexed nodes in a full binary tree. You have to figure out the values to the even-indexed nodes. You can represent the tree using a one-dimensional array. Most people learn this in undergraduate data structures courses. Then it's just a matter of filling in the array, where you use the odd-indexed values to calculate the even-indexed values. Instead of an array representation, you could also implement your own binary tree with left and right nodes, and apply recursion to fill in the tree.

The BC Winter Programming Contest is coming up this Saturday, January 16th. I've been making the rounds to different classrooms, trying to encourage some new students to give it a try. Last night I held a three hour practice session and luckily a few new faces showed up to give it a go. I picked five problems from the 2009 Greater New York Regional programming contest. I picked this set as I knew a lot of teams solved all the problems, so I figured it would have some pretty manageable problems for complete newbies.

The students worked on problems A, C, D, H, and I. Most students solved A and D, and John Hawthorn was the only one to solve C.

Problem A is quite straight-forward. You need to read in a list of 10 numbers and print the 3rd largest value. Probably the fastest way to code this is to read in the 10 numbers, sort them and print the 7th number in the array. This should only take a few lines.

int P;
cin >> P;
while(P--) {
  int num;
  cin >> num;
  vector<int> t(10);
  for(int i = 0; i < 10; i++) cin >> t[i];
  sort(t.begin(), t.end());
  cout << num << " " << t[7] << endl;
}

The second easiest problem was problem D. In this problem you have to read in a list of numbers and for every odd-indexed number, print the current median of the list. The key here is to make sure your sort is fast enough to get under the time limit and to follow their output specification exactly. Most students made mistakes with the output format. The built in sort routines in C++ or Java should be fast enough for this problem.

Problem C is a little tricky to understand. The problem describes a scenario where you drop glass balls from different floors. The goal of dropping these balls is to determine what the last floor is that you could drop a ball from without having it break. In the classic version of this problem, sometimes involving eggs, you have to figure out the optimum strategy for this, which is a variation on binary search. However, in this problem they want you to figure out what the minimum number of drops is in the worst case. This means, if we choose the worst strategy, what is the best we can hope for?

To solve this, we can try to enumerate all possible scenarios given the number of balls we have and the number of floors we can potentially drop a ball from. We can enumerate these states through recursion over two variables, our current number of balls left and the number of floors left. We also need to use memoization to store our states so that we don't repeat states that we've already computed. Finally, we need to determine what the conditions are for this recursion. There is basically two cases, we drop a ball b from a floor f and the ball breaks leaving us with one less ball and knowing that we need to search floors below f, or the ball does not break, meaning we need to search floors above f. From these two scenarios, we want to keep track of the worst result, but the minimum overall value.

int rec(int balls, int floors) {
  if(balls == 1) return floors;
  if(floors == 0) return 0;
  if(floors == 1) return 1;
  
  // we already calculated this one
  if(memo[balls][floors] >= 0) return memo[balls][floors];

  int best = floors;
  for(int f = 1; f <= floors; f++) {
    // ball breaks on this floor, one less ball
    int r1 = rec(balls-1, f-1);
    // ball does not break, search above
    int r2 = rec(balls, floors-f);
    // keep track of the worst result
    int result = 1 + max(r1, r2);
    // keep track of the minimum for all worst cases
    best = min(best, result);
  }
  memo[balls][floors] = best;
  return best;
}

Problem H states that you need to find all lattice points contained within a convex polygon. All coordinates for the lattice points and the polygon vertices are integers. There's several ways you could solve this problem. One way is to do point in polygon tests to determine which lattice points are contained within the polygon. To do this, you can calculate all the potential lattice points by determining the maximum x-coordinate, maximum y-coordinate, minimum x-coordinate and minimum y-coordinate based on all vertices in the polygon. Then, you can loop from the minimum y to maximum y, minimum x to maximum x, and test each point.

Finally, problem I describes a puzzle with 7 positions, 6 of which contain a letter and one position is blank. A valid move is to move a letter from its current position into the blank position. The goal is to convert the game into the winning state as described by the problem statement. The problem states that given an initial configuration, print out the minimum number of moves along with the solution to reach the win state or print NO SOLUTION if it is not possible.

This is a simple example of a "Searchy type problem" that I had blogged about before. The positions can be represented as nodes in a graph, edges exist between the nodes based on how the puzzle is described. You can then perform a breadth-first-search over the graph, where a new state for the queue is added for each valid movement of a letter to the current blank space. Also in the state, you need to keep track of the path you took to reach that state. Once you find the winning state, print the path and length.

I spent part of today trying to debug a Linux specific issue in which wizard pages are not being shown properly.  Actually, the content of some wizard pages are not showing up at all (Bug 298805 if you’re interested).

While thinking through the problem on IRC (yes, you should be on IRC), Susan McCourt had a great idea — install the SWT Spy and see what it shows.

The SWT Spy is a small tool that allows you to place your mouse over a widget and get information about that widget, including:

1. Layout information
2. Bounds
3. Siblings
4. Parent Chain (back to the shell)

I hacked the tool a bit to add the visibility field.  The SPY is available from: http://www.eclipse.org/swt/tools.php. Once installed, you can toggle the spy using CTRL+ALT+SHIFT+”.”.

An oldie but a goodie.

A paper based on some of the innovations in Diver has been accepted to the 2010 European Conference on Software Maintenance and Reengineering. I will be presenting the paper in Madrid in March.

A lot of technical and technological innovation does come from academia. You don't always see it directly in the commercial products right away, but I do believe that it has influence. Especially as software engineering and computer science graduates move into industry, bringing their research expertise with them. A lot of the things that we take for granted in our IDEs were first written up in academic conferences or journals. Take the interactive debugger that we all use all the time as an example [Isoda, 87]. I think that industry and academia really benefit from good research relationships.

Anyway, it turns out that the way that Diver reduces the size of trace visualizations (in the sequence diagram) by cross-linking the trace with the source code is actually a new idea. So, the nice people at CSMR decided to let me write about it and give a presentation.

The paper is called "Utilizing Debug Information to Compact Loops in Large Program Traces." (Sounds exciting doesn't it? ;-) ). Everyone knows that most of the execution of any program is really caused by an enormous amount of repetitive calls to a subset of the methods/functions/subs/whatever that are written in the code. Most of these calls occur within loops structures. That causes a big problem for visualizing traces. Most standard programs will will have millions of calls in the span of a few seconds (Hello World in Java has upwards of 100 000 calls or something rediculous like that!). That's far too big for any standard visualization.

So, what Diver does that is unique is it recognizes that most of the repetitive calls will occur within loops that can be found in the source code of your program. So, it searches your source code (or the source code attached to your jars in Eclipse), and looks for where calls originate from. If they occur in a loop, then only one iteration of the loop is shown at a time.

I ran some experiments on several traced programs, including Eclipse, and found that you can get upwards of an 85% reduction in the size of your visualization (depending on the program that you tracing, and on the visualization--it's particularly good for sequence diagrams) just by compacting loops in this way. That's a pretty significant reduction. The Eclipse JDK was a huge help for this, by the way. It has awesome Java indexing, and a great Java parser that made my work a lot easier.

So, anyway, if you are in the vicinity of Madrid around March 15-18 2010, come by CSMR and say hello.

It's been a couple of weeks since my last post as there's been less going on with the programming teams lately due to exams. This post is about how to run your own programming contest, but first, I thought I should mention that all the UVic team members were recognized and awarded Outstanding Leadership Awards last night at the computer science department Christmas party. There's also been talk about establishing some kind of yearly high school programming competition in BC. It would potentially be great for recruitment, be a good way to get young people interested in computer science, and hopefully keep the top BC students in BC.

Ok, now onto the topic: how to setup and run your own programming contest.

Before I get into the details, I'll just mention a few bad experiences I have had as a competitor. You may not think organizing a contest would be that difficult, but it can be quite a disaster if there isn't much care put into it. I use to compete in the Northeast North America regional. This is one of the few regions in North America that has preliminary rounds. Between all the contest sites, there is no consistency in the problem writing style or the submission software used. Year to year, the contest submission software changes and not always for the better.

In one particular preliminary contest, every team had to use a Windows system, but telnet into a Unix box, and use a single non-resizable terminal for coding and submitting. Even more surprising was that the problems were not printed for the teams before the contest and teams had to read the problems directly on the machine. We were told that we could print screen the problems piece by piece if we needed print outs.

Since only one terminal was supported, you would of course be forced to switch between your code editor back to the single terminal for compiling, running, and submitting. The submission software consisted of shell scripts, solution judgements were written into a file, which you would need to periodically check.

Many of the input files had been created on a Windows machine and ported to Unix, which led to strange end of line and end of file characters. Finally, there was a number of errors in both the judge's test cases and the problem specifications. Not surprisingly, over half the teams solved nothing, and we came in second with a grand total of three problems solved.

One of the other issues with the preliminary round was the problem writing inconsistency. This may have been due to lack of experience from the problem writters or lack of care from the organizers, but each problem would usually be formatted completely different. Some looked as if they were typed in Notepad, with no input and output specified, sometimes without any sample test cases. Others may be a PDF file, written in Latex. Usually if there was some description of the input and output, the constraints of the problem would not be specified.

Now that the horror stories are complete, as for running your own contest, there are several options and it's not really that complicated, but is perhaps a little daunting for those unfamiliar with competing. To start with my own experience, I've written problems for, acted as judge, organized, and ran about half a dozen contests, both at UVic and the University of New Brunswick (UNB). Probably the most difficult part, besides getting students interested in coming out for such an event, is coming up with the problem set, judge's inputs and outputs, all without major errors.

The goal with most ACM-style contests is to create a problem set such that every student/team solves at least one problem, no student/team solves all the problems, but all problems are solved by someone. This is very tricky to pull off. If the problems are too simple, then you may end up with a situation like this year's Greater NY Regional where nine teams solved all the problems. This is usually a sign of a poorly designed and potentially unfair contest. It potentially rewards the fastest coders for simple problems rather than the best problem solvers.

One of the major issues I've struggled with in any contest that I've run is the large variance in skill level between the few exceptional students I had access to and the less experienced students. You don't want the more advanced students solving everything in the first two hours, but you don't want to make the problem set so difficult that the majority of the students leave frustrated and embarrassed. I've been both successful and unsuccessful at achieving this balance.

For example, in the last contest I ran at UNB, the top two students solved 6/7 problems, two students solved 2, two solved 1, and everyone else solved nothing. I felt quite bad judging this contest, and many of the students left frustrated. However, the first UVic contest that I organized, had a much better balance (scoreboard).

In individual contests, I have usually tried to have between 6 and 7 problems, with at least one very simple problem to get everyone started on the right foot. I also usually organize the problems roughly from easiest to hardest, as a lot of inexperienced people will start with the first problem regardless of its difficulty. I also usually try to have the second or third easiest problem be something that is easy to understand conceptually, but may take some time to implement. My goal here is to give less experienced students something to work on and potentially solved, but it will keep them busy for a while. Finally, I try to mix in some shorter to code problems that require a bit of insight.

If you are simply trying to set up a contest environment for team practice, then you can probably skip the problem writing stage. If you go to the regional page on the ACM ICPC website and follow the links to various regionals, many will include their problem set, judges input and output, and solutions. You can use these files to create your own practice contest environment.

In all the contests that I've organized, I've used the PC^2 software for problem submission and judging. I recommend using version 9, as it's much better with firewall issues. PC^2 is quite simple to set up. The software is written in Java, so it runs on most platforms. It has several different programs, a server, scoreboard, judge, admin, and client. You start by running the server, and all other programs connect through the server. Configuration is as simple as modifying a config file to point to the server location. The administration control panel is used for creating accounts, inputting problems, and configuring how the judgements will run. Judging can be done automatically or semi-automatically.

I always create a judge's set of input and output, and configure PC^2 with that information for each problem. I also use automatic judging as a guide. If the automatic judge gives me an accept, I usually take it. If there's a different answer, I'll do a side by side comparison between the submitted program output and my judge's output just to make sure.

The client software is what the students or teams use to submit their solutions. They can select the problem to submit under, the language of the source code, and the source file. Submissions are put into a queue on the judge's side. The client software also supports clarification submissions, which are questions about the problem set that you can send to the judge.

The scoreboard is very simple, it writes the current scores into different html files. The summary.html is the best view. The admin software allows you to configure when the scoreboard should be frozen, typically for the last hour or half hour in a contest.

There are other contest systems out there. CodeChef, which I wrote about in my last post, will host contests for you. One of the advantages of using PC^2 is that it is the system used both at the world finals and at a lot of the regional level contests so it exposes your team to the system early. It is very simple to use, so it's probably not a huge gain, but it may help a bit :-).

Just in time for the Holidays, the Eclipse platform team has made Eclipse 3.6 Milestone 4 available.

Feel free to download it:
http://download.eclipse.org/equinox/drops/S-3.6M4-200912101301/index.php

Upgrade to it:
http://download.eclipse.org/eclipse/updates/3.6milestones

or just browse the New and Noteworthy:
http://download.eclipse.org/eclipse/downloads/drops/S-3.6M4-200912101301/eclipse-news-M4.html

There’s a whole host of new features such as Virtual Folders

and the ability to execute multiple quick fixes at once:

Enjoy the early Christmas present

I've had a number of requests to get Diver running on Linux. So, I've spent the past few days trying to get it done. I think that I've had success, but it needs more testing.



I've tested it on a Linux machine here at the university. The above screen shot was taken by X-forwarding Eclipse to my local XP machine using Cygwin/X. The native code is compiled to 32bit, so it should be compatible with pretty much any Linux machine. All the code is statically linked, so you don't need to have any libraries installed.

It hasn't been released to the "stable" stream (whatever that means in research ;-) ). You can install it from the "developer" stream using P2: https://diver.svn.sourceforge.net/svnroot/diver/Development. I haven't done integration tests on Windows yet.

Right now, both the Windows version and the Linux version are held in the same plug in fragment. I know it would be better to include only one of them for each platform. I'm a little confused about how to set up my features to do this though. Does anyone have any tips?

I sometimes get questions from people asking me about how to get into competition programming, how to practice, how to use the various problem archive websites and so forth, so I thought I'd write a blog explaining how it all works. Most of the practice and competition sites out there have very good guides for this very thing, so this post will mostly give a short description of your various options, what I think of them, and it will hopefully be useful to those that are currently in the dark about this kind of thing.

Before I get into describing the various online options, if you're in university or high school there is two main competitions that you could potentially get involved in. For high school students this is the International Olympiad of Informatics (IOI). I've never been involved with this competition, so I don't know a lot about it. I do know that it is a world-wide competition and up to four individuals from a country can compete. There's typically a national round first in order to choose a country's four members. If you're in high school and have some programming skills it might be something to consider. I'd first try finding some information about previous competitors from your country and find out how to get involved.

University students can compete in the ACM Intercollegiate Programming Competitions (ICPC). This is the largest competition of its kind and the type of competition I've been primarily involved in as a competitor and coach. Participants compete on teams of three with a single computer for five hours. The teams that solve the most problems in the least amount of time win. Recently, the top 100 teams from around the world meet to compete against each other in the world finals.

To qualify for the world finals, you have to place high in a regional level competition. The world is divided into around 40 regions. In North America, usually you have to be one of the top two teams in the region to move onto the finals. If you're in university, find your region and see if your school has a team. If they don't, then I encourage you to get involved. You just need a faculty member to sponsor you and hopefully they can help you get whatever funding is necessary for travel.

Ok, great, you're sold on the idea of competing, so how to practice? There's several great websites out there that can help. Most of them follow a similar format; problem statement, with description of input and output formats, and several example test cases. You submit to an online judging system, usually through a form, and the online judge compiles your source and runs the executable against a hidden set of test cases. If you pass everything, you solved the problem. Be very careful when you start, you need to match the specified input and output formats exactly. Even if you are off by a period or whitespace, your answer will be wrong.

UVA Online Judge - This site contains thousands of problems and an online judging system. To use the site, simply register, then pick a problem, solve it offline on your own computer, and when you're satisfied, submit it through the UVA online submission form. You'll get an email indicating whether the problem was accepted (yay!) or if your code produced a wrong answer, time limit exceeded, runtime error, or compile error. The site also hosts online competitions, however, watch out for the timezone. One disadvantage of the site is that the problems are not really organized by problem type, so it's hard to practice certain types of problems. However, if you search the message board for say "dynamic programming" you can often find someone listing problem numbers of this problem type. The site supports C, C++, Java and Pascal solutions.

ACM Live Archive - This site is similar to UVA and run by, I believe, some of the same people. It contains previous problems from many of the regional competitions and world finals. Like UVA, you can submit solutions directly through a web form. There's also a message board for finding help, although it's not nearly as populated as the UVA message board. One major issue with this site is they only support Java 1.0, which basically means, they don't support Java.

Project Euler - I've known about this site for a while, but only recently started using it. There's several nice things about the site. The first is that the problems are listed in increasing difficulty, so problem 1 is suppose to be the easiest and the latest posted problem (currently 266) is the hardest. The other really nice thing is that you only submit an answer to a problem, rather than source code. This allows you to solve the problem in any language that you are comfortable with. It's a great way to experiment with learning a new language. The problems tend to often be math oriented. It's a great resource, but since it is a different style than the ACM or IOI competitions, it may not be as good a representation of how it is to compete in those particular competitions.

CodeChef - I just discovered this site after a friend sent me a link. It's a fairly new competition website, similar to the UVA online archive. They have a competition every month, where 6 problems are posted and competitors have 10 days to try to solve them. You earn 1 point for each solved problem. There's also team competitions, but I am not sure how often they are organized.

Problems are organized by easy, medium and hard. There seems to be a great community contributing to the site. The social aspects of the site are tightly integrated with the problem sets and contests in comparison to the older websites that simply have message boards. One other nice thing is that it supports a wide range of languages. Finally, if you do well, there's prize money :-).

TopCoder - This is one of the largest competition sites available. Anyone can compete, and there's typically two or three algorithm competitions a month (SRM - single round matches). Once you sign up, you can run the competition applet and try problems from previous competitions. There's several key differences in comparison to ACM style competitions.

First, there's two divisions, Division I and II, based on your membership rating. You earn points by competing, people with ratings less than 1200 compete in Division II, everyone else is in Division I. So, when you first sign up, you'll be in Division II. If you do poorly in a competition relative to other people with similar ranking to you, then your rating can actually drop.

Second, there's always 3 problems, each with different point values. The faster you solve a problem, the more points you get. There's an easy, medium, and hard problem, the more difficult the more points you can potentially get. Third, unlike ACM contests where after you submit you get a judgement about your problem, on TopCoder, submissions are not judged until after the competition. If you decide to re-submit, you lose 10% of your original point value. Unlike, ACM contests, you do not have to worry about writing input and output parses based on some described format. Typically, you are asked to write a specific class with a method that takes certain parameters and returns a certain parameter.

Finally, contests only last an hour and 15 minutes. After the coding part of a competition, there's a 10 minute break, and then a challenge phase. During the challenge phase, you get to look at other people's source code and challenge their solutions. If you make their code fail, you get extra points and they lose whatever points they would have potentially scored. Once this phase is complete, the judge's hidden input cases are run against all submitted programs. If you fail any cases, you lose whatever points you accumulated for that problem.

There's several great things about training on TopCoder. There's lots of competitions, so it gets you use to competing. Because you really only get a single submission, it can help you improve your accuracy. You can see other people's source code, so it can be a great way to learn how to solve a problem or learn a better way to solve a problem. There's also editorials after each SRM describing how to solve the problems. The problem archive is nicely organized and searchable based on different criteria like difficulty and problem type (DP, greedy, search, etc). Also, if you are very talented, you can earn a substantial amount of money competing on TopCoder. Many contests and tournaments are organized by companies as a way to recruit potential employees.

This post is already quite long, so hopefully that's enough to get any newbies out there pointed in the right direction. Next time, I'll post about how to run your own competition and provide some suggestions for how to get things going at your own school.

There has been a lot of talk lately about what the Eclipse community is and is not doing.  While I have no intention of going anywhere near that conversation, I did want to highlight something that makes me very proud to be part of this great community.  This month, the Eclipse community raised over $3,000 for men’s health issues, and that’s awesome!

Of course I’m talking about Movember!

David Green led all Mommitters with $740 raised.  Thanks David.  A big thank-you also goes out to Kevin Barnes who replied to my tweet on Oct 30th and motivated me to start the Mommitters. This would not have happened without you Kevin.  I also want to thank Kim Moir (and Kim Horne for the great suggestion) who helped get our Movember splash screen in the I-Builds.

All the Eclipse Mommitters also deserve a big thank-you for stepping up and growing a stache for charity.  You all looked terrific.

But the biggest thanks goes out to all the community members who stepped up with their wallets and donated a few bucks to a great cause.  Looking through the list of donations it was quite a diverse group of individuals.  As a community there may be things we can improve, but I think we should be very proud of this accomplishment.

I came across a funny error today while I was working with a plug-in fragment in Eclipse. I had a fragment that contained several resources for use in a host plug-in. All of a sudden, my host plugin was no longer able to find the resources from the fragment. I couldn't figure out why. Then I stumbled across some information about MANIFEST.MF files in Java jar collections. Apparently, there is a limit to the length that a line can be in a MANIFEST.MF file. If a line is more than 72 characters long, then it must be broken into more than one line. You can do so by breaking it on the 72nd character and continuing the next line with a space. My MANIFEST.MF file had one such line. So, changing the line from (imagine that there is no word wrap):


Eclipse-Variable-Example: Here is my really long manifest line that is more than 72 characters


To:


Eclipse-Variable-Example: Here is my really long manifest
 line that is more than 72 characters


Made it work. I knew that you could break lines, but I didn't know that you
had to break them. Now I know.

But this leaves me questioning: the standard says that you should break the line on the 72nd character. Does that mean that my example should have really looked like this:


Eclipse-Variable-Example: Here is my really long manifest line that is m
 ore than 72 characters


? That just seems like a weird way of doing it.

A lot of problems in the ACM and TopCoder competitions can be solved using a general search technique like breadth-first search (BFS). Many BFS type problems are represented with an initial grid and you want to determine whether you can achieve a certain state or grid configuration, possibly in the minimum number of moves. These problems are very popular and can vary in complexity, however, the general problem solving principles remain the same.

You can usually determine whether BFS is the right approach for a problem of this sort by first checking the bounds of the grid. Most of the time, the grid will be less than 20x20. Secondly, you need to determine how to represent the current state of the problem. You can think of this state as a node in a graph. Finally, you need to determine if one state can be transformed into a subsequent and valid state through a move with a cost of one. You can think of these moves as edges between your nodes. Another hint is that many of these problems can be classified as single player game problems.

Let's consider an example. In the problem Traffic!, a simple game is described where are given an initial puzzle configuration consisting of blocks of varying sizes. The goal of the game is to figure out how to remove the white piece by moving the various puzzle pieces and repositioning the white piece so that it slides through the opening in the puzzle. In the problem you are asked to find the minimum number of moves to accomplish this task.

So, let's go back to our criteria for determining whether BFS is a valid approach. First, the grid is of size 6x6, so that's well within our heuristic 20x20 bound. Second, the state of the problem can be represented as a list of the current locations for each puzzle piece. A move in the game consists of moving a single puzzle piece any number of open positions horizontally or vertically. Horizontal pieces can only move horizontally and vertical pieces can only move vertically. Sliding a horizontal piece one spot to the right has the same cost as moving it two spots to the right, that is, it counts as one single move. Thus, we can transition from one state of the board to another with a cost of one. Finally, the problem even fits the format of being described as a single player game.

Once we've established that we can solve the problem using BFS, then the algorithm to actually solve the problem is quite straight-forward. A generic approach could be something similar to the following code:

int solve(State start) {
  set<State> visited;
  queue<State> q;

  q.push(start);

  while(!q.empty()) {
    State s = q.top(); q.pop();
    // skip states we've already processed
    if(visited.find(s) != visited.end()) continue;

    // we reached our goal, return moves
    if(goalStateReached(s)) return s.moves;

    // visit the state
    visited.insert(s);

    // try all valid moves 
    // and add them to our queue
    enqueueValidMoves(q, s);
  }
  // never reached the goal
  return -1;
}

In this case, State is going to consist of a list of the current block locations, the number of moves it took to achieve this state, and a less than operator for storing the state properly within our visited set. The enqueueValidMoves will loop over the positions in our state object and create a new state for any valid vertical and horizontal moves. We know we reached the goal state when the white piece is located in column 6.

There are a few simple tips for working on problems of this type or grid representations in general. First, let's consider a simple 0/1 matrix where from any cell i,j, containing a one, you can move east, west, north or south provided the move takes you to a cell containing a one:

110
010
111

So, the cell 0,0 can only move to cell 0,1 as this is its only neighbor containing a one. We could potentially perform a BFS where we check for valid moves as follows:

while(!q.empty()) {
  // queue consists of pairs of integers 
  // representing cell locations
  pair<int, int> p = q.top(); q.pop();

  if(visited[p]) continue;

  // process potential moves
  if(p.first-1 >= 0 && grid[p.first-1][p.second] == 1)  
    // enqueue item
  if(p.first+1 < rowCount && grid[p.first+1][p.second] == 1) 
   // enqueue item
  if(p.second-1 >= 0 && grid[p.first][p.second-1] == 1) 
   // enqueue item
  if(p.second+1 < colCount && grid[p.first][p.second+1] == 1) 
   // enqueue item
}

That will work, but all the bounds checking and if statements are kind of ugly and error prone.

To clean up this code a bit, one simple trick is to remove bound checks by padding the grid with empty cells. For example, our grid from above would become:

00000
01100
00100
01110
00000

Now, our check just needs to verify whether a given cell contains a value of one.

Another simple tip when processing moves over a grid, like north, south, east and west transitions is to store these moves as x, y and possibly z deltas in an array. Thus, with those two simple tricks combined, our messy code above becomes:

int x[] = {1, 0, -1, 0};
int y[] = {0, 1, 0, -1};
while(!q.empty()) {
  // queue consists of pairs of integers representing cell locations
  pair p = q.top(); q.pop();

 if(visited[p]) continue;

 // process potential moves
 for(int i = 0; i < 4; i++) {
   int r = p.first+x[i];
   int c = p.second+y[i];
   if(grid[r][c] == 1) // enqueue move
 }
}

It seems like a pretty simple change, and I'm sure some will think it's not worth it, especially for this simple example where there's only four possible move directions, but once you start allowing moves along the diagonal you are up to having 8 if statements to write. The more code you have to write, especially with only slight modifications like adding one here and subtracting one there, the more probable it is that you will make a mistake that will cost you debugging time.

Other problems of this type:
439 - Knight Moves
841 - Snake
589 - Pushing Boxes
10793 - The Orc Attack