- Prepare
- Algorithms
- Search
- Count Luck
- Discussions
Count Luck
Count Luck
+ 4 comments ron won't be impressed very much, once he get to know hermione used backtracking
+ 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.
3All five should return "Impressed".
+ 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.
+ 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
+ 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/
Sort 171 Discussions, By:
Please Login in order to post a comment