/ HackerRank Functional Challenges

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:


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 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
      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 ]
  |> 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 ...

let main argv =
  let n = Console.ReadLine() |> int
  |> 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
Alex Netkachov

Alex Netkachov

Alex likes functional programming, algorithms and code reviews. Apart from programming, his favourites are walking with his family in the parks and national trails and reading books.

Read More

Why not to stay updated if the subject is interesting? Join Telegram channel Alex@Net or follow alex_at_net on Twitter. Or just, use the comments form below.