Functions and Fractals - Recursive Trees - Bash! Logic Issue

Question

I am trying to build a fractal tree based on requirement to build it. Something is wrong. Please assist. I am trying to build fractal tree based on the level requested. Here the levels are getting skipped. Need to understand how to fix the issue.

    #!/bin/bash
declare -A matrix
for ((i=1;i<=63;i++)) do
    for ((j=1;j<=100;j++)) do
        matrix[$i,$j]='_'
    done
done
function update_matrix {
p1=$1
p2=$(echo $2-1|bc)
p1=$(echo $p1-1|bc)
p3=$(echo 2^$p2|bc)
p4=$(echo 2*$p3|bc)
p5=$(echo $p3/2|bc)
p6=$3
for ((q1=$p3;q1<$p4;q1++)) do
        if [ "$(echo $q1-$p3|bc)" -lt "$p5" ]
            then
            q2=$(echo $p6-$(echo $p5-$(echo $q1-$p3|bc)|bc)|bc)
            q3=$(echo $p6+$(echo $p5-$(echo $q1-$p3|bc)|bc)|bc)
            matrix[$q1,$q2]=1
            matrix[$q1,$q3]=1
            #printf '%s' "$q1 $q2 -- $q1 $q3"
            #echo ""
            else
            matrix[$q1,$p6]=1
            #echo $q1 $p6
        fi
done

if [ $p1 -ge 1 ]
then
update_matrix $p1 $p2 $(echo $p6+$p5|bc)
update_matrix $p1 $p2 $(echo $p6-$p5|bc)
else
return
fi
}
read iteration
if [ $iteration -ge 1 ]
then
    update_matrix $iteration 6 32
fi
for ((i=1;i<=63;i++)) do
    for ((j=1;j<=100;j++)) do
        printf '%s' "${matrix[$i,$j]}"
    done
    echo ""
done

Output is:

____________________________________________________________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1___1______________________________________________
__________________________________________________1_1_______________________________________________
___________________________________________________1________________________________________________
___________________________________________________1________________________________________________
___________________________________________________1_______1________________________________________
____________________________________________________1_____1_________________________________________
_____________________________________________________1___1__________________________________________
______________________________________________________1_1___________________________________________
_______________________________________________________1____________________________________________
_______________________________________________________1____________________________________________
_______________________________________________________1____________________________________________
_______________________________________________________1____________________________________________
_______________________________________1_______________1____________________________________________
________________________________________1_____________1_____________________________________________
_________________________________________1___________1______________________________________________
__________________________________________1_________1_______________________________________________
___________________________________________1_______1________________________________________________
____________________________________________1_____1_________________________________________________
_____________________________________________1___1__________________________________________________
______________________________________________1_1___________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________________________________________1____________________________________________________
_______________1_______________________________1____________________________________________________
________________1_____________________________1_____________________________________________________
_________________1___________________________1______________________________________________________
__________________1_________________________1_______________________________________________________
___________________1_______________________1________________________________________________________
____________________1_____________________1_________________________________________________________
_____________________1___________________1__________________________________________________________
______________________1_________________1___________________________________________________________
_______________________1_______________1____________________________________________________________
________________________1_____________1_____________________________________________________________
_________________________1___________1______________________________________________________________
__________________________1_________1_______________________________________________________________
___________________________1_______1________________________________________________________________
____________________________1_____1_________________________________________________________________
_____________________________1___1__________________________________________________________________
______________________________1_1___________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________
_______________________________1____________________________________________________________________

Need to understand why left node created right one is not created.

Sonyasoo

Answer 1

What I was missing is to declare variables as local. Due to which global variables were getting updated and thus my program was not working properly.

I fixed the issue and used local variables and it worked like a charm.

Code for the solution is Its for Hackerrank Functions and Fractals - Recursive Trees - Bash! Program. Took me 3hr to nail it down. Really refreshing to finally solve it.

    #!/bin/bash
declare -A matrix
for ((i=1;i<=63;i++)) do
    for ((j=1;j<=100;j++)) do
        matrix[$i,$j]='_'
    done
