Gradient RegEx Fractal Index and length Error FIXED

[Boleeman]

Hi All.

I have converted a Gradient RegEx Fractal code from Java to CSharp in which you type in a RegEx string like 1*2*0 and it creates a fancy gradient pattern, saved to a png file. It used a nuget package called Fare which implements dk.briks.automation.

The Java version was originally here:
GitHub - SSODelta/GradientRegexImages: Creating pretty images from regular expressions using edit distance
and the Fare nuget for CSharp is here:

GitHub - moodmosaic/Fare: Port of Java dk.brics.automaton and xeger, mostly used for generating strings that match a specific regular expression.

Port of Java dk.brics.automaton and xeger, mostly used for generating strings that match a specific regular expression. - moodmosaic/Fare

github.com

The
Fare did not have implemented GetStrings, but in the Java version of dk briks automation it was there.

In Java version:

private static void getStrings(State s, Set<String> strings, StringBuilder path, int length) {
if (length == 0) {
if (s.accept)
strings.add(path.toString());
} else
for (Transition t : s.transitions)
for (int n = t.min; n <= t.max; n++) {
path.append((char)n);
getStrings(t.to, strings, path, length - 1);
path.deleteCharAt(path.length() - 1);
}
} 
 
and also 

public static Set<String> getStrings(Automaton a, int length) {
HashSet<String> strings = new HashSet<String>();
if (a.isSingleton && a.singleton.length() == length)
strings.add(a.singleton);
else if (length >= 0)
getStrings(a.initial, strings, new StringBuilder(), length);
return strings;

I tried to make a C# version of GetStrings that matches the Java code but I get the error message "Index and length must refer to a location within the string".
Googling suggested: The error occurs in C# when you are trying to perform an operation (like accessing or removing characters) on a string or StringBuilder and the provided index and/or length is out of bounds for the current string or string-like object, but I still cannot find where that error is (getting really frustrated). Any help or hints would be greatly appreciated. I would really like to get it working in CSharp. At present the program compiles to an exe and is run in the console with say a test RegEx string 1*2*0 but I get the error message "Index and length must refer to a location within the string".

public static HashSet<string> GetStrings(Automaton automaton, int length)
{
    HashSet<string> strings = new HashSet<string>();
    if (automaton.IsSingleton && automaton.Singleton.Length == length)
        strings.Add(automaton.Singleton);
    else if (length >= 0)
        GetStrings(automaton.Initial, strings, new StringBuilder(), length);
    return strings;
}

private static void GetStrings(State s, HashSet<string> strings, StringBuilder path, int length)
{
    if (length == 0)
    {
        if (s.Accept)
            strings.Add(path.ToString());
    }
    else
    {
        foreach (Transition t in s.Transitions)
        {
            for (int n = t.Min; n <= t.Max; n++)
            {
                path.Append((char)n);
                GetStrings(t.To, strings, path, length - 1);
                
                // Only remove the last character if the path is not empty
                if (path.Length > 0)
                    path.Remove(path.Length - 1, 1);
            }
        }
    }
}

The problem might be too hard to solve, but I thought I would ask for help.

 

[Skydiver]

This is what happens when you do Pokemon exception handling:

try
{
   :
}
catch (FormatException)
{
    :
}
catch (IOException)
{
    :
}
catch (Exception ex)    // <--- Pokemon exception handling
{
    :
}

You should only catch the exceptions that you are expecting to happen and know how to handle. Doing a catch-all exception handler just sets you up for future instability. Yes, your code might not have crashed, but do you know if all your objects are still in a good state?

Granted, you do have it at the top level because you wanted to crash gracefully, but beware that someone else may just copy and paste the code and not realize what is going on.

Anyway, if you set Visual Studio to stop for all CLR exceptions:

You'll see that it stops at:

public static Point RegexToPoint(string regex)
{

    //If it's the last letter, then we're at base case
    if (regex.Length == 1)
    {
        char c = regex[0];
        switch (c)
        {
            case '0':
                return new Point(0, 1);
            case '1':
                return new Point(0, 0);
            case '2':
                return new Point(1, 0);
            default:
                return new Point(1, 1);
        }
    }


    //Get the next location
    Point p = RegexToPoint(regex.Substring(regex.Length - 1, regex.Length));

    //Get what this point *would* have been
    Point q = RegexToPoint(regex.Substring(0, regex.Length - 1));
    Point k = new Point(q.X * 2 + p.X, q.Y * 2 + p.Y);
    return k;
}

You are asking for a substring of regex that is regex.Length characters long, but starting at the last character. Obviously, that would go beyond the string.

 

[Skydiver]

Not related to your problem, but you should only create a singleton Random object instance and use that one instead of doing something like:

private static int RandomColor()
{
    Random random = new Random();
    return random.Next(COLORS.Length);
}

The Random object in C# is initialized with the current time as the seed. The time resolution is typically much bigger than the speed of most code that runs in a tight loop. So you'll end up with essentially the same random values within a small timeframe.

 

[Skydiver]

Ah! I see. Looks like an error in porting the Java code to C#. In C#, the String.Substring() method takes a starting index and length. In Java, the string.substring() takes a starting index and an exclusive ending index.

 

[Boleeman]

Thank you Skydiver for helping out. I was totally looking in the wrong spot (thought the error was from private static void GetStrings(State s, HashSet<string> strings, StringBuilder path, int remainingLength).
You were correct: "Looks like an error in porting the Java code to C#. In C#, the String.Substring() method takes a starting index and length. In Java, the string.substring() takes a starting index and an exclusive ending index."

Thanks for the tip to set Visual Studio to stop for all CLR exceptions. I am still learning different aspects of the CSharp IDE (I am much more used to the Lazarus IDE but I wanted to get more into CSharp by making a few different programs but for this project I feel like it's gone over the top).

I now have in public static Point RegexToPoint(string regex)[:

Point p = RegexToPoint(regex.Substring(regex.Length - 1, 1));
Point q = RegexToPoint(regex.Substring(0, regex.Length - 1));

After fixing that I was getting a Null error, as there were no matches:

      private int GetDistance(string k)
        {
            if (matches == null || matches.Count == 0)
            {
                throw new InvalidOperationException("The 'matches' collection is null or empty.");
            }

            int dist = int.MaxValue;
            foreach (string s in matches)
            {
                int d = HammingDistance(s, k);
                if (d == 1)
                {
                    return 1;
                }

                if (d < dist)
                {
                    dist = d;
                }
            }

The last output from the console (Error: The 'matches' collection is null or empty.):

Processing states...
        Progress: |--------------------------------------------------------------------------------|
                  |
Processing state: Path='', RemainingLength=8
Starting from the empty path.
Processing state: Path='0', RemainingLength=7
Processing state: Path='00', RemainingLength=6
Processing state: Path='000', RemainingLength=5
Processing state: Path='0000', RemainingLength=4
Processing state: Path='00000', RemainingLength=3
Processing state: Path='000000', RemainingLength=2
Processing state: Path='0000000', RemainingLength=1
Processing state: Path='00000000', RemainingLength=0
Accepting state reached with string: 00000000
Error: The 'matches' collection is null or empty.

Now for trying to work out why there are no matches, as the 'matches' collection should be filled dynamically?
Perhaps I missed something in the Java to CSharp conversion or something acts differently in CSharp?

 

[Skydiver]

That's because you declared a local variable named matchesand initialized and used that instead of initializing and using your instance variable named matches.

I am away from my computer right now so I can't tell you which method that was where you declared the local variable.

After I fixed that, I think I started getting pretty pictures this morning.

 

[Skydiver]

It was in your method Generate(). Right under the Console.WriteLine("Computing language...");

 

[Boleeman]

Ah Skydiver that was it. I declared a local variable named matches and initialized and used that instead of initializing and using your instance variable named matches. I was too focused on fixing the earlier bug in the wrong area to realize that. Success at last.

What I did notice was that it took a lot longer to make the same fractal in CSharp than it did for Java.
Man, I so happy that you helped me out to fix the bugs in the CSharp version.
As I mentioned earlier I normally program in Lazarus, so I am stepping out on a limb trying to work things out in the CSharp environment (felt a bit like I went out from the city and wandered into some bushy country area).

Thanks Skydiver for your great help.

Lastly you mentioned:
that I should only create a singleton Random object instance and use that one instead of doing something like:

private static int RandomColor()
{
Random random = new Random();
return random.Next(COLORS.Length);
}

Can you sort of explain how to do that. In Lazarus I would put a Randomize in the startup of the program, but in CSharp I'm still not getting what you meant.

 

[Boleeman]

Another thing that I noticed was that some color combinations don't give a nice result. Got to work out a way to perhaps pick colors that complement each other in a much more pleasing way.

 

[JohnH]

Single instance for .Net framework means:

private static readonly Random random = new Random();

For .Net you can instead use Random.Shared anywhere:

return Random.Shared.Next(COLORS.Length);

Your project is .Net 6.0 and supports the latter.

 

[Skydiver]

What I did notice was that it took a lot longer to make the same fractal in CSharp than it did for Java.

Are you sure that it's not all the extra Console.WriteLines() that you inserted that is causing the slow down? Are you checking speed in Release mode, or Debug mode?

Here's my tests in Release mode of your version of the code with the extra console output removed. I was comparing it to my version of the code where I started doing some optimizations. 2.5 seconds for a depth of 10 shouldn't be considered slow. (With some optimizations, I got it down to 1.6 seconds.)

Spoiler

using System;
using System.IO;
using gradientregex;
using Fare;
using System.Diagnostics;

namespace gradientregex
{
    public class ProgramClass
    {
        static void TimeAction(string caption, Action action)
        {
            var stopwatch = new Stopwatch();
            Console.WriteLine(caption);
            stopwatch.Start();
            action();
            stopwatch.Stop();
            Console.WriteLine($"Elapsed time: {stopwatch.Elapsed}");
        }

        public static void Main(string[] args)
        {
            var pattern = ".?2*1.3";
            var depth = 10;
            TimeAction("Original", () => Fractal.GenerateAndSaveImage(pattern, $"{Rnd()}.png", depth));
            TimeAction("Minor optimizations", () => Fractal2.GenerateAndSaveImage(pattern, $"{Rnd()}.png", depth));
        }

        static Random s_random = new();
        private static int Rnd()
        {
            return s_random.Next(0, int.MaxValue);
        }
    }
}

[/code]

 

[Boleeman]

Yes, I did forget to remove all those the extra Console.WriteLines(). I put them in for debugging purposes to see if the states and matches were working.

"I started doing some optimizations. 2.5 seconds for a depth of 10 shouldn't be considered slow. (With some optimizations, I got it down to 1.6 seconds.)". Impressive for a 1024 pixel sized png.

Also thanks JohnH for clarifying Single instance randomizing.

​

 

[Skydiver]

Interesting to read this from the original author of the Java implementation:

This algorithm is very, very slow though. I’ve not been able to generate any larger than 512×512 images on my laptop (my patience lasts about 1 hour), and I fear a 1024×1024 is impossible due to the time complexity of the algorithm.

But in the GitHub link he did commit a speed improvement. I think the code you presented above is based on that speed improvement.