Endless Paradigm

So, I joined hackerrank lately, after learning a bit of C, Python, and Java after ruby, so I could focus on learning algorithms, instead of 9001 languages. I decided to dabble in their bash section for a while, since my hackerrank is on my linkedin profile, and I'd like for potential employers to be able to see my mad bash skills. Thinking I was hot spoon after getting up pretty decent on the bash leaderboards, I decided to try the "Hard" section of their bash... section. I was presented with this marvelous challenge:

Spoiler:

Code:

			**Submissions with the design hard-coded in them, will be rejected** 
____________________________________________________________________________________________________
__________________1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1___________________
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________
____________________1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________
______________________1_____1_________1_____1_________1_____1_________1_____1_______________________
_______________________1___1___________1___1___________1___1___________1___1________________________
________________________1_1_____________1_1_____________1_1_____________1_1_________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
_________________________1_______________1_______________1_______________1__________________________
__________________________1_____________1_________________1_____________1___________________________
___________________________1___________1___________________1___________1____________________________
____________________________1_________1_____________________1_________1_____________________________
_____________________________1_______1_______________________1_______1______________________________
______________________________1_____1_________________________1_____1_______________________________
_______________________________1___1___________________________1___1________________________________
________________________________1_1_____________________________1_1_________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________1_______1______________________________________________
______________________________________________1_____1_______________________________________________
_______________________________________________1___1________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________


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.

Iteration #1 
In the beginning, we simply create a Y. There are 63 rows and 100 columns in the grid below. The triangle is composed of underscores and ones as shown below. The vertical segment and the slanting segments are both 16 characters in length.

  
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________1_______1______________________________________________
______________________________________________1_____1_______________________________________________
_______________________________________________1___1________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________


Iteration #2

At the top of the left and right branches of the first Y, we now add a pair of Y-shapes, which are half the size of the original Y.


____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________1_______________1_______________1_______________1__________________________
__________________________1_____________1_________________1_____________1___________________________
___________________________1___________1___________________1___________1____________________________
____________________________1_________1_____________________1_________1_____________________________
_____________________________1_______1_______________________1_______1______________________________
______________________________1_____1_________________________1_____1_______________________________
_______________________________1___1___________________________1___1________________________________
________________________________1_1_____________________________1_1_________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
_________________________________1_______________________________1__________________________________
__________________________________1_____________________________1___________________________________
___________________________________1___________________________1____________________________________
____________________________________1_________________________1_____________________________________
_____________________________________1_______________________1______________________________________
______________________________________1_____________________1_______________________________________
_______________________________________1___________________1________________________________________
________________________________________1_________________1_________________________________________
_________________________________________1_______________1__________________________________________
__________________________________________1_____________1___________________________________________
___________________________________________1___________1____________________________________________
____________________________________________1_________1_____________________________________________
_____________________________________________1_______1______________________________________________
______________________________________________1_____1_______________________________________________
_______________________________________________1___1________________________________________________
________________________________________________1_1_________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________
_________________________________________________1__________________________________________________


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.

Your eyes do not deceive you, folks! They want you to make a mandelbrot generator in bash! Holy spoon! Needless to say, I just nope'd the fudge out of that, and stuck to moderate challenges (This is actually the only hard one)

There was one coder that solved the test by generating HASKELL code to a file, and using the HASKELL program to dump the fractal, instead of using bash.

Also, hackerrank has a timeout rule, so this monstrosity of a script has to generate the fractal before the site decides that it is taking too long, and fails you for it!

Heh...

Code:

			#!/bin/bash
declare -a a=('.' '~' "'" 'O' "'" '~' '.' '*')
[[ $# = 0 ]] && s=9 || s=$1
[[ $s -gt 5 ]] || s=5
for (( w=1, r=7, n=1; n<=$s; n++ )) ; do
  for (( i=$s-n; i>0; i-- )) ;  do
    echo -n " "
  done
  for (( i=1; i<=w; i++ )) ; do
    echo -n "${a[r]}"
    [[ $r -gt 5 ]] && r=0 || r=$r+1
  done
  w=$w+2
  echo " "
done;
echo " "

Is that a Christmas tree? Lol, while that's nice, its not quite as hard as the fractal generator, since its always the same size. I could make that same code, probably. The fractal generator is supposed to ask for a number, and print out a level of complexity based on the number you give it, like 1=the small fractal, and if I know hackerrank testers at all, they'd be cocks, and give something ludicrous like "8362", or try to segfault it with "65536" to try and break it.

Code:

			#!/bin/bash -i

for i in 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ; do
  cols[$i]="`tput setaf $i`"
done

L=99
P=100000000
Q=$(( P/100 ))
X=$(( Q*320 / (`tput cols` - 1) ))
Y=$(( Q*210 / `tput lines` ))
y=$(( Q*-105 ))
v=$(( Q*-220 ))
x=$v
 
while (( y<105*Q )); do
 
  while (( x<P )); do
    (( a=b=i=c=0 ))
    while (( a*a + b*b < 4*P**2 && i++ < L )); do
      (( c=a,
         a=(a**2 - b**2)/P + x,
         b=2*b*c/P + y ))
    done
 
    if (( i >= L )); then j=0; else (( j=i%16 )); fi
 
    if (( j>7 )); then (( k=1, j-= 8 )); else k=0; fi
 
    printf "${cols[$j]}#"
 
    (( x+=X ))
  done
  tput sgr0

  (( x=v, y+=Y ))
done

I solved it By the way:

Code:

			read n;
declare -A matrix
num_rows=63
num_columns=100

for ((i=1;i<=num_rows;i++)) do
    for ((j=1;j<=num_columns;j++)) do
        matrix[$i,$j]="_";
    done
done

function drawTree()
{
    local x=$1;
    local y=$2;
    local depth=$3;
    local height=$4;

    if [ $depth -eq 0 ]; then
        return 1;
    fi 
    local hh=$((height/2));
    for ((i=1;i<=hh;i++)) do
        matrix[$(($y+$i)),$x]="1";
        matrix[$(($y+$hh+$i)),$(($x-$i))]="1";
        matrix[$(($y+$hh+$i)),$(($x+$i))]="1";
    done
    drawTree $((x-hh)) $((y+height)) $((depth-1)) $hh;
    drawTree $((x+hh)) $((y+height)) $((depth-1)) $hh;
}

drawTree 50 0 $n 32

for ((i=num_rows;i>=0;i--)) do
    for ((j=1;j<=num_columns;j++)) do
        printf '%s' "${matrix[$i,$j]}";
    done
    printf '\n';
done

Algorithms are good challenges when you're learning (better than knowing a lot of languages) IMO.
Never dug deep into Bash as other languages tended to do what I needed.

Good job solving it!

Barcelona

Joom

Barcelona

Joom

Barcelona

ZiNgA BuRgA