- Practice
- Algorithms
- Search
- Count Luck
- Discussions

# Count Luck

# Count Luck

manni991 + 4 comments ron won't be impressed very much, once he get to know hermione used backtracking

tcharding + 0 comments Two thumbs up

rajeev11430 + 1 comment True that. Stack Overflows.

zainul118 + 2 comments solved the maze using backtracking but how to count the guesses??

amsborse + 0 comments did it by brute force if else if else :P

saketk21 + 1 comment Everytime you push a branching node on the final path on the stack, increment the count. At the end, if the count equals K, then Ron impresses Hermione.

snaran + 1 comment Should we use a stack or a queue? I think either would work, but not sure which would be faster. In my solution, the thing I pushed onto the queue was the node (x, y position) plus the, number of intersection encountered to have reached that point.

In the case that there are multiple routes to the final point, it might be more complicated.

saketk21 + 0 comments Either works. Just that the question suggests backtracking and so I used a stack :)

rwan7727 + 1 comment Global vars are char **a, int numCrossJunctions, bool found

Function move with r,c,n,m as inputs:

`if (found) return; int numPath=0; //try up if ((r-1)>=0) { // check for boundary first if (a[r-1][c]=='.') { a[r][c]='X'; numPath++; move(r-1,c,n,m); } else if (a[r-1][c]=='*') { numPath++; found=true; } } //try down if ((r+1)<n) { // check for boundary first if (a[r+1][c]=='.') { a[r][c]='X'; numPath++; move(r+1,c,n,m); } else if (a[r+1][c]=='*') { numPath++; found=true; } } //try left if ((c-1)>=0) { // check for boundary first if (a[r][c-1]=='.') { a[r][c]='X'; numPath++; move(r,c-1,n,m); } else if (a[r][c-1]=='*') { numPath++; found=true; } } //try right if ((c+1)<m) { // check for boundary first if (a[r][c+1]=='.') { a[r][c]='X'; numPath++; move(r,c+1,n,m); } else if (a[r][c+1]=='*') { numPath++; found=true; } } if (found && (numPath>1)) numCrossJunctions++;`

In main:

`int t; cin >> t; for (int test=0;test<t;test++) { int n,m; cin >> n >> m; // allocate memory for grid a=(char **)malloc(sizeof(char *)*n); a[0]=(char *)malloc(sizeof(char)*n*m); for(int i=0;i<n;i++) a[i]=(*a+m*i); // input grid & k int startrow,startcol; for (int r=0;r<n;r++) for (int c=0;c<m;c++) { cin >> a[r][c]; if (a[r][c]=='M') { // found M position startrow=r; startcol=c; } } int k; cin >> k; // process found=false; numCrossJunctions=0; move(startrow,startcol,n,m); // start from M // Determine output if (numCrossJunctions==k) cout << "Impressed" << endl; else cout << "Oops!" << endl; // free grid free(a[0]); free(a); }`

snaran + 0 comments But if you backtrack, you have to revert numCrossJunctions to what it was? My solution was to have a Queue of paths (which is a point plus the number of interesections to reach this point), and if there is more than 1 direction, then add both new points to the queue.

Do you have to keep track of going back to the point you came from? So I also marked a point as visited, but not 100% sure if this is necessary.

snaran + 0 comments She didn't use backtracking. We used backtracking, queues with multiple paths, etc to prove her right, but the wand was magic.

m_a_r_c_e_li_n_o + 15 comments Piggybacking on a few complaints made here, I think that labeling this challenge as "easy" is a bit misleading. The amount of rational required to solve it seems fairly close to another challenge in this section called "Connected Cell in a Grid" and that one is labeled as "Moderate". Regardless, easy or not, this challenge is a great quest and the sum of points awarded is reasonable.

For those struggling, try a recursive "Depth First Search" approach where you bubble up information about the amount of forks in the path leading up to the*exit point*, denoted as a***in the grid. There will only be one path to the*exit point*, all others will terminate in a dead end and you should discard all information related to those useless paths.

Here's an informal test case to help you catch some edge cases:

`5`

3 6

*.M...

.X.X.X

XXX...

1

3 6

*..M..

.X.X.X

XXX...

2

3 6

*M....

.X.X.X

XXX...

1

3 6

*....M

.X.X.X

XXX...

2

3 6

*.....

.X.X.X

XXX.M.

3All five should return "Impressed".

arkalyk + 0 comments This test saved me!

piniMeister + 0 comments Cheers mate!

shshnk28 + 0 comments These simple test cases saved my day. Thanks!

ankit711m + 0 comments Bazinga!!

AnuragSinha + 0 comments Thanks, very helpful!

xuhuanze + 0 comments Thanks. Corner cases are much more helpful than those large tests.

MrAsimov + 0 comments thank you.

I_am_Nobody + 1 comment Can u please point out the error or make necessary corrections?

#include<bits/stdc++.h> #define ll long long #define ull unsigned long long int #define mod 10000007 #define rep(a,b,c) for(int i=a;i<=b;i+=c) #define repi(a,b,c) for(int i=a;i>=b;i-=c) #define lb lower_bound #define ub upper_bound #define pushb push_back #define popb pop_back using namespace std; char f[101][101]; bool v[101][101]; int k,Count=0; void dfs(int n,int m,int i,int j) { v[i][j]=1; if(f[i][j+1]=='*') return ; else if(f[i][j-1]=='*') return ; else if(f[i-1][j]=='*') return ; else if(f[i+1][j]=='*') return ; if(!v[i][j-1]&&!v[i+1][j]&&f[i][j-1]=='.'&&f[i+1][j]=='.') Count++; else if(!v[i][j-1]&&!v[i-1][j]&&f[i][j-1]=='.'&&f[i-1][j]=='.') Count++; else if(!v[i][j-1]&&!v[i][j+1]&&f[i][j-1]=='.'&&f[i][j+1]=='.') Count++; else if(!v[i+1][j]&&!v[i][j+1]&&f[i+1][j]=='.'&&f[i][j+1]=='.') Count++; else if(!v[i+1][j]&&!v[i-1][j]&&f[i+1][j]=='.'&&f[i-1][j]=='.') Count++; else if(!v[i][j+1]&&!v[i-1][j]&&f[i][j+1]=='.'&&f[i-1][j]=='.') Count++; if(!v[i+1][j]&&f[i+1][j]=='.') dfs(n,m,i+1,j); if(!v[i-1][j]&&f[i-1][j]=='.') dfs(n,m,i-1,j); if(!v[i][j-1]&&f[i][j-1]=='.') dfs(n,m,i,j-1); if(!v[i][j+1]&&f[i][j+1]=='.') dfs(n,m,i,j+1); } int main() { int t; cin>>t; while(t--) { int n,m,i,j; cin>>n>>m; Count=0; memset(f,'X',sizeof(f)); memset(v,false,sizeof(v)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { cin>>f[i][j]; } cin>>k; int I,J; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(f[i][j]=='M') { I=i; J=j; if(!v[i][j]) { dfs(n,m,i,j); } } } if(Count==k) cout<<"Impressed"<<endl; else cout<<"Oops!"<<endl; } return 0; }

VasilyM + 0 comments What obfuscator did you use?

schen175 + 0 comments Make sure your not including the dest node when your counting the # of nodes with more than 1 fork

RahulWadekar + 0 comments Thanks. These test cases were very helpful.

john_canessa + 0 comments Harder than expected. Love it. Keep them coming !!!

nirvik1993 + 0 comments these were extremely helpful !

abhinitsati + 0 comments [deleted]sidajwalia + 0 comments this set helped me.

MrMafia + 0 comments I think they have changed the test cases now because we should not count the wand swings after reaching the destination.

AKSaigyouji + 1 comment This problem is more straightforward than I think most (even the problem setter) realize.

