Generate fractals from bit patterns in ASCII
Common Lisp, 248 242 bytes
(lambda(n r g &aux(s(expt r g)))(labels((f(g x y s)(or(= g 0)(#2=multiple-value-bind(q x)(floor x s)(#2#(p y)(floor y s)(if(logbitp(+ q(* p r))n)(f(1- g)x y(/ s r))))))))(#3=dotimes(y s)(#3#(x s)(princ(if(f g x y(/ s r))"# "" ")))(terpri))))
Ungolfed
(defun fractal (n r g &aux (s (expt r g)))
(labels((f(g x y s)
(or(= g 0)
(multiple-value-bind (px x) (truncate x s)
(multiple-value-bind (py y) (truncate y s)
(and
(logbitp (+ px (* py r)) n)
(f (1- g) x y (/ s r))))))))
(fresh-line)
(dotimes(y s)
(dotimes(x s)
(princ
(if (f g x y(/ s r))
"# "
" ")))
(terpri))))
Explanation
- Input:
- N is the encoded pattern
- R is the size of the pattern
- G is the generation
- The output is an implicit square matrix of length S=RG
- We iterate over each row y, column x (nested
dotimes) and compute whether each cell should be drawn (raycasting-like approach). This is done by recursively looking inside the fractal with thefauxiliary function. - If the fractal at position (x,y) shall be drawn, print
"# ", or else print" ". Of course we also print newlines at the end of each row.
For example, Sierpinsky's triangle is represented by S=7 and R=2. At generation 3 the square size is 23=8. For each cell (x,y), the following happen:
fis called with x, y, g bound to 3 and s bound to 4 (8/2)- We truncate x by s, in order to know if x belongs to the left or right side of the implicit matrix.
truncatereturns both the quotient and the remainder, which are bound respectively to px and x (we reuse the same symbol x, but this not a problem). - The same goes for y which gives py and new y.
- In this example, px and py can be either 0 or 1 (because the pattern is a square of length 2). They identify where is (x,y) in the fractal's pattern: when the bit at position py.R + px of N is 0, x and y represent a position where nothing should be drawn.
- Otherwise, we must "zoom" into the corresponding part of the fractal and we call
frecursively with the new bindings for x and y. Those are now the relative position inside the inner fractal. We pass G-1 for the generation and s/2 to represent the half-length of the fractal. - The base case of the recursion is encountered when G is zero, in which case the current (x,y) position should be drawn.
Example
(fractal 186 3 3)
#
# # #
#
# # #
# # # # # # # # #
# # #
#
# # #
#
# # #
# # # # # # # # #
# # #
# # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #
# # #
# # # # # # # # #
# # #
#
# # #
#
# # #
# # # # # # # # #
# # #
#
# # #
#
Computing the 8th generation of the Sierpinski Carpet using (fractal 495 3 8) takes 24.7 seconds and generates an output text file of 83 MB. I wrote a slightly modifed version which outputs an image. For the same parameters, the GIF file weights 1.5MB (same computation time):
Vicsek (click to see original size):
Pyth, 38 bytes
VJ^UQvwjdm@" #".A@L_.[0^Q2jvz2+V*RQNdJ
Try it online: Regular Input / Test Suite
Explanation follows later.
Ruby,154
Score is for the function only. Presented ungolfed below in test program. The only golfing I'm claiming at the moment is removal of comments and indents. I will golf later. At the moment, I'm having fun playing with the program.
The function takes six arguments, but on the initial call only the first 3 are provided per the spec. This causes the three remaining arguments to be set to default values, and in particular the string a where the output is stored is created and initialized to lines of spaces terminated by newlines. As a side effect the global variable $w is also created, indicating the number of symbols per line.
When the function calls itself recursively, it provides all six arguments, including the string a and the x and y coordinates of the top left corner of the next recursion
The rest of the program is pretty straightforward, as indicated in the comments.
#function
f=->b,s,g,x=0,y=0,a=(' '*(-1+2*$w=s**g)+'
')*$w{ #accept arguments, if x,y,a are not provided create them. $w = number of symbols per row
v=s**g/s #v=width of blocks for this recursion depth
if g==0
a[2*y*$w+2*x]=?# #if g==0 plot a #
else #else iterate s*s times through the bits of b, and recurse as necessary
(s*s).times{|i|b>>i&1>0&&f.call(b,s,g-1,x+i%s*v,y+i/s*v,a)}
end
a
}
#test program (requires 3 input numbers separated by newlines)
b=gets.to_i
s=gets.to_i
g=gets.to_i
#get return value and output to stdout
puts f.call(b,s,g)
Output
Here's a set of fractals loosely based on the form of the letters of the word GOLF. More realistic letters could be achieved with larger bitmaps. As the last example shows, the most interesting fractals are discovered by accident.
63775,4,2 (G)
# # # # # # # # # # # # # # # #
# # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # # #
#
# #
# # # #
# # # # # # # #
# #
# # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
# # # #
# # # # # # # #
# # # # # # # # # # # # # # # #
495,3,3 (O, sierpinski carpet)
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
457,3,3 (L)
#
#
# # #
#
#
# # #
# # #
# # #
# # # # # # # # #
#
#
# # #
#
#
# # #
# # #
# # #
# # # # # # # # #
# # #
# # #
# # # # # # # # #
# # #
# # #
# # # # # # # # #
# # # # # # # # #
# # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #
7967,4,2 (F)
# # # # # # # # # # # # # # # #
# # # #
# # # # # # # # # # # # # # # #
# # # #
# # # #
#
# # # #
#
# # # # # # # # # # # # # # # #
# # # #
# # # # # # # # # # # # # # # #
# # # #
# # # #
#
# # # #
#
1879,3,3 (skull and crossbones discovered by accident)
# # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # #
# # #
# # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # #
# # # # # # # # # # # #
# # # # # # # # #
# # #
# # # # # #
# # #
#
# #
# # # # # #
# #
# # # #
# # # # # # # # # # # # # # # # # #
# # # # # #
# # # # # # # # # # # #
# # # # # #
# #
# # # #
# # # # # # # # # # # #
# # # #
# # # # # # # #