diff options
author | Jesse Luehrs <doy@tozt.net> | 2009-05-15 10:05:49 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2009-05-15 10:05:49 -0500 |
commit | db1d685414ac9257082803be8af9b27a088d8938 (patch) | |
tree | 92bba99d4ada3fab21ef64cea35181a75986e2bb /189-broken.lua | |
parent | 5afab29454b75fa55cc54fc32fa39b20aea75134 (diff) | |
download | projecteuler-db1d685414ac9257082803be8af9b27a088d8938.tar.gz projecteuler-db1d685414ac9257082803be8af9b27a088d8938.zip |
mark these old ones as non-working
Diffstat (limited to '189-broken.lua')
-rw-r--r-- | 189-broken.lua | 27 |
1 files changed, 27 insertions, 0 deletions
diff --git a/189-broken.lua b/189-broken.lua new file mode 100644 index 0000000..a4ae546 --- /dev/null +++ b/189-broken.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 |