Breadth Recursion – a yield Solution to Post’s Correspondence Problem

P.C.P. Angel Dust; Number One Teen Killer!!!, by Mick Orlosky, CC-BY-NC 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.

Advertisements

2 thoughts on “Breadth Recursion – a yield Solution to Post’s Correspondence Problem

  1. Hmmm, I fail to see your position that using yield to build recursions is a bad idea…
    Since recursion and iteration are basically interchangable you cannot support that position in theory. In reality, some recursions are so complex that they are hard to look at, but are still valid.

  2. My problem with using yield in recursions is that I simply don’t like the code I see. It usually involves using yield and then foreach-ing over the result of the recursive call.
    It’s all a matter of taste.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s