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

```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="\${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}
prev_y=\${unpakt}
prev_bla=\${unpakt}
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}
cmd=''

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
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;
```
This entry was posted in Uncategorized. Bookmark the permalink.