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.
I fully solved it using Bellman-Ford and a full graph structure. It's a very fat solution and could use a lot of cleaning up, there were quite a few caveats to handle. Overall this challenge was really hard for me, I really don't think it should be marked easy, even though I am amateurish with graphs (as this challenge has thoroughly proven). If you're having a hard time like I did, don't give up! You CAN do it! The test cases were extremely well thought out, don't try to 'cheat' your way through it - if the solution doesn't seem elegant it probably won't pass further test cases.
Here is the Bellman-Ford function I used - hopefully it will help:
// No
bool bellmanFord( Graph* graph, int src, vector<int>& dist, vector<pair<int,int>>* prev = nullptr )
{
int V = graph->vertices.size();
int E = graph->edges.size();
dist.resize( V );
if( prev ) prev->resize( V );
// Step 1: Initialize distances from src to all other vertices
// as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
(*prev)[src] = make_pair(-1,-1);
// Step 2: Relax all edges |V| - 1 times. A simple shortest
// path from src to any other vertex can have at-most |V| - 1
// edges
for (int i = 0; i < V-1; i++)
{
for (int k = 0; k < E; k++)
{
int u = graph->edges[k].a->index;
int v = graph->edges[k].b->index;
int weight = graph->edges[k].distance;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
{
dist[v] = dist[u] + weight;
if( prev )
(*prev)[v] = make_pair( u, k );
}
}
}
// Step 3: check for negative-weight cycles. The above step
// guarantees shortest distances if graph doesn't contain
// negative weight cycle. If we get a shorter path, then there
// is a cycle.
for (int i = 0; i < E; i++)
{
int u = graph->edges[i].a->index;
int v = graph->edges[i].b->index;
int weight = graph->edges[i].distance;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
{
return false;
}
}
return true;
}
Note that this is a modified version of the function provided here:
http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
Please take the time to read this artictle and watch some videos explaining the algorithm, it takes a bit to grasp fully but it's good stuff to know! I'll leave it to you to figure out how to interpret a path from the information provided here.
You will need to handle several edge cases. What happens if it is more efficient to roll a higher number than do a hop? For instance, if we roll 2 and have a ladder that takes us to 4, we might as well have rolled a 5 or 6 (assuming no snakes). Also bear in mind situations where there are 6+ snakes with no empty slots between them - unless there is a ladder to bypass them, that grid is unsolvable. Bear in mind, also, the case in which you might take a ladder - then a snake - to save on distance costs... but could have had fewer ROLLS by bypassing the ladder entirely!
Again, best of luck and keep at it! I wanted to quit several times but forced myself to keep going and I'm glad I did. =D
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Snakes and Ladders: The Quickest Way Up
You are viewing a single comment's thread. Return to all comments →
I fully solved it using Bellman-Ford and a full graph structure. It's a very fat solution and could use a lot of cleaning up, there were quite a few caveats to handle. Overall this challenge was really hard for me, I really don't think it should be marked easy, even though I am amateurish with graphs (as this challenge has thoroughly proven). If you're having a hard time like I did, don't give up! You CAN do it! The test cases were extremely well thought out, don't try to 'cheat' your way through it - if the solution doesn't seem elegant it probably won't pass further test cases.
Here is the Bellman-Ford function I used - hopefully it will help:
Note that this is a modified version of the function provided here: http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ Please take the time to read this artictle and watch some videos explaining the algorithm, it takes a bit to grasp fully but it's good stuff to know! I'll leave it to you to figure out how to interpret a path from the information provided here.
You will need to handle several edge cases. What happens if it is more efficient to roll a higher number than do a hop? For instance, if we roll 2 and have a ladder that takes us to 4, we might as well have rolled a 5 or 6 (assuming no snakes). Also bear in mind situations where there are 6+ snakes with no empty slots between them - unless there is a ladder to bypass them, that grid is unsolvable. Bear in mind, also, the case in which you might take a ladder - then a snake - to save on distance costs... but could have had fewer ROLLS by bypassing the ladder entirely!
Again, best of luck and keep at it! I wanted to quit several times but forced myself to keep going and I'm glad I did. =D