SIGUSR2▉ home apg(7) colophon feed

% Regex Fractals % code, fractals % 2014-10-09

I recently discovered the Daily Programmer sub-reddit, which posts coding challenges 3 times a week (one small, one medium, one hard). It’s been going on for quite a while now, and looking back through the archives I bit, I stumbled upon something that really caught my eye–generating fractals with regex.

Now, I used to write Perl, so I know my way around regular expressions, but I hadn’t ever considered them as a way to generate art. Well, OK. Writing regular expressions is an artform in and of itself, I suppose, but it’s all text based, not graphical. The description of the challenge pointed me to this imgur gallery, which explained what was happening.

There are 4 quadrants in the Cartesian coordinate system. The top right is quadrant 1, top left is quadrant 2, bottom left–3, bottom right–4. It makes a “C” for Cartesian¹. Pixels can be described by subdivisions of those quadrants, by a string containing the characters {'1', '2', '3', '4'}. So, the string “11” describes the very top right pixel of a 4 by 4 pixel image (the imgur makes this pretty clear I think).

Now, if you loop through all of the strings that describe those pixels and color only those that match a given regular expression such as .*1.* a fractal will be the result. My mind was pretty much blown at this point, and I just had to implement it. There is a somewhat obvious recursive solution to it, and indeed many people choose to take that route, but I wanted to do something different. I wanted to do it without recursion , and in as few lines as possible.

For some reason I chose Python². Python and me go way back, but I tend to not utilize it as much as I once did. That said, I knew I could do the bulk of the work in 2 steps, and complete it in 4:

1. Generate all pixel “coordinates”, e.g. the strings representing each pixel
2. Filter the stream of “coordinates” via the regex
3. Translate the “coordinates” into actual Cartesian coordinates
4. Put the pixel on a canvas.

But, how do you turn the string coordinates into a Cartesian, x, y pair? That stumped me for a bit, but after sleeping on it, I came up with:

def str2pt(s):
    L = len(s) - 1
    x, y = 1, 1
    for n in s:
        y += 2**L if n in '34' else 0
        x += 2**L if n in '14' else 0
        L -= 1
    return x-1, y-1

Start at 1, and add 2^L (where L is a recursion level³ to the Y coordinate if in the negative Y coordinates, and add 2^L to X if the current coordinate is in the positive X range.

Tie in the following:

def generate(n):
    return map(lambda x: ''.join(x), itertools.product('1234', repeat=n))

def fractal(r, n):
    return map(str2pt, (c for c in generate(n) if re.match(r, c)))

and we have a solution. Of course, drawing it is just a matter of looping over the coordinates given to us by fractal and putting them on a canvas.

On a 1024 by 1024 canvas with the regex .*1.* a beautiful, though admittedly skewed, Serpeinski’s Triangle is seen.

The code is here, along with the output from the regex above