Merge remote-tracking branch 'upstream/master'

1 files changed, 54 insertions, 0 deletions

diff --git a/challenge-213/roger-bell-west/python/ch-2.py b/challenge-213/roger-bell-west/python/ch-2.py
new file mode 100755
index 0000000000..14b9bc35a9
--- /dev/null
+++ b/challenge-213/roger-bell-west/python/ch-2.py
@@ -0,0 +1,54 @@
+#! /usr/bin/python3
+
+from itertools import islice
+from collections import deque,defaultdict
+
+# https://docs.python.org/3/library/itertools.html
+def sliding_window(iterable, n):
+    # sliding_window('ABCDEFG', 4) --> ABCD BCDE CDEF DEFG
+    it = iter(iterable)
+    window = deque(islice(it, n), maxlen=n)
+    if len(window) == n:
+        yield tuple(window)
+    for x in it:
+        window.append(x)
+        yield tuple(window)
+
+def shortestroute(r0, origin, destination):
+  r = defaultdict(set)
+  for rt in r0:
+    for rp in sliding_window(rt, 2):
+      r[rp[0]].add(rp[1])
+      r[rp[1]].add(rp[0])
+  out = []
+  stack = deque()
+  stack.append([[origin], set([origin])])
+  while len(stack) > 0:
+    s = stack.popleft()
+    l = s[0][-1]
+    if l == destination:
+      out = s[0]
+      break
+    else:
+      for pd in r[l] - s[1]:
+        q = [s[0].copy(), s[1].copy()]
+        q[0].append(pd)
+        q[1].discard(pd)
+        stack.append(q)
+  return out
+      
+
+import unittest
+
+class TestShortestroute(unittest.TestCase):
+
+  def test_ex1(self):
+    self.assertEqual(shortestroute([[1, 2, 6], [5, 6, 7]], 1, 7), [1, 2, 6, 7], 'example 1')
+
+  def test_ex2(self):
+    self.assertEqual(shortestroute([[1, 2, 3], [4, 5, 6]], 2, 5), [], 'example 2')
+
+  def test_ex3(self):
+    self.assertEqual(shortestroute([[1, 2, 3], [4, 5, 6], [3, 8, 9], [7, 8]], 1, 7), [1, 2, 3, 8, 7], 'example 3')
+
+unittest.main()