- 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 + 2 comments 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.

rwan7727 + 2 comments 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.

aditosh007 + 0 comments The Solution in Python3!

#HackerRank: "https://www.hackerrank.com/challenges/count-luck/problem" def countLuck(matrix, k): turns = 0 ron = positionRon(grid) size = findLargestRegion(grid, ron[0], ron[1], turns) if size==k: return "Impressed" return "Oops!" def positionRon(matrix): for i in range(rows): for j in range(cols): if matrix[i][j] == 'M': return [i,j] def findLargestRegion(grid, row, col, turns): if row<0 or row>=rows or col<0 or col>=cols: return None elif grid[row][col]=='X': return None elif grid[row][col]=='*': return turns path = 0 if not row-1<0: if grid[row-1][col]=='.' or grid[row-1][col]=='*': path += 1 if not row+1>=rows: if grid[row+1][col]=='.' or grid[row+1][col]=='*': path += 1 if not col-1<0: if grid[row][col-1]=='.' or grid[row][col-1]=='*': path += 1 if not col+1>=cols: if grid[row][col+1]=='.' or grid[row][col+1]=='*': path += 1 if path>1: turns+=1 grid[row][col]='1' else: grid[row][col]='0' for x in [[row-1, col], [row+1, col], [row, col-1], [row, col+1]]: r = x[0] c = x[1] if r<0 or r>=rows or c<0 or c>=cols: continue if grid[r][c] == '1' or grid[r][c] == '0': continue size = findLargestRegion(grid, r, c, turns) #RECURSION CALL! if size==None: continue else: return size t = int(input()) for _ in range(t): rows, cols = map(int,input().split(' ')) grid = [] for i in range(rows): grid.append(list(input())) k = int(input()) print(countLuck(grid,k))

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.

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:)

Sort 135 Discussions, By:

Please Login in order to post a comment