HR F#: Functions and Fractals: Sierpinski triangles
The problem of drawing the Sierpinski triangles is considered to be advanced problem and it really is.
The Sierpinski triangle is a fractal, constructed by recursively subdividing equilateral triangles into smaller equilateral triangles. If you ever played Deus Ex you may have noticed that its logo is inspired by the Sierpinski triangle.
This challenge involves the construction of such triangles, in the form of ASCII Art. The restriction is, that you need to accomplish this with functional programming, and you cannot declare even local variables!
The program should be able to draw first 5 iterations of the Sierpinski triangle on the canvas of 32 rows and 63 columns. Something like this:
_______________________________1_______________________________
______________________________111______________________________
_____________________________1___1_____________________________
____________________________111_111____________________________
___________________________1_______1___________________________
__________________________111_____111__________________________
_________________________1___1___1___1_________________________
________________________111_111_111_111________________________
_______________________1_______________1_______________________
______________________111_____________111______________________
_____________________1___1___________1___1_____________________
____________________111_111_________111_111____________________
___________________1_______1_______1_______1___________________
__________________111_____111_____111_____111__________________
_________________1___1___1___1___1___1___1___1_________________
________________111_111_111_111_111_111_111_111________________
_______________1_______________________________1_______________
______________111_____________________________111______________
_____________1___1___________________________1___1_____________
____________111_111_________________________111_111____________
___________1_______1_______________________1_______1___________
__________111_____111_____________________111_____111__________
_________1___1___1___1___________________1___1___1___1_________
________111_111_111_111_________________111_111_111_111________
_______1_______________1_______________1_______________1_______
______111_____________111_____________111_____________111______
_____1___1___________1___1___________1___1___________1___1_____
____111_111_________111_111_________111_111_________111_111____
___1_______1_______1_______1_______1_______1_______1_______1___
__111_____111_____111_____111_____111_____111_____111_____111__
_1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1_
111_111_111_111_111_111_111_111_111_111_111_111_111_111_111_111
The problem can be decomposed into smaller ones:
- how to generate triangles?
- how to render them on the canvas?
Generation of the triangles can be done with simple recursive function. However the data structure chosen for the triangles greatly affects the complexity of the solution.
One of the obvious approaches is to store the triangles as coordinates in the 2D space:
// x, y on the 2D plane
type Point = float * float
// top, left, and right points of the triangle
type Triangle = Point * Point * Point
Producing next group of triangles is easy:
let step (triangles : Triangle list) =
[ for t in triangles do
yield newTopTriangle t
yield newLeftTriangle t
yield newRightTriangle t ]
The function step replaces original triangles with triades of smaller triangles. Applying this function several times will produce the Sierpinski triangle of particular level. newXXXTriangle are just a function with a bit of trigonometry in them.
Although this approach will definitely do the job, there are a few things to notice:
- it is possible to use this algorithm with any triangles, not only equilateral;
- it is possible to generate much more levels of the Sierpinski triangles than required.
Considering the fact that these triangles should be displayed on a very limited ASCII canvas, correct implementation of this approach goes far beyond the original requirements. This is a very strong indicator of premature generalisation.
The following looks more appropriate:
// triangle: x, y, level
// levels:
// 1 - 1 - 2^0 row, 2^1-1 column
// 2 - 1
// 111 - 2^1 rows, 2^2-1 columns
// 3 - 1
// 111
// 1 1
// 111 111 - 2^2 rows, 2^3-1 columns
// n - ... - 2^(n-1) rows, (2^n)-1 columns
type Tri = int * int * int
This simple type alias groups together coordinates of the top vertex and level. Rectangle on the first level takes just one pixel of the canvas and it does not make any sense to draw any smaller traingles.
The step function does not require any trigonometric calculations:
let pow (x : int) (y : int) =
match y with | 0 -> 1
| 1 -> x
| _ -> [ 2..y ] |> List.fold (fun r _ -> r * x) x
let step (ts : Tri list) =
[ for t in ts do
let x, y, n = t
yield! [ x, y, n-1
x-(pow 2 (n-2)), y + (pow 2 (n-2)), n-1
x+(pow 2 (n-2)), y + (pow 2 (n-2)), n-1 ] ]
It decreases the level of the base triangle and "hangs" two more triangles below the left and right vertices.
Drawing of the triangles takes much more than actually generating them. This problem is a kind of problems where functional programming does not fit nicely. Its devotedness to immutable data structures does not help much when what you want to do is to change color of single point on the canvas.
However, in this particular problem purely functional solution can be afforded, as the canvas is very small. Also a few techniques can be applied to decrease number of unwanted data duplications:
- Split canvas into rows and copy unchanged rows to the new canvas.
- Draw triangles by drawing the horisontal lines, not individual pixels.
Drawing:
// drawing canvas of width * height * rows
type Canvas = int * int * string list
// point on the canvas
type Point = int * int
// draws horisontal line from x of length n in row
let drawhlr (row : string) (x : int) (n : int) =
let len = row.Length
if x < len then
let s1 = row.Substring(0, x)
let p = x + n
if p < len then
let s2 = String('1', n)
let s3 = row.Substring(p)
sprintf "%s%s%s" s1 s2 s3
else
let s2 = String('1', len - x)
sprintf "%s%s" s1 s2
else row
// draws horisontal line from p of length n on the canvas
let drawhl (c : Canvas) (p : Point) (n : int) =
let w, h, rows = c
let x, y = p
let newr = rows
|> List.mapi (fun i row ->
if y = i then drawhlr row x n
else row)
w, h, newr
// draws triangle on canvas
let draw (c : Canvas) (t : Tri) =
let x, y, n = t
let lines = [ for i in 1..(pow 2 (n-1)) do
yield (x-(i-1), y+(i-1)), i*2-1 ]
lines
|> List.fold (fun c v -> drawhl c (fst v) (snd v)) c
let render (c : Canvas) =
let _, _, rows = c
String.Join("\n", rows)
And the rest of the solution:
open System
... code for triangles ...
... code for drawing ...
[<EntryPoint>]
let main argv =
let n = Console.ReadLine() |> int
[1..n]
|> List.fold (fun ts _ -> step ts) [ (31, 0, 6) ]
|> List.fold (fun c t -> draw c t) (63, 32, [ for i in 0..31 do yield String('_', 63) ])
|> render
|> printf "%s"
0 // return an integer exit code