Merge pull request #4196 from Abigail/abigail/week-115

Abigail/week 115

2 files changed, 100 insertions, 0 deletions

diff --git a/challenge-115/abigail/python/ch-1.py b/challenge-115/abigail/python/ch-1.py
new file mode 100644
index 0000000000..25e5541513
--- /dev/null
+++ b/challenge-115/abigail/python/ch-1.py
@@ -0,0 +1,51 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-1.py < input-file
+#
+
+import fileinput
+
+for line in fileinput . input ():
+    #
+    # Read in the data; create a graph: the first and last character
+    # of each string are the nodes, and there is a directed edge
+    # from the beginning to the end of the string.
+    #
+    strings = line . split ()
+    nodes   = {}
+    graph   = {}
+    for string in strings:
+        first = string [:1]
+        last  = string [-1:]
+        nodes [first] = 1
+        nodes [last]  = 1
+        if not first in graph:
+            graph [first] = {}
+        if not last in graph:
+            graph [last]  = {}
+        graph [first] [last] = 1
+
+    #
+    # Calculate the transitive closure using Floyd-Warshall
+    #
+    for k in nodes:
+        for i in nodes:
+            for j in nodes:
+                if not j in graph [j]:
+                    if k in graph [i] and j in graph [k]:
+                        graph [i] [j] = 1
+
+    #
+    # There is a cycle iff at least one node can be reached from itself
+    #
+    out = 0
+    for i in nodes:
+        if i in graph [i]:
+            out = 1
+
+    print (out)
diff --git a/challenge-115/abigail/python/ch-2.py b/challenge-115/abigail/python/ch-2.py
new file mode 100644
index 0000000000..a3b040b832
--- /dev/null
+++ b/challenge-115/abigail/python/ch-2.py
@@ -0,0 +1,49 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-2.py < input-file
+#
+
+import fileinput
+
+NR_OF_DIGITS = 10
+
+for line in fileinput . input ():
+    #
+    # Parse the input, count digits
+    #
+    digits = []
+    for d in range (NR_OF_DIGITS):
+        digits . append (0)
+    for d in line . split ():
+        d = int (d)
+        digits [d] = digits [d] + 1
+
+    #
+    # Find the smallest even number
+    #
+    last = -1
+
+    for d in range (NR_OF_DIGITS - 2, -1, -2):
+        if digits [d] > 0:
+            last = d
+
+    #
+    # If we don't have an even number, skip
+    #
+    if last < 0:
+        continue
+    digits [last] = digits [last] - 1
+
+    #
+    # Print the rest of the digits, highest to lowest
+    #
+    for d in range (NR_OF_DIGITS - 1, 0, -1):
+        for i in range (digits [d]):
+            print (d, end = '')
+
+    print (last)