Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Amazing fractal tree on bash
# @see https://www.hackerrank.com/challenges/fractal-trees-all
# Creating a Fractal Tree from Y-shaped branches
#
# This challenge involves the construction of trees, in the form of ASCII Art.
#
# We have to deal with real world constraints, so we cannot keep repeating the pattern infinitely.
# So, we will provide you a number of iterations, and you need to generate the ASCII version
# of the Fractal Tree for only those many iterations (or, levels of recursion). A few samples are provided below.
#
# Input Format
# A single integer, N.
#
# Constraints
# N <= 5
#
# Output Format
# The Nth iteration of the Fractal Tree, as shown above.
# It should be a matrix of 63 rows and 100 columns. (i.e. 6300 printable characters)
# It should be composed entirely of underscores and ones, in a manner similar to the examples provided.
# Do not include any extra leading or trailing spaces.
#____________________________________________________________________________________________________
#__________________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_______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__________________________________
#_________________________________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__________________________________________________
#!/usr/bin/env bash
read N
MAX_N=5
BLANK_N=$((MAX_N - N))
COLS=100
ROWS=64
LEAFS_NUMBER=1
LINE_BREAK=$'\\n'
BRANCH="1"
BLANK="_"
draw_sub_tree ()
{
local SUB_TREE_HEIGHT=$1
local ROOTS_NUMBER=$2
local ROW_INDEX=${SUB_TREE_HEIGHT}
local SUB_TREE=""
while [ ${ROW_INDEX} -gt 0 ]
do
SUB_TREE="${SUB_TREE}$(draw_line ${SUB_TREE_HEIGHT} ${ROW_INDEX} ${ROOTS_NUMBER})"
ROW_INDEX=$((ROW_INDEX - 1))
done
echo "$SUB_TREE"
}
draw_line ()
{
#1. Evaluate all parameters
local SUB_TREE_HEIGHT=$1
local ROW_INDEX=$2
local ROOTS_NUMBER=$3
local LEAFS_NUMBER=${ROOTS_NUMBER}
local LINE=""
[ ${ROW_INDEX} -gt $((SUB_TREE_HEIGHT / 2)) ]
local IS_LEAF_PART=$?
local LEFT_SIDE_LENGTH=0
local RIGHT_SIDE_LENGTH=0
local BETWEEN_LEAFS_LENGTH=0
local BETWEEN_ROOTS_LENGTH=0
# Leafs part of tree
if [ ${IS_LEAF_PART} -eq 0 ]; then
LEAFS_NUMBER=$((ROOTS_NUMBER * 2))
BETWEEN_LEAFS_LENGTH=$(( (ROW_INDEX - SUB_TREE_HEIGHT / 2) * 2 - 1 ))
if [ ${ROOTS_NUMBER} -eq 1 ]; then
BETWEEN_ROOTS_LENGTH=0
else
BETWEEN_ROOTS_LENGTH=$(( (SUB_TREE_HEIGHT * 2) - 1 - (BETWEEN_LEAFS_LENGTH + 1) ))
fi
LEFT_SIDE_LENGTH=$(( (COLS - LEAFS_NUMBER - (BETWEEN_LEAFS_LENGTH * (LEAFS_NUMBER / 2)) - (BETWEEN_ROOTS_LENGTH * (ROOTS_NUMBER - 1)) ) / 2 ))
# Root part of tree
else
if [ ${ROOTS_NUMBER} -eq 1 ]; then
BETWEEN_ROOTS_LENGTH=0
else
BETWEEN_ROOTS_LENGTH=$(( (SUB_TREE_HEIGHT * 2) - 1 ))
fi
BETWEEN_LEAFS_LENGTH=0
LEFT_SIDE_LENGTH=$(( (COLS - ROOTS_NUMBER - (BETWEEN_ROOTS_LENGTH * (ROOTS_NUMBER - 1)) ) / 2 ))
fi
RIGHT_SIDE_LENGTH=$((LEFT_SIDE_LENGTH + 1))
#2. Build sub tree
LINE="${LINE}$(for ((i=0; i<$LEFT_SIDE_LENGTH; i++)); do echo -n ${BLANK}; done)"
for ((i=0; i<${LEAFS_NUMBER}; i++))
do
LINE="${LINE}${BRANCH}"
if [ ${i} -eq $((LEAFS_NUMBER - 1)) ]; then
break
elif [ $(($i % 2)) -eq 0 ] && [ ${IS_LEAF_PART} -eq 0 ]; then
LINE="${LINE}$(for ((i=0; i<$BETWEEN_LEAFS_LENGTH; i++)); do echo -n ${BLANK}; done)"
else
LINE="${LINE}$(for ((i=0; i<$BETWEEN_ROOTS_LENGTH; i++)); do echo -n ${BLANK}; done)"
fi
done
LINE="${LINE}$(for ((i=0; i<$RIGHT_SIDE_LENGTH; i++)); do echo -n ${BLANK}; done)"
echo "${LINE}${LINE_BREAK}"
}
while [ ${N} -gt 0 ]
do
ROWS=$((ROWS / 2))
TREE="$(draw_sub_tree ${ROWS} ${LEAFS_NUMBER})${TREE}"
LEAFS_NUMBER=$((LEAFS_NUMBER * 2))
N=$((N - 1))
done
while [ ${BLANK_N} -ge 0 ]
do
ROWS=$((ROWS / 2))
for ((i=0; i<${ROWS}; i++))
do
TREE="$(for ((i=0; i<${COLS}; i++)); do echo -n ${BLANK}; done)${LINE_BREAK}${TREE}"
done
BLANK_N=$((BLANK_N - 1))
done
echo -e "$TREE"
@nkapliev
Copy link
Author

nkapliev commented Jun 28, 2016

Masterpiece!
💃 🌟 👑

@hinupurthakur
Copy link

hinupurthakur commented Apr 23, 2020

Hey @nkapliev was going through your code. I ran it successfully and was trying to understand it.
I have few questions regarding the code one of which is why You have initialised ROWS=64 ?
Line92

@nkapliev
Copy link
Author

nkapliev commented Apr 23, 2020

Hey @NupurThakur27,

I ran it successfully and was trying to understand it.

Me too :)
Based on my own comment Masterpiece! it seems that I did understand it back then. But you know, it was a while ago, sorry.

why You have initialised ROWS=64

This is kind of a starting point. You need to specify size of the tree.
I guess you could set

ROWS=2^(N+1)-1

But do not take my word on that 😅

@pancudaniel7
Copy link

pancudaniel7 commented Dec 26, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment