Evaluation-05 Hackerrank Evaluation on Stack

Hackerrank Evaluation on Stacks

E-Section
Dr. Santosh Pattar
July 15, 2023

About
This Hackerrank contest is for the 5th evaluation of Problem Solving with Data Structures
course (18ECSP102) for 50 marks on Chapter-03: Stacks and Recursion conducted on July
15th , 2023.

Contest URL
[Link]

Scoring
• A student‘s marks depends on the number of test cases a student‘s code submission
successfully passes.

• Multiple submissions are treated as invalid.

Problem Statement
Tom and Harry are playing a Stack game. Each of them gets one stack each, with ’n’ numbers.
Rules of the game are:

1. If the number picked by Tom is bigger than Harry then Harry removes the number that
was picked from his stack.

2. If the number picked by Tom is smaller than Harry then Tom removes the number that
was picked from his stack.

3. If both have the same number then both of them remove the number that was picked
from their stack.

– The game ends when at least one of them has no more elements to be picked.
– Looser of the game is one who has no more numbers left on his stack.
– Display the name of the winner (in small cases).
– If there is tie display tie.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 1 of 7

Evaluation-05 Hackerrank Evaluation on Stack

Constraints
• Each player has to give equal number of inputs.
• Minimum size of input should be five.
• Maximum size of input should be ten.

Input Format
The input numbers for both the stacks should be given in two separate lines.
• First line is input for Tom.
• Second line is input for Harry.
• Numbers are to be separated by single space.
• Last number in the stack should be followed by enter key (newline) not space.
Sample Input
1 6 4 2 3 4
5 6 3 2 1 3

Output Format
• For inputs that do not satisfy constraints display: invalid constraint.
• Display name of the winner in small cases.
• Check spelling: harry and tom.
• If game is tied display: tie.

Sample Input/Output
Sample-1 Sample-2
Input Input
1 2 3 4 5 6 1 2
4 3 1 7 3 2 5 3 4

Output Output
invalid game invalid game
Sample-3 Sample-4
Input Input
2 3 4 2 2 2 2 2 2 2
1 2 3 4 2 2 2 2 2 2

Output Output
invalid game tie

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 2 of 7

 Evaluation-05 Hackerrank Evaluation on Stack

Sample-5 Sample-6
Input Input
1 2 4 5 6 1 2 3 4 5
1 3 5 6 7 1 1 1 1 1

Output Output
tom harry

Program
1 /*
2 * @author : SPattar
3 * @date : Jul 4 , 2023
4 * @desc : Hackerrank Stack Evaluation
5 */
6
7 // Header Files .
8 # include < stdio .h >
9 # include < stdlib .h >
10
11 // Constant to hold the size of stack according to problem constraint .
12 # define SIZE 10
13

14 // Function to read the input in given format .

15 int readStack ( int * , int *) ;
16
17 // Stack Operation Functions .
18 void push ( int * , int * , int ) ;
19 void pop ( int *) ;
20 int peek ( int [] , int ) ;
21 int isEmpty ( int ) ;
22
23 // Function to Compare the numbers on the top of the stack .
24 int compare ( int , int ) ;
25

26 // Function to test the game rules .

