ayt_cem ayt_cem - 4 years ago 56
C# Question

Generating Schröder Paths

I want to generate schröder paths from (0, 0) to (2n, 0) with
no peaks, i.e., no up step followed immediately by a down step.
Some examples are for n=3 : shröder paths.

/ is coded as U, -- is coded as R and \ is coded as D. Here is my code to generate these paths :

public static void addParen(List<String> list, int upstock,int rightstock,int
downstock,bool B, char[] str, int count,int total,int n)
{


if (total == n && downstock == 0)
{
String s = copyvalueof(str);
list.Add(s);
}

if (total > n || (total==n && downstock>0) )
return;
else
{
if (upstock > 0 && total<n)
{
str[count] = 'U';
addParen(list, upstock - 1,rightstock, downstock+1,B=true, str, count + 1,total+1,n);
}
if (downstock > 0 && total<n && B==false)
{
str[count] = 'D';
addParen(list, upstock,rightstock, downstock - 1,B=false, str, count + 1,total+1,n);
}

if (rightstock > 0 && total < n)
{
str[count] = 'R';
addParen(list, upstock, rightstock-1, downstock, B = false, str, count + 1, total + 2,n);
}
}
}

public static List<String> generatePaths(int count)
{

char[] str = new char[count * 2];
bool B = false;
List<String> list = new List<String>();
addParen(list, count-1, count, 0,B,str, 0, 0,count*2);
return list;
}


The total is 2n. I start with n-1 ups n rights and zero downs.Since there is no Up yet my bool B is false ( if there comes an up then down can not come after it,so to prevent this I put B=true which prevents it.) If an up comes, then there should be a corresponding down, and total should be incremented by one. If right comes then, total should be incremented by 2. My algorithm in general works like that but I couldn't get a correct result with this implementation.

Answer Source

The original solution didn't adapt to OP's needs, as it was too complicated to port to javascript and the intention was to show better practices solving these kind of problems more than actually solving easily this one in particular.

But in the spirit of using immutable types to solve path algorithms, we can still do so in a much simpler fashion: we'll use string.

Ok as always, lets build up our infrastructure: tools that will make our life easier:

private const char Up = 'U';
private const char Down = 'D';
private const char Horizontal = 'R';
private static readonly char[] upOrHorizontal = new[] { Up, Horizontal };
private static readonly char[] downOrHorizontal = new[] { Down, Horizontal };
private static readonly char[] all = new[] { Up, Horizontal, Down };

And a handy little helper method:

private static IList<char> GetAllPossibleDirectionsFrom(string path)
{
    if (path.Length == 0)
        return upOrHorizontal;

    switch (path.Last())
    {
        case Up: return upOrHorizontal;
        case Down: return downOrHorizontal;
        case Horizontal: return all;
        default:
            Debug.Assert(false);
            throw new NotSupportedException();
    }
}

Remember, break down your problems to smaller problems. All difficult problems can be solved solving smaller easier problems. This helper method is hard to get wrong; thats good, its hard to write a bug inside easy short methods.

And now, we solve the bigger problem. We'll not use iterator blocks so porting is easier. We'll concede here using a mutable list to keep track of all the valid paths we find.

Our recursive solution is the following:

private static void getPaths(IList<string> allPaths, 
                             string currentPath, 
                             int height,
                             int maxLength,
                             int maxHeight)
{
    if (currentPath.Length == maxLength)
    {
        if (height == 0)
        {
            allPaths.Add(currentPath);
        }
    }
    else
    {
        foreach (var d in GetAllPossibleDirectionsFrom(currentPath))
        {
            int newHeight;

            switch (d)
            {
                case Up:
                    newHeight = height + 1;
                    break;
                case Down:
                    newHeight = height - 1;
                    break;
                case Horizontal:
                    newHeight = height;
                    break;
                default:
                    Debug.Assert(false);
                    throw new NotSupportedException();
            }

            if (newHeight < 0 /*illegal path*/ ||
                newHeight > 
                    maxLength - (currentPath.Length + 1)) /*can not possibly
                                                            end with zero height*/
                    continue;

            getPaths(allPaths, 
                     currentPath + d.ToString(), 
                     newHeight, 
                     maxLength, 
                     maxHeight);
        }
    }
}

Not much to say, its pretty self explanatory. We could cut back some on the arguments; height is not strictly necessary, we could count ups and downs in the current path and figure out the height we are currently at, but that seems wasteful. maxLength could also, and probably should be removed, we have enough information with maxHeight.

Now we just need a method to kick this off:

public static IList<string> GetSchroderPathsWithoutPeaks(int n)
{
    var allPaths = new List<string>();
    getPaths(allPaths, "", 0, 2 * n, n);
    return allPaths;
}

And we're set! If we take this out for a test drive:

var paths = GetSchroderPathsWithoutPeaks(2);
Console.WriteLine(string.Join(Environment.NewLine, paths));

We get the expected results:

URRD
URDR
RURD
RRRR

As to why your solution doesn't work? Well, just the fact that you can't figure it out says it all about how unecessary complicated your current solution is starting to look. When that happens, its normally a good idea to take a step back, rethink your approach, write down a clear specification of what your program should be doing step by step and start over.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download