Around two weeks ago, I found this email in my inbox, with the subject “Complaint about Robozzle”:

Hi Igor

Robozzle is really cute, I like it, but why on earth is it polluted with hundreds of invisible links to porn sites? From a guy like you I don’t expect to do such dirty things. pls remove them.

David

Hoping for a simple explanation, I looked at the source of the RoboZZle front page. And my heart sunk as I saw hundreds of spam links on the bottom:

<a href=”<a hijacked site>.com/files/cms/7/pornhud.com-20076.html”>porn hud.com</a>
<a href=”<a hijacked site>.com/files/cms/7/www.tube.com8-5852.html”>www.tube.com 8</a>
…

The links were inside a <p> tag with visibility set to “hidden”, so the links were only visible to search engines, not to human visitors.

I wondered if this affected how my site shows up in search engines. So, I searched for RoboZZle on Google (results in Bing or Yahoo! were not affected), and here is what I got:

Oh crap. This sucks. How did it happen?

Site infestation

So what did the hackers do to my poor game? I looked around to find what has changed:

1. Planted links
   Multiple pages on my site have been modified to import a planted config.ini file. The config.ini file contained hundreds of fake links, and was updated every couple hours with a new set of links. The links all pointed to spammy content planted on another hijacked site.
    
2. Planted content
   My site also contained thousands of small planted HTML files, similar to the spammy stuff that the planted links pointed to. An odd folder (something like http://robozzle.com/old/old2/) contained the HTML files, all with links to suspicious content, and all infested with spammy keywords.
    
3. Backdoor PHP scripts
   And finally, my site also contained a couple of PHP backdoor scripts. If you visited a particular URL on the robozzle.com domain, you’d get a file manager that lets you upload, delete, and manage files on my site, no passwords needed. As I found out later, the hackers actually knew my FTP password so they didn’t need the backdoors, but they left the backdoors so that they can get in once I change my password.

I carefully checked my site and removed all of this stuff. Even after I removed the PHP backdoors, the config.ini file continued to get updated until I changed my FTP password. From that point, I was pretty sure that the attackers somehow got my FTP password.

Looking for other hijacked sites

After cleaning up my site, one of the first things I did was notify the other compromised site, which hosted the planted content linked from my site.

I also wondered if more sites have been hacked in a similar way. I tried various online tools to find other sites that contain the same links that have been planted on my site.

I found a handful of hacked sites right away. The fact that the links change every few hours made the task more difficult, though. The newest links generally point to content that has not yet been crawled by search engines. But, there is a simple solution. By looking at older versions of several compromised sites in a service like Google Cache, I eventually found older links that lead me to many more hijacked sites.

After repeating the process for a couple hours, I ended up with a list of over a 150 infected sites, including some fairly major sites. The larger sites generally removed the infestation quickly, though. Here are a few sites that haven’t cleaned up, despite the fact that I alerted them at least two weeks ago:

• bayonnenj.org – City of Bayonne, NJ
• steinercollege.edu – Rudolf Steiner College
• dillard.senategop.org – GOP Senator Kirk Dillard
• egnc-ibm.gov.eg – Egypt-IBM Nanotechnology Research Center

Don’t go to these sites unless you know what you are doing. At the time of writing this post, these sites appear to be compromised, so they may well contain viruses or malware.

UPDATE: Most of the sites are suddenly not showing the links. My guess is that the hacker group distributed an empty config.ini file after this story became popular on reddit. I don’t believe that so many obscure sites on my list would be fixed over night when they have been infected for months before. Some sites still contain the planted links, but those seem to be the ones that haven’t been updating the links regularly. These are probably the sites that the hackers only have partial control over at this point (e.g., FTP password changed, but there is still a backdoor on the site somewhere). You should be able to view the planted links on all infected sites by looking at Google Cache.

I did my best to contact owners of as many hijacked sites as I could. Looking for contact information on that many sites – most of them not in English – is a time-consuming endeavor, though.

Tools I used

I found these tools useful when tracking down other sites that have been hijacked:

And how did I get hacked in the first place?

Of course, I have been wondering about how the hackers got my FTP password in the first place. It wasn’t really guessable or discoverable by brute force, and I didn’t use the same password on other sites.

And then I got an email from my webhost, notifying me that FTP passwords may have been stolen due to a vulnerability. They tracked down the issue to a particular software package they use.

So, I assume that my password got stolen this way. If not, it is also possible that I logged into my site on a computer with a particular virus. Apparently, that’s how many FTP passwords get stolen.

If you liked this article, check out these ones:

Human heart is a Turing machine, research on XBox 360 shows. Wait, what?

Numbers that cannot be computed

Implications of the Turing completeness of reaction-diffusion models, informed by GPGPU simulations on an XBox 360: Cardiac arrhythmias, re-entry and the Halting problem [PDF]

Turing completeness, cardiac arrhythmias, XBox 360… those things don’t seem to have much in common. But, I had my interest piqued. I looked up the paper and read through it. And, it turns out that not only is the paper serious, what it has to say is also quite interesting.

Heart and logic circuits

I had to take author’s word on the medical aspects of the article, since I know nothing about cardiology. Apparently, understanding of electrical signals between cells in a human heart is important for research into heart arrhythmias. Makes sense.

The important insight of the article is that a logic NOR gate can be simulated using electrical signals between heart cells. Constructing a NOR gate is a powerful result, because similarly to NAND, NOR is a universal logic gate. That means that all other logic gates like AND, OR and NOT can be built out of NORs:

NOT(A)    = NOR(A, A)
OR(A, B)  = NOR(NOR(A, B), NOR(A, B))
AND(A, B) = NOR(NOR(A, A), NOR(B, B))

So, since you can simulate a NOR gate using cardiac cells, you can simulate an arbitrary logic circuit in heart tissue.

Heart and Turing machines

But, there has to be more to the story. The paper title mentioned Turing machines, and logic circuits are not Turing-complete. Halting problem doesn’t even make sense when applied to boolean expressions!

The missing part is the passage of time. See, a logic circuit is not Turing-complete. But, if you take a logic circuit with multiple inputs, the same number of outputs as inputs, and repeatedly apply the circuit over the results of the previous iteration, you get a Turing-complete system. This type of a system can be modeled with behavior of a heart tissue over a period of time.

The most intuitive explanation that I can think of is via Game of Life. In the Game of Life, each cell dies, becomes alive or stays alive depending on how many live neighbors it had in the previous generation.  Here is one example of a Game of Life board in action:

Now, the important observation is that the Game of Life rules can be encoded using a logic circuit. For example, if the eight neighbors of a particular cell are represented as A, B … H, then the rule that the cell becomes alive if it has exactly three neighbors can be encoded as  ((A and B and C and not(D) and … and not(H)) or (A and B and not(C) and D and not(E) … and not(H)) or …). This expression will be combined with an OR together with the situations under which the cell remains alive, rather than becoming alive. This will be a pretty ugly logic circuit, but it should be clear that it can be constructed.

Since Game of Life is known to be Turing-complete, then an “iterated logic circuit” is also Turing-complete, and the behavior of cardiac tissue is … Turing-complete.

Why is this useful?

Proving that a particular behavior of cardiac tissue is Turing-complete is a useful result because it shows that the cardiac tissue is in a certain sense “unpredictable”.

For example, since Game of Life is Turing-complete, the Halting problem applies. So, it is a proven fact that there is no general algorithm that can look at a particular Game of Life board and decide whether the movement will eventually stop or continue forever.

Similarly, there is no algorithm that can decide any of these properties for all Game-of-Life boards:

• Whether the board will ever reach a particular configuration
• Whether the number of live cells will ever exceed X
• Whether the game will ever enter a cycle
• etc.

Since the studied behavior of cardiac tissue is also Turing-complete, there is no general algorithm that can look at the state of cardiac tissue and decide whether the activity will ever stop, enter a regular pattern, achieve a particular configuration, etc. That is certainly a worthwhile result!

What about the XBox?

Constructing a NOR gate out of cardiac cells is computationally intensive, and the researcher used a GPU in an XBox 360 for that task.

However, the paper doesn’t conclusively show that using an XBox was a real benefit. The paper says that a C++ implementation that was originally “designed more for ease of expansion […] than for speed” ran slower on an XBox 360 CPU than an “unoptimized” shader-based implementation on an XBox 360 GPU. Comparing implementations not designed for speed is unconvincing. If the goal was to speed up the computation, why not first try to optimize the original code instead of porting it to shaders, which is undoubtedly a much more difficult task?

Also, the article doesn’t say how did XBox 360 CPU compare against an ordinary x86 machine, or against say a CUDA-based implementation on a common NVidia card. So, the paper doesn’t come close to showing that the researchers gained much by coding against the XBox 360 GPU, rather than following the current state-of-the-art approaches.

But, it is still a cool paper, and adding XBox 360 into the picture certainly attracted attention. The paper was reported in press, with titles such as these:

• How Xbox Can Help Fight Heart Disease [time.com].
• Parallel processor computing of XBox chip could save thousands [techshout.com].

And, if it weren’t for the sensational articles, I wouldn’t have found out about the paper at all, so I guess I shouldn’t complain.

The book consists of 70 chapters on optimization, graphics, and assembly programming. The entire book is insightful and interesting, but my favorite chapters are these:

• The Best Optimizer Is between Your Ears
• There Ain’t No Such Thing as the Fastest Code
• Optimizing for 286 and 386, 486 (continued), and Pentium (continued here and here).
• Algorithms for fast drawing of lines, anti-aliased lines, polygons, fast convex polygons, and 3d objects (continued)
• Quake’s visible-surface determination, 3D clipping, hidden-surface removal, span sorting, lighting, surface caching and post-mortem.

Enjoy! Again, the entire book is accessible here: Graphics Programming Black Book.

pre.code { margin-left: 40px; }

Over the past couple of years, auto-complete has popped up all over the web. Facebook, YouTube, Google, Bing, MSDN, LinkedIn and lots of other websites all try to complete your phrase as soon as you start typing.

Auto-complete definitely makes for a nice user experience, but it can be a challenge to implement efficiently. In many cases, an efficient implementation requires the use of interesting algorithms and data structures. In this blog post, I will describe one simple data structure that can be used to implement auto-complete: a ternary search tree.

Trie: simple but space-inefficient

Before discussing ternary search trees, let’s take a look at a simple data structure that supports a fast auto-complete lookup but needs too much memory: a trie. A trie is a tree-like data structure in which each node contains an array of pointers, one pointer for each character in the alphabet. Starting at the root node, we can trace a word by following pointers corresponding to the letters in the target word.

Each node could be implemented like this in C#:

class TrieNode
{
    public const int ALPHABET_SIZE = 26;
    public TrieNode[] m_pointers = new TrieNode[ALPHABET_SIZE];
    public bool m_endsString = false;
}

Here is a trie that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

Implementing auto complete using a trie is easy. We simply trace pointers to get to a node that represents the string the user entered. By exploring the trie from that node down, we can enumerate all strings that complete user’s input.

But, a trie has a major problem that you can see in the diagram above. The diagram only fits on the page because the trie only supports four letters {A,B,C,D}. If we needed to support all 26 English letters, each node would have to store 26 pointers. And, if we need to support international characters, punctuation, or distinguish between lowercase and uppercase characters, the memory usage grows becomes untenable.

Our problem has to do with the memory taken up by all the null pointers stored in the node arrays. We could consider using a different data structure in each node, such as a hash map. However, managing thousands and thousands of hash maps is generally not a good idea, so let’s take a look at a better solution.

Ternary search tree to the rescue

A ternary tree is a data structure that solves the memory problem of tries in a more clever way. To avoid the memory occupied by unnecessary pointers, each trie node is represented as a tree-within-a-tree rather than as an array. Each non-null pointer in the trie node gets its own node in a ternary search tree.

For example, the trie from the example above would be represented in the following way as a ternary search tree:

The ternary search tree contains three types of arrows. First, there are arrows that correspond to arrows in the corresponding trie, shown as dashed down-arrows. Traversing a down-arrow corresponds to “matching” the character from which the arrow starts. The left- and right- arrow are traversed when the current character does not match the desired character at the current position. We take the left-arrow if the character we are looking for is alphabetically before the character in the current node, and the right-arrow in the opposite case.

For example, green arrows show how we’d confirm that the ternary tree contains string ABBA:

And this is how we’d find that the ternary string does not contain string ABD:

Ternary search tree on a server

On the web, a significant chunk of the auto-complete work has to be done by the server. Often, the set of possible completions is large, so it is usually not a good idea to download all of it to the client. Instead, the ternary tree is stored on the server, and the client will send prefix queries to the server.

The client will send a query for words starting with “bin” to the server:

And the server responds with a list of possible words:

Implementation

Here is a simple ternary search tree implementation in C#:

public class TernaryTree
{
    private Node m_root = null;

    private void Add(string s, int pos, ref Node node)
    {
        if (node == null) { node = new Node(s[pos], false); }

        if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
        else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
        else
        {
            if (pos + 1 == s.Length) { node.m_wordEnd = true; }
            else { Add(s, pos + 1, ref node.m_center); }
        }
    }

    public void Add(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        Add(s, 0, ref m_root);
    }

    public bool Contains(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        int pos = 0;
        Node node = m_root;
        while (node != null)
        {
            int cmp = s[pos] - node.m_char;
            if (s[pos] < node.m_char) { node = node.m_left; }
            else if (s[pos] > node.m_char) { node = node.m_right; }
            else
            {
                if (++pos == s.Length) return node.m_wordEnd;
                node = node.m_center;
            }
        }

        return false;
    }
}

And here is the Node class:

class Node
{
    internal char m_char;
    internal Node m_left, m_center, m_right;
    internal bool m_wordEnd;

    public Node(char ch, bool wordEnd)
    {
        m_char = ch;
        m_wordEnd = wordEnd;
    }
}

Remarks

For best performance, strings should be inserted into the ternary tree in a random order. In particular, do not insert strings in the alphabetical order. Each mini-tree that corresponds to a single trie node would degenerate into a linked list, significantly increasing the cost of lookups. Of course, more complex self-balancing ternary trees can be implemented as well.

And, don’t use a fancier data structure than you have to. If you only have a relatively small set of candidate words (say on the order of hundreds) a brute-force search should be fast enough.

Further reading

Another article on tries is available on DDJ (careful, their implementation assumes that no word is a prefix of another):

http://www.ddj.com/windows/184410528

If you like this article, also check out these posts on my blog:

• Skip lists are fascinating!
• Numbers that cannot be computed
• Quicksort killer

Let’s go over the affected browser features one by one, and discuss ways of getting them working in Silverlight apps.

Feature 1: Bookmarking and deep linking

Users like to be able to copy the link from the address bar, email it to a friend, bookmark it, or post it on Twitter or Facebook.

A Silverlight app will typically transition between different views without redirecting the user to a different URL. This makes the user experience smooth and polished. As an unfortunate consequence, a user that copies the URL from the address bar or bookmarks the page will not get a link to the current active view, but instead a link to the initial view of the app.

Thankfully, there is a solution in Silverlight. A Silverlight app can modify the “bookmark” section of the URL, which is the part of the URL following the # character. The app can update the URL each time the user transitions to a different view, and read the bookmark on startup. See this article for details on how to implement this.

The Navigation Framework feature in the upcoming Silverlight 3 release will provide an easy-to-use solution to this problem.

Feature 2: Search engine discoverability

If your Silverlight app links to another page, that link is invisible to search engines. As a result, pages on your site that cannot be reached via traditional HTML links will likely not get listed in search results.

The solution is simple: list all pages on your site in an XML document called a Sitemap. Host the Sitemap on your site, and submit the Sitemap link to search engines. Once you do that, the search engines should include all pages on your site in their indexes.

For details, see the Wikipedia article on Sitemaps.

Feature 3: Back and Forward browser buttons

The Back and Forward browser buttons do not work in Silverlight apps. Switching to a different view in a Silverlight app does not insert a bookmark into the browser history, so the user can’t go to the previous view by clicking the Back button.

The problem is similar to the bookmarking issue (Feature 1), except that the solution is more complicated. If the Silverlight app modifies the bookmark part of the URL, the previous bookmark does not get recorded in the browser history, so the user still cannot use the Back button to return to the previous view.

It is in fact possible to get the Back and Forward buttons working. As of SP1 3.5, ASP.NET exposes a History Control that simplifies the solution significantly (see Control Silverlight by Using Browser Back and Forward Buttons). There is a variety of solutions available online in case you are not using ASP.NET 3.5 SP1, but beware that they typically involve hacks that don’t necessarily work in all browsers.

Or, you can wait until Silverlight 3, because browser history is properly handled in the Navigation Framework.

Feature 4: Support of external tools (translation, accessibility, …)

Automated translation, special browsers for people with disabilities, automated RSS aggregating… these are just some examples of useful tools that consume web content. These tools typically process HTML, but don’t peek inside Silverlight applications.

Since HTML is the standard representation of online documents, consider whether it would make sense to expose a simplified version of your content as a simple HTML page, in addition to your Silverlight application.

Feature 5: Printing

Silverlight does not currently have much support for printing. In Internet Explorer 7, Silverlight applications show up on the printout, but in Firefox or Safary they do not.

So, a Firefox or Safari user will not be able to print out the information displayed by your Silverlight application (at least not without taking screenshots, etc).

If you need to support printing, you can try two different solution approaches. If you only need to print content that can be represented using HTML (e.g., no Silverlight-generated charts and such), see this solution. An alternate approach is to convert XAML to an image format on the server.

Feature 6: Open link in new tab

There doesn’t seem to be a very good way to implement the ‘Open link in new tab’ feature in Silverlight. You can use a HyperlinkButton with a Target set to _blank, which seems to open a new tab in Firefox and a new Window in IE 7. But that still won’t allow the user to choose whether to open the page in the same or different tab/window.

If you are committed enough, you can probably implement a HyperlinkButton with a context menu allowing the user to open the link in a new tab/window. Right-clicking is not directly supported in Silverlight, but workarounds do exist.

Or, use hyperlinks sparingly in Silverlight apps.

Feature 7: Find on this page

I use the ‘Find on this page’ feature (CTRL+F) extensively when browsing the web. But, content inside Silverlight apps is not searched by the browser.

A mitigation is to carefully design the app UI in a way that minimizes the user’s need to search. Data should be sortable and searchable in various ways, and important information should be shown prominently (e.g., the user’s own position on a scoreboard should be highlighted).

These are all good practices regardless of your development platform, but unavailability of the ‘Find on this page’ feature makes them even more important.

Conclusion

Hopefully you’ll find these points helpful when designing your next Silverlight application. If you have other tips on extending browser features into Silverlight apps, let me know in the comments!

The video made the reddit front page, so you can read the usual mixture of insightful, funny, and outright insane comments on the reddit page and the YouTube page.

My favorite funny comment is this one:

And finally, this is the video:

One solution to this performance problem is to use a “precomputed view”. Unlike an ordinary view, a precomputed view is stored in a table rather than computed on demand. When data in one of the aggregated tables changes, the update operation also updates the precomputed view table.

A great thing about precomputed views is that they can be implemented fully in SQL. Any code that accesses the database sees a precomputed view as a regular table. Also, if you have an existing regular view, you can change it into a precomputed view without having to modify any code that queries the view.

To explain the precomputed view pattern, let’s look at an example loosely inspired by the reddit social news site. Users submit articles to reddit and the articles receive up and down votes from other users. User’s “karma” is computed as a sum of votes on positively-voted articles submitted by the user.

To store the reddit data, you can store users in one table, articles in another table, and votes (+1 or -1) from users on articles in a third table:

Now, say that we want to find the top 10 users with highest karma. To compute a user’s karma, we need to sum up the scores of all articles submitted by the user. And to compute each article score, we need to aggregate the votes for that article. It should be clear that this query is going to be very expensive, no matter how much you tune and optimize it.

Views could be used to factor the complex query into simpler pieces, but not to decrease its overall cost:

It is easy to find the top 10 users, simply by querying User_View. Unfortunately, if the database contains millions and millions of votes, the query will take a long time to run. The query will have to group all votes by article, group all articles by user, and then pick the top users. Imagine the impact on performance if you wanted to show the top users on every page of your web app!

However, by changing the views into precomputed views, we can make the query for top users cheap:

Let’s walk through the conversion of Article_View to a precomputed view. First, we’ll create a table for the precomputed view:

    CREATE TABLE Article_PView(
        ArticleId int NOT NULL,
        Title varchar(40) NOT NULL,
        Url varchar(250) NOT NULL,
        VoteSum int NOT NULL,
    )

Second, we’ll need two triggers. This trigger inserts a row into Article_PView whenever a new row is inserted into the Article table:

    CREATE TRIGGER TRG_ArticleInsert
        ON  Article
        AFTER INSERT
    AS
    BEGIN
        SET NOCOUNT ON;

        INSERT INTO Article_PView (ArticleId, Title, Url, VoteSum)
        SELECT Id As ArticleId, Title, Url, 0
        FROM Inserted
    END

And this trigger recomputes a row in Article_PView whenever a vote is inserted, updated or deleted:

    CREATE TRIGGER TRG_Vote
        ON  Vote
        AFTER INSERT, UPDATE, DELETE
    AS
    BEGIN
        SET NOCOUNT ON;

        WITH articleIds(ArticleId) As
        (
            SELECT ArticleId From Inserted
            UNION
            SELECT ArticleId From Deleted
        )
        UPDATE Article_PView
            SET VoteSum = (
                SELECT SUM(Vote) FROM Vote
                WHERE Article_PView.ArticleId = articleIds.ArticleId)
        FROM articleIds
        WHERE Article_PView.ArticleId = articleIds.ArticleId
    END

And finally, we’ll populate the precomputed view with data that is already in the database:

    INSERT INTO Article_PView (ArticleId, Title, Url, VoteSum)
    SELECT Article.Id, Title, Url, ISNULL((SELECT SUM(vote) FROM Vote WHERE ArticleId = Article.Id), 0)
    FROM Article

Article_PView precomputed view is now ready, and User_PView can be created in a similar fashion.

Remarks

Note that my example assumes articles never get removed or updated. Adding support for that functionality is straightforward: you’ll need to extend the TRG_ArticleInsert trigger to also handle updates and deletes. This will be very similar to what TRG_Vote does, but I left it out from the sample for simplicity.

There are several interesting variations of how Article_PView could be implemented. In the implementation above, the trigger aggregates the votes for an article each time someone votes on it. If you want to avoid this cost, you can change the trigger so that it only adjusts the article score instead of recomputing it. For example, if a vote was updated from -1 to +1, the trigger would add 2 to the score of the article. Avoiding concurrency issues may be tricky with that approach, though.

Another interesting variation is adding the VoteSum column to the Article table instead of creating a separate table. Choose the approach that better fits your table design.

Hope you find this pattern useful!

For decades, computer science students have been taught that so-called NP-hard problems do not have known efficient solutions. These problems include the infamous Travelling salesman problem, subset sum, 3SAT, and many more.

But – as is often the case – where theoretical Computer Science failed, sound software engineering practices will succeed. By using loosely-coupled OOP, agile methodologies and the model-view-controller architectural pattern, I developed a solution that someone trapped in the world of formulas and big Ohs would never dream of.

Enough with the background, and let’s take a deep dive into the intriguing design.

Introducing the choose expression

As most other elegant designs, this one is very simple. My proposal calls for a choose expression with this syntax:

    choose { boolean_expression1, boolean_expression2 }

Choose expression is basically the || operator, only with a slight twist. The semantics of the choose expression are similarly simple:

1. If boolean_expression1 or boolean_expression2 will evaluate to true, the runtime will evaluate the true expression, but not the other expression. The return value of the choose expression will be true in this case.
2. If both expressions will evaluate to false, the runtime will evaluate neither expression. The return value of the choose expression is false in this case.

Let’s look at a few simple usage examples:

    bool a = choose {
        1 == 2,
        1 < 2
    };

Variable a will be set to true, because the condition 1 < 2 is true.

Here is another example:

    bool a = choose {
        ((Func<bool>)(() => { Console.WriteLine("Hello"); return false; }))(),
        1 < 2
    };

There is no point executing the first function, because it would return false anyways. So, this code sample does not print anything to screen. Instead, the choose expression will execute the second function. The second expression returns true, so variable a will be set to true.

And another simple one:

    bool a = choose {
        ((Func<bool>)(() => { Console.WriteLine("Hello1"); return false; })(),
        ((Func<bool>)(() => { Console.WriteLine("Hello2"); return false; })(),
    };

This code sample will not be print anything to screen either. It is obvious; why evaluate either of the two functions if they are going to return false anyways? This code simply assigns false to variable a.

Now, let’s cut to the chase, and use choose expressions to give an efficient implementation of an NP-hard problem. Let’s look at subset sum:

    bool SubsetSum(int[] arr)
    {
        return SubsetSumHelper(arr, 0, 0);
    }

    bool SubsetSumHelper(int[] arr, int index, int sumSoFar)
    {
        if (index == arr.Length)
        {
            return sumSoFar == 0;
        }

        return choose {
            () => SubsetSumHelper(arr, index + 1, sumSoFar + arr[index]),
            () => SubsetSumHelper(arr, index + 1, sumSoFar)
        };
    }

Yes, that’s right! An O(N) implementation of the subset sum problem. There you have it, computer scientists. You said it was impossible. If anyone at the University of British Columbia needs my mailing address to send me a refund check for my education, you can find my contact information in the margin.

Under the hood of the choose expression

After a couple hours of coding, I was able to develop a simple prototype. It works perfectly, but since it is only a prototype, I simplified my life a little bit by allowing choose to execute both functions. After all, I don’t have to slave through all the nitty-gritty details in the initial prototype, right? The performance of my implementation is not that great either, but I haven’t had the time to fire up the profiler so far. Perhaps I need to unroll a loop somewhere, or ensure that method calls are getting inlined optimally.

To further prove the feasibility of my design, I developed a non-deterministic Turing machine construction that evaluates choose expressions extremely efficiently.

Non-deterministic Turing machines are known to be a good realistic abstraction of computing hardware; there was a study that proved that. To be exact, the study was only a moderate success. The researchers built a mechanical non-deterministic Turing machine that solved a Travelling Salesperson problem with 5 cities without a hitch. On the 6-city version of the problem, the experiment had to be abruptly interrupted after sprawling machine replicas filled up the room, and the head of one of the researchers got caught in a loop of tape.

So, it is clear that this design is sound. There may be performance issues in the first release, but they will improve as the technology matures. And once CPU manufacturers include a non-deterministic branching instruction in the instruction set, the cost of evaluating the choose expression will drop down to a couple of instructions.

Summary

I don’t know the detailed plans surrounding the C# language, but if there is a C# 4.1., I would like to see the choose expression included.

And the larger lesson of this post is simple: computer science is largely obsolete in today’s world of technology. Computer science says that this is impossible, that is impossible… As you just saw, anything is possible, so long as you have enough paper to print out all the UML diagrams.

For fun, I’ll discuss different aspects of RoboZZle and assign each a letter grade.

Game Addictiveness: A

Let’s start with the positive. RoboZZle has shown to be an addictive game, at least for a certain audience. There is a core group of players that log in regularly, solve puzzles, participate in discussions, design puzzles, propose improvements, and so forth.

A great illustration of my point is a quote from player recursive after finally cracking a long unsolved puzzle designed by evko:

This level is amazing.

I spent about 6 hours solving this one. It took me a while to realize that every movement had to be saved on a stack. Then I developed diagrams, models, and a logical structure around it. And eventually stumbled my way to the solution logically. But it all seems so intuitively obvious now.

This is the best level I’ve solved so far. Bravo.

RoboZZle players have contributed in a variety of ways:

• aalku contributed articles to a number of sections of the wiki (still in an early stage).
• evko is a brilliant puzzle designer who created 42 puzzles, many of them amazingly clever and innovative.
• hr0nix implemented an automated solver for simpler RoboZZle puzzles.
• life96 made a number of helpful suggestions, and investigated the CPU usage of the game.
• stingray blogged about RoboZZle. The article Can Games Teach You To Program? got popular on reddit.
• recursive has an amazingly deep understanding of the game, and discovered shortest known solution for nearly all puzzles.

Finally, I really like this comment left by player spikeless the day that RoboZZle launched:

Brilliant game! It has seriously impacted productivity in our development team leaving nothing to be heard but frustrated curses and elated ‘Yesss’s.

For addictiveness, I give RoboZZle a shameless A.

Features: B

My approach has been to do the minimal set of features I can get away with (but no less), and then grow the game from there. Otherwise, I would still be only 50% done; or more likely, I’d have given up a long time ago.

Since the game launched, I’ve been furiously adding features, in part driven by user feedback, and in part based on what I think will make the game work better.

I added forums, RSS feed for puzzles, wiki, scoreboard for shortest solutions, a stepping debugger for solutions, a new game mode, and lots more.

I give RoboZZle a B here because there are so many more things that I want to do with the game. I can already tell that this will keep me busy for a good while.

Code Quality: B-

This section is about bugs! Similarly to features, I tried to make things “good enough”, and then deploy. Otherwise, I would never get anything done.

Most of the time, this worked fine. Only once a new feature introduced a major bug that impacted the game play for a lot of users. That time, the robot would sometimes seriously misbehave, e.g. continuing its path even though it should have died by falling off a tile.

Except for this one instance, most bugs have been minor issues that most players won’t run into. There are a few minor blemishes still present in the game, but I’m working my way through them.

So, it seems appropriate that RoboZZle gets a B- for quality.

Incoming Traffic: C+

Hmm… incoming traffic. While the loyalty of visitors seems to be great, the incoming traffic numbers aren’t quite as impressive. This table gives a quick summary:

23,000 visits is nothing to sneeze at, but I’ve seen similar numbers for  a blog post that took me a weekend to write. (In all fairness, most of those visitors probably spent less than a second “reading” my blog post.)

Here are the main sources of incoming traffic for robozzle.com:

So, it’s silverlight.net, some popular Russian site, google, dotnetkicks, and two blogs (both recommended reading). Other than that, there are many sources that contribute a small number of visitors each.

I should be able to do better. A part of the problem is that most people still don’t have Silverlight installed, and Silverlight gaming is in its infancy. There are signs that this is about to improve, such as http://mashooo.com, http://silverarcade.com and http://silverlightclub.com, so I’m keeping my fingers crossed.

The other part of the problem is that I need to learn how to better market RoboZZle and draw in visitors. This is a new territory for me, but I’m learning new things every day.

And that’s the main reason I’m working on RoboZZle, so it’s OK.

RoboZZle is an online puzzle game that challenges you to program a robot to pick up all stars on a game board. The game mechanics are simple, yet allow for a wide variety of challenges that call for very different solution approaches.

Here is an example of a solved RoboZZle puzzle, with the arrow edited-in to show the path of the robot:

Since designing RoboZZle puzzles is as much fun as solving them, the game includes a tool to make puzzles yourself. After you create a puzzle, you submit it, and other players will get an opportunity to try to solve it.

In this screenshot, I am just about done designing a challenging puzzle:

Players rate the difficulty of each puzzle, as well as vote whether they liked it or not. When looking for the next puzzle to solve, players can use the ratings to find cool puzzles with the difficulty that suits their current mood.

This screenshot shows the main RoboZZle page at http://robozzle.com:

Players can lookup their ranking, as well as statistics on all players and puzzles on the statistics pages.

In a Web 2.0 fashion, RoboZZle is designed to be a user-driven, social experience. Please check it out, install Silverlight if you need to (it is safe to install), and let me know how you like the game.