rows=63
cols=100
max_it=5
first_y_size=16

declare -A fractal_positions

function fractals {
    local it=$1
    local row=$2
    local col=$3
    local y_size=$4
    
    if (( $it > $max_it)) || (( $it > $N )); then
        return
    fi
    
    fractals $(( $it + 1 )) $(( $row - $y_size * 2 )) $(( $col - $y_size )) $(( $y_size / 2 ))
    fractals $(( $it + 1 )) $(( $row - $y_size * 2 )) $(( $col + $y_size )) $(( $y_size / 2 ))
    
    for (( i = $row; i > $row - $y_size; i--)); do
        fractal_positions[$(printf "%d|%d" $((i-1)) $col)]=1
    done
    
    local tmp=1
    for (( i = $row - $y_size; i > $row - $y_size * 2; i--)); do
        fractal_positions[$(printf "%d|%d" $((i-1)) $(( $col - $tmp )))]=1
        fractal_positions[$(printf "%d|%d" $((i-1)) $(( $col + $tmp )))]=1
        tmp=$(($tmp+1))
    done
}

read -r N

fractals 1 $rows $(( $cols / 2 )) $first_y_size

for ((i=0; i < $rows; i++)); do
    for ((j=0; j < $cols; j++)); do
        if ((fractal_positions[$(printf "%d|%d" $i $j)] == 1)); then
            printf "1"
        else
            printf "_"
        fi
    done
    printf "\n"
done

#!/bin/bash
read tree_depth
xpos=(50) # Roots where we start the Ys
for ((y=1; y<=63; y++)); do
  for ((x=1; x<=100; x++)); do
    char=_
      if (( tree_depth > printed )); then # if we need more depth
        length=$((2**(4-printed))) b=y-offset-length
        # b is the y coordinate from the point of view of the center of the Y we are drawing
        if (( b <= length )); then
          (( b < 0 )) && b=0 # Force vertical (to draw a Y instead of an X)
          for p in "${xpos[@]}"; do
            if (( p-b == x || p+b == x )); then
              char=1
              # If b == length, we are finishing drawing this rank's Ys
              # So we save the x position for future Y roots
              (( b == length )) && new_xpos+=("$x")
            fi
          done
        fi
      fi
    printf %s "$char"
  done
  if (( b == length )); then
    # We finished drawing the Ys for this level
    # We set the new roots and the offset for coordinate computation
    xpos=("${new_xpos[@]}") new_xpos=() printed=$((printed+1)) offset=$y
  fi
  echo
done | tac

#!/bin/bash

draw_blank_lines () {
    for i in $(seq $1); do
       printf %"100"s | tr " " "_" | sed 's/$/\n/'
    done
}

# to get the "right" answer we have to add 18 "_" to the left side
# and 19 "_" to the right side since we use a 63-column box in our calculations
# instead of a 100-column box in order to properly draw all the trees together
fix_width () {
    sed 's/^/__________________/' | sed 's/$/___________________/'
}

# Natural Natural
# takes two numbers that represent a number of "_" before "1"
# and after "1" accordingly and draws a line
draw_line () {
	printf %"$1"s | tr " " "_"
    printf "1"
	printf %"$2"s | tr " " "_"
}

# Width Height
# Natural Natural
#_____1_______1_____
#______1_____1______
#_______1___1_______
#________1_1________
#_>_______1_________
#_>_______1_________
#_>_______1_________
#_>_______1_________
draw_stalk () {
    let before=$1/2
    let after=$1/2

	for i in $(seq $2); do
		draw_line $before $after
		printf "\n"
	done
}

# Width Height
# Natural Natural
#_>___1_______1_____
#_>____1_____1______
#_>_____1___1_______
#_>______1_1________
#_________1_________
#_________1_________
#_________1_________
#_________1_________
draw_fork () {
    let left_a=0
    let right_b=0
    let left_b=($1/2)-1
    let right_a=($1/2)-1

    for i in $(seq $2); do
      draw_line $left_b $left_a; printf "_"
      draw_line $right_b $right_a; printf "\n"

      # we're moving "1"s for both branches with every itteration
      # making the distance between them wider and wider
      let left_b=$left_b-1; let left_a=$left_a+1
      let right_b=$right_b+1; let right_a=$right_a-1
    done
    
}

draw_tree () {
    let width=$1
    let height=$2
    
    draw_stalk $width $height
    draw_fork $width $height
}

# Natural Natural Natural -> String
# Width   Height  n_trees 
# composes a string with calls to draw_tree, so that 
# we could eval it later
# result="<(draw_tree 7 2) <(draw_tree 7 2) <(draw_tree 7 2)"
next_trees () {
    result=""
    for i in $(seq $3); do
        # if we add anything to an empty var ""
        # there is no space after the first argument
        result="<(draw_tree $1 $2) $result"
    done

    echo $result
}

main () {
    # n =< 5
    read -p "n<=5: " n
    # width and height of the very first tree
    width=63
    height=16
    lines=63
    trees=1
    steps=0
    
    for i in $(seq $n); do
        # tr '\t' '0' 
        # replace "\t" between trees with "_"
        eval paste $(next_trees $width $height $trees) | tr '\t' '_' | fix_width
        # at each step we reduce the number of blank lines by the height of the tree
        let lines=$((lines - (height * 2)))
        let width=$width/2
        let height=$height/2
        let trees=$trees*2
    done

    draw_blank_lines $lines
}

main | tac

declare -A matrix
NUM_ROWS=63
NUM_COLS=100

for ((i=1; i<=NUM_ROWS; i++)) do
    for ((j=1; j<=NUM_COLS; j++)) do
        matrix["$i,$j"]="_"
    done 
done

read RECURSION_LEVEL
  
func() {
    local COL="$1"   
    local N="$2" 
      
    local ROW=$((2**(7-$N)))   
    local SIZE=$(( 2**(5-$N) ))  
     
    for ((height=0; height<=$SIZE; height++)) do
        row=$(( $ROW - $height ))  
        matrix[$row,$COL]="1" 
        
        row=$(( $row -$SIZE ))  
        col1=$(( $COL+$height ))
        col2=$(( $COL-$height ))
        matrix[$row,$col1]="1"
        matrix[$row,$col2]="1"
    done   
 
    if [[ $N -lt $RECURSION_LEVEL && $SIZE -gt 1 ]]; then  
        func $(($COL-$SIZE)) $((N+1))  
        func $(($COL+$SIZE)) $((N+1))
    fi 
}
  
func 50 1
  
for ((i=1; i<=NUM_ROWS; i++)) do
    for ((j=1; j<=NUM_COLS; j++)) do
        echo -n ${matrix["$i,$j"]}
    done
    echo 
done