Sunday, January 18, 2009

Creating websites WITHOUT using HTML

Want to see something that will blow your mind? Something that will shoot your brain out the back of your skull, through the window, and onto your neighbor's freshly waxed Pinto?

<?xml version="1.0" encoding="UTF-8"?>
<?xml-stylesheet type="text/xsl" href="layout/frontpage.xsl"?>
<page lang="en_us">

This is the source code for a website's entire home page (which is that of the upcoming computer game Starcraft 2 by Blizzard Entertainment).

I could be in the minority, but I've never seen XSLT used to transform XML documents into web pages...and I've never realized how powerful it can be. After exploring the source code of the website, here are some advantages and disadvantages of this technique that I've discovered:

Advantage - Separation of concerns

Using XSLT, you can more effectively separate the content of your website from the presentation. The Starcraft 2 website has *all* of its text separated out into XML files (pretty cool!). For example, you can find all the text on the Terran page, in a file devoted solely to storing Terran-related text (terran.xml).

Advantage - i18n

By separating the content from the presentation, another benefit is that it makes it easy to internationalize the website. This is what Blizzard has done. The XML files used to store text are located in their own directory, named according to the language of the text (such as "fr_fr" for French). The language of the guy viewing the website is stored in the "lang" attribute of "page" tag of each individual web page (see the above code snippet). This attribute is used to determine which directory to retrieve the text from.

Also, you can do things that you would normally think could only be done using server-side languages:

Advantage - Access to special functions

Since XSLT uses the XPath language, you get to use all the special functions that XPath comes with. Tasks like string manipulation, date/time formatting, rounding numbers--all things that one might typically associate only with server-side languages, can all be done with XPath. For example, the following code, taken from a shared file called includes.xsl, uses the "concat" function to build a URI that points to a language-specific version of an XML file:

<xsl:variable name="terran" select="document(concat('/strings/',$lang,'/terran.xml'))"/>

Advantage - Avoiding code duplication

Just as you might define a function in a server-side script that performs some task, you can define function-like constructs with XSLT that "output" HTML. If you look at movies.xsl (a file used to generate the Movies page) you can see that for each movie listed on the page, a template is called:

<xsl:call-template name="movies-entry">
<xsl:with-param name="title" select="$loc/strs/str[@id='sc2.labels.movies.movie6.title']"/>
<xsl:with-param name="movieid" select="'6'"/>
... more parameters ...

The template, defined in a shared file called includes.xsl, contains the HTML code used to display the movie:

<xsl:template name="movies-entry">
<xsl:param name="title"/>
<xsl:param name="movieid"/>
... more parameters ...
... HTML/XSL code used to display the movie ...

So instead of having to do a lot of copying and pasting, as you would have to do if using plain HTML, the code stays centralized in one place, making bug fixes and other maintenance tasks easier to handle.

Disadvantage - Backward-compatibility

XSLT didn't become a W3C recommendation until 1999, so any browser created before or around that time probably won't have strong support for the language (this includes IE 5 and earlier). So you have to consider the software your audience is likely to be using before building your site. Blizzard probably thought it safe to use this technology, since gamers tend to use the latest and greatest browsers and are therefore unlikely to run into any compatibility issues.

So in conclusion, I've found that using XSLT to build web sites gives you many advantages that you don't get when developing with vanilla HTML. Perhaps I will use it for my next web development project!

Sunday, January 11, 2009

SudokuSolver released

I've developed a bit of an addiction recently. Thankfully, it's not alcohol-related. But like drinking, it does take up time and money.

If you're not familiar with the puzzle game Sudoku, you've probably at least seen it either in your daily newspaper or somewhere online. The goal is: given a square board 9 cells high and 9 cells wide, fill each row, column, and 3 by 3 sub-square with all the numbers 1 through 9. No number can be repeated in any of those three places. For example, the number 5 can't appear more than once in the same row. The board starts with some cells already filled in to give you a starting point. The less completed cells you start with, the harder the puzzle is.

After solving enough of these, I thought it would be an interesting exercise to write a program which solves them automatically! As I got deep into creating the algorithm, one data structure stood out as being the keystone--sets.

In mathematics, a set is a collection of numbers where:

  1. the order the numbers are in does not matter and

  2. no number can be repeated.

For example, this is a set:
{ 3, 7, 5, 9 }

Since order doesn't matter, this is the same set as the one above:
{ 9, 3, 7, 5 }

But this is NOT a set because there are two 7s:
{ 9, 3, 7, 5, 7 }

In this algorithm, sets are useful when trying to figure out what number a cell should be. The algorithm can be summarized with this pseudo-code:

while board is not complete
for each cell in board
if cell is empty
possibleValues = findPossibleValues(cell)
if size of possibleValues == 1
cell.empty = false
cell.value = possibleValues[0];

function findPossibleValues(cell)
possibleValues = new set{1,2,3,4,5,6,7,8,9}

for each rowcell in cell's row
if rowcell is not empty
//if possibleValues doesn't contain rowcell.value, then nothing happens
possibleValues -= rowcell.value

for each colcell in cell's column
if colcell is not empty
possibleValues -= colcell.value

for each squarecell in cell's square
if squarecell is not empty
possibleValues -= squarecell.value

return possibleValues

Given a current board state, for each cell in the board, a set containing all values the cell could possibly be is created. If this set only contains one number, then that's the only number the cell can be, so we fill in the cell with that number. This keeps repeating until all cells are filled in. (There are some other tricks that have to be taken into account, but this is the most fundamental part of the algorithm.)

If you'd like to try it out or look at the source code, you can download it here: