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
+ 0 comments def quickestWayUp(ladders, snakes): # Store snakes and ladders for lookup graph = {s[0]: s[1] for s in snakes} graph.update({l[0]: l[1] for l in ladders}) visited = set([1]) queue = [1] rolls = {} while queue: idx = queue.pop(0) for i in range(1, 7): # If neighbour is a snake/ladder, jump to its end point # else, increment as is neighbour = graph.get(idx + i, idx + i) if neighbour not in visited: rolls[neighbour] = rolls.get(idx, 0) + 1 visited.add(neighbour) queue.append(neighbour) if neighbour == 100: return rolls[neighbour] return -1
+ 0 comments C++ BFS Simple
typedef unordered_map<int,int> graph; graph buildGraph(vector<vector<int>> &input){ graph temp; for(const auto &x : input) temp[x[0]] = x[1]; return temp; } int quickestWayUp(vector<vector<int>> ladders, vector<vector<int>> snakes) { graph ladders_graph = buildGraph(ladders); graph snakes_graph = buildGraph(snakes); vector<int> visited(101, INT_MAX/2); visited[1] = 0; queue<int> que; que.push(1); while(!que.empty()){ auto idx = que.front(); que.pop(); for(int i = 1; i <= 6 && idx + i <= 100; i++){ auto j = idx + i; if(snakes_graph.count(j)) j = snakes_graph[j]; else if(ladders_graph.count(j)) j = ladders_graph[j]; if(visited[idx] + 1 < visited[j]){ visited[j] = visited[idx] + 1; que.push(j); } } } return visited[100] == INT_MAX/2 ? -1 : visited[100]; }
+ 0 comments Python 3:
class Graph: def __init__(self, ladders, snakes): self.adj_list = {i:set() for i in range(100)} special = {v-1:w-1 for v, w in ladders} special.update({v-1:w-1 for v, w in snakes}) for i in range(99): for j in range(i+1, min(100, i+7)): if i in special: continue self.adj_list[i].add(special.get(j, j)) def bfs(self): q = deque([(0, 0)]) vis = set([0]) while q: dist, v = q.popleft() if v == 99: return dist for u in self.adj_list[v]: if not u in vis: vis.add(u) q.append((dist+1, u)) return -1 def quickestWayUp(ladders, snakes): g = Graph(ladders, snakes) return g.bfs()
+ 0 comments it looks like a classical https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
but on a second thought it is easier to do a https://en.wikipedia.org/wiki/Breadth-first_search
and of course you don't need to construct the full graph, you can navigate it on the fly
+ 0 comments it looks like a classical https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
but on a second thought it is easier to do a https://en.wikipedia.org/wiki/Breadth-first_search
Load more conversations
Sort 232 Discussions, By:
Please Login in order to post a comment