theWhiteFox DESIGNING & BUILDING WEBSITE / MOBILE APPS

thewhitefox

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];.

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 ☝️.

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.

Nautilus shell fibonacci

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

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.

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.

Dijkstra Graph

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
Reference
big O cheat sheetbeginners guide to big O notation
algorithms importantSO fibonacci recursive
Dijkstrasthatjsdude check Palindrome
JS algorithms from scratchpalindromelist
medium Tim Severien substitution cipher JSReverse a string
You Dont Know JSfreecodecamp js arrayreverse tut
theWhiteFox algorithms-in-js
APIsLearn React