done
i=0
declare -A arr
function update_matrix {
local p1 p2 p3 p4 p5 p6 q1 q2 q3 p11 p12 p13 p14 p15 p16
p1=$1
p2=$(echo $2-1|bc)
p1=$(echo $p1-1|bc)
p3=$(echo 2^$p2|bc)
p4=$(echo 2*$p3|bc)
p5=$(echo $p3/2|bc)
p6=$3
for ((q1=$p3;q1<$p4;q1++)) do
        if [ "$(echo $q1-$p3|bc)" -lt "$p5" ]
            then
            q2=$(echo 18+$p6-$(echo $p5-$(echo $q1-$p3|bc)|bc)|bc)
            q3=$(echo 18+$p6+$(echo $p5-$(echo $q1-$p3|bc)|bc)|bc)
            matrix[$q1,$q2]=1
            matrix[$q1,$q3]=1
            #printf '%s' "$q1 $q2 -- $q1 $q3"
            #echo ""
            else
            matrix[$q1,$(echo 18+$p6|bc)]=1
            #echo $q1 $p6
        fi
done

if [ $p1 -ge 1 ]
then
p11=$p1
p12=$p2
p13=$(echo $p6-$p5|bc)
p14=$(echo $p6+$p5|bc)
p15=$p1
p16=$p2

#echo $p11 $p12 $p6 $p5 $p13
update_matrix $p11 $p12 $p13
#echo $p15 $p16 $p6 $p5 $p14

update_matrix $p15 $p16 $p14
t=4
else
s=2
fi
}
read iteration
if [ $iteration -ge 1 ]
then
    #echo $iteration 6 32
    update_matrix $iteration 6 32
fi
for ((i=1;i<=63;i++)) do
    for ((j=1;j<=100;j++)) do
        printf '%s' "${matrix[$i,$j]}"
    done
    echo ""
done

Sonyasoo

Answer 2

The question asked by HackerRank requires you to make the code recursive. To be recursive the code must call itself at some point. Below I've made a create_y function that is recursive. This function will continually call itself until it meets its stop condition. The stop condition is the if statement that checks if the iteration variable is greater than 0.

The function itself naturally wants to build a Y, and at the end of the Y branches, make new Y's that are half the size of the original. When it is done it will print to standard out.

#!/bin/bash
declare -A SCREEN
SCREENR=63
SCREENW=100
DEPTH=0
MAX=16

function create_y {
    local originR=$1
    local originC=$2
    local iteration=$3
    local size=$4
    local originVR=0
    local originVC=0
    local originNYLR=0
    local originNYLC=0
    local originNYRR=0
    local originNYRC=0

    if [[ iteration -gt 0 ]]; then
        for ((i=0;i<$size;i++))
        do
            SCREEN[$(($originR-$i)),$originC]=1
            let originVR="$(($originR-$i))"
        done

        for ((i=1;i<=$size;i++))
        do
             SCREEN[$(($originVR-$i)),$(($originC - $i))]=1
             let originNYLR="$(($originVR-$i))"
             let originNYLC="$(($originC - $i))"
             SCREEN[$(($originVR-$i)),$(($originC + $i))]=1
             let originNYRR="$(($originVR-$i))"
             let originNYRC="$(($originC + $i))"
        done

        create_y $(($originNYLR-1)) $originNYLC $(($iteration-1)) $(echo "$size/2" | bc)
        create_y $(($originNYRR-1)) $originNYRC $(($iteration-1)) $(echo "$size/2" | bc)
    fi  
}

for ((i=1;i<=$SCREENR;i++)) 
do
    for ((j=1;j<=$SCREENW;j++)) 
    do
        SCREEN[$i,$j]='_'
    done
done

read DEPTH

create_y $SCREENR $(echo "$SCREENW/2" | bc) $DEPTH $MAX

for ((i=1;i<=$SCREENR;i++)) do
    for ((j=1;j<=$SCREENW;j++)) do
         printf '%s' "${SCREEN[$i,$j]}"
    done
    echo ""
done

exit 0

Toadflax

Thank you for this code snippet, which might provide some limited short-term help. A proper explanation would greatly improve its long-term value by showing why this is a good solution to the problem, and would make it more useful to future readers with other, similar questions. Please edit your answer to add some explanation, including the assumptions you've made. – Swap

Answer 3

Attempting to explain why this is optimal below. Idea of creating the grid and solving the problem is pretty straight-forward in terms of logic.

Algorithm:

• Create a grid.
• Create a solving function.
• Create a column (vertical line) of 1's, with length of l (interval, initially 16) starting from the middle.
• Mark left, right diagonals from the end of the line with 1's.
• You now have a Y!
• Recurse left and right from the top corners of Y, to create "sub-Y's".
• When recursing be sure your data are correct (interval should be divided by 2 etc.).

