Ramsey's theorem: Difference between revisions

Content added Content deleted

Inline

@@ Line 89: / Line 89: @@
 =={{header|D}}==
+{{trans|Tcl}}
-{{incorrect|D|The task has been changed to also require demonstrating that the graph is a solution.}}
+<lang d>import std.stdio, std.string, std.algorithm, std.range;
-{{trans|C}}
-<lang d>import std.stdio;
+/// Generate the connectivity matrix.
-void main() {
+immutable(char)[][] generateMatrix() {
-    enum size_t N = 17;
-    char[N][N] mat = '0';
+    immutable r = format("-%b", 53643);
+    return r.length.iota.map!(i => r[$-i .. $] ~ r[0 .. $-i]).array;
+}
+/**Check that every clique of four has at least one pair connected
-    foreach (immutable i, ref row; mat)
+and one pair unconnected. It requires a symmetric matrix.*/
-        row[i] = '-';
+string ramseyCheck(in char[][] mat) pure @safe
+in {
+    foreach (immutable r, const row; mat) {
+        assert(row.length == mat.length);
+        foreach (immutable c, immutable x; row)
+            assert(x == mat[c][r]);
+    }
+} body {
+    immutable N = mat.length;
+    char[6] connectivity = '-';
-    foreach (immutable e; 0 .. 4) {
+    foreach (immutable a; 0 .. N) {
-        foreach (immutable i, ref row; mat) {
+        foreach (immutable b; 0 .. N) {
-            immutable j = (i + (2 ^^ e)) % N;
+            if (a == b) continue;
-            row[j] = mat[j][i] = '1';
+            connectivity[0] = mat[a][b];
+            foreach (immutable c; 0 .. N) {
+                if (a == c || b == c) continue;
+                connectivity[1] = mat[a][c];
+                connectivity[2] = mat[b][c];
+                foreach (immutable d; 0 .. N) {
+                    if (a == d || b == d || c == d) continue;
+                    connectivity[3] = mat[a][d];
+                    connectivity[4] = mat[b][d];
+                    connectivity[5] = mat[c][d];
+                    // We've extracted a meaningful subgraph,
+                    // check its connectivity.
+                    if (!connectivity[].canFind('0'))
+                        return format("Fail, found wholly connected: ",
+                                      a, " ", b," ", c, " ", d);
+                    else if (!connectivity[].canFind('1'))
+                        return format("Fail, found wholly " ~
+                                      "unconnected: ",
+                                      a, " ", b," ", c, " ", d);
+                }
+            }
         }
     }
+    return "Satisfies Ramsey condition.";
-    writefln("%(%(%c %)\n%)", mat);
+}
+void main() {
+    const mat = generateMatrix;
+    writefln("%-(%(%c %)\n%)", mat);
+    mat.ramseyCheck.writeln;
 }</lang>
 {{out}}
@@ Line 126: / Line 164: @@
 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
-1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -</pre>
+1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
+Satisfies Ramsey condition.</pre>
 =={{header|Erlang}}==