A collection of dynamic programming algorithms implemented in TypeScript for studying

DynamicProgrammingAlgorithm.ts

//=========================- - Dynamic Programming Algorithms - -=========================//

/*
- Dynamic Programming:
  is a problem-solving technique that involves breaking down a complex problem into smaller, simpler
  subproblems and solving each subproblem only once, storing the results to avoid redundant calculations.
  The technique is based on the idea of using the solutions of previously solved subproblems to solve the larger problem.

- Optimization problems: Dynamic Programming algorithms can be used to solve optimization problems, such as the Knapsack
  problem, where the goal is to maximize the value of objects that can be placed in a knapsack subject to its weight capacity.

- Pathfinding: Dynamic Programming algorithms can be used to find the shortest path between two points in a graph, such
  as the Bellman-Ford algorithm and the Floyd-Warshall algorithm.

- Sequencing problems: Dynamic Programming algorithms can be used to solve sequencing problems, such as the Longest Common
  Subsequence problem, where the goal is to find the longest subsequence that is common to two sequences.

- Game Theory: Dynamic Programming algorithms can be used to solve games that involve decisions made over time, such as
  the minimax algorithm used in game-playing AI.

- Computational Biology: Dynamic Programming algorithms can be used to solve problems in computational biology, such as
  the Needleman-Wunsch algorithm used to align DNA sequences.

- Finance: Dynamic Programming algorithms can be used to solve problems in finance, such as the Binomial Options Pricing
  Model used to price financial options.
*/

namespace DynamicProgramming {
  export interface Item { value: number, weight: number }
  //dp stands for dynamic programming
  export function knapsack(items: Item[], capacity: number) {
    const n = items.length
    const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0))

    for (let i = 1; i <= n; i++) {
      const { value, weight } = items[i - 1]

      for (let j = 1; j <= capacity; j++) {
        if (weight <= j) {
          dp[i][j] = Math.max(value + dp[i - 1][j - weight], dp[i - 1][j])
        } else {
          dp[i][j] = dp[i - 1][j]
        }
      }
    }

    return dp[n][capacity]
  }

  export const fpKnapsack = (items: Item[], capacity: number) => {
    // Define a function to calculate the maximum value for a subset of the items
    const maxSubsetValue = (i: number, remainingCapacity: number) => {
      // Base case: if there are no more items or capacity left, the value is 0
      if (i === items.length || remainingCapacity === 0) {
        return 0
      }

      const { weight, value } = items[i]
      const nextIndex = i + 1

      // If the current item's weight exceeds the remaining capacity, skip it
      if (weight > remainingCapacity) {
        return maxSubsetValue(nextIndex, remainingCapacity)
      }

      // Otherwise, consider both the case where the current item is included and the case where it is not
      const includeValue = value + maxSubsetValue(nextIndex, remainingCapacity - weight)
      const excludeValue = maxSubsetValue(nextIndex, remainingCapacity)

      return Math.max(includeValue, excludeValue)
    }

    return maxSubsetValue(0, capacity)
  }

  export type Edge = { from: string; to: string; weight: number }

  export function bellmanFord(edges: Edge[], start: string, vertices: string[]) {
    // Step 1: initialize the distances
    const distances = new Map<string, number>(
      vertices.map((v) => [v, v === start ? 0 : Infinity])
    );

    // Step 2: relax edges repeatedly
    for (let i = 0; i < vertices.length - 1; i++) {
      for (const edge of edges) {
        const { from, to, weight } = edge;

        const fromDistance = distances.get(from)!

        if (fromDistance === Infinity) continue

        const toDistance = distances.get(to)!
        const newDistance = fromDistance + weight;

        if (newDistance < toDistance) {
          distances.set(to, newDistance)
        }
      }
    }

    // Step 3: detect negative cycles
    for (const edge of edges) {
      const { from, to, weight } = edge

      if (distances.get(from)! + weight < distances.get(to)!) {
        throw new Error("Negative cycle detected")
      }
    }

    return distances
  }

  export function floydWarshall(graph: number[][]) {
    // Create a copy of the input graph to store the shortest distances
    const dist = [...graph.map(row => [...row])]

    // Number of vertices in the graph
    const n = graph.length

    // Iterate over all intermediate vertices
    for (let k = 0; k < n; k++) {
      // Iterate over all pairs of vertices
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
          // If the distance from i to j through k is shorter than the current distance, update it
          if (dist[i][k] + dist[k][j] < dist[i][j]) {
            dist[i][j] = dist[i][k] + dist[k][j]
          }
        }
      }
    }

    // Return the shortest distances between all pairs of vertices
    return dist
  }

  export const fpFloydWarshall = (graph: ReadonlyArray<ReadonlyArray<number>>) => {
    // Create a copy of the input graph to store the shortest distances
    const dist = graph.map(row => [...row])

    // Number of vertices in the graph
    const n = graph.length

    // Compute the shortest distances using a functional approach
    const intermediateVertices = getIntermediateVertices(n)

    intermediateVertices.forEach(k =>
      getVertices(n).map((_, x) =>
        getVertices(n).map((_, y) =>
          calculateShortestDistance(dist, x, y, k)
        ))
      .forEach((updatedDist, i) => updateDist(dist, i, updatedDist))
    )

    // Return the shortest distances between all pairs of vertices
    return dist
  }

  // Helper functions
  const getIntermediateVertices = (n: number) => [...Array(n).keys()]
  const getVertices = (n: number) => [...Array(n).keys()]
  const calculateShortestDistance = (dist: ReadonlyArray<ReadonlyArray<number>>, x: number, y: number, k: number) =>
    Math.min(dist[x][y], dist[x][k] + dist[k][y])

  const updateDist = (dist: Array<Array<number>>, i: number, updatedDist: Array<number>) =>
    dist[i] = updatedDist

  export function fibonacciSequenceWhileLoop(limit: number) {
    const sequence: number[] = [0, 1];

    let next = 1;

    while (next <= limit) {
      next = sequence[sequence.length - 1] + sequence[sequence.length - 2];

      if (next <= limit) {
        sequence.push(next);
      }
    }

    return sequence;
  }

  export function fibonacciSequenceForLoop(limit: number) {
    const sequence: number[] = [0, 1];

    for (let i = 2; i <= limit; i++) {
      const next = sequence[i - 1] + sequence[i - 2];

      if (next <= limit) {
        sequence.push(next);
      } else {
        break;
      }
    }

    return sequence;
  }

  export function fibonacciSequenceRecursion(limit: number) {
    const addNextNumber = (sequence: number[]) => {
      const next = sequence[sequence.length - 1] + sequence[sequence.length - 2];

      return next <= limit ? addNextNumber([...sequence, next]) : sequence;
    };

    return addNextNumber([0, 1]);
  }
}

