Added medium/linear_congruence

bradhanson · bradhanson · commit 3ef2d96ce776 · 2018-07-25T11:05:09.000-04:00
diff --git a/medium/linear_congruence.js b/medium/linear_congruence.js
@@ -0,0 +1,33 @@
+/**
+ * Using the JavaScript language, have the function linearCongruence(str) read
+ * the str parameter being passed which will be a linear congruence equation in
+ * the form: "ax = b (mod m)" Your goal is to solve for x and return the number
+ * of solutions to x. For example: if str is "32x = 8 (mod 4)" then your program
+ * should return 4 because the answers to this equation can be either 0, 1, 2,
+ * or 3.
+ *
+ * https://www.coderbyte.com/results/bhanson:Linear%20Congruence:JavaScript
+ *
+ * @param  {string} str
+ * @return {number}
+ */
+function linearCongruence(str) {
+    // http://mathworld.wolfram.com/LinearCongruenceEquation.html
+
+    // parse 'ax = b (mod m)'
+    const [, a, b, m] = str
+        .match(/([\d]+)x[ ]+=[ ]+([\d]+)[ ]+\(mod ([\d]+)\)/)
+        .map(Number);
+
+    const answers = [];
+
+    for (let i = 0; i < m; i++) {
+        if ((a * i) % m === b % m) {
+            answers.push(i);
+        }
+    }
+
+    return answers.length;
+}
+
+module.exports = linearCongruence;
diff --git a/medium/linear_congruence.test.js b/medium/linear_congruence.test.js
@@ -0,0 +1,33 @@
+const linearCongruence = require('./linear_congruence');
+
+describe('linearCongruence()', () => {
+    test('returns number of solutions to given linear congruence problem', () => {
+        expect(linearCongruence('32x = 8 (mod 4)')).toBe(4);
+
+        expect(linearCongruence('12x = 5 (mod 2)')).toBe(0);
+
+        expect(linearCongruence('12x = 4 (mod 2)')).toBe(2);
+    });
+
+    test('passes Coderbyte.com tests', () => {
+        expect(linearCongruence('32x = 8 (mod 4)')).toBe(4);
+
+        expect(linearCongruence('12x = 5 (mod 2)')).toBe(0);
+
+        expect(linearCongruence('12x = 4 (mod 2)')).toBe(2);
+
+        expect(linearCongruence('1x = 1 (mod 2)')).toBe(1);
+
+        expect(linearCongruence('22x = 2 (mod 3)')).toBe(1);
+
+        expect(linearCongruence('222x = 5 (mod 2)')).toBe(0);
+
+        expect(linearCongruence('64x = 4 (mod 18)')).toBe(2);
+
+        expect(linearCongruence('64x = 4 (mod 16)')).toBe(0);
+
+        expect(linearCongruence('64x = 4 (mod 12)')).toBe(4);
+
+        expect(linearCongruence('124x = 12 (mod 12)')).toBe(4);
+    });
+});
