HackerRank “BASh Recursive Trees” Solution

This BASh script was written during the process of solving the Functions and Fractals – Recursive Trees – Bash! problem on Hacker-Rank. Yes it is slight overkill for that problem, but adds neat interesting features that no sane developer should implement in a shell script – such as drawing arbitrary lines, “Y” shapes, and recursive trees to any number of iterations (“screen” size and computational/memory/time-constraints withstanding) on an ASCII-art “screen”. Why not a more-limited, simpler approach to the problem? During the dev process, I found that I benefitted from incrementally breaking down the problem to its simpler components: reliably drawing any arbitrary pixel, then a straight line, then a “Y”, then any number of those Y’s on the screen to form a tree. Probably the trickiest part was deciphering exactly *what* idiosyncratic method the author of the Hacker-Rank problem had used to draw his full tree, then replicating that in a manner that was automatic and repeatable across iterations. Although high-school level, the math was the fun part.

Can also be downloaded here

declare -a _scrn
_rows=63
_cols=100
max_iters=5
trunk_row=0

start_bl=$(( ($_rows + 1) / ( $max_iters - 1) ))
trunk_col=`expr $_cols / 2`

declare debug=''

function blankScreen()
{
    blank=`yes 2>/dev/null | head -n $(( $_cols + 1 )) | tr -d y | paste -sd_ -`
    for ((i=0; i<_rows; i++)); do
        _scrn[$i]=$blank
    done
}

declare new_row_val
function flipRow()
{
    new_row_val=$(( $_rows - $1 - 1 ))
}

function drawWood()
{
    row=$1; col=$2
    flipRow $row
    old_row=${_scrn[$new_row_val]}
    _scrn[$new_row_val]=${old_row:0:$col-1}1${old_row:$col}
}

function drawLine()
{
    x1=$1; y1=$2; x2=$3; y2=$4 
    if [ $x1 -eq $x2 ]; then
        x=$x1
    else
        m=`echo "scale=4; (${y2} - ${y1})/(${x2} - ${x1})" | bc`
        b=`echo "scale=4; ${y1} - ${m} * ${x1}" | bc`
    fi
    for y in `seq $y1 $y2`; do
        if [ $x1 -ne $x2 ]; then
            x=`printf '%.0f\n' $(echo "scale=4; (${y} - ${b})/${m}" | bc)`
        fi
        if [ -n "$debug" ]; then 
            echo drawWood $y $x 1>&2
        else
            drawWood $y $x
        fi
    done
}

function drawY()
{
    start_x=$1; start_y=$2; stem_len=$3
    drawLine $start_x   $start_y    $start_x    $(( $start_y + $stem_len ))
    start_y=$(( $start_y + $stem_len + 1 ))
    drawLine $(( $start_x - 1 ))    $start_y    \
            $(( $start_x - $stem_len - 1 ))     $(( $start_y + $stem_len ))
    drawLine $(( $start_x + 1 ))    $start_y    \
            $(( $start_x + $stem_len + 1 ))     $(( $start_y + $stem_len ))
}

function drawTree()
{
    iters=$1
    declare -a curr_ys
    bla=$(( $start_bl - 1 ))
    curr_ys[0]="${trunk_col}_${trunk_row}_${bla}"

    for curr_iter in `seq 1 $iters`; do
        declare -a next_ys
        next_ys_ind=0
        for y in ${curr_ys[*]}; do 
           declare -a unpakt=( `echo $y | tr _ ' '` )
           drawY ${unpakt[*]}
           prev_x=${unpakt[0]}
           prev_y=${unpakt[1]}
           prev_bla=${unpakt[2]}
           prev_bl=$(( $prev_bla + 1 ))
           next_y=$(( $prev_y + $prev_bl * 2 ))
           next_bla=$(( $prev_bl / 2 - 1 ))
           next_ys[$next_ys_ind]=$(( $prev_x - $prev_bl ))'_'$next_y'_'$next_bla
           next_ys_ind=$(( $next_ys_ind + 1 ))
           next_ys[$next_ys_ind]=$(( $prev_x + $prev_bl ))'_'$next_y'_'$next_bla
           next_ys_ind=$(( $next_ys_ind + 1 ))
        done 
        curr_ys=( ${next_ys[*]} )
        unset next_ys
    done
    unset curr_ys
}

blankScreen
echo 'Hello. You can enter "h" or "help" to view the documentation at any time, or enter commands to continue. "q" to quit.' 

while true ; do
    draw_screen=y
    read -u 0 -p '$ ' line
    declare -a cmd=( $line ) 
    c=${cmd[0]}
    cmd[0]=''

    case $c in
        c)
            unset _scrn
            blankScreen
            ;;
        d)
            if [ -n "$debug" ]; then debug=''; else debug='y'; fi
            draw_screen=''
            ;;
        h|help)
            echo '
This simple shell draws lines, single pixels, "Y"s, or a "fractal tree" on an ASCII-art "screen". Please enlarge your terminal to at least 100 columns wide & 64 rows high so that the "screen" can be displayed. Available to you our fearless user, are the following one-letter commands (note there is no error-checking):

c   Clear the screen
d   toggle Debug mode. When in debug mode, diagnostic information may be printed, but no screen will be displayed
h   read this Help again
l   draw a Line, format:
    l [x1] [y1] [x2] [y2]
    example:
    l 1 22 3 45
    x1,x2,y1,y2 should all be integers within the screen (0<=x<=100, 0<=y<=63)
p   draw a "Pixel" on the screen, format:
    p [row(y)] [col(x)]
    example:
    p 54 3
q   feeling Queasy, say buhbaiee
t   draw a "fractal Tree" with a branch iteration between 1 and 5:
    t [iter-level]
    example:
    t 5
y   draw a single "Y" or branching structure, format:
    y [root-x] [root-y] [stem-length]
    example:
    y 23 34 5

**Other commands, and parameters that fall outside valid ranges will result in undefined behavior such as:
    a) this script crashing
    b) inter-galactic thermonuclear war resulting in death & destruction at an apocalyptic scale
    c) your dog eating your child"s food and quietly peeing on the carpet yet again
'    
            draw_screen=''
            ;;
        l)
            drawLine ${cmd[@]}
            ;;
        p)
            drawWood ${cmd[@]}
            ;;
        q)
            break    
            ;;
        t)
            drawTree ${cmd[@]}
            ;;
        y)
            drawY ${cmd[@]}
            ;;
        *)
            echo 'I seem to be running with an nonexistent amount of disk space... ;-D'
            draw_screen=''
            ;;
    esac
    [ -n "$draw_screen" -a -z "$debug" ] && echo ${_scrn[*]} | tr ' ' $'\n'
    unset cmd
done;