namespace GreedyAlgorithm {
  export class Graph {
    private adjacencyList: Map<string, Map<string, number>> = new Map();

    public addVertex(vertex: string) {
      if (!this.adjacencyList.has(vertex)) {
        this.adjacencyList.set(vertex, new Map());
      }
    }

    public addEdge(vertex1: string, vertex2: string, weight: number) {
      this.addVertex(vertex1);
      this.addVertex(vertex2);
      this.adjacencyList.get(vertex1)?.set(vertex2, weight);
      this.adjacencyList.get(vertex2)?.set(vertex1, weight);
    }

    // - Dijkistra's
    public dijkstra(startVertex: string) {
      const distances: Map<string, number> = new Map();
      const visited: Set<string> = new Set();
      const queue: [string, number][] = [];

      distances.set(startVertex, 0);
      queue.push([startVertex, 0]);

      while (queue.length) {
        const [ currentVertex, currentDistance ] = queue.shift()!;

        if (visited.has(currentVertex)) {
          continue;
        }

        visited.add(currentVertex);

        const neighbors = this.adjacencyList.get(currentVertex);

        for (const [neighbor, weight] of neighbors!) {
          const distance = currentDistance + weight;

          if (!distances.has(neighbor) || distance < distances.get(neighbor)!) {
            distances.set(neighbor, distance);
            queue.push([neighbor, distance]);
          }
        }
      }

      return distances;
    }
  }
}

const { knapsack, fpKnapsack, bellmanFord, floydWarshall, fpFloydWarshall, fibonacciSequenceForLoop, fibonacciSequenceWhileLoop, fibonacciSequenceRecursion } = DynamicProgramming

//- The knapsack algorithm is a backtracking and dynamic programming approach to solving the knapsack problem
//  It is a method to optimize the selection of items with different weights and values to fit into a limited-capacity knapsack
//  in order to maximize the total value of the selected items.

