10
\$\begingroup\$

There was an interesting idea brought up in The 2nd Monitor where one of our regulars was trying to split a bunch of strings into a specific format.

The format should be similar to the following:

A000
A00
900
90

Where A is any alphabetical letter, 0 is any number, and 9 is any number 1-9. No result string should begin with 0, it should always begin with A-Z or 1-9, and all alphabet characters will always be capitalized.

The input comes in a format similar to any of the following:

Input         | Result
900A000       | 900, A000
900900        | 900, 900
90            | 90
99099         | 990, 99
A009A09       | A009, A09
A009A09900    | A009, A09, 900
A0990A09900   | A09, 90, A09, 900
A099090A09900 | A09, 90, 90, A09, 900
A09A990       | A09, A990
A990          | A990

The input will always parse to a valid group of strings.

The method:

public List<string> SpecialSplit(string input)
{
    var result = new List<string>();

    var currentString = new StringBuilder(4);
    for (var i = 0; i < input.Length; i++)
    {
        var c = input[i];

        if (currentString.Length > 0)
        {
            // Determine whether we're at constraints or not.
            var firstCharLetter = currentString[0] >= 'A' && currentString[0] <= 'Z';
            var atMaxLetterLength = firstCharLetter && currentString.Length == 4;
            var atMaxNumberLength = !firstCharLetter && currentString.Length == 3;

            // Split if at max letter/number length, or if we're on a letter.
            var mustSplit = atMaxLetterLength || atMaxNumberLength || c >= 'A' && c <= 'Z';

            if (mustSplit)
            {
                // If we must split our string, then verify we're not leaving an orphaned '0'.
                if (c == '0')
                {
                    // Go back a letter, take it out of the new string, and set our `c` to it.
                    i--;
                    currentString.Length--;
                    c = input[i];
                }

                // Add and clear the string to our result.
                result.Add(currentString.ToString());
                currentString.Clear();
            }
        }

        // Add our `c` to the string.
        currentString.Append(c);
    }

    // Add our string to the result.
    result.Add(currentString.ToString());

    return result;
}

And the test code:

var tests = new string[] {
    "909A999",
    "909999",
    "90",
    "99099",
    "A009A09",
    "A009A09900",
    "A0990A09900",
    "A099090A09900",
    "A09A990",
    "A990"
};

var resultStrings = new List<string>();

foreach (var test in tests)
{
    var split = SpecialSplit(test);
    Console.WriteLine(test + ": {" + string.Join(", ", split) + "}");
    resultStrings.AddRange(split);
}

if (resultStrings.Any(x => x[0] == '0'))
    Console.WriteLine("Test failed");
else
    Console.WriteLine("Test passed");
\$\endgroup\$
  • \$\begingroup\$ No result string should begin with 0, it should always begin with A-Z or 1-9 this does not seem to work for A0990A091900 which splits into A09, 90, A091, 900. Shouldn't the result be A0, 9, 90, A0, 9, 1, 900? \$\endgroup\$ – t3chb0t Mar 20 '17 at 18:51
  • 1
    \$\begingroup\$ @t3chb0t No, because the string should be as long as possible, up to 3 numbers with an optional letter. \$\endgroup\$ – 410_Gone Mar 20 '17 at 18:52
  • \$\begingroup\$ oops, the title say this ;-] tl;dr :-P sorry \$\endgroup\$ – t3chb0t Mar 20 '17 at 18:53
  • 2
    \$\begingroup\$ @Anyone tempted to solve this with a regex: this all started with ([A-Z]?\d{2,3})+ failing to do the job =) \$\endgroup\$ – Mathieu Guindon Mar 20 '17 at 18:54
4
\$\begingroup\$

Using a StringBuilder isn't necessary if we know that the resulting string isn't exceeding 4 chars. I would go with a char[] instead which will be a magnitude faster if performance is a concern (which mostly is).

The following loc's are executed each iteration which is a waste of time as well.

var firstCharLetter = currentString[0] >= 'A' && currentString[0] <= 'Z';
var atMaxLetterLength = firstCharLetter && currentString.Length == 4;
var atMaxNumberLength = !firstCharLetter && currentString.Length == 3;

// Split if at max letter/number length, or if we're on a letter.
var mustSplit = atMaxLetterLength || atMaxNumberLength || c >= 'A' && c <= 'Z';  

I would prefer a style which is more natural to read like using char.IsLetter() like t3chbot has mentioned in his answer.


A name like firstCharLetter isn't telling enough about what it is because its incomplete. firstCharIsLetter would be better imo.


The if condition

if (currentString.Length > 0)  

is only helpful/needed for the very first iteration and could be removed if the loop would start at 1 like so

