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;