Do a simple BFS or DFS to find the unique path from the start to the exit. Then, for each point in the path excluding the start and finish, count the number of neighbors. If the number of neighbors is more than 2, that's a fork, and you can add 1 to your running total. Finally, add another 1 if the start has more than 1 neighbor.

No backtracking or recursion. Just a BFS to find a path, then a linear pass over the path to count forks.

tombombadillo + 0 comments Yesss.

I did the same, completed within an hour, came to the comments to look for more elegant solutions, only to find everyone talking about complicated recursion, backtracking algorithms and complaining about the dificulty hahahah.

Matt_Scandale + 2 comments This challenge should be worth 100 points (not 45) and it should be classified as "Advanced" (not "Easy"). It took me 10 hours and nearly 200 lines of code. And I still didn't pass all the test cases. And it should be named something like "Navigate the Maze" which would be more descriptive.

AllisonP + 1 comment Thank you for the feedback. The challenge difficulty has been raised to

*Moderate*, and the point value has been raised to*50*. Due to the relatively high rate of success (*80%*) for this challenge, it would not qualify as an*Advanced*challenge.Arun_DMan + 0 comments I think success rate should not be a measure of difficulty, or I can say that difficulty of a question should not depend on its success rate.

shreyansh2495 + 0 comments use backtrack its easy buddy

ravioactive + 3 comments My code fails for the same particular input inside more than one test case, which I managed to identify after unlocking the test case. It is the last input in test case 2, and last but 3rd input in test case 6. I do not want to spoil it for other participants, so I am reluctant to give the input here, but the admins should know which one I'm referring. The given value of K in the test case is 294, while my code is returning 479. It works for all the other cases, except this, so I am not sure what am I getting wrong.

My submission is the following: https://www.hackerrank.com/challenges/count-luck/submissions/code/11456984

Can anyone help me out please?

EDIT: got it, I'm counting all the branches, instead of the only path which leads to the exit. That is a good test case.

ayushchatur + 0 comments i am getting same Wrong amswer with my submission can u explain what is wrong in the logic ... briefly

Titas_Nandi + 1 comment I am stuck at the same place! Can you help me figure it out?

ayushchatur + 0 comments check the boundary conditions thoroughly ... and the logic ... there is a glitch in the first logic that hits the mind ...download input test cases and run thoroughly .. u can also look into my solution ..but i wont recommend that ... it is a very good problem and i advise you to not to give up .!! and try even harder and better

ashishsahu2008 + 0 comments [deleted]

ignorantCity + 1 comment Not too bad once you read up on backtracking - was able to come up with a relatively short recursion to solve the maze then use the solution as an input to check the 'chance' condition for the final output.

Found this to be quite helpful: https://www.cs.bu.edu/teaching/alg/maze/

dgpskundu + 0 comments thanks for the link:)

iamnvd + 2 comments How does this question even qualify as easy. Or am I missing something. Please Help.

prabodhprakashAsked to answer + 1 comment I have not solved the question, but from what I undestood - she always go on the right path and you have to tell the number of points where she had multiple choices to chose a path from.

For e.g. If the path is like A-->B and B-->C and B-->D

and A-->B-->C is the right path, then at B she had two choices and she would use her wand.

One option could be using shortest path algorithm to find out the shortest (which is also the only path) possible path and in that path you have to find number of points where there were multiple choices of path selection.

I would also say that a simple DFS will also solve the question (given there is only one unique path - which makes it tree and not a graph).

AllisonP + 0 comments The challenge difficulty is now upgraded to

*Moderate*.

nikweber + 0 comments Yes - this was a fun problem! Thank you!

lonewolff + 0 comments wasnt too tough but took a lot of time than expected... a little trick.. instead of checking for boundary conditions or using exception handling just surround the matrix by a "X" outer block. all the best to others.

Sort 107 Discussions, By:

Please Login in order to post a comment