c# Bruteforce starting from a specified point

Question

I need to find a way to start this string generating algorithm at a specified string instead of the beginning. For example not starting at 'aaaa' but 'baxi' and go through the rest of the string space.

    private static String Charset = "abcdefghijklmnopqrstuvwxyz";

    /// <summary>
    /// Start Brute Force.
    /// </summary>
    /// <param name="length">Words length.</param>
    public static void StartBruteForce(int length)
    {
        StringBuilder sb = new StringBuilder(length);
        char currentChar = Charset[0];

        for (int i = 1; i <= length; i++)
        {
            sb.Append(currentChar);
        }

        int counter = 0;
        ChangeCharacters(0, sb, length, ref counter);
        Console.WriteLine(counter);
    }

    private static void ChangeCharacters(int pos, StringBuilder sb, int length, ref int counter)
    {
        for (int i = 0; i <= Charset.Length - 1; i++)
        {                
            sb[pos] = Charset[i];
            if (pos == length - 1)
            {
                counter++;
                Console.WriteLine(sb.ToString());
            }
            else
            {
                ChangeCharacters(pos + 1, sb, length, ref counter);
            }
        }
    }

Answer 1

What you have is pretty close, but it looks like the root of your problem is that ChangeCharacters is written to always start at the first possible string, e.g. the characters at each position always start at the first letter of your alphabet ('a' in your example). You need the first pass at each position in your starting string to start with the letter that's already in place, and subsequent passes would then start with the first character of your generating alphabet.

Thus, with the code that you already have, you need to do make the following changes:

1. Pass along a flag indicating this is the first pass.
2. Select your loop's starting point based on the first pass flag.
3. Pass that first pass flag down your recursive calls.
4. Reset the flag after the first pass at each position.
5. Initialize the StringBuilder with your starting string, rather than the current default starting point.

There are some other items worth changing for clarity's sake. None of these are strictly required for correctness, but they do make the code easier to read and understand:

1. There's no need to pass around length, as it's always the same as sb.Length. Duplicated information at best forces readers to keep track of more information, and at worst can lead to bugs if later code changes break the relationship.

2. The standard idiom for index loops in languages that use zero-based indexing is "endpoint-exclusive" form, using a 'less-than' (or even 'not-equal') comparator, as this avoids overflow errors at the boundaries, e.g. i < length instead of i <= length - 1. Most code readers understand this idiom instinctively, whereas endpoint-inclusive forms typically force a reader to consider why the anti-idiom is required.

3. Rather than passing around your counter by reference, simply return the count of strings generated. Methods that don't mutate external state, often referred to as "pure" or "functional", are generally easier to understand. (Note, however, that you also have state in the StringBuilder being passed around.)

   • As a further refinement, I'd even suggest returning an IEnumerable<string>, which not only removes the need for tracking a count, but it also lets the caller determine what to do with the string, rather than making that decision (e.g. calling Console.WriteLine and incrementing a counter) insider your method.

Taking all of that together, your code becomes this (annotated with comments pointing to which change or suggestion is in play):

public static void StartBruteForce(string start)
{
   /*change 5*/ StringBuilder sb = new StringBuilder(start);
   /*sugg 3*/ int counter = ChangeCharacters(0, /*change 1*/ true, sb);
   Console.WriteLine(counter);
}

private static int ChangeCharacters(int pos, /*change 1*/ bool firstPass , StringBuilder sb)
{
    /*sugg 3*/ int counter = 0;
    for (int i = /*change 2*/ firstPass ? Charset.IndexOf(sb[pos]) : 0; /*sugg 2*/ i < Charset.Length; i++)
    {                
        sb[pos] = Charset[i];
        if (pos == /*sugg 1*/ sb.Length - 1)
        {
            counter++;
            Console.WriteLine(sb.ToString());
        }
        else
        {
            /*sugg 3*/ counter += ChangeCharacters(pos + 1, /*change 3*/ firstPass, sb);
            /*change 4*/ firstPass = false;
        }
    }
    /*sugg 3*/ return counter;
}

Answer 2

Your recursive algorithm needs to be broken into steps so it can be resumed.

See this factorial algorithm broken into steps so it can be resumed.

---

Alternatively, you need to know the resume point [which you will need in any case] but ignore all values prior to hitting that point.

This is a (worse-than) naive implementation, and CPU-wise it invalidates the whole idea of resuming the computation -- since it doesn't actually resume, it just doesn't capture/print the earlier values:

private static String Charset = "abcdefghijklmnopqrstuvwxyz";

/// <summary>
/// Start Brute Force.
/// </summary>
/// <param name="length">Words length.</param>
public static void StartBruteForce(int length)
{
    StringBuilder sb = new StringBuilder(length);
    char currentChar = Charset[0];

    for (int i = 1; i <= length; i++)
    {
        sb.Append(currentChar);
    }

    int counter = 0;

    var resumePoint = 60975;

    ChangeCharacters(0, sb, length, ref counter, resumePoint);

    Console.WriteLine(counter);
}

private static void ChangeCharacters(int pos, StringBuilder sb, int length, ref int counter, int resumePoint)
{
    for (int i = 0; i <= Charset.Length - 1; i++)
    {
        sb[pos] = Charset[i];
        if (pos == length - 1)
        {
            counter++;
            if (counter >= resumePoint)
            {
                Console.WriteLine(string.Format("{0} : {1}", counter, sb.ToString()));
            }
        }
        else
        {
            ChangeCharacters(pos + 1, sb, length, ref counter, resumePoint);
        }
    }
}