Cracking the Piggy Bank Puzzle: A Java Adventure in Dynamic Programming

Hey there, intrepid coders! Today, we're diving into a piggy bank heist… of the intellectual kind, of course! We'll be using a powerful technique called Dynamic Programming (DP) to crack the code of a mischievous piggy bank and unlock its hidden treasures. Buckle up, because this adventure requires both logic and a dash of mathematical magic.

Imagine a piggy bank with compartments numbered 1 to N. Each compartment holds a certain amount of coins. Your mission is to maximise the total coins you can collect by following these two rules:

1. You can only start at compartment 1 and move rightward, collecting all the coins in a compartment before proceeding.
2. You can either skip a compartment (earning you 0 coins) or rob a compartment, but robbing two consecutive compartments is forbidden.

This might seem tricky, but DP comes to the rescue! It breaks down the problem into smaller, overlapping subproblems and cleverly stores the solutions, saving you from redundant calculations. Think of it like mapping a treasure hunt – each solution to a subproblem guides you towards the bigger prize.

class PiggyBankBreaker {

    private final int[] coins; // Array storing coins in each compartment (1-indexed)
    private final int[] maxCoins; // DP array to store max achievable coins at each position (0-indexed)

    public PiggyBankBreaker(int[] coins) {
        this.coins = coins; // Copy original coin values
        this.maxCoins = new int[coins.length + 1]; // Allocate DP array with space for starting point (index 0)
    }

    public int crackPiggyBank() {
        // Base case: No coins at starting point
        maxCoins[0] = 0;

        // Loop through each compartment from index 1 (inclusive)
        for (int i = 1; i <= coins.length; i++) {
            // Option 1: Rob current compartment + max from 2 positions back (non-consecutive)
            int robCurrent;

            // Check if robbing current is even possible (avoid accessing coins[-1])
            if (i >= 3) {
                robCurrent = coins[i - 1] + maxCoins[i - 3];
            } else {
                // Default to skipping for initial positions where robbing isn't valid
                robCurrent = 0;
            }

            // Option 2: Skip current compartment and take max from previous position (consecutive)
            int skipCurrent = maxCoins[i - 1];

            // Choose the option that yields more coins
            maxCoins[i] = Math.max(robCurrent, skipCurrent);
        }

        // Return the maximum achievable coins from the last compartment
        return maxCoins[coins.length];
    }

    public static void main(String[] args) {
        // Example piggy bank with coins
        int[] coins = {2, 3, 1, 4, 5, 7, 10};

        PiggyBankBreaker breaker = new PiggyBankBreaker(coins);
        int maxLoot = breaker.crackPiggyBank();
        System.out.println("Maximum amount you can collect: " + maxLoot);
    }
}

This Java code solves the piggy bank problem, where you maximise the coins collected while adhering to two rules:

1. Start at compartment 1 and move rightward, collecting all coins in each compartment.
2. You can either skip or rob a compartment, but not two consecutive compartments.

The code utilises Dynamic Programming (DP) to efficiently solve this problem by breaking it down into smaller, overlapping subproblems. Here's a breakdown of the key aspects:

• The method calculates the maximum coins achievable from any starting point.
• Base case: maxCoins[0] = 0 since no coins are earned before starting.
• Loop: Iterates through each compartment (index 1 to length).
• Rob current option:
  • Calculates robCurrent by adding the current coin value (coins[i - 1]) to the maximum coins achievable two positions back (maxCoins[i - 3]).
  • Fix: A conditional statement (i >= 3) ensures this calculation only happens for valid positions (avoiding coins[-1] access).
  • Otherwise, robCurrent is set to 0, mimicking skipping the compartment for initial positions.
• Skip current option: Simply takes the maximum coins from the previous position (maxCoins[i - 1]).
• Comparison: Chooses the maximum value between robCurrent and skipCurrent and stores it in maxCoins[i]. This ensures the optimal decision is recorded for future subproblems.
• Final result: The last element maxCoins[coins.length] represents the maximum achievable coins from the starting point (compartment 1).

Longest common subsequence in Java

Longest Common Subsequence (LCS)

• It's the longest sequence of characters that is present in the same relative order within two or more strings.
• It doesn't have to be a contiguous substring; the characters can appear in different positions within the original strings.

Understanding the Problem

• Imagine two strings, written vertically on separate columns.
• The goal is to find the longest sequence of characters that appears in the same order within both strings, even if they're not consecutive.

Character Grid

• Create a grid where each row represents a character from the first string, and each column represents a character from the second string.
• Fill each cell with a color indicating whether the corresponding characters match (e.g., green) or not (e.g., white).

Tracing Paths

• Start at the top-left corner of the grid.
• Move diagonally down-right only when characters match (green cells).
• If characters don't match, move either down or right to continue searching for matches.
• The path you take represents the LCS.

