JS Algorithms

2022 January 11th Written by theWhiteFox

Algorithms written in JS:

Vinilla JavaScript (JS) Algorithms are repeatable? The following are some Algorithms I wrote in JS.

1. Two Sum
2. Fibonacci - learn recursion
3. Fizzbuzz - little fun test
4. Dijkstra - shortest path between nodes
5. Harmless Ransom Note use Big O notation
6. Palindrome - String & array manipulation - String and array methods
7. Caesar's Cipher - encryption
8. Reverse string

Write Algorithms & write them in JS:

I love to cook delicious food while figuring out new recipes. Algorithms for me are like programming recipes. As with recipes I Read, Cook, Eat, Tweak & Repeat this concept I follow with algoritms Read, Write, Run, Tweak & Repeat.

In my humble opinion, a good way to improve one's cooking skills is to take recipes and create your own either by tweaking or taking the concepts of what one has learned and applying them to different ingredients, in this post different programming languages.

As with my cooking, my programming and problem solving I hopw will improve by learning algorithms, these are some JavaScript (JS) algorithms that I will understand, not just do. JS(ES6)

In this post I chose JS as the language to learn the below algorithms because it's modern, fun, always evleving and most importantly the language of the web.

Using Big O Notation

A way to test time & space of an algorithm.

"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity." Wikipedia

Two Sum

Check an array for the sum of two values using Big O notation looping through the array twice to find a pair.

The first algorithm will be a JS function twoSumBrute that takes two parameters, a numbers array arr and a sum value sum. twoSumBrute returns a of pair indices from arr that add up to the sum value, function parameter.

The first attempt will use brute force O(n2). The arr passed in has already been defined within the JS code as const arr = [3, 7, 11, 15];.

Copy
1// Brute Two Sum return indices O(n)2
2// returns a of pair indices from `arr`
3// that add up to the `sum` parameter
4const arr = [3, 7, 11, 15];
5const sum = 10;
6
7const twoSumBrute = (arr, sum) => {
8  const sums = [];
9
10  // check first element in arr
11  for (let firstElement = 0; firstElement < arr.length; firstElement++) {
12    // check second element in arr
13    for (let secondElement = 0; secondElement < arr.length; secondElement++) {
14      if (arr[firstElement] + arr[secondElement] === sum) {
15        sums.push(arr[firstElement] + arr[secondElement]);
16      }
17    }
18  }
19  return sums;
20};
21
22twoSumBrute(arr, sum);

A faster solution would be linear time using using a Hash table instead of the brute force algorithm above ☝️.

Copy
1// faster Two Sum using hashTable
2const arr = [3, 7, 11, 15];
3const sum = 10;
4
5const twoSumHash = (arr, sum) => {
6  const sums = [];
7  const hashTable = {};
8
9  // check first element in arr
10  for (let firstElement = 0; firstElement < arr.length; firstElement++) {
11    const sumMinusElement = sum - firstElement[i];
12    // check second element in arr
13    for (let secondElement = 0; secondElement < arr.length; secondElement++) {
14      if (hashTable[sumMinusElement.toString] !== undefined) {
15        sums.push(arr[firstElement], sumMinusElement);
16      }
17
18      // add the current number to the hash table
19      hashTable[arr[i].toString()] = arr[i];
20    }
21  }
22  return sums;
23};
24
25twoSumHash(arr, sum);

Fibonacci

Fibonacci was a mathematician who developed the Fibonacci sequence, such that each number is the sum of the two preceding ones. The Fibonacci Sequence is found all throughout nature, too. It is a naturally occurring pattern. My first learning of Fibonacci was in nature as part of my art studies, I drew a Nautilus shell.

Fibonacci using while loops, recursion O(2^n) Memoization

Copy
1(function () {
2  // Big O
3  // 1, 1, 2, 3, 5, 8, 11
4  function fibonacci(num) {
5    var a = 1,
6      b = 0,
7      temp2;
8
9    while (num > 0) {
10      temp2 = a;
11      a = a + b;
12      b = temp2;
13      num--;
14      console.log(temp2);
15    }
16    return b;
17  }
18  fibonacci(7);
19
20  const basicFib = () => {
21    let first = 1,
22      second = 0,
23      answer = first + second;
24
25    while (answer < 10) {
26      console.log(answer);
27      second = first;
28      first = answer;
29      answer = first + second;
30    }
31    basicFib();
32  };
33})();

Fizzbuzz

An algorithm sometimes used as a basic interview test.

Copy
1// FizzBuzz
2// modulus operator
3console.log("modulus operator: 7 % 3 = " + (7 % 3));
4
5function fizzBuzz(num) {
6  for (var i = 1; i <= num; i++) {
7    if (i % 15 === 0) console.log("FizzBuzz");
8    else if (i % 5 === 0) console.log("fizz");
9    else if (i % 3 === 0) console.log("Buzz");
10    else console.log(i);
11  }
12}
13
14fizzBuzz(20);
15
16// Dijkstra’s Algorithm
17const problem = {
18  start: { A: 5, B: 2 },
19  A: { C: 4, D: 2 },
20  B: { A: 8, D: 7 },
21  C: { D: 6, finish: 3 },
22  D: { finish: 1 },
23  finish: {},
24};

Dijkstra

Dijkstra an algorithm for finding the shortest paths between nodes in a graph.

Copy
1// Dijkstra’s Algorithm
2const problem = {
3  start: { A: 5, B: 2 },
4  A: { C: 4, D: 2 },
5  B: { A: 8, D: 7 },
6  C: { D: 6, finish: 3 },
7  D: { finish: 1 },
8  finish: {},
9};
10
11// implementing the algorithm
12const lowestCostNode = (costs, processed) => {
13  return Object.keys(costs).reduce((lowest, node) => {
14    if (lowest === null || costs[node] < costs[lowest]) {
15      if (!processed.includes(node)) {
16        lowest = node;
17      }
18    }
19    return lowest;
20  }, null);
21};
22
23// func that returns the min cost and path to reach finish
24const dijkstra = (graph) => {
25  // track lowest cost to reach each node
26  const costs = Object.assign({ finish: Infinity }, graph.start);
27
28  // track paths
29  const parents = { finish: null };
30
31  // add children of the start node
32  for (let child in graph.start) {
33    parents[child] = "start";
34  }
35
36  // track nodes that have already been processed
37  const processed = [];
38
39  // get the cost of the current node
40  let node = lowestCostNode(costs, processed);
41
42  // get all the children of the current
43  while (node) {
44    let cost = costs[node];
45    let children = graph[node];
46    // loop through each of the children
47    for (let n in children) {
48      let newCost = cost + children[n];
49      if (!cost[n]) {
50        costs[n] = newCost;
51        parents[n] = node;
52      }
53      if (costs[n] > newCost) {
54        costs[n] = newCost;
55        parents[n] = node;
56      }
57    }
58    // push to processed data structure
59    processed.push(node);
60    node = lowestCostNode(costs, processed);
61  }
62
63  let optimalPath = ["finish"];
64  let parent = parents.finish;
65
66  while (parent) {
67    optimalPath.push(parent);
68    parent = parents[parent];
69  }
70
71  optimalPath.reverse(); // reverse array to get order
72
73  const results = {
74    distance: costs.finish,
75    path: optimalPath,
76  };
77  return results;
78};
79
80console.log(dijkstra(problem));
81
82// Object { distance: 12, path: […] }
83// distance: 12
84// path: […]​
85// 0: "parent"
86// 1: "parent"
87// 2: "parent"
88// 3: "finish"
89// length: 4