Added hard/optimal_assignments

bradhanson · bradhanson · commit 307159c402dd · 2018-07-16T00:00:27.000-04:00
diff --git a/hard/optimal_assignments.js b/hard/optimal_assignments.js
@@ -0,0 +1,91 @@
+/**
+ * Using the JavaScript language, have the function optimalAssignments(strArr)
+ * read strArr which will represent an NxN matrix and it will be in the
+ * following format: ["(n,n,n...)","(...)",...] where the n's represent
+ * integers. This matrix represents a machine at row i performing task at column
+ * j. The cost for this is matrix[i][j]. Your program should determine what
+ * machine should perform what task so as to minimize the whole cost and it
+ * should return the pairings of machines to tasks in the following format:
+ * (i-j)(...)... Only one machine can perform one task. For example: if strArr
+ * is ["(5,4,2)","(12,4,3)","(3,4,13)"] then your program should return
+ * (1-3)(2-2)(3-1) because assigning the machines to these tasks gives the least
+ * cost. The matrix will range from 2x2 to 6x6, there will be no negative costs
+ * in the matrix, and there will always be a unique answer.
+ *
+ * https://www.coderbyte.com/results/bhanson:Optimal%20Assignments:JavaScript
+ *
+ * @param  {array} strArr
+ * @return {string}
+ */
+function optimalAssignments(strArr) {
+    // Parse input to 2d array
+    const matrix = strArr.map(row => row.match(/\d+/g).map(Number));
+
+    // Array index = machine (row)
+    // Array value = task (col)
+    const tasks = [];
+    for (let i = 0; i < strArr.length; i++) {
+        tasks.push(i);
+    }
+
+    // Brute force check all possibilities
+    const permutations = permute(tasks);
+
+    let minCost = Number.MAX_SAFE_INTEGER;
+    let minAssignment = [];
+    permutations.forEach(permutation => {
+        const cost = getTotalCost(matrix, permutation);
+
+        if (cost < minCost) {
+            minCost = cost;
+            minAssignment = permutation;
+        }
+    });
+
+    // Format output to spec
+    const result = minAssignment
+        .map((value, index) => `(${index + 1}-${value + 1})`)
+        .join('');
+
+    return result;
+}
+
+function getTotalCost(matrix, assignment) {
+    let cost = 0;
+    for (let i = 0; i < assignment.length; i++) {
+        cost += matrix[i][assignment[i]];
+    }
+    return cost;
+}
+
+// https://en.wikipedia.org/wiki/Heap's_algorithm
+// Iterative
+function permute(arr) {
+    let count = Array(arr.length).fill(0);
+
+    const results = [arr.slice()];
+
+    let i = 0;
+    while (i < arr.length) {
+        if (count[i] < i) {
+            if (i % 2 === 0) {
+                const temp = arr[0];
+                arr[0] = arr[i];
+                arr[i] = temp;
+            } else {
+                const temp = arr[count[i]];
+                arr[count[i]] = arr[i];
+                arr[i] = temp;
+            }
+            results.push(arr.slice());
+            count[i]++;
+            i = 0;
+        } else {
+            count[i] = 0;
+            i++;
+        }
+    }
+    return results;
+}
+
+module.exports = optimalAssignments;
diff --git a/hard/optimal_assignments.test.js b/hard/optimal_assignments.test.js
@@ -0,0 +1,62 @@
+const optimalAssignments = require('./optimal_assignments');
+
+describe('optimalAssignments()', () => {
+    test('passes Coderbyte.com tests', () => {
+        expect(optimalAssignments(['(5,4,2)', '(12,4,3)', '(3,4,13)'])).toBe(
+            '(1-3)(2-2)(3-1)'
+        );
+
+        expect(optimalAssignments(['(1,2,1)', '(4,1,5)', '(5,2,1)'])).toBe(
+            '(1-1)(2-2)(3-3)'
+        );
+
+        expect(
+            optimalAssignments([
+                '(13,4,7,6)',
+                '(1,11,5,4)',
+                '(6,7,2,8)',
+                '(1,3,5,9)'
+            ])
+        ).toBe('(1-2)(2-4)(3-3)(4-1)');
+
+        expect(optimalAssignments(['(1,1,4)', '(5,2,1)', '(1,5,2)'])).toBe(
+            '(1-2)(2-3)(3-1)'
+        );
+
+        expect(optimalAssignments(['(1,1,2)', '(2,1,5)', '(1,5,1)'])).toBe(
+            '(1-1)(2-2)(3-3)'
+        );
+
+        expect(optimalAssignments(['(1,4)', '(5,18)'])).toBe('(1-2)(2-1)');
+
+        expect(optimalAssignments(['(1,2)', '(1,1)'])).toBe('(1-1)(2-2)');
+
+        expect(
+            optimalAssignments([
+                '(13,2,7,1)',
+                '(1,2,3,4)',
+                '(6,7,2,3)',
+                '(67,4,8,18)'
+            ])
+        ).toBe('(1-4)(2-1)(3-3)(4-2)');
+
+        expect(
+            optimalAssignments([
+                '(1,14,2,4)',
+                '(5,1,4,15)',
+                '(1,5,2,7)',
+                '(1,4,7,17)'
+            ])
+        ).toBe('(1-4)(2-2)(3-3)(4-1)');
+
+        expect(
+            optimalAssignments([
+                '(90,75,75,80,82)',
+                '(35,85,20,50,41)',
+                '(40,2,24,1,67)',
+                '(4,70,2,11,23)',
+                '(23,25,56,44,21)'
+            ])
+        ).toBe('(1-2)(2-3)(3-4)(4-1)(5-5)');
+    });
+});