Visualize the LCS

• Highlight the cells along the longest path with a bolder color or border.
• The characters in those cells, read in order, form the LCS.

Example:

Consider strings "AGGTAB" and "GXTXAYB":

LCS: "GTAB" (highlighted cells)

Algorithm

1. Dynamic Programming Table:

   • Create a 2D table dp with dimensions (m+1) x (n+1), where m and n are the lengths of the two strings.
   • Fill the first row and column with 0s, indicating no LCS for empty strings.

2. Filling the Table:

   • Iterate through the table, starting from dp[1][1].
   • For each cell dp[i][j]:
     • If the characters at indices i-1 and j-1 in the strings match:
       • Set dp[i][j] = dp[i-1][j-1] + 1 (add 1 to the LCS length of the previous substrings).
     • Else:
       • Set dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the maximum LCS length from the previous options).

3. Reconstructing the LCS:

   • Start from the bottom-right corner of the table (dp[m][n]).
   • Backtrack:
     • If the characters at indices i-1 and j-1 match, add the character to the LCS and move diagonally up (i--, j--).
     • Else, move to the cell with the maximum value (either i-- or j--).
   • Reverse the constructed LCS string to get the correct order.

 

public class LCS {

    public static String lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];

        // Build the table in a bottom-up manner
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Reconstruct the LCS
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // Reverse the LCS string
        return lcs.reverse().toString();
    }

    // Example usage for testing
    public static void main(String[] args) {
        System.out.println(lcs("ABCDEFG", "BCDGK"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("ABCDE", "A"));
        System.out.println(lcs("A", "BCDEF"));
    }
}

Explanation for code

1. lcs() Method:

• Takes two strings as input.
• Uses dynamic programming to find the longest common subsequence (LCS).
• Returns the LCS string.

Steps

• Create a DP Table: Stores the lengths of LCSs for substrings of different lengths.
• Fill the DP Table:
  • Iterates through characters of both strings.
  • For each cell, calculates the length of the LCS based on previous calculations:
    • If characters match, add 1 to the LCS length of the previous substrings.
    • If not, take the maximum LCS length from the previous options.
• Reconstruct the LCS: Backtracks through the DP table to find the characters in the LCS.
• Reverse the LCS: Since it's built backward, reverse it before returning.

Take away points

• Bottom-up approach: Builds the solution from smaller subproblems to the final LCS.
• Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
• Time complexity: O(mn), where m and n are string lengths.
• Space complexity: O(mn), due to the DP table.

Knapsack Problem implementation in Java

Imagine a hiker's backpack (the knapsack) with limited space (capacity).

They have a collection of items, each with a value (usefulness) and a weight (space it occupies).

The goal is to fill the backpack with the most valuable combination of items, without exceeding its weight capacity.

Visualizing the Items

Item 1:  (value 60, weight 10)
Item 2:  (value 100, weight 20)
Item 3:  (value 120, weight 30)

The Knapsack

Decision-Making

• Can't fit all items directly (total weight 60).
• Optimal choice would be to put these items in the bag
  
• Item: {value: 120, weight: 30}
• Item: {value: 100, weight: 20}

Optimal Solution

KNAPSACK  (capacity 50)
     (value 120, weight 30)

Key Points

• Knapsack represents a resource constraint (limited capacity).
• Items represent choices with associated values and constraints (weight).
• Goal is to maximize value within the constraint.
• Often involves trade-offs and strategic decision-making.

In formal language, given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, find the subset of items that maximizes the total value while fitting within the weight capacity.

Dynamic Programming Approach

1. Create a table dp:

   • Dimensions: (n + 1) x (W + 1), where n is the number of items and W is the knapsack capacity.
   • dp[i][w] stores the maximum value achievable using items up to the i-th item and with a maximum weight of w.

2. Fill the table:

   • Base cases:
     • dp[0][w] = 0 for all w (no items, value is 0).
     • dp[i][0] = 0 for all i (zero weight capacity, value is 0).
   • Recursive formula:
     • dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w (Choose between including or excluding the i-th item)
     • dp[i][w] = dp[i-1][w] otherwise (Item cannot be included due to weight constraint)

3. Solution:

• The maximum value is dp[n][W] (using all items with the knapsack capacity).
• Backtrack to find the selected items.

