From 7e7b56db42ceb8d2b8973eae678fa4b58d5d3659 Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Wed, 13 May 2009 23:32:40 -0500
Subject: add old solutions

---
 189.lua | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
 create mode 100644 189.lua

(limited to '189.lua')

diff --git a/189.lua b/189.lua
new file mode 100644
index 0000000..a4ae546
--- /dev/null
+++ b/189.lua
@@ -0,0 +1,27 @@
+local triangle_graph = {
+}
+
+--[[
+http://en.wikipedia.org/wiki/Graph_coloring#Computing_the_chromatic_polynomial
+]]
+function chromatic_polynomial(g, t)
+    local edge_start
+    for v1, edges in ipairs(g) do
+        for v2index, v2 in ipairs(edges) do
+            if v1 == v2 then return 0 end
+            if not edge_start then edge_start = v1 end
+        end
+    end
+
+    if edge_start == nil then return t^#g end
+
+    local edge_end = table.remove(g[edge_start])
+    local edge_removed = chromatic_polynomial(g, t)
+    table.insert(g[edge_start], edge_end)
+
+    -- need to contract the edge here
+    local edge_contracted = chromatic_polynomial(g, t)
+    -- and then fix it back up
+
+    return edge_removed - edge_contracted
+end
-- 
cgit v1.2.3-54-g00ecf