27 void game ( int * , int * , int , int * , int * , int ) ;
28
29 // Driver Code .
30 int main ()
31 {
32 // Stack for Harry and Tom .
33 int H [ SIZE ] , T [ SIZE ];
34
35 // Top of respective stacks .
36 int tH = -1 , tT = -1;
37

38 // Number of elements on the respective stacks .

39 int n1 , n2 ;
40
41 // Read the players ’ input from STDIN
42 // This stores the input on the respective player ’s stack .
43 // And capture the size of the input .
44 n1 = readStack (H , & tH ) ;
45 n2 = readStack (T , & tT ) ;
46

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 3 of 7

 Evaluation-05 Hackerrank Evaluation on Stack

47 // Apply game rules and decide the result .

48 game (H , & tH , n1 , T , & tT , n2 ) ;
49
50 return 0;
51 }
52
53 /*
54 * @func : n = readStack ( stack , top )
55 * @param : 1. p -> base address of the stack .
56 * 2. t -> pointer to the top of stack .
57 * @return : n -> size of stack .
58 * @desc : Reads the input numbers from stack
59 * in "[ number ][ space - bar ]" format till the
60 * end of line . Further , it pushes the read
61 * number on the stack and returns the number
62 * of inputs read and stored on stack .
63 */
64 int readStack ( int *p , int * t )
65 {
66 int i = 0 , temp , n = 0;
67 char ch ;
68
69 /* Read the number and space - bar till newline is
70 encountered */
71 while ( 2 == scanf ( " % d % c " , & temp , & ch ) )
72 {
73 // Push the read number on top of stack .
74 push (p , t , temp ) ;
75
76 // Check if read character is newline .
77 if ( ch == ’\ n ’)
78 // If it is newline , stop reading .
79 break ;
80 i ++;
81 }
82
83 // Size of the input .
84 n = i + 1;
85
86 return n ;
87 }
88
89 /*
90 * @func : push ( stack , top , element )
91 * @param : 1. p -> base address of the stack .
92 * 2. t -> pointer to the top of stack .
93 * 3. e -> element to be pushed .
94 * @return : none .
95 * @desc : Pushes the given number on the top
96 * of the stack . If stack has overflow , then
97 * according to the problem constraint it is
98 * invalid input and thus terminate the program .
99 */
100 void push ( int *p , int *t , int e )
101 {
102 if ( * t == SIZE -1 )
103 {
104 printf ( " invalid game " ) ;
105 exit (1) ;
106 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 4 of 7

 Evaluation-05 Hackerrank Evaluation on Stack

107
108 * t += 1;
109 *( p + * t ) = e ;
110 }
111
112 /*
113 * @func : pop ( top )
114 * @param : t -> pointer to the top of stack .
115 * @return : none .
116 * @desc : Pops the element from the top of the stack .
117 */
118 void pop ( int * t )
119 {
120 if ( * t == -1 )
121 return ;
122
123 * t -= 1;
124 }
125

126 /*
127 * @func : element = peek ( stack , top )
128 * @param : 1. p -> base address of the stack .
129 * 2. t -> pointer to the top of stack .
130 * @return : element -> number on top of stack .
131 * @desc : Performs the peek operations and
132 * returns the number on top of the stack .
133 */
134 int peek ( int s [] , int t )
135 {
136 return s [ t ];
137 }
138
139 /*
140 * @func : flag = isEmpty ( top )
141 * @param : t -> pointer to the top of stack .
142 * @return : flag -> 1: stack is empty .
143 * flag -> 0: stack is not empty .
144 * @desc : Checks if the stack is empty or not .
145 */
146 int isEmpty ( int t )
147 {
148 if ( t == -1 )
149 return 1;
150 else
151 return 0;
152 }
153
154 /*
155 * @func : result = compare (x , y )
156 * @param : 1. x -> number on top of harry ’s stack
157 * 2. y -> number on top of tom ’s stack
158 * @return : result -> 0: both equal
159 * -> 1: Harry ’s number is greater than Tom
160 * -> 2: Tom ’s number is greater than Harry
161 * @desc : Compares the numbers on the top of both the stacks .
162 */
163 int compare ( int x , int y )
164 {
165 if ( x == y )
166 return 0;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 5 of 7

 Evaluation-05 Hackerrank Evaluation on Stack

167 else if ( x > y )

168 return 1;
169 else
170 return 2;
171 }
172
173 /*
174 * @func : game ( harry ’s stack , top of harry ’s stack , size of harry ’s stack
175 * tom ’s stack , top of tom ’s stack , size of tom ’s stack )
176 * @param : 1. Harry ’s stack and top -> H and tH .
177 * 2. Tom ’s stack and top -> T and tT .
178 * 3. Size of both stacks -> n1 and n2 .
179 * @return : none .
180 * @desc : Declares the result of game by verifying the rules .
181 * First it checks for valid input size according to
182 * the problem constraints . Then , it peeks into the
183 * top of the player ’s stack and compares the numbers .
184 * Based on the results of comparison the numbers are
185 * poped from the stack . Finally , it validates the stack
186 * contents and displays result .
187 */
188 void game ( int *H , int * tH , int n1 , int *T , int * tT , int n2 )
189 {
190 int hNum , tNum , c ;
191

192 if ( n1 != n2 || n1 < 5 || n2 < 5)

193 {
194 printf ( " invalid game " ) ;
195 return ;
196 }
197 else
198 {
199 while ( ! isEmpty (* tH ) || ! isEmpty (* tT ) )
200 {
201 // Peek the topmost element from both stacks .
202 hNum = peek (H , * tH ) ;
203 tNum = peek (T , * tT ) ;
204
205 // Compare the peeked numbers .
206 c = compare ( hNum , tNum ) ;
207
208 // Check for the numbers , i . e . , game rules .
209 if ( c == 0 )
210 {
211 // Both have chosen same numbers .
212 // Pop from both stacks .
213 pop ( tH ) ;
214 pop ( tT ) ;
215 }
216 else if ( c == 1 )
217 // Harry ’s number is greater .
218 // Pop from Tom ’s stack .
219 pop ( tT ) ;
220 else
221 // Tom ’s number is greater .
222 // Pop from Harry ’s stack .
223 pop ( tH ) ;
224
225 // After poping , check if any stack is empty .
226 if ( isEmpty (* tH ) || isEmpty (* tT ) )

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 6 of 7

 Evaluation-05 Hackerrank Evaluation on Stack

227 // If empty stop checking the game rules .

228 break ;
229 }
230 }
231
232 // Both stack are empty .
233 if ( isEmpty (* tH ) && isEmpty (* tT ) )
234 printf ( " tie " ) ;
235 // Tom ’s stack is empty but Harry ’s is not .
236 else if ( ! isEmpty (* tH ) && isEmpty (* tT ) )
237 printf ( " harry " ) ;
238 // Harry ’s stack is empty but Tom ’s is not .
239 else if ( isEmpty (* tH ) && ! isEmpty (* tT ) )
240 printf ( " tom " ) ;
241 // Both stack are not empty .
242 else
243 printf ( " invalid game " ) ;
244
245 return ;
246 }

Test Cases and Scores

Test Case Input Output Score
1 2 3 4 5 6
T1 invalid game 5
4 3 1 7 3 2 5
1 2
T2 invalid game 5
3 4
1 2 3 4 5
T3 invalid game 5
1 2 3
2 2 2 2 2 2
T4 tie 10
2 2 2 2 2 2
1 2 4 5 6
T5 tom 10
1 3 5 6 7
1 2 3 4 5
T6 harry 10
1 1 1 1 1
1 2 3 4 5
T6 tie 5
1 2 3 4 5
Total Score 50

Rubrics
• Test cases add up to 50 marks.

• 50 marks converted to 30 marks.

• 30 marks converted to final 12 marks.

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 7 of 7