import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    public static List knapsack(List items, int capacity) {
        int[][] dp = new int[items.size() + 1][capacity + 1];

        // Build table dp[][] in a bottom-up manner
        for (int i = 0; i <= items.size(); i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (items.get(i - 1).weight <= w) {
                    dp[i][w] = Math.max(items.get(i - 1).value + dp[i - 1][w - items.get(i - 1).weight], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // Reconstruct the solution
        List selectedItems = new ArrayList<>();
        int i = items.size(), w = capacity;
        while (i > 0 && w > 0) {
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(items.get(i - 1));
                w -= items.get(i - 1).weight;
            }
            i--;
        }

        return selectedItems;
    }

    public static void main(String[] args) {
        List items = new ArrayList<>();
        items.add(new Item(60, 10));
        items.add(new Item(100, 20));
        items.add(new Item(120, 30));
        int capacity = 50;

        List selected = knapsack(items, capacity);
        System.out.println("Selected items: " + selected);
    }

    public static class Item {
        int value;
        int weight;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Item: {value: " + value + ", weight: " + weight + "}";
        }
    }
}

Explanation of code

1. Item Class:

• Represents an item with its value and weight.

2. knapsack() Method:

• Takes a list of items and a knapsack capacity as input.
• Uses dynamic programming to solve the 0-1 Knapsack Problem.
• Returns a list of selected items that maximize the total value without exceeding the capacity.

Steps

• Create a 2D DP array: Stores intermediate results for subproblems.
• Fill the DP array:
  • Iterate through items and capacities.
  • For each cell, calculate the maximum value achievable considering the current item and remaining capacity.
• Reconstruct the solution: Backtrack through the DP array to find the selected items.

Take away points

• Bottom-up approach: Builds the solution from smaller subproblems to the final solution.
• Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
• Time complexity: O(nW), where n is the number of items and W is the capacity.
• Space complexity: O(nW), due to the DP array.

Dijkstra algorithm implementation in Java

Purpose

• Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
• Commonly used in GPS navigation, network routing, and logistics planning.

Key Concepts

• Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
• Source Vertex: The starting point for finding shortest paths.
• Shortest Path: The path with the minimum total weight between two vertices.

Algorithm Steps

1. Initialization:

   • Create a set S to store visited vertices (initially empty).
   • Initialize an array distances with infinite values for all vertices except the source, which is set to 0.
   • Create a priority queue Q to store vertices, prioritized by their tentative distances.
   • Add the source vertex to Q.

2. Exploration Loop:

   • While Q is not empty:
     • Extract the vertex u with the minimum distance from Q.
     • Add u to the set S (mark as visited).
     • For each neighbor vertex v of u:
       • If v is not visited and the distance to v through u is shorter than its current distance:
         • Update the distance to v in the distances array.
         • Add v to the priority queue Q (or update its priority if already present).

3. Result:

   • The distances array now contains the shortest distances from the source vertex to all other vertices.
   • To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

public class Dijkstra {

    public static List dijkstra(Graph graph, int source) {
        int[] distances = new int[graph.numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
        pq.offer(source);

        boolean[] visited = new boolean[graph.numVertices];
        while (!pq.isEmpty()) {
            int u = pq.poll();
            visited[u] = true;
            for (Edge edge : graph.adjacencyList.get(u)) {
                int v = edge.to;
                int weight = edge.weight;
                if (!visited[v] && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    pq.offer(v);
                }
            }
        }

        return Arrays.stream(distances).boxed().collect(Collectors.toList());
    }

    public static Graph createRandomGraph(int numVertices) {
        Graph graph = new Graph(numVertices);
        Random random = new Random();
        // Add edges with random weights
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                // Decide whether to create an edge with 50% probability
                if (random.nextBoolean()) {
                    int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
                    graph.addEdge(i, j, weight);
                    graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
                }
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = createRandomGraph(9);
        graph.visualize();
        int source = 0;
        List distances = dijkstra(graph, source);
        System.out.println("Shortest distances from " + source + ": " + distances);
    }

    public static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Graph {
        int numVertices;
        List> adjacencyList;

        Graph(int numVertices) {
            this.numVertices = numVertices;
            adjacencyList = new ArrayList<>();
            for (int i = 0; i < numVertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to, int weight) {
            adjacencyList.get(from).add(new Edge(to, weight));
        }

        void visualize() {
            System.out.println("Graph Visualization:\n");
            for (int vertex = 0; vertex < numVertices; vertex++) {
                System.out.print(vertex + " -> ");
                for (Edge edge : adjacencyList.get(vertex)) {
                    System.out.print(edge.to + "(" + edge.weight + ") ");
                }
                System.out.println();
            }
        }
    }
}

Explanation of code

• Graph Representation

  • The Graph class models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights.
  • The Edge class encapsulates the destination vertex and weight of an edge.

• Dijkstra's Algorithm Implementation

  • The dijkstra(Graph, source) method implements the algorithm's logic:
    • It maintains a priority queue to explore vertices in order of their tentative distances.
    • It iteratively relaxes edges to update distances and explore reachable vertices.
    • It ultimately returns a list of the shortest distances from the source vertex to all other vertices.

• Random Graph Generation

  • The createRandomGraph(numVertices) method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.