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.
Snakes and Ladders: The Quickest Way Up
Snakes and Ladders: The Quickest Way Up
Sort by
recency
|
250 Discussions
|
Please Login in order to post a comment
"Snakes and Ladders: The Quickest Way Up" problem, we can use the Breadth-First Search (BFS) algorithm. Below is the PHP solution for this problem:
Explanation:
Initialization:
board
array stores the effect of ladders and snakes on each cell.queue
is used for BFS, initialized with the starting position (1, 0) representing the start of the board and 0 moves.visited
array keeps track of visited cells to avoid revisiting them.Setup Ladders and Snakes:
BFS to Find Shortest Path:
Handling Input:
readInput
function reads the input from standard input and processes it.quickestWayUp
function for each test case and print the result.Pthon
BFS
Rust is generally a bit verbose. The execution time is nice, though. time ./target/release/rust < input_1.txt (test case #1) real 0m0.016s user 0m0.006s sys 0m0.008s
I noticed HackerRank is passing on all cases for a code that is incorrect.
To solve this problem, I implemented the following code:
But it resulted in a wrong answer for the following input:
You can notice I have a set of visited nodes, and that I will process each node of the graph only once. Also, I'm processing the nodes in the order they are being added to the queue.
When processing node 1, I will add to the queue nodes from 2 to 7 with one roll. When processing node 6, I will add node 12 in the queue with two rolls. But I can arrive in node 12 with only one roll, by falling on node 7 after the first roll and use the ladder. Since node 12 was first added to the queue with 2 rolls, I will process it using two rolls, and will not process it again with 1 roll (I have a continue on the code).
For the input I provided, it will result in an answer of 18. And HackerRank is accepting the solution.
But I can arrive on node 100 with only 13 rolls. The following method is correct and generates the answer of 13.
from collections import deque def quickestWayUp(ladders, snakes):