From ae9e83f5d7eb2bf6860ec88785b7216e98f53adf Mon Sep 17 00:00:00 2001 From: William Carroll Date: Fri, 20 Mar 2020 16:49:49 +0000 Subject: Solve InterviewCake.com's mesh-message problem Write a function that returns the shortest path between nodes A and B in an unweighted graph. I know two algorithms for finding the shortest path in a *weighted* graph: - Use a heap as a priority queue instead of the regular queue that you would use when doing a BFT. This is called Dijkstra's algorithm. You can also use Dijkstra's algorithm in an unweight graph by imaginging that all of the weights on the edges are the same value (e.g. 1). - Map the weighted graph into an unweighted graph by inserting N nodes between each node, X and Y, where N is equal to the weight of the edge between X and Y. After you map the weighted graph into an unweighted graph, perform a BFT from A to B. A BFT will always find the shortest path between nodes A and B in an unweighted graph. I had forgotten that a BFT in an unweighted graph will always return the shortest path between two nodes. I learned two things from InterviewCake.com's solution: 1. I remembered that a BFT in an unweighted graph will return the shortest path (if one exists). 2. I learned to use a dictionary to store the edge information and then back-tracking to reconstruct the shortest path. --- scratch/deepmind/part_two/mesh-message.py | 183 ++++++++++++++++++++++++++++++ 1 file changed, 183 insertions(+) create mode 100644 scratch/deepmind/part_two/mesh-message.py (limited to 'scratch/deepmind/part_two/mesh-message.py') diff --git a/scratch/deepmind/part_two/mesh-message.py b/scratch/deepmind/part_two/mesh-message.py new file mode 100644 index 000000000000..a265296ab066 --- /dev/null +++ b/scratch/deepmind/part_two/mesh-message.py @@ -0,0 +1,183 @@ +import unittest +from collections import deque +from heapq import heappush, heappop + + +################################################################################ +# InterviewCake.com +################################################################################ +# construct_path :: Map String String -> String -> String -> [String] +def construct_path(paths, beg, end): + """ + Reconstruct the path from `beg` to `end`. + """ + result = [] + current = end + + print(paths) + print(beg, end) + print('-----') + while current: + result.append(current) + current = paths[current] + + result.reverse() + return result + + +def get_path_ic(graph, beg, end): + """ + InterviewCake uses a dictionary and back-tracking to store and reconstruct + the path instead of storing the path as state on each node. + This reduces the memory costs. See get_path_bft for an example of this less + optimal solution. + """ + if beg not in graph: + raise Exception('Origin node absent from graph.') + + if end not in graph: + raise Exception('Destination node absent from graph.') + + q = deque() + q.append(beg) + paths = {beg: None} + + while q: + node = q.popleft() + + if node == end: + print(graph) + return construct_path(paths, beg, end) + + for x in graph[node]: + if x not in paths: + paths[x] = node + q.append(x) + + return None + + +################################################################################ +# Per-node state +################################################################################ +def get_path_bft(graph, beg, end): + """ + Here we find the shortest path from `beg` to `end` in `graph` by doing a BFT + from beg to end and storing the path state alongside each node in the queue. + """ + if beg not in graph: + raise Exception('Origin node absent from graph.') + + if end not in graph: + raise Exception('Destination node absent from graph.') + + q = deque() + seen = set() + q.append([beg]) + + while q: + path = q.popleft() + node = path[-1] + seen.add(node) + + if node == end: + return path + + for x in graph[node]: + if x not in seen: + q.append(path + [x]) + + +################################################################################ +# Dijkstra's Algorithm +################################################################################ +def get_path(graph, beg, end): + """ + Here we find the shortest path using Dijkstra's algorithm, which is my + favorite solution. + """ + if beg not in graph: + raise Exception( + 'The origin node, {}, is not present in the graph'.format(beg)) + + if end not in graph: + raise Exception( + 'The origin node, {}, is not present in the graph'.format(end)) + + q = [] + seen = set() + heappush(q, (1, [beg])) + + while q: + weight, path = heappop(q) + node = path[-1] + seen.add(node) + + if node == end: + return path + + for x in graph[node]: + if x not in seen: + heappush(q, (weight + 1, path + [x])) + + return None + + +# Tests +class Test(unittest.TestCase): + def setUp(self): + self.graph = { + 'a': ['b', 'c', 'd'], + 'b': ['a', 'd'], + 'c': ['a', 'e'], + 'd': ['b', 'a'], + 'e': ['c'], + 'f': ['g'], + 'g': ['f'], + } + + def test_two_hop_path_1(self): + actual = get_path(self.graph, 'a', 'e') + expected = ['a', 'c', 'e'] + self.assertEqual(actual, expected) + + def test_two_hop_path_2(self): + actual = get_path(self.graph, 'd', 'c') + expected = ['d', 'a', 'c'] + self.assertEqual(actual, expected) + + def test_one_hop_path_1(self): + actual = get_path(self.graph, 'a', 'c') + expected = ['a', 'c'] + self.assertEqual(actual, expected) + + def test_one_hop_path_2(self): + actual = get_path(self.graph, 'f', 'g') + expected = ['f', 'g'] + self.assertEqual(actual, expected) + + def test_one_hop_path_3(self): + actual = get_path(self.graph, 'g', 'f') + expected = ['g', 'f'] + self.assertEqual(actual, expected) + + def test_zero_hop_path(self): + actual = get_path(self.graph, 'a', 'a') + expected = ['a'] + self.assertEqual(actual, expected) + + def test_no_path(self): + actual = get_path(self.graph, 'a', 'f') + expected = None + self.assertEqual(actual, expected) + + def test_start_node_not_present(self): + with self.assertRaises(Exception): + get_path(self.graph, 'h', 'a') + + def test_end_node_not_present(self): + with self.assertRaises(Exception): + get_path(self.graph, 'a', 'h') + + +unittest.main(verbosity=2) -- cgit 1.4.1