Coding Adventures: Mastering Algorithms with JavaScript 🚀

Linear Search

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Return the index if the target is found
    }
  }
  return -1; // Return -1 if the target is not found in the array
}

This code demonstrates a simple linear search algorithm in JavaScript.
It iterates through an array to find the index of a target element, or -1 if not found.

Binary Search

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // Return the index if the target is found
    } else if (arr[mid] < target) {
      left = mid + 1; // Discard the left half if the target is in the right
    } else {
      right = mid - 1; // Discard the right half if the target is in the left
    }
  }

  return -1; // Return -1 if the target is not found in the array
}

This code illustrates the binary search algorithm in JavaScript.
It assumes the array is sorted and efficiently narrows down the search space.

Depth-First Search (DFS)

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }

  depthFirstSearch(start) {
    const result = [];
    const visited = {};

    const dfs = (vertex) => {
      if (!vertex) return;

      result.push(vertex);
      visited[vertex] = true;

      this.adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          dfs(neighbor);
        }
      });
    };

    dfs(start);
    return result;
  }
}

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addEdge('A', 'B');
console.log(graph.depthFirstSearch('A'));

This code demonstrates a basic implementation of Depth-First Search in JavaScript.
It explores as far as possible along each branch before backtracking.

A* Search Algorithm

class AStarNode {
  constructor(x, y, cost, heuristic) {
    this.x = x;
    this.y = y;
    this.cost = cost;
    this.heuristic = heuristic;
    this.totalCost = cost + heuristic;
  }
}

function aStarSearch(grid, start, goal) {
  const openSet = [new AStarNode(start.x, start.y, 0, heuristic(start, goal))];
  const closedSet = new Set();

  while (openSet.length > 0) {
    openSet.sort((a, b) => a.totalCost - b.totalCost);
    const current = openSet.shift();

    if (current.x === goal.x && current.y === goal.y) {
      return reconstructPath(current);
    }

    closedSet.add(`${current.x},${current.y}`);

    getNeighbors(current, grid).forEach((neighbor) => {
      if (!closedSet.has(`${neighbor.x},${neighbor.y}`)) {
        const tentativeCost = current.cost + 1;
        const neighborNode = openSet.find((node) => node.x === neighbor.x && node.y === neighbor.y);

        if (!neighborNode || tentativeCost < neighborNode.cost) {
          openSet.push(new AStarNode(neighbor.x, neighbor.y, tentativeCost, heuristic(neighbor, goal)));
        }
      }
    });
  }

  return null; // No path found
}

// Helper functions for A* Search
function heuristic(node, goal) {
  return Math.abs(node.x - goal.x) + Math.abs(node.y - goal.y); // Manhattan distance
}

function getNeighbors(node, grid) {
  // Returns valid neighbors for the current node
  // (assuming a 2D grid where each cell is either passable or impassable)
  // Adjust as needed for your specific use case.
  const neighbors = [];
  // ... implementation to find neighbors ...
  return neighbors;
}

function reconstructPath(node) {
  // Reconstructs the path from the goal node to the start node
  const path = [];
  // ... implementation to backtrack and reconstruct path ...
  return path.reverse();
}

This code demonstrates the A* search algorithm in JavaScript.
A* is a pathfinding algorithm that efficiently finds the shortest path in a weighted graph.

Trie Data Structure

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        return false; // Prefix not found
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

// Example Usage:

const trie = new Trie();
trie.insert("apple");
console.log(trie.search("app")); // Output: false
console.log(trie.search("apple")); // Output: true

This code demonstrates the implementation of a Trie data structure in JavaScript.
Tries are tree-like structures used for efficient retrieval of keys, making them ideal for autocomplete and dictionary applications.

Merge Sort Algorithm

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Example Usage:

const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray); // Output: [11, 12, 22, 25, 64]

This code demonstrates the Merge Sort algorithm in JavaScript.
Merge Sort is a divide-and-conquer algorithm that efficiently sorts an array or a linked list.

Dijkstra's Shortest Path Algorithm

class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

function dijkstra(graph, start, end) {
  const distances = {};
  const previous = {};
  const priorityQueue = new PriorityQueue();

  for (let vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    priorityQueue.enqueue(vertex, distances[vertex]);
    previous[vertex] = null;
  }

  while (priorityQueue.values.length) {
    const currentVertex = priorityQueue.dequeue().val;

    if (currentVertex === end) {
      return getPath(previous, start, end);
    }

    if (distances[currentVertex] !== Infinity) {
      for (let neighbor in graph[currentVertex]) {
        const nextNode = graph[currentVertex][neighbor];
        const potentialDistance = distances[currentVertex] + nextNode.weight;

        if (potentialDistance < distances[neighbor]) {
          distances[neighbor] = potentialDistance;
          previous[neighbor] = currentVertex;
          priorityQueue.enqueue(neighbor, potentialDistance);
        }
      }
    }
  }

  return null; // No path found
}

