Iterated Function Systems

An Iterated Function System (IFS) is a method of constructing self-similar fractals. Each fractal is defined recursively as the union of several copies of itself, with each copy obtained by applying a transformation function to the whole. The functions are usually affine transformations of the form x↦Mx+b: i.e. a linear transformation such as a rotation, scaling or reflection, followed by a translation. Given a set of transformations, the fractal can then be obtained iteratively as follows: begin with a point (for example the origin) and repeatedly apply a randomly-selected transformation from the set. The sequence of points generated, which converges to the fixed point of the IFS, is then plotted.

The most famous example of an IFS is the Barnsley Fern. This is produced from four affine transformations, shown in the diagram below (taken from Wikipedia).

enter image description here

The affine transformations used in this questions involve only uniform scaling, rotation by a multiple of 90°, and translation. They can be implemented as follows, where n is the scale factor, θ is the rotation angle in radians and b is the translation in 'plot units' (e.g. pixels):

enter image description here

Seven-segment displays

A seven-segment display (SSD) is a cheap and simple electronic display device often used in clocks, meters and calculators to display decimal numerals. Though it wasn't designed to display letters, it is sometimes used to do so. The resulting alphabet is often ambiguous and sometimes unintuitive, but is sufficient for certain status messages (e.g. "nO dISC" or "gOOdbYE"). Below is one way to represent the 26 letters and 10 numerals on a seven-segment display.

enter image description here

Task

The aim of this challenge is to produce word fractals using IFSs and the SSD alphabet above.

  • The input is a string of multiple alphanumeric characters. The string may contain both upper and lower case letters, though the SSD alphabet is case insensitive. The program need not support punctuation or whitespace characters.
  • The output should be an IFS plot representing the string as rendered in the SSD alphabet above. Each lit segment in each character should correspond to an additional affine transformation mapping the bounding box of the rendered word to that of the segment. Horizontal segments should remain facing upwards, while vertical segments should face 'outwards' (i.e. left-side up on the left, right-side up on the right). The precise alignment/overlap of segments is left up to the solver, as long as the output is legible. For an example output showing one possible alignment, see below.
  • There should be a constant non-empty gap between the letters, to make the output legible.
  • The plot should contain enough points to be legible.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. The output should be drawn either to screen or to a file in any standard graphic format. As part of the answer you should include a screenshot of your output for the word "COdEgOLF". Standard code golf restrictions apply.

Example

enter image description here

Scoring

Shortest code (in bytes) wins. Standard rules apply.

Miscellania

For a good mathematical introduction to IFSs (including fractal compression) see these PDF lecture notes.

For a similar challenge concerning self-similar text see Words within words within words within words . . ..

  • Sigh, this could have been an ascii-art instead... – Optimizer Apr 22 '15 at 10:34
  • @Optimizer: You mean like the linked challenge at the end? ASCII art works well with rewriting systems (like L-system) but I can't see how you would make it work for IFSs? – Uri Zarfaty Apr 22 '15 at 12:34
  • It looks like the majority of the code is needed for encoding the alphabet, so i expect it to turn into a competition of who can write a shorter version of exec(base64decode("VeryLongStringOfGibberish")). How about letting us declare a minimal representation with 7 bit per character (for example letters=[[1,1,1,1,1,1,0], [0,1,0,1,1,1,1],[1,1,0,1,1,0,1], ...[1,1,1,1,0,1,1]]) for "free"? that would result in more logic and less compression. – DenDenDo Apr 22 '15 at 13:20
  • @DenDenDo Do you think so? I assumed that most people would go for 1 byte per letter plus some decoding logic, and that it would end up being about half compression half logic. I even thought it might be too 'boring' if the alphabet is passed in as a parameter. Is that not what you're finding? – Uri Zarfaty Apr 22 '15 at 13:29
  • If that was your intention from the beginning, then its fine of course. Its just my personal preference to have challenges focus on one aspect. – DenDenDo Apr 22 '15 at 13:45
up vote 2 down vote accepted

Python (518)

from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',[map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))
def T(A,C):y,x=A.shape;M=zeros((2*x-1,x+y));p=A[::-1].T;q=A.T[::-1];M[:y,:x]=C[0]*A;M[:x,:y]=C[1]*p;M[:x,-2*y:-y]=C[2]*q;M[x-1:x-1+y,:x]=C[3]*A;M[x-1:,:y]=C[4]*p;M[x-1:,-2*y:-y]=C[5]*q;M[2*x-1-y:2*x-1,:x]=C[6]*A;return M
def R(S,N):
 V=ones((1,3))
 for i in range(N):V=concatenate([T(V,D[C])for C in S],1)
 ion();imshow(V)

Call as R('CODEGOLF', 3)

first i make a dictionary that maps letters to their 7-bit SSD-representaion, where each bit stands for one bar, the .-corners are simply overwritten by the most recent bar

.000.
1   2
1   2
1   2
.333.
4   5
4   5
4   5
.666.

The function T(BaseArray, BooleanArray) makes a big empty array for one letter and puts rotated copies of BaseArray along the bars as indicated by BooleanArray. Finally R(String, N_levels) connects all the letters form the input and uses the result as BaseArray for the next iteration.
While technically correct, the result is quite ugly because of interpolation and the default colourmap

enter image description here

Unglofed

from pylab import*
D=dict(zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789',
           [map(int,bin(7145037215283832782017591362181079009730769141301710950254702714880607436795)[2+n*7:9+n*7])for n in range(36)]))

def T(A,C):
    y,x = A.shape
    M = zeros((2*x-1,x+y))
    if C[0]: M[:y,           :x] = A
    if C[1]: M[:x,           :y] = A[::-1].T
    if C[2]: M[:x,      -2*y:-y] = A.T[::-1]
    if C[3]: M[x-y+y/2:x+y/2,:x] = A # middle bar shifted upwards by half thickness
    if C[4]: M[x-1:,         :y] = A[::-1].T
    if C[5]: M[x-1:,    -2*y:-y] = A.T[::-1]
    if C[6]: M[2*x-1-y:2*x-1,:x] = A
    return M

def R(S,N):
    V = ones((1,3))
    for i in range(N):
        V = concatenate([T(V, D[C]) for C in S], 1)
    imsave('%s_%s.png'%(S,N), V ,cmap='gray')

The initial seed V kinda controls the font on the deepest level. [1 1 1] make the smallest possible 3x5 letters
enter image description here

With V = ones((1,11)) you get long and thin letters
enter image description here

And with

V=array([[0,1,1,1,1,1,1,1,1,0],
         [1,0,0,0,0,0,0,0,0,1],
         [0,1,1,1,1,1,1,1,1,0]])

you can make hollow letters

enter image description here

  • You can save 6 bytes by using int(0xfcbf29fdbb3dbe245dea51ddbbfcf4335ad6edc3be7777b92bb6dd6bdf4bffb) instead of 7145037215283832782017591362181079009730769141301710950254702714880607436795 – mbomb007 Apr 22 '15 at 21:08
  • 3
    @mbomb007 Even better: int("e6960af16emx8y1bwvphxs0dtjuoss3z140s2kh98sq44ny0r",36) – Sp3000 Apr 23 '15 at 0:51

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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