We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Search
  4. Count Luck
  5. Discussions

Count Luck

Sort 135 Discussions, By:

votes

  • 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.

            • saketk21 + 0 comments

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

            • iykekings + 0 comments

              Stack is faster especially when the matrix gets bigger.

    • 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.
    3

    All 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.

  • LinkedHK + 1 comment

    I managed to beat it! Thanks for a great challenge. I was a dumb in graphs searching algorithms, now I feel myself more "competent" in this topic xD

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

Load more conversations