function getPath(previous, start, end) {
  const path = [];
  let current = end;

  while (current !== null) {
    path.unshift(current);
    current = previous[current];
  }

  return path;
}

// Example Usage:

const weightedGraph = {
  A: { B: { weight: 4 }, C: { weight: 2 } },
  B: { A: { weight: 4 }, D: { weight: 5 } },
  C: { A: { weight: 2 }, D: { weight: 1 } },
  D: { B: { weight: 5 }, C: { weight: 1 } },
};

const shortestPath = dijkstra(weightedGraph, 'A', 'D');
console.log(shortestPath); // Output: ['A', 'C', 'D']

This code demonstrates Dijkstra's algorithm in JavaScript.
Dijkstra's algorithm finds the shortest path between nodes in a weighted graph.

Observer Design Pattern

class Subject {
  constructor() {
    this.observers = [];
  }

  addObserver(observer) {
    this.observers.push(observer);
  }

  removeObserver(observer) {
    this.observers = this.observers.filter((obs) => obs !== observer);
  }

  notify(message) {
    this.observers.forEach((observer) => observer.update(message));
  }
}

class Observer {
  constructor(name) {
    this.name = name;
  }

  update(message) {
    console.log(`${this.name} received message: ${message}`);
  }
}

// Example Usage:

const subject = new Subject();
const observer1 = new Observer('Observer 1');
const observer2 = new Observer('Observer 2');

subject.addObserver(observer1);
subject.addObserver(observer2);
subject.notify('Hello Observers!');

// Output: "Observer 1 received message: Hello Observers!"
//         "Observer 2 received message: Hello Observers!"

This code demonstrates the Observer design pattern in JavaScript.
The Observer pattern defines a one-to-many dependency between objects, where changes in one object trigger updates in its dependents.

Memoization for Fibonacci Sequence

// Snippet 9: Memoization for Fibonacci Sequence
// Description: This code demonstrates memoization in JavaScript to optimize the calculation of Fibonacci numbers.
// Memoization is a technique that stores previously calculated results to avoid redundant computations.

function fibonacciMemoization(n, memo = {}) {
  if (n <= 1) {
    return n;
  }

  if (!memo.hasOwnProperty(n)) {
    memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
  }

  return memo[n];
}

// Example Usage:

console.log(fibonacciMemoization(6));

This code demonstrates memoization in JavaScript to optimize the calculation of Fibonacci numbers.
Memoization is a technique that stores previously calculated results to avoid redundant computations.

Singleton Design Pattern

class Singleton {
  constructor() {
    if (!Singleton.instance) {
      Singleton.instance = this;
    }

    return Singleton.instance;
  }

  logMessage(message) {
    console.log(`Singleton: ${message}`);
  }
}

// Example Usage:

const singleton1 = new Singleton();
const singleton2 = new Singleton();

console.log(singleton1 === singleton2); // Output: true
singleton1.logMessage('Hello Singleton Pattern!'); // Output: "Singleton: Hello Singleton Pattern!"

This code demonstrates the Singleton design pattern in JavaScript.
The Singleton pattern ensures a class has only one instance and provides a global point of access to it.

Genetic Algorithm for Knapsack Problem

class Individual {
  constructor(chromosomeLength) {
    this.chromosome = Array.from({ length: chromosomeLength }, () => Math.round(Math.random()));
    this.fitness = 0;
  }
}

function knapsackGeneticAlgorithm(populationSize, chromosomeLength, generations) {
  // Initialize population
  const population = Array.from({ length: populationSize }, () => new Individual(chromosomeLength));

  for (let generation = 0; generation < generations; generation++) {
    // Evaluate fitness of each individual
    population.forEach((individual) => {
      individual.fitness = evaluateFitness(individual.chromosome);
    });

    // Select parents based on fitness
    const parents = selectParents(population);

    // Crossover (recombination)
    const offspring = crossover(parents);

    // Mutate offspring
    mutate(offspring);

    // Replace old population with new one
    population.splice(0, populationSize, ...offspring);
  }

  // Find the best individual in the final population
  const bestIndividual = population.reduce((best, current) => (current.fitness > best.fitness ? current : best));

  return bestIndividual;
}

function evaluateFitness(chromosome) {
  // Implement a fitness function based on the problem constraints and goals
  // Fitness should reflect how well the individual solves the problem
  // For the Knapsack Problem, it might be the total value of selected items
  // minus a penalty for exceeding the weight capacity.
}

function selectParents(population) {
  // Implement a selection algorithm to choose parents based on their fitness
  // Common methods include roulette wheel selection or tournament selection.
}

function crossover(parents) {
  // Implement crossover (recombination) to create offspring from selected parents
  // This could involve combining parts of the parents' chromosomes to produce new individuals.
}

