Omer van Kloeten's .NET Zen

Breadth Recursion - a yield Solution to Post's Correspondence Problem

Post's Correspondence Problem (the other PCP) is a computer science problem, in which you have (and I simplify matters) a set of tiles, each having any number of letters on them from a preset group. For instance, you may have the tiles:

The idea is to create a sequence of tiles (when you can use an infinite amount of tiles from each kind) to get the exact same combination of letters both on the top row and the bottom one. One such combination would be aaaabab, where you would use tiles 4, 4, 2 and 1 to create the sequence: [aa][aa][b][ab] at the top and [a][a][a][abab] at the bottom. If you like, a good mental exercise would be to find the next shortest sequences.

PCP is an undecidable decision problem, which means that no program can be written that could receive a finite set of tiles as its input and return true or false as to whether a combination exists, without the risk of running indefinitely. However, a program that has the risk of running indefinitely that solves the problem can be written: Simply check all sequences of length 1, 2, 3, etc. and stop at the first that is a match.

Writing such a program is a bit cumbersome, as at each sequence of length n, you will have to either save all sequences of length n-1 or recalculate them. Using a classic recursion isn't that useful, since those are used for depth-based analysis, rather than breadth based. Luckily, C# 2.0's yield statement offers us a different type of recursion - the breadth recursion:

IEnumerable<Tile> GetTileSequence(IEnumerable<Tile> tiles)
{
    foreach (Tile tile in tiles)
    {
        yield return new Tile { Top = tile.Top, Bottom = tile.Bottom };
    }

    foreach (Tile sequence in GetTileSequence(tiles))
    {
        foreach (Tile tile in tiles)
        {
            yield return new Tile { Top = sequence.Top + tile.Top, Bottom = sequence.Bottom + tile.Bottom };
        }
    }
}

The above code runs on the set of tiles to create single tile sequences and then uses itself to create sequences one tile longer than itself. It's a bit confusing, I admit, but after a couple of minutes of examining it you may start seeing the hidden beauty of it. Using it to solve the problem would look something like this:

Tile[] tiles = new Tile[] { 
    new Tile { Top = "ab", Bottom = "abab" },
    new Tile { Top = "b", Bottom = "a" },
    new Tile { Top = "aba", Bottom = "b" },
    new Tile { Top = "aa", Bottom = "a" }
};

foreach (Tile sequence in GetTileSequence(tiles))
{
    if (sequence.Top == sequence.Bottom)
    {
        Debug.WriteLine("Match: " + sequence.Top + ", " + sequence.Bottom);
        return sequence;
    }
}

This whole piece of code was written a few days after a little debate I had with @yosit about whether using yield statements to build recursions was a good idea or not. I still hold the firm belief that it usually isn't a good idea, since it's, as you can see for yourself, pretty confusing; That and the fact that most people are used to the classic recursion.