currentString.Append(input[0]);
for (var i = 1; i < input.Length; i++)
    {

Parameter validation is missing for this public method but you wouldn't do that in production code like I know. Because of that I omitted the validation as well.

My take on this is a little bit longer but a little bit faster as well

public List<string> Split(string input)
{
    var results = new List<string>();
    char[] result = new char[4];
    int j = 0;
    bool hasLetter = false;

    for (int i = 0; i < input.Length - 1; i++)
    {

        char c = input[i];

        if (char.IsLetter(c))
        {
            if (j > 0)
            {
                results.Add(new string(result));
                result = new char[4];
                j = 0;
            }
            result[j++] = c;
            hasLetter = true;
            continue;
        }

        bool nextIsZero = (input[i + 1] == '0');

        if (!hasLetter)
        {

            if (!nextIsZero)
            {
                result[j++] = c;
            }
            if (j == 3)
            {
                results.Add(new string(result));
                result = new char[4];
                j = 0;
            }
            if (nextIsZero)
            {
                result[j++] = c;
            }
            continue;

        }

        if (nextIsZero && j == 3)
        {
            results.Add(new string(result));
            result = new char[4];
            j = 0;
            hasLetter = false;
        }
        result[j++] = c;

    }
    result[j++] = input[input.Length - 1];

    results.Add(new string(result));
    return results;
}
\$\endgroup\$
4
\$\begingroup\$

I like your algorithm because I think it does the splitting exacly the way it should be done.

What I like less are the comments. I find they are unnecessary if the logic is encapsulated appropriately but one explaining the 0 and why the backtracking takes place.

As the string is always capitalized I think it's ok to use char.IsLetter rather then the range A-Z.

With a little bit of C# 7 and its new local funcitons and the new switch it could look like this:

public IEnumerable<string> SpecialSplit(string value)
{
    var result = new StringBuilder();
    for (int i = 0; i < value.Length; i++)
    {
        if (CanSplit())
        {
            Backtrack();
            yield return result.ToString();
            result.Clear();
        }
        result.Append(Current());

        char Current() => value[i];
        bool CanSplit() => result.Length > 0 && (result.Length == MaxLength() || char.IsLetter(Current()));

        void Backtrack()
        {
            // If we must split our string, then verify we're not leaving an orphaned '0'.
            if (Current() == '0')
            {
                i--;
                result.Length--;
            }
        }
    }

    if (result.Length > 0) yield return result.ToString();  

    int MaxLength()
    {
        switch (result[0])
        {
            case char c when char.IsLetter(c): return 4;
            case char c when char.IsDigit(c): return 3;
            default: throw new ArgumentOutOfRangeException($"Invalid char {result[0]}");
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Btw, this is a nice trick result.Length--; :-) \$\endgroup\$ – t3chb0t Mar 21 '17 at 18:01
  • \$\begingroup\$ Hohoho, a DV. Reason? \$\endgroup\$ – t3chb0t Mar 22 '17 at 15:40
  • \$\begingroup\$ Don't understand the DV either. \$\endgroup\$ – Heslacher Mar 22 '17 at 15:44
  • \$\begingroup\$ Unintentional DV. Just saw it now myself and wondering how it happened! Mis-click? If you can edit the answer I will undo - can't now because it happened over 2 hours ago. Really sorry about this \$\endgroup\$ – AlanT Mar 22 '17 at 17:40
  • \$\begingroup\$ @AlanT edited. You're the first person I've ever met that explained a DV ;-) \$\endgroup\$ – t3chb0t Mar 22 '17 at 17:49
4
\$\begingroup\$

right ... "tempted to solve this with a regex" doesn't quite cut it. There is a regex that kinda sorta somewhat works, but I didn't get it to do exactly what I want.
Doesn't matter though, because I can make it do what I wanted, namely spit out the results directly as separate groups. Instead I got it to match the "last result" an:

private readonly Regex someNiceName = new Regex(@"^((?:[A-Z]\d|[1-9])\d{1,2})+$", RegexOptions.Compiled);

public List<string> SpecialSplit(string input)
{
    if (input == "") 
    {
       return new List<string>(); // base case for recursion
    }
    var match = someNiceName.Match(input);
    string last = match.Groups[1].Value;
    var precedessors = SpecialSplit(input.Substring(0, match.Groups[1].Index));
    precedessors.Add(last);
    return precedessors;
}

With a bit of luck we don't actually need this mess, but can rely on Captures instead:

public List<string> SpecialSplit(string input) 
{
    var match = someNiceName.Match(input);
    var fullMatch = match.Groups[0];
    return fullMatch.Captures().Select(c => c.Value).ToList();
}

unfortunately I do not have C# available to check right now, but that might work better :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.