Archive for January, 2009

Size Matters

Saturday, January 31st, 2009

Ha! I did get a blog entry posted in January. (And I’m not dead, in case you were wondering… just swamped with work. Only a few weeks until my current project is complete and then I should have time to post some new stuff!)

Anyway, I thought I’d write a little blurb about my recent entry into the Mix 10K Smart Coding Challenge. I did not plan to participate in this contest because of other demands on my time. Then Wednesday night someone mentioned that there were only two days left. I took a quick peek at some of the existing entries and I suddenly got the urge to give it a shot. Not that I thought I could do better… (I know my limitations when it comes to design! ;)) Rather, it was the caliber of other participants that drew me in. Plus, the idea of squishing coolness into a mere 10K of code just seemed like fun. I just needed an idea!

That’s when I saw one of my favorite Christmas stocking stuffers sitting on the corner of my desk… Sit & Solve Sudoku. The shape of this little book says it all!

I love a good puzzle! I first discovered Sudoku a couple of years ago when spending a few weeks in India. Now it’s one of my favorite leisure activities when trapped on a plane.

Yes, I’m aware there are lots of online Sudoku games out there. But I’ll wager that very few, if any, are written using less than 10K of code! So there was my challenge. And I’m happy to say that I met that challenge.

You should be able to check out my entry, JAGS 10K, in the contest gallery shortly. I submitted it yesterday but it has yet to appear on the site.

I’ll add a link here when the app goes live. In the meantime, below is a sneak peak:

I probably won’t win any awards for this little game, but I’m pretty proud of it nonetheless! I had a blast packing it full of features and whittling it down to size.

Introduction to JAGS 10K

First, the name JAGS 10K stands for “Just Another Game of Sudoku (in 10K)”. It is quite possibly the smallest, fully functional version of Sudoku ever created! (hyperbole intended! :D)

Instructions

If you’ve never played Sudoku before, the rules are quite simple… Fill in the grid such that every row, column, and 3×3 box contains every digit from 1 to 9. That’s it!

Game Play

You can play JAGS 10K using the keyboard, the mouse, or both. For keyboard play, simply select a cell using the tab or arrow keys and press the desired number. Press 0 (zero) or Delete to clear a cell. For mouse play, simply click an empty cell and drag the mouse downward to cycle through the available digits. Release the mouse when you find the digit you desire.

The application will generate custom games for you, or it can obtain recently published games from the web. Just launch the app, choose your difficulty level, and enjoy!

Cutting it Down to Size

I thought it would be fun to share a few of the tricks I used to bring this application within the 10K limit. You can think of the remainder of this post as my tips for the next 10K challenge. 🙂

First, I should point out that JAGS 10K is written in WPF (duh!). But most of the tricks described here would work equally well in WPF or that other XAML-based platform. (You know what I’m talking about, right? That web platform. What was it called again? I’m sure you know what I mean, anyway… that technology whose logo looks like a big blue iridescent thong! Oh never mind.)

I should also point out that calling this contest a “smart” coding challenge is a bit of a misnomer. I would call it a “clever” coding challenge, at best. (But then they couldn’t play off the “art” in smart, so that wouldn’t fly.) In any event, making an application run in 10K or less involves the intentional implementation of some very poor coding practices! Using these tricks for a production application is not advisable.

First Things First… Make it Work

I began by simply writing the application the way I would any new WPF project. I always start with the view model and an extremely simple view to prove out the view model. This provides a very basic proof of concept app, without the eye candy (styling and visual appeal).

I was able to create a very simple Sudoku game in just a few short hours. I used fully descriptive variable names during this phase (since it’s rather important that one understand and easily follow the code they are creating). I also used a brute force algorithm for generating new game boards. I won’t bore you with the details, but I will readily admit that it is inelegant and architected purely to keep the code simple.

Downsizing via the Obvious Stuff

Once I had the game working the way I wanted, it was time to cut it down to size. At this point, it was about 60K. Clearly, when trying to get under 10 kilobytes, every byte counts! (Literally.) There are some very obvious things you can do: remove all white space, rename all variables using 1 character names, drop all the “private” qualifiers, group similar variables and declare them using a comma-delimited list, etc. After doing these things, I was down to about 20K.

Now for some of the less obvious tricks…

Use integers instead of enum values

