Getting a chain of letters from a string based on a specific letter

Question

I have a string containing a Polish notation that represents a floor-plan (VLSI placement), and it contains something like: "1234VHV56HV". (FYI, this means: Separate 3 & 4 vertically then separate the result & 2 horizontally then separate the result & 1 vertically, separate 5 & 6 horizontally, then separate the previous two results vertically.)

Assume the string variable is called: polishNotation. The letters contained are ONLY 'V' for vertical or 'H' for horizontal.

I am trying to apply an algorithm called: "Simulated Annealing" to change the Polish notation, so I want to randomly select an index (which is of course less than the polishNotation.Length) and if this index points to a letter ('V' or 'H'), I want to get the chain of letters including it and then change every 'V' to 'H' and change every 'H' to 'V'... In other words: complement the chain!

• For example: Assume polishNotation = "1234VHV56HV" and the random index = 5, so the result is "H"... I want to retrieve "VHV" and complement it to become: "1234HVH56HV".
• Another example: Assume polishNotation = "1234VHV56HV" and the random index = 9, so the result is "H"... I want to retrieve "HV" and complement it to become: "1234VHV56VH".
• Another example: Assume polishNotation = "1234VHV56HV" and the random index = 6, so the result is "V"... I want to retrieve "VHV" and complement it to become: "1234HVH56HV".

I hope I got myself clear... Any suggestions? I am using C#.net

Answer 1

You could try something like this. I bet there's a way to do this with regular expressions, but I don't know off the top of my head.

    string Complement(string floorPlan)
    {
        int index = rand.Next(floorPlan.Length); //get a random integer within array bounds

        if (floorPlan[index] != 'H' || floorPlan[index] != 'V') // if we didn't grab a letter, return
            return floorPlan;

        int start = index; //we'll need to find the start of the 'letter group'

        for (int i = index; i >= 0; i--) // work backwards through the string
            if (floorPlan[i] == 'H' || floorPlan[i] == 'V') // updating if we find another letter
                start = i;
            else // break when we don't
                break;            

        StringBuilder sb = new StringBuilder(floorPlan); // use a string builder for ease of char replacement

        for (int i = start; i < floorPlan.Length; i++) // using the start index, interate through
            if (floorPlan[i] == 'V') // and replace accordingly
                sb[i] = 'H';
            else if (floorPlan[i] == 'H')
                sb[i] = 'V';
            else // breaking when we encounter a number
                break;

        return sb.ToString();
    }