PS: Ladies and Gentlemen when sharing code, please give it a proper try when it comes on commenting, even for the smallest snippet. It will change your lives!

 #!/bin/bash

 declare -A grid

 #Solves the fractal problem.
 #Variables:
 #  d: depth of recursion.
 #  l: length of gaps/interval.
 #  r: row
 #  c: column.
 solve(){
  local d=$1
  local l=$2
  local r=$3
  local c=$4

  #base case, return.
  if [ $d -eq 0 ]; then
      return
  fi

# iterate backwards.
# create a column/vertical. line of 1's.
# sizeof(line) = l (length of interval) [initially 16].
# See graph below:
: '
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
        -------------------------------------------------1--------------------------------------------------
'
for (( i = l; i > 0; i-- )); do
    grid[$((r-i)).$c]=1
done

((r -= l))

# iterate backwards.
# create the V-shaped tree/fractal.
# sizeof(tree) = l (length of interval) [initially 16].
# should fill all diagonal cells with 1's .
#       {[r-1, c-1] (left), [r-1, c+1] (right)} --> 1st.
#       {[r-2, c-2] (left), [r-2, c+2] (right)} --> 2nd.                                        for(i in [1,l]) {                       //remember l is dynamic. (16, 8, 4, 2, 1, ..)
#           ...                                                                         ---->       {[r-i, c-l] (left), [r-i, c+l] (right)} = 1 
#           ...                                                                                 }
#       {[r-l, c-l] (left), [r-l, c+l] (right)} --> 16th (or l-th).


for (( i = l; i > 0; i--)); do
    grid[$((r-i)).$((c-i))]=1
    grid[$((r-i)).$((c+i))]=1
done

: '
    This for n = 1 creates the following pattern:

    ----------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------
    ---------------------------------1-------------------------------1----------------------------------
    ----------------------------------1-----------------------------1-----------------------------------
    -----------------------------------1---------------------------1------------------------------------
    ------------------------------------1-------------------------1-------------------------------------
    -------------------------------------1-----------------------1--------------------------------------
    --------------------------------------1---------------------1---------------------------------------
    ---------------------------------------1-------------------1----------------------------------------
    ----------------------------------------1-----------------1-----------------------------------------
    -----------------------------------------1---------------1------------------------------------------
    ------------------------------------------1-------------1-------------------------------------------
    -------------------------------------------1-----------1--------------------------------------------
    --------------------------------------------1---------1---------------------------------------------
    ---------------------------------------------1-------1----------------------------------------------
    ----------------------------------------------1-----1-----------------------------------------------
    -----------------------------------------------1---1------------------------------------------------
    ------------------------------------------------1-1-------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------




'

#   Now comes the fun part, we should recurse.
#   For a complete analysis about why recursion is optimal u could read CLRS
#   or any other Algorithms book of ur choice (be extra carefull on big-O notation, Master Theorem and recursion trees).

# Idea:
#   - We will subrtact 1 from the depth for each complete fractal we create, so we will eventually terminate.
#   - Interval gets reduced by half for any fractal, thus l' = l/2.
#   - r-l: Executed 2 times (see line 48) will bring us to the left/right topmost part of the newly created Y (left/right corner), on the proper row [---------].
#   - c-l/c+l: Will result us beeing on either left or right corner of the Y [See below figure for more].

: '
    
    ----------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------
    ---------------------------------O-------------------------------O----------------------------------        After performing 2 recursive calls (left/right), the execution on the new copy
    ----------------------------------1-----------------------------1-----------------------------------        will start from points marked with "O".
    -----------------------------------1---------------------------1------------------------------------        
    ------------------------------------1-------------------------1-------------------------------------
    -------------------------------------1-----------------------1--------------------------------------
    --------------------------------------1---------------------1---------------------------------------
    ---------------------------------------1-------------------1----------------------------------------
    ----------------------------------------1-----------------1-----------------------------------------
    -----------------------------------------1---------------1------------------------------------------
    ------------------------------------------1-------------1-------------------------------------------
    -------------------------------------------1-----------1--------------------------------------------
    --------------------------------------------1---------1---------------------------------------------
    ---------------------------------------------1-------1----------------------------------------------
    ----------------------------------------------1-----1-----------------------------------------------
    -----------------------------------------------1---1------------------------------------------------
    ------------------------------------------------1-1-------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------
    -------------------------------------------------1--------------------------------------------------




'

# This will work recursivelly so only thing we need to do, is wait and pray that our exit case will work.   
# This can also be seen as "Divide and Conquer" algorithm.

solve $((d-1)) $((l/2)) $((r-l)) $((c-l))
solve $((d-1)) $((l/2)) $((r-l)) $((c+l))

}

 # Just visualize the grid under given assumptions
 print_grid(){
    for ((i=0; i<63; i++)); do
        for ((j=0; j<100; j++)); do
              if [[ ${grid[$i.$j]} ]]; then
              printf 1
              else
                printf -
              fi
        done
        echo
    done
 }

 read n
 solve $n 16 63 49
 print_grid

Earthen