const items: DynamicProgramming.Item[] = [
  { value: 60, weight: 10 },
  { value: 100, weight: 20 },
  { value: 120, weight: 30 },
]

const capacity = 50

console.log(`Knapsack value: ${knapsack(items, capacity)}`)
console.log(`Knapsack value: ${fpKnapsack(items, capacity)}`)

//- - - Dijkistra's
//-     Shortest path from one node to all nodes

//- - - Bellman-Ford
//-     Shortest path from one node to all nodes, negative edges allowed

//- - - Floyd-warshall
//-     Shortest path between all pairs of vertices, negative edges allowed

//- - The Bellman-Ford algorithm is a dynamic programming approach to finding the shortest path in a weighted graph
//-   that may have negative edge weights, by iteratively relaxing each edge in the graph and checking for negative weight cycles.

const edges: DynamicProgramming.Edge[] = [
  { from: 'A', to: 'B', weight: 4 },
  { from: 'A', to: 'C', weight: 3 },
  { from: 'B', to: 'C', weight: -2 },
  { from: 'B', to: 'D', weight: 2 },
  { from: 'B', to: 'E', weight: -3 },
  { from: 'C', to: 'D', weight: 5 },
  { from: 'C', to: 'E', weight: 1 },
  { from: 'D', to: 'E', weight: -2 },
]

const start = "A"
const vertices = ["A", "B", "C", "D", "E"]

const distances = bellmanFord(edges, start, vertices)
console.log(distances)
//============= Output: Map { 'A' => 0, 'B' => 4, 'C' => 2, 'D' => 6, 'E' => 1 }

//- Floyd-Warshall algorithm is a dynamic programming approach to finding the
//  shortest path between all pairs of vertices in a weighted graph, even if it contains negative edge weights,
//  by considering intermediate vertices and updating a matrix of minimum distances.

// Example usage
//     ─► 3
//     ◄─ 8
//    A─────B
//  2 │↖    │ 8
//  ▲ │ \ 5 │ │
//  │7│  \  │ ▼
//   ││   \ │
//   ▼│    \│
//    D─────C
//      ◄─ 1

const exampleGraph = [
  [0, 3, Infinity, 7],
  [8, 0, 2, Infinity],
  [5, Infinity, 0, 1],
  [2, Infinity, Infinity, 0]
]

const shortestDistances = floydWarshall(exampleGraph)
console.log(shortestDistances)
//===================== Output: [ [ 0, 3, 5, 6 ], [ 5, 0, 2, 3 ], [ 3, 6, 0, 1 ], [ 2, 5, 7, 0 ] ]

const fpShortestDistances = fpFloydWarshall(exampleGraph)
console.log(fpShortestDistances)
//======================= Output: [ [ 0, 3, 5, 6 ], [ 5, 0, 2, 3 ], [ 3, 6, 0, 1 ], [ 2, 5, 7, 0 ] ]

const points = ['A', 'B', 'C', 'D']
const lastLine = '\n  A B C D'
const matrixGrapthLog = fpShortestDistances.reduce((acc, cur, i)=> `${acc}\n${points[i]}|${cur}|`, '').concat(lastLine);
console.log(matrixGrapthLog)

//- Fibonacci Sequence algorithm is a dynamic programming approach to create a
//  sequence of numbers in which each number is the sum of the two preceding numbers.

console.log(fibonacciSequenceWhileLoop(100));
console.log(fibonacciSequenceForLoop(100));
console.log(fibonacciSequenceRecursion(100));
//==================================== outputs [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

//- Dijkstra's algorithm is a Greedy algorithm NOT a dynamic programming,
//  it's a way to find the shortest path between two points in a graph with non-negative weights on its edges.
//  It starts at a given starting point and visits neighboring nodes to find the shortest path to each node until it reaches the end point.

const { Graph } = GreedyAlgorithm

// Example usage
const graph = new Graph();

graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'C', 1);
graph.addEdge('B', 'D', 5);
graph.addEdge('C', 'D', 8);
graph.addEdge('C', 'E', 10);
graph.addEdge('D', 'E', 2);

const distancesFromA = graph.dijkstra('A');

console.log(distancesFromA);
//====================Output: Map { 'A' => 0, 'B' => 4, 'C' => 2, 'D' => 9, 'E' => 11 }