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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Count Luck
  5. Discussions

Count Luck

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 171 Discussions, By:

votes

Please Login in order to post a comment

  • manni991
    7 years ago+ 4 comments

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

    141|
    Permalink
    View more Comments..
  • m_a_r_c_e_li_n_o
    6 years ago+ 16 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".

    42|
    Permalink
    View more Comments..
  • AKSaigyouji
    6 years ago+ 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.

    17|
    Permalink
  • LinkedHK
    8 years ago+ 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

    12|
    Permalink
  • ignorantCity
    6 years ago+ 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/

    8|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature