Post Reply 
Think you're good at bash? Think again!
Author Message
Barcelona
Too Young To Care

Posts: 1,247.2872
Threads: 88
Joined: 10th Jul 2010
Reputation: -0.02892
E-Pigs: 60.4042
Offline
Post: #1
Think you're good at bash? Think again!
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
**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!

[Image: A73TX.png]
Quotes That Made Me Lol
Joomla12 Wrote:Who are you?
(02/08/2011 08:26 AM)eKusoshisut0 Wrote:  ┻┻ ︵ヽ(`Д´)ノ︵ ┻┻
Previous Signatures
First Signature Wrote:Rep me up or I'll GENTLY CARESS you in the booty!
Second Signature Wrote:Studies have shown that for everyone person that doesn't rep me up, an angel gets a hernea.
Third Signature Wrote:Dead Trademark91 killed me.
Fourth Signature Wrote:Windows Proud
Fifth Signature Wrote:I'm waiting for someone to chime in with an arrow. Any tamed wolves you can be traced back to my forum signature.
Sixth Signature Wrote:[Image: 7hjyW.png]
(This post was last modified: 25/05/2016 11:48 PM by Barcelona.)
25/05/2016 11:42 PM
Find all posts by this user Quote this message in a reply
Joom
WOOP
Worlds End

Posts: 4,206.7320
Threads: 417
Joined: 20th Mar 2009
Reputation: 5.41709
E-Pigs: 134.1772
Offline
Post: #2
RE: Think you're good at bash? Think again!
Heh...

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/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 " "


[Image: ROVBdMh.png]
3DS Friend Code: 5000-6045-4964
(This post was last modified: 27/05/2016 09:47 AM by Joom.)
27/05/2016 09:47 AM
Find all posts by this user Quote this message in a reply
Barcelona
Too Young To Care

Posts: 1,247.2872
Threads: 88
Joined: 10th Jul 2010
Reputation: -0.02892
E-Pigs: 60.4042
Offline
Post: #3
RE: Think you're good at bash? Think again!
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.

[Image: A73TX.png]
Quotes That Made Me Lol
Joomla12 Wrote:Who are you?
(02/08/2011 08:26 AM)eKusoshisut0 Wrote:  ┻┻ ︵ヽ(`Д´)ノ︵ ┻┻
Previous Signatures
First Signature Wrote:Rep me up or I'll GENTLY CARESS you in the booty!
Second Signature Wrote:Studies have shown that for everyone person that doesn't rep me up, an angel gets a hernea.
Third Signature Wrote:Dead Trademark91 killed me.
Fourth Signature Wrote:Windows Proud
Fifth Signature Wrote:I'm waiting for someone to chime in with an arrow. Any tamed wolves you can be traced back to my forum signature.
Sixth Signature Wrote:[Image: 7hjyW.png]
(This post was last modified: 27/05/2016 01:20 PM by Barcelona.)
27/05/2016 01:19 PM
Find all posts by this user Quote this message in a reply
Joom
WOOP
Worlds End

Posts: 4,206.7320
Threads: 417
Joined: 20th Mar 2009
Reputation: 5.41709
E-Pigs: 134.1772
Offline
Post: #4
RE: Think you're good at bash? Think again!

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/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


[Image: ROVBdMh.png]
3DS Friend Code: 5000-6045-4964
27/05/2016 03:36 PM
Find all posts by this user Quote this message in a reply
Barcelona
Too Young To Care

Posts: 1,247.2872
Threads: 88
Joined: 10th Jul 2010
Reputation: -0.02892
E-Pigs: 60.4042
Offline
Post: #5
RE: Think you're good at bash? Think again!
[Image: ucmuCqw.png]

I solved it By the way:

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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


[Image: A73TX.png]
Quotes That Made Me Lol
Joomla12 Wrote:Who are you?
(02/08/2011 08:26 AM)eKusoshisut0 Wrote:  ┻┻ ︵ヽ(`Д´)ノ︵ ┻┻
Previous Signatures
First Signature Wrote:Rep me up or I'll GENTLY CARESS you in the booty!
Second Signature Wrote:Studies have shown that for everyone person that doesn't rep me up, an angel gets a hernea.
Third Signature Wrote:Dead Trademark91 killed me.
Fourth Signature Wrote:Windows Proud
Fifth Signature Wrote:I'm waiting for someone to chime in with an arrow. Any tamed wolves you can be traced back to my forum signature.
Sixth Signature Wrote:[Image: 7hjyW.png]
27/05/2016 05:07 PM
Find all posts by this user Quote this message in a reply
ZiNgA BuRgA
Smart Alternative

Posts: 17,023.4213
Threads: 1,174
Joined: 19th Jan 2007
Reputation: -1.71391
E-Pigs: 446.0333
Offline
Post: #6
RE: Think you're good at bash? Think again!
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!
(This post was last modified: 28/05/2016 05:59 AM by ZiNgA BuRgA.)
28/05/2016 05:59 AM
Visit this user's website Find all posts by this user Quote this message in a reply
Post Reply 


Forum Jump:


User(s) browsing this thread: 1 Guest(s)

 Quick Theme: