# Gradient Images from Regular Expressions

The source code for this project can be found at its GitHub-page: https://github.com/SSODelta/GradientRegexImages

## Gradient Images from Regular Expressions

In one of my posts from last year, I detailed an algorithm for creating pretty fractal images based on regular expressions. While this idea wasn’t novel, it was still very interesting, and it was a challenge for me to code it. However, the other day I got a great idea – I had figured out a way to generalize this concept to (I presumed) create even more pretty images.

The problem with the old method was that it was binary whether or not a given pixel belonged to the regular language. This makes excellent sense from a computer science theoretical perspective, but when making pretty images it’s nice to have some variation. So instead of the binary approach, I’m going to allow pixels to have a certain distance to being a member of the regular language. We define that d=0 means that a pixel belongs to the regular language, and d=1 means that it has an edit distance of 1 to belonging to the language. We only use substitution as a transformation in this example, however, because we want all strings to have the same length

As an example, let’s consider the regular language 3*, and consider of strings of length 2. Obviously, the only string of length 2 that belongs to this language (and thus has d=0) is “33”. The strings of distance d=1 are the strings that can result in “33” after only 1 substitution. An example of this is the string “32”, which after changing the 2 to a 3 suddenly belongs to the regular expression. Likewise, an example of a string with d=2 is “11”, where both characters need to be changed for it to belong to the language.

## Determining the Distance of Every String

Like in the old post, we need to generate all strings of length n, check if they belong to the language, and then paint the image based on this information. In the old post, however, it was pretty straight forward checking if the strings belonged to the language or not. But in this approach, we’re faced with a far more complicated problem – how do we determine the edit distance of any one string?

To do so, we first generate all strings of length and then we check which of these strings belong to the language (we first find all d=0 strings) and remember them in a HashMap. Then we generate all variations of these strings. Obviously, any string which is a variation of a d=0 string must be at most a d=1 – so, using this set of variations we mark all the strings not previously marked with d=0 with d=1. We continue doing so until we’ve exhausted the list of strings (which must happen eventually, as any two strings of length are at most edits apart).

At each step, we remove all strings for which we’ve already determined its edit distance as keeping it would only generate copies. Also, we stop after d=n-1 and mark the remaining strings as d=n (again, because the maximum edit distance is n).

### Coloring the Pixels

After finding the edit distance of every string, we have an integer $d \in [0; n]$. We map this unto the interval $[0; 1]$ by dividing each edit distance with n. Next up, we associate some color 0xRRGGBB with 0, and another color 0xRRGGBB with 1 and give each pixel a color in this gradient.

### Performance

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. I’m sure there are many ways to improve the algorithm’s performance (dynamic programming, probably), but I’ve yet to find them. But if you find an improvement (or a mistake), feel free to leave a comment.

## Gallery

Here is a list of all images I’ve yet to render on my machine. It’s very difficult to generate massive amounts of images due to the complexity of the algorithm (as opposed to my post on Newton’s Fractals, where I have a gallery of 100+ images)

## 7 thoughts on “Gradient Images from Regular Expressions”

1. nya says:

I wrote some time ago a png generator based on the past example, so I tried to change it to match this..
I’ve not spent time optimizing it (or even document it), but i get results in ~5s for a 1024×1024 canvas (well, the time depends much on the regex complexity)

I don’t know what gradient you used but the results i get look similar;
also i don’t know if the code it’s correct or readable enough to help speed up your program, but you can find it here
https://github.com/ltlollo/misc/blob/master/distrx.cpp

1. That is super nice! Can I see some of your pictures?

Also, I can’t decipher your code – which algorithm are you using?

1. nya says:

well first i populate a matrix(2^n, 2^n) with the with the quadrant indices ([2, 1, 3, 4] but you could choose [1, 2, 3, 4]) then recursively populate each subquadrant. the matrix it’s just a flat array because c++ doesn’t (yet) have an array view.
then i filter the matrix with the regex getting the elements with d=0 (let’s put them in a vector and call this vector v0)

and lastly for each element of the matrix i search in v0 the element with the minimun distance and store it in a new matrix with the same shape of the original ( and then you normalize by the “string size” which is the recursion depth, create the pixels form the gradient and the normalized distance, etc… but it’s essentially the same matrix with the same shape actually)

I guess the main thing to keep in mind is not to alter the shape of the original matrix.
I hope this is clear.

the seeds i managed to save are
[“1(121|212|313)?(333|444)*”
,”1+(.[123].)?(444)*”
,”[23][12][24]+”
,”[12]*[23]*[24]*”]

2. Though I haven’t thought about it in detail, at a glance the problem of computing the distances of strings sounds like a dynamic programming problem. I wrote a blog post a while ago using dynamic programming to compute edit distance, and it sounds like you could adapt it to your setting. That is, if you want to compute the edit distance between two fixed strings, it should not take more than n^2 time (and you definitely shouldn’t have to generate all strings to do it).

http://jeremykun.com/2011/12/19/metrics-on-words/

1. The problem as far as I see it is that we don’t have any two fixed strings – we have to check the edit distance to *any* of the strings in the regular language, which suddenly becomes n^2*m worst case (for m strings in the regular language).

But I’ll definitely check out your post and see if I can use it 🙂 it’d be nice to be able to generate desktop backgrounds like @nya apparently can.

1. Aren’t you fixed to strings of a given length though? So if you can efficiently generate all strings of length n in the language, then you can use the same technique to compute the distances of any string from the set.

2. You’re right it will be slower by a factor of |L| for the language L, though.