6
\$\begingroup\$

I am given a string containing the possible characters of : 0, 1, and ?, iterating over possibilities, replacing the wildcard ? with either 0 or 1.

For example; given "1?00?101", the outcome would be: ["10000101", "10001101", "11000101", "11001101"].

My code seems to work, I tested with two wildcards and three wildcards, but is there a better way to solve this.

class MainClass
    {
        static void BinaryString(char [] word, int a, int b, int count){
            if (count == 0) {
                Console.WriteLine (word);
            } else {
                for (int i = a; i < b; i++) {
                    if (word [i].Equals ('?')) {
                        word [i] = '0';
                        count--;
                        BinaryString (word, i, word.Length - 1, count);
                        word [i] = '1';
                        BinaryString (word, i, word.Length - 1, count);
                        word [i] = '?';
                        count++;
                    }
                }
            }
        }
        public static void Main (string[] args)
        {
            string binary = "1?00?1?1";
            char[] bi = binary.ToCharArray ();
            int count = 0;
            for (int i = 0; i < bi.Length; i++) {
                if (bi [i].Equals ('?')) {
                    count++;
                }
            }
            BinaryString (bi, 0, bi.Length - 1, count);
        }
    }
\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

Naming

a and b don't really convey anything. You should use descriptive names like startIndex and endIndex. Method names should be verbs.

Spacing

You should have consistent spacing. You have char[] in one place and char [] in another. You also have no space before an opening brace and have a space before the other opening braces.

Safety and Readability

You should favor safety and readability over performance. Premature optimization is not a good thing. If, after writing safe and readable code, you're having performance issues, use a profiler to find the bottleneck and optimize that. You're passing in a bunch of parameters to your BinaryString method and mutating a char array to make sure you don't search through the char array more than necessary, but this is hard to read and can easily lead to bugs. I believe you have a bug where if the last character is a wildcard nothing will get printed out. I suggest working with a string instead of a char array and using a helper method that returns a new string with the first wildcard replaced (some good implementations here). This uses more memory and might take longer, but you can always optimize it later if it turns out to be a bottleneck.

Single Responsibility Principle

The BinaryString method should return a list of strings. Then you can iterate through that list and print each one out.

Here is the updated code:

class MainClass
{
    private static IEnumerable<string> GetVariations(string word)
    {
        if(!word.Any(c => c.Equals('?')))
        {
            return new[] { word };
        } 
        else
        {
            string newWord1 = ReplaceFirstMatch(word, "?", "0");
            string newWord2 = ReplaceFirstMatch(word, "?", "1");
            return GetVariations(newWord1).Concat(GetVariations(newWord2));                
        }
    }

    private static string ReplaceFirstMatch(string theString, string oldValue, string newValue)
    {
        int loc = theString.IndexOf(oldValue);
        if(loc < 0)
        {
            return theString;
        }
        return theString.Remove(loc, oldValue.Length).Insert(loc, newValue);
    }

    public static void Main (string[] args)
    {
        string binary = "1?00?1?1";            
        foreach(string variation in GetVariations(binary))
        {
            Console.WriteLine(variation);
        }
    }
}
\$\endgroup\$
7
  • \$\begingroup\$ You need a var or string in front of newWord1 and newWord2 \$\endgroup\$
    – RobH
    Jul 27, 2015 at 11:44
  • \$\begingroup\$ Nicely done. I think I'd have GetVariations yield the results as they come in. No need to Concat them then. \$\endgroup\$ Jul 27, 2015 at 12:02
  • \$\begingroup\$ @RobH: Good catch! Fixed. \$\endgroup\$ Jul 27, 2015 at 12:18
  • \$\begingroup\$ @Mat'sMug: Because Concat is lazy, wouldn't it be essentially the same as yielding the results as they come in? There's also the tradeoff of having to write two foreach loops. \$\endgroup\$ Jul 27, 2015 at 12:33
  • \$\begingroup\$ Would probably be the same indeed. I just can't help thinking yield whenever I see IEnumerable<T> as a return type ;-) \$\endgroup\$ Jul 27, 2015 at 12:39
7
\$\begingroup\$

Let's get the obvious out of the way first.

Style.

The first thing that hits me is the indentation being offset here:

class MainClass
    {

Should be:

class MainClass
{

The next thing that hits me (in the same millisecond, really), is the inconsistent braces. You have them next-line-style at class level, and anything under class scope has them same-line-style. It's.... annoying to read. C# typically uses next-line braces:

if (count == 0) 
{
    Console.WriteLine (word);
} 
else 
{
    ...
}

Also, it seems like you're fighting your IDE here:

char[] bi = binary.ToCharArray ();

And here:

if (bi [i].Equals ('?'))

These spaces feel very awkward. C# reads better like this:

char[] bi = binary.ToCharArray();
if (bi[i].Equals('?'))

The last thing, and perhaps the most important one, is about method ordering: code should read like a book, and unveil like a story. Just like you wouldn't start reading a story at the end, a class' code shouldn't start with its implementation details - I expect void Main to be the first thing: that's where everything starts, after all.


Abstractions & Responsibilities.

Programming is about making abstractions - the abstraction level of Main is too low, it's not clear what that loop is there for and what's being counted: count isn't exactly the most meaningful name to use here. You're counting question marks, and question marks are a thing in the context of this app. Why isn't there a concept of wildcard anywhere?

private static readonly char Wildcard = '?';

You have a loop in Main, that's counting the wildcards. You could extract a method to better express that intent, but it's probably simpler to inline a bit of LINQ there - note that ToCharArray() is completely useless, since a string can already be iterated as an IEnumerable<char> in C#:

var wildcardCount = binary.Count(c => c.Equals(Wildcard));

Notice how much easier it is to figure out exactly what's going on - and why.

Now, looking at the BinaryString method (bad name, methods should start with a verb, they're actions), I'm questioning why you would need to pass in the wildcardCount as a parameter, when all it's used for is really to exit the looping/recursion logic - you already have that information in the character array itself:

if (!word.Any(c => c.Equals(Wildcard)))
{
    Console.WriteLine(word);
}

Ah.. and now I see why ToCharArray was used - the method returning void, your entire logic depends on the ability to mutate array elements! That smells funky, because parameters are passed by value. A much more idiomatic way, in my opinion, would be to take a string input, and return a new string after processing.

That would make it easier to leave the console output out of the function's logic, too - I don't like that the function is responsible for producing/computing the string (/mutating the character array) and producing the output. It just feels wrong, clearly it breaks the Single Responsibility Principle.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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