Added hard/vertex_covering

bradhanson · bradhanson · commit 827ba288a368 · 2018-07-17T13:26:20.000-04:00
diff --git a/hard/vertex_covering.js b/hard/vertex_covering.js
@@ -0,0 +1,52 @@
+/**
+ * Using the JavaScript language, have the function vertexCovering(strArr) take
+ * strArr which will be an array of length three. The first part of the array
+ * will be a list of vertices in a graph in the form (A,B,C,...), the second
+ * part of the array will be the edges connecting the vertices in the form
+ * (A-B,C-D,...) where each edge is bidirectional. The last part of the array
+ * will be a set of vertices in the form (X,Y,Z,...) and your program will have
+ * to determine whether or not the set of vertices given covers every edge in
+ * the graph such that every edge is incident to at least one vertex in the set.
+ *
+ * For example: if strArr is ["(A,B,C,D)","(A-B,A-D,B-D,A-C)","(A,B)"] then the
+ * vertices (A,B) are in fact one of the endpoints of every edge in the graph,
+ * so every edge has been accounted for. Therefore your program should return
+ * the string yes. But, if for example the last part of the array was (C,B) then
+ * these vertices don't cover all the edges because the edge connecting A-D is
+ * left out. If this is the case your program should return the edges given in
+ * the second part of the array that are left out in the same order they were
+ * listed, so for this example your program should return (A-D).
+ *
+ * The graph will have at least 2 vertices and all the vertices in the graph
+ * will be connected. The third part of the array listing the vertices may be
+ * empty, where it would only contain the parenthesis with no values within it:
+ * "()"
+ *
+ * https://www.coderbyte.com/results/bhanson:Vertex%20Covering:JavaScript
+ *
+ * @param  {array} strArr
+ * @return {string}
+ */
+function vertexCovering(strArr) {
+    let [, edges, vertices] = strArr;
+
+    edges = edges.substr(1, edges.length - 2).split(',');
+    vertices = vertices.substr(1, vertices.length - 2).split(',');
+
+    const missingEdges = edges.filter(edge => {
+        return !vertices.some(vertice => {
+            if (vertice === '') {
+                return false;
+            }
+            return edge.includes(vertice);
+        });
+    });
+
+    if (missingEdges.length === 0) {
+        return 'yes';
+    }
+
+    return `(${missingEdges.join(',')})`;
+}
+
+module.exports = vertexCovering;
diff --git a/hard/vertex_covering.test.js b/hard/vertex_covering.test.js
@@ -0,0 +1,57 @@
+const vertexCovering = require('./vertex_covering');
+
+describe('vertexCovering()', () => {
+    test('passes Coderbyte.com tests', () => {
+        expect(
+            vertexCovering(['(A,B,C,D)', '(A-B,A-D,B-D,A-C)', '(A,B)'])
+        ).toBe('yes');
+
+        expect(
+            vertexCovering(['(A,B,C,D)', '(A-B,A-D,B-D,A-C)', '(C,B)'])
+        ).toBe('(A-D)');
+
+        expect(vertexCovering(['(A,B,C,D)', '(A-B,A-D,B-D,A-C)', '(C)'])).toBe(
+            '(A-B,A-D,B-D)'
+        );
+
+        expect(vertexCovering(['(X,Y,Z,Q)', '(X-Y,Y-Q,Y-Z)', '(Z,Y,Q)'])).toBe(
+            'yes'
+        );
+
+        expect(vertexCovering(['(X,Y,Z,Q)', '(X-Y,Y-Q,Y-Z,X-Q)', '(X)'])).toBe(
+            '(Y-Q,Y-Z)'
+        );
+
+        expect(vertexCovering(['(X,Y,Z,Q)', '(X-Y,Y-Q,Y-Z,X-Q)', '(Q)'])).toBe(
+            '(X-Y,Y-Z)'
+        );
+
+        expect(vertexCovering(['(X,Y,Z,Q)', '(X-Y,Y-Q,Y-Z,X-Q)', '()'])).toBe(
+            '(X-Y,Y-Q,Y-Z,X-Q)'
+        );
+
+        expect(
+            vertexCovering([
+                '(A,B,C,D,E,F)',
+                '(A-B,A-D,B-D,B-C,C-F,E-D)',
+                '(B,F)'
+            ])
+        ).toBe('(A-D,E-D)');
+
+        expect(
+            vertexCovering([
+                '(A,B,C,D,E,F)',
+                '(A-B,A-D,B-D,B-C,C-F,E-D)',
+                '(D,B,F)'
+            ])
+        ).toBe('yes');
+
+        expect(
+            vertexCovering([
+                '(A,B,C,D,E,F,G)',
+                '(A-B,A-D,B-D,B-C,C-F,E-D,F-E,G-F)',
+                '(B,F)'
+            ])
+        ).toBe('(A-D,E-D)');
+    });
+});