The WPF and BlueThong platforms contain a lot of enums with long, descriptive value names. Typing out these names uses up precious bytes. In my code, I instead specified enum members via their explicit integral values, which are easily discovered using reflector.

For example, instead of using:

  ResizeMode=ResizeMode.CanResizeWithGrip;

You might use:

  ResizeMode=(ResizeMode)3;

Voila! You’ve just saved 15 bytes!

CAUTION: This is one of those shortcuts that you would never want to do in real code! If Microsoft decides to reorder enum values in a future update, the application will surely break.

Use a series of if statements instead of a switch statement

The following example combines the enum trick with the elimination of a switch statement to further reduce size (at the slight expense of performance). When processing keyboard input, each KeyDown event provides the key that was pressed using the System.Windows.Input.Key enum. Rather than writing typical code that looks like this:

  switch (e.Key)
  {
      case Key.Back:
      case Key.Delete:
          f();
          break;

     case Key.NumPad0:
     case Key.D0:
           b();
           break;
  }

I instead wrote code like this:

  int v=(int)e.Key;
  if(v==2||v==32)f();
  if(v==34||v==74)b();

Even in its most compact form, the switch statement above requires 94 bytes, whereas the less optimal series of if statements using known integral values only requires 56 bytes. An instant savings of almost 40 bytes!

Reuse Global Variables

If you find yourself declaring a lot of similar variables in different methods, consider just declaring the variable once in the global scope of your class and reusing it in those various methods.

Remember that code may be more compact than markup

Instead of this:

  <ComboBox Name="c">
    <s:String>Easy</s:String>
    <s:String>Medium</s:String>
    <s:String>Hard</s:String>
  </ComboBox>

You can do this:

  <ComboBox Name="c"/>

With this in the code behind:

  c.ItemsSource=new string[]{"Easy","Medium","Hard"}

Another 40-byte savings!

Instantiate variables using the var keyword

Since this contest targets .NET 3.5 and the current releases of the .NET languages, there are some additional cool tricks at our disposal. For example, instead of doing this:

  ListBoxItem x=new ListBoxItem();

You can do the following to save some bytes:

  var x=new ListBoxItem();

Use abbreviated property declarations

If you don’t need to access their private backing fields, declare properties using abbreviated notation:

  public string T{get;set;}

Leverage an existing framework class for INotifyPropertyChanged support

Remember, its size that matters… not efficiency. When I was looking for those last 100 bytes, I realized that a lot of space was wasted implementing the INotifyPropertyChanged interface on my view model class.

My original class began like this:

  public class P : INotifyPropertyChanged
  {
      public event PropertyChangedEventHandler PropertyChanged;
      void N(string n)
      {
          if (PropertyChanged != null)
              PropertyChanged(this, new PropertyChangedEventArgs(n));
      }

Clearly this contains long class names that are out of my control. Even with the white space removed, the above support for INotifyPropertyChanged requires a full 193 bytes.

Knowing that the framework contains several classes that already implement INotifyPropertyChanged, I set out with reflector to find one that could be leveraged for my needs. I decided GroupStyle was a good candidate, so I changed my class to derive from it, as shown here:

  public class P:GroupStyle
  {
      void N(string n){OnPropertyChanged(new PropertyChangedEventArgs(n));}

Using this simple trick, I now had full support for property change notifications for about half the asking price (96 bytes instead of 193). Tricky, eh?

Leverage Resources

Watch for lengthy elements that appear multiple times in your markup and surface those as resources. For example, if you notice that you are applying the same drop shadow effect in multiple locations, declare it as a resource and simply use a StaticResource reference to reuse it. (Okay, this is just good general advice for structuring resources, but it is even more important when you are up against a 10K size limit. :))

Make a few hard choices about Form vs. Function

Visual coolness costs big bytes! Markup-declared animations are very verbose. Styles are really lengthy because of all their Setters. The same is true for the Triggers collection on an element or within a style or template.

By the time I had developed the game engine and view model, I had already exhausted the majority of my 10K allotment. I then had to choose very carefully how I would design the actual user interface. I didn’t have room for gratuitous animations or other flashiness. In the end, I decided that my 10K app was more about function than form. (This decision may cost me in the voting, but I’m okay with that.) I was still able to pull off a nice look and feel (using a grand total of 10,195 bytes, or 9.96K) and I’m really happy with the overall product! In fact, I think I’ll bid you adieu now and go play another game of Sudoku!