We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Recursion
  4. Functions and Fractals: Sierpinski triangles
  5. Discussions

Functions and Fractals: Sierpinski triangles

Sort by

recency

|

39 Discussions

|

  • kabadagiomkar
     + 0 comments

    I came up with a solution that updates a matrix like an image and prints the matrix as the output. Here is my solution in Ocaml

    (* rect interface *)
type rect = {
  x: int;
  y: int;
  w: int;
  h: int;
}

let create_triangle mat rect =
  for y = 0 to (rect.h - 1) do
    for x = (rect.w/2 - y) to (rect.w/2 + y)do
      mat.(rect.y + y).(rect.x + x) <- "1";
    done
  done


(* print utility *)
let print_matrix printer mat = 
  Array.iter (
    fun row -> Array.iter (
      fun e -> printer e; print_string "";
    ) row; print_newline ()
  ) mat


(* helper functions *)
let upper_rect rect =
  let w' = rect.w/2 in
  let h' = rect.h/2 in
  {
    x = rect.x + w'/2 + 1;
    y = rect.y; 
    w = w';
    h = h';
  }

let left_rect rect =
  let w' = rect.w/2 in
  let h' = rect.h/2 in
  {
    x = rect.x;
    y = rect.y + h'; 
    w = w';
    h = h';
  }

let right_rect rect =
  let w' = rect.w/2 in
  let h' = rect.h/2 in
  {
    x = rect.x + w' + 1;
    y = rect.y + h'; 
    w = w';
    h = h';
  }


(* sierpinkski fractal algorithm *)
let sierpinkski_fractal ~size ~iteration =
  let height = int_of_float (2.0 ** float_of_int size) in
  let width = (height * 2) - 1 in
  let grid = Array.make_matrix height width "_" in
  let init = {x = 0; y = 0; w = width; h = height} in
  let grid_create_triangle = grid |> create_triangle in
  let rec aux r itr =
    match itr with
    | i when i = iteration -> grid_create_triangle r
    | i ->
        begin
          aux (upper_rect r) (i + 1);
          aux (left_rect r) (i + 1);
          aux (right_rect r) (i + 1)
        end
  in aux init 0;
  grid


(* main *)
let iter = stdin |> input_line |> int_of_string
let () = sierpinkski_fractal ~size:5 ~iteration:iter |> print_matrix print_string

  • mykhail0
     + 0 comments

    My recursion solution in Haskell:

    main :: IO ()
main = readLn >>= putStr . unlines . sierpinski 32 63

sierpinski :: Int -> Int -> Int -> [String]
sierpinski _ m 0 = f <$> [1,3..m]
  where
    f i = zeroes ++ (replicate i '1') ++ zeroes
      where zeroes = replicate ((m - i) `div` 2) '_'

sierpinski n m i = (zeroes `comb` smaller `comb` zeroes)
  ++ (smaller `comb` column `comb` smaller)
  where
    m' = m `div` 2
    n' = n `div` 2
    smaller = sierpinski n' m' (i - 1)
    zeroes = replicate n' $ replicate ((m - m') `div` 2) '_'
    column = replicate n' "_"
    comb = zipWith (++)

  • __alexey__
     + 0 comments

    This problem is about recursion and functional programming.

    Let's discover recursion pattern. The first figure:
    r = 1 (recursion level)
    h = 4 (hight of the figure) 

    ___1___
__111__
_1___1_
111_111

    The second figure:
    r = 2
    h = 8 

    _______1_______
______111______
_____1___1_____
____111_111____
___1_______1___
__111_____111__
_1___1___1___1_
111_111_111_111

    Each triangle with h=4 on the last picture has been submitted by the identical 3 other triangles with half hight (h'=h/2) and less level of recursion (r'=r-1) from the first picture.

    Thus, recursion function looks like 

    def figure(r: Int, h: Int): Array[String] ={
	if (r == 0 | h == 1) triangle(h) else create(figure(r-1, h/2), h/2)
}

    where 

    def triangle(h: Int): Array[String] = {
<returns Array with simple triangle like this 
___1___
__111__
_11111_
1111111
>
}

    and 

    def create(arr: Array[String], h: Int): Array[String] = {
		<arr is an input triangle. Function returns a figure, which was created from 3 triangles with hight=h and several other objects		
		>		
}

    The transpose(arr), rectangle(h), line(h) functions will help to solve this problem with no val or var :)

  • kirk16
     + 0 comments

    I seemed to have thought about it differently. I saw each triangle a square where each coordinate is colored 1 if (c<=r) and 0 if (c>r). If you add a modulo function over powers of two, you can then generate each succesively smaller pattern. If you multiply them all together you end up with a single function that you then can apply over the range of rows and columns, drop the odd rows, pretty this up into a string and then print it out.

    haskell:

    sm :: Int -> Int -> Int -> Int
sm r c m
| (mod c m) > (mod r m) = 0
| otherwise = 1

mv :: [Int] -> [Int] -> [Int]
mv [] [] = []
mv (x:xs) (y:ys) = (x*y):(mv xs ys)

prod :: Int -> Int -> Int -> [Int]
prod d r 1 = [sm r c d | c<-[0..(d-1)]]
prod d r l = mv ([sm r c (div d (2^(l-1))) | c<-[0..(d-1)]]) (prod d r (l-1))

sier :: Int -> Int -> [[Int]]
sier d l = [prod d r l | r <- [0,2..(d-1)]]


sier :: Int -> Int -> [[Int]]
sier d l = [prod d r l | r <- [0,2..(d-1)]]

    `

  • tinmarino
     + 0 comments

    Bash

    for((y=64;y--;));do s="";for((x=64;x--;));do(((x-y/2)&y))&&s+=" "||s+="Δ";done;echo "$s";done