Merge pull request #4548 from Abigail/abigail/week-121

Abigail/week 121

1 files changed, 69 insertions, 0 deletions

diff --git a/challenge-121/abigail/lua/ch-2.lua b/challenge-121/abigail/lua/ch-2.lua
new file mode 100644
index 0000000000..72ad70f2eb
--- /dev/null
+++ b/challenge-121/abigail/lua/ch-2.lua
@@ -0,0 +1,69 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-2.lua < input-file
+--
+
+function shortest_path (matrix, from, to, exclude) 
+    if (1 + #exclude == #matrix) then
+        return matrix [from] [to], {to}
+    end
+
+    local shortest = 10 ^ 999   -- Should be big enough...
+    local sh_path  = {}
+    local new_exclude = {}
+    for k, v in pairs (exclude) do
+        new_exclude [k] = v
+    end
+    new_exclude [from] = 1
+
+    local next
+    for next = 1, #matrix do
+        if next == from or next == to or new_exclude [next] == 1 then
+            goto end_loop
+        end
+
+        local length
+        local path
+        length, path = shortest_path (matrix, next, to, new_exclude)
+        if  shortest > length + matrix [from] [next] then
+            shortest = length + matrix [from] [next]
+            sh_path = {}
+            sh_path [1] = next
+            for k, v in pairs (path) do
+                sh_path [k + 1] = v
+            end
+        end
+        ::end_loop::
+    end
+
+    return shortest, sh_path
+end
+
+
+matrix = {}
+
+for line in io . lines () do
+    row = {}
+    for d in line : gmatch ("%d+") do
+        table . insert (row, d)
+    end
+    table . insert (matrix, row)
+end
+
+
+local length
+local path
+length, path = shortest_path (matrix, 1, 1, {})
+
+print (length)
+io . write ("0")
+for i = 1, #path do
+    io . write (" ")
+    io . write (path [i] - 1)
+end
+print ("")