function mutate(offspring) {
  // Implement mutation to introduce small changes in the offspring's chromosomes
  // This adds genetic diversity to the population.
}

// Example Usage:

const result = knapsackGeneticAlgorithm(50, 10, 100);
console.log(result);

This code implements a genetic algorithm to solve the Knapsack Problem in JavaScript.
The Knapsack Problem involves selecting a combination of items with maximum value without exceeding a given weight capacity.

Radix Sort Algorithm

function radixSort(arr) {
  const getMax = () => Math.max(...arr);
  const countSort = (arr, exp) => {
    const output = new Array(arr.length);
    const count = new Array(10).fill(0);

    for (let i = 0; i < arr.length; i++) {
      count[Math.floor(arr[i] / exp) % 10]++;
    }

    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    for (let i = arr.length - 1; i >= 0; i--) {
      output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
      count[Math.floor(arr[i] / exp) % 10]--;
    }

    for (let i = 0; i < arr.length; i++) {
      arr[i] = output[i];
    }
  };

  const max = getMax();

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countSort(arr, exp);
  }

  return arr;
}

// Example Usage:

const unsortedArray = [170, 45, 75, 90, 802, 24, 2, 66];
const sortedArray = radixSort(unsortedArray);

console.log(sortedArray); // Output: [2, 24, 45, 66, 75, 90, 170, 802]

This code implements the Radix Sort algorithm in JavaScript.
Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits.

Factory Design Pattern

class Shape {
  draw() {
    throw new Error('draw() method must be implemented');
  }
}

class Circle extends Shape {
  draw() {
    console.log('Drawing Circle');
  }
}

class Square extends Shape {
  draw() {
    console.log('Drawing Square');
  }
}

class ShapeFactory {
  createShape(type) {
    switch (type) {
      case 'circle':
        return new Circle();
      case 'square':
        return new Square();
      default:
        throw new Error('Invalid shape type');
    }
  }
}

// Example Usage:

const factory = new ShapeFactory();
const circle = factory.createShape('circle');
const square = factory.createShape('square');

circle.draw(); // Output: "Drawing Circle"
square.draw(); // Output: "Drawing Square"

This code demonstrates the Factory design pattern in JavaScript.
The Factory pattern provides an interface for creating instances of a class, but allows subclasses to alter the type of objects that will be created.

Markov Chain Text Generator

class MarkovChain {
  constructor(order) {
    this.order = order;
    this.states = {};
  }

  train(text) {
    const words = text.split(' ');
    
    for (let i = 0; i < words.length - this.order; i++) {
      const state = words.slice(i, i + this.order).join(' ');
      const nextWord = words[i + this.order];
      
      if (!this.states[state]) {
        this.states[state] = [];
      }

      this.states[state].push(nextWord);
    }
  }

  generate(seed, length) {
    let current = seed;
    let result = seed.split(' ');

    for (let i = 0; i < length - this.order; i++) {
      const nextState = result.slice(i, i + this.order).join(' ');
      const nextOptions = this.states[nextState];

      if (nextOptions && nextOptions.length > 0) {
        const nextWord = nextOptions[Math.floor(Math.random() * nextOptions.length)];
        result.push(nextWord);
      } else {
        break; // Unable to generate further, break the loop
      }
    }

    return result.join(' ');
  }
}

// Example Usage:

const text = "The quick brown fox jumps over the lazy dog.";
const generator = new MarkovChain(2);

generator.train(text);
const generatedText = generator.generate('quick brown', 5);
console.log(generatedText);

This code implements a simple Markov Chain Text Generator in JavaScript.
Markov Chains are used to model random processes, and this generator creates text based on the probability of transitioning from one word to another.

Fisher-Yates Shuffle Algorithm

function fisherYatesShuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]]; // Swap elements at indices i and j
  }
  return array;
}

// Example Usage:

const originalArray = [1, 2, 3, 4, 5];
const shuffledArray = fisherYatesShuffle(originalArray.slice());

console.log(shuffledArray); // Output: A random permutation of the original array.

This code implements the Fisher-Yates Shuffle algorithm in JavaScript.
Fisher-Yates Shuffle is an algorithm for generating a random permutation of a finite sequence.

Trie Data Structure for Autocomplete

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
    this.words = [];
  }
}

class AutocompleteTrie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
      node.words.push(word);
    }
    node.isEndOfWord = true;
  }

  autocomplete(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return []; // Prefix not found
      }
      node = node.children[char];
    }
    return node.words;
  }
}

// Example Usage:

const autocompleteTrie = new AutocompleteTrie();
autocompleteTrie.insert('apple');
autocompleteTrie.insert('appetizer');
autocompleteTrie.insert('banana');

const suggestions = autocompleteTrie.autocomplete('app');
console.log(suggestions); // Output: ['apple', 'appetizer']

This code extends the Trie data structure for efficient autocomplete in JavaScript.
It includes methods for inserting words and finding autocomplete suggestions.