Skip to content

ALGORITHM_EXPLANATION.md

Latest commit

 

History

History
661 lines (501 loc) · 17.3 KB

ALGORITHM_EXPLANATION.md

File metadata and controls

661 lines (501 loc) · 17.3 KB

Complete Algorithm Explanation - Like You're 5 Years Old

The Bridge Puzzle Problem

Imagine you have islands (circles with numbers). The number tells you how many bridges must connect to that island. Bridges can only be horizontal or vertical, and they can't cross each other.

Your goal: Connect all islands with the right number of bridges.

Part 1: PureDAC.java - Simple Divide and Conquer

🎯 BIG IDEA

Split the problem into smaller pieces, solve each piece with a simple greedy approach (no going back).

📊 DATA STRUCTURES (What we store in memory)

1. uniqueXs and uniqueYs (Lists of floats)

Example puzzle with islands at positions:
Island A at (100, 200)
Island B at (300, 200)  
Island C at (100, 400)

uniqueXs = [100, 300]  ← sorted unique X coordinates
uniqueYs = [200, 400]  ← sorted unique Y coordinates

Why? We convert the messy float positions into a clean grid system:

  • Island A → grid position (0, 0)
  • Island B → grid position (1, 0)
  • Island C → grid position (0, 1)

2. Region (A rectangle on the grid)

Region {
    int x = 0;     // Left grid column
    int y = 0;     // Top grid row
    int w = 2;     // Width (how many columns)
    int h = 2;     // Height (how many rows)
}

This means: "Look at grid from (0,0) to (1,1)" - a 2x2 area.

3. SplitStep (One divide operation)

SplitStep {
    Region r;           // Which region to split
    boolean vertical;   // True = cut vertically (|), False = horizontally (—)
    int cutPos;         // Where to cut
    int depth;          // How deep in the tree (0 = root)
}

4. splitSteps (Queue of SplitSteps)

A line of planned splits, like a to-do list:

[Split1, Split2, Split3, ...]
↑ Next to show

🔄 EXECUTION FLOW (What happens when you press "Next")

STEP 1: First Click - Initialization

User presses 'N' → doNextMove() is called

What happens:

  1. initialized == false, so we enter the initialization block
  2. Call planSplits():
planSplits() {
    // Get all islands
    List<Integer> islandIds = [23, 45, 67, 89, ...]
    
    // Collect their X and Y positions
    xs = [100, 300, 100, ...]
    ys = [200, 200, 400, ...]
    
    // Sort and remove duplicates
    uniqueXs = [100, 300]
    uniqueYs = [200, 400]
    
    // Create the starting region (entire grid)
    Region wholeGrid = new Region(0, 0, 2, 2);  // 2x2 grid
    
    // Recursively plan all splits
    planSplitsRec(wholeGrid, islandMap, depth=0);
}
  1. planSplitsRec() does the actual splitting:
planSplitsRec(Region(0,0, w=2, h=2), islands, depth=0) {
    // Check if region has more than 1 island
    islands_here = [A, B, C]  // 3 islands, so we split!
    
    // Split the LARGER dimension
    // width=2, height=2 → equal, but let's say we pick vertical
    splitVertical = true
    
    midX = 0 + (2 / 2) = 1  // Cut at column 1
    
    // Add this split to the queue
    splitSteps.add(SplitStep(Region(0,0,2,2), vertical=true, cutPos=1, depth=0))
    
    // Recursively split LEFT half: columns [0..0]
    planSplitsRec(Region(0, 0, 1, 2), islands, depth=1)
    
    // Recursively split RIGHT half: columns [1..1]  
    planSplitsRec(Region(1, 0, 1, 2), islands, depth=1)
}

Result after initialization:

splitSteps = [Split_at_col1, Split_left_half, Split_right_half]
nextIsSplit = true

STEP 2: Second Click - Show First Split

User presses 'N' again → doNextMove()

What happens:

  1. splitSteps is NOT empty
  2. nextIsSplit == true, so we show a split
SplitStep s = splitSteps.poll();  // Remove first from queue
// s = Split_at_col1

logSplit(s);   // Print to console
drawSplit(s);  // Draw colored rectangles on screen

drawSplit() breakdown:

drawSplit(s) {
    // Clear previous drawings
    entitySystem.clearDebugLines();
    
    // Calculate world coordinates
    rx1 = worldXAt(0) = uniqueXs[0] = 100    // Left edge
    rx2 = worldXAt(1) = uniqueXs[1] = 300    // Right edge
    ry1 = worldYAt(0) = uniqueYs[0] = 200    // Top edge
    ry2 = worldYAt(1) = uniqueYs[1] = 400    // Bottom edge
    
    // Since s.vertical == true:
    leftW = cutPos - region.x = 1 - 0 = 1   // Left half is 1 column wide
    rightW = (region.x + region.w) - cutPos = 2 - 1 = 1  // Right half is 1 column
    
    // Draw LEFT half (green tint)
    drawRect(100, 200, 100, 400, color=GREEN_TINT)
    
    // Draw RIGHT half (orange tint)
    drawRect(300, 200, 300, 400, color=ORANGE_TINT)
    
    // Draw WHITE outline around LEFT half (this goes next in recursion)
    drawRect(100, 200, 100, 400, thickness=6, color=WHITE)
    
    // Draw the actual CUT LINE (purple)
    cx = worldXBetween(1) = (100 + 300) / 2 = 200
    addLine(200, minY, 200, maxY, thickness=6, color=PURPLE)
    
    // Draw YELLOW 'X' for next split in queue
    next = splitSteps.peek() = Split_left_half
    drawRect(next.region, color=YELLOW)
    addLine(diagonal X)
}

Visual result:

Screen shows:
┌─────────────┐
│ GREEN       │ ← Left half (column 0)
│   [A]       │
│      | ← Purple cut line at column 1
│   [C]ORANGE │ ← Right half (column 1)
│       [B]   │
└─────────────┘
White outline around GREEN (next to recurse)
Yellow X on the actual next region from queue
  1. Set nextIsSplit = false (next time we conquer)

STEP 3: Third Click - Make a Bridge Connection

User presses 'N' → doNextMove()

What happens:

  1. splitSteps is NOT empty
  2. nextIsSplit == false, so we conquer
doOneConquerMove() {
    prev = edgeSystem.getPrevMove();  // -1 (no bridges yet)
    greedy.doNextMove();              // Greedy makes one bridge decision
    visualizeGreedyDelta(prev);       // Show what changed
}

Inside greedy.doNextMove():

GreedySolver {
    // Has a priority queue: pick island with HIGHEST bridge requirement
    pq = [(need=4, island=A), (need=3, island=B), ...]
    
    top = pq.poll() = (need=4, island=A)
    
    // Find A's neighbors
    neighbors = [B, C]
    
    // Pick first valid neighbor (doesn't cross, not full)
    // Connect A → B with 1 bridge
    edgeSystem.createEdge(A, B, count=1)
    
    // Update A's remaining need: 4 → 3
    A.bridgeNo = 3
}

visualizeGreedyDelta():

newMoveEdgeId = edgeSystem.getPrevMove();  // Now points to A-B edge
e = getEdgeComponent(newMoveEdgeId);       // e.nodeA=A, e.nodeB=B

// Draw green highlights and line
addHighlight(A, GREEN)
addHighlight(B, GREEN)
addLine(A.x, A.y, B.x, B.y, GREEN)

LOG: "Bridge A(need=3) <-> B(need=2) | count=1 | Reason: Greedy picks highest-demand"

Visual result:

Screen shows:
[A]━━━━━━━[B]  ← Green line between A and B
 ↑GREEN   ↑GREEN highlights
  1. Set nextIsSplit = true (next time we split again)

STEP 4-N: Alternating Split → Conquer → Split → Conquer...

The pattern repeats:

  • Even clicks: Show a split (DIVIDE phase)
  • Odd clicks: Make a bridge (CONQUER phase)

Once splitSteps queue is empty:

if (!splitSteps.isEmpty()) {
    // Alternate split/conquer
} else {
    // Only conquer from now on
    doOneConquerMove();
}

🎓 WHY IS IT CALLED "PURE DAC"?

Divide: We split the grid recursively (just like merge sort splits an array).

Conquer: We use a greedy algorithm to make bridge decisions.

Pure: We NEVER undo a decision. Once a bridge is placed, it stays. This is not guaranteed to solve all puzzles, but it shows the DAC pattern clearly.

Part 2: DACSolver.java - DAC with Backtracking

🎯 BIG IDEA

Same splitting (divide) as PureDAC, but instead of greedy, we use DFS backtracking to systematically try all valid bridge combinations until we find a solution.

📊 ADDITIONAL DATA STRUCTURES

1. CandidateEdge (A possible bridge)

CandidateEdge {
    int aId = 23;        // Island A's ID
    int bId = 45;        // Island B's ID
    float ax = 100;      // A's X position
    float ay = 200;      // A's Y position
    float bx = 300;      // B's X position
    float by = 200;      // B's Y position
    boolean horizontal = true;  // Is this a horizontal bridge?
}

We build a list of ALL possible edges at initialization:

edges = [A-B, A-C, B-D, ...]

2. Backtracker (The DFS search engine)

Backtracker {
    List<CandidateEdge> edges;     // All possible bridges
    int[] edgeCounts;              // How many bridges on each edge
                                   // -1 = unassigned, 0 = skip, 1-2 = bridges
    
    int[] remaining;               // How many bridges each island still needs
    int[] unassignedInc;           // How many unassigned edges touch each island
    
    LinkedList<Frame> stack;       // DFS call stack
}

Example state:

edges = [A-B, A-C, B-C]
edgeCounts = [-1, -1, -1]  ← All unassigned initially

remaining = [4, 3, 2]  ← Island 0 needs 4 bridges, island 1 needs 3, island 2 needs 2
unassignedInc = [2, 2, 2]  ← Each island has 2 unassigned edges touching it

3. Frame (One level of the DFS tree)

Frame {
    int edgeIdx = 0;       // Which edge we're deciding
    int nextTry = 2;       // Next count to try (2, 1, or 0)
    int chosen = -1;       // What we actually chose (-1 = nothing yet)
}

Think of it like a decision tree:

           Root
          /  |  \
        2   1    0   ← Try 2 bridges, 1 bridge, or 0 bridges on edge 0
       /
     ...

🔄 EXECUTION FLOW (DACSolver)

STEP 1-N: Split Phase (Identical to PureDAC)

Same alternating split visualization until splitSteps queue is empty.

STEP N+1: First DFS Step

User presses 'N' → doNextMove()

What happens:

  1. splitSteps is empty
  2. Call bt.step():
Backtracker.step() {
    // Stack is empty, so select first edge
    if (stack.isEmpty()) {
        next = selectNextEdge();  // Find first unassigned edge
        // next = 0 (edge A-B)
        
        maxTry = maxTryFor(0);
        // maxTry = min(2, remaining[A], remaining[B])
        //        = min(2, 4, 3) = 2
        
        stack.push(Frame(edgeIdx=0, nextTry=2));
    }
    
    // Try count = 2
    f = stack.peek();  // Frame(edgeIdx=0, nextTry=2)
    count = f.nextTry--;  // count=2, nextTry becomes 1
    
    // Can we assign 2 bridges to A-B?
    if (canAssign(0, 2)) {
        commitAssign(0, 2);
        // edgeCounts[0] = 2
        // remaining[A] = 4 - 2 = 2
        // remaining[B] = 3 - 2 = 1
        
        f.chosen = 2;
        
        // Select next edge to decide
        next = selectNextEdge();  // edge A-C (index 1)
        stack.push(Frame(edgeIdx=1, nextTry=...));
        
        // VISUALIZE
        drawGreenLine(A, B);
        LOG: "DFS ADD: Edge A(rem=2) <-> B(rem=1) | count=2"
        
        return Step.ADD;
    } else {
        // Rejected! Log why
        LOG: "Reject A-B count=2 | Reason: would cross existing bridge"
        // Try count=1 next time
    }
}

Visual result:

[A]═══════[B]  ← Green double line (count=2)
 ↑GREEN  ↑GREEN highlights

STEP N+2: Next DFS Step (Continue Forward)

bt.step() {
    // Stack has: [Frame(edge=0, chosen=2), Frame(edge=1, nextTry=2)]
    
    f = stack.peek();  // Frame(edge=1, nextTry=2)
    count = f.nextTry--;  // Try 2 bridges on edge A-C
    
    if (canAssign(1, 2)) {
        commitAssign(1, 2);
        ...
        return Step.ADD;
    } else {
        LOG: "Reject A-C count=2 | Reason: remaining[A]=2, can't assign 2"
        // Will try count=1 next
    }
}

STEP N+K: Backtracking (Dead End)

bt.step() {
    // Suppose we're at Frame(edge=5, nextTry=0)
    // We've tried all counts [2, 1, 0] and none worked
    
    f = stack.peek();
    // nextTry < 0, so we exhausted this frame
    
    LOG: "Exhausted all counts for edge X<->Y, popping stack"
    stack.pop();
    
    // Now back to previous frame
    f = stack.peek();  // Frame(edge=4, chosen=1)
    
    // Undo the previous decision
    if (f.chosen >= 0) {
        count = f.chosen;  // count=1
        undoAssign(4, 1);
        // edgeCounts[4] = -1  (back to unassigned)
        // remaining[X] += 1
        // remaining[Y] += 1
        
        f.chosen = -1;
        
        if (count > 0) {
            // VISUALIZE REMOVAL
            drawRedLine(X, Y);
            LOG: "DFS BACKTRACK: Remove edge X<->Y count=1 (dead end, trying alternative)"
            return Step.REMOVE;
        }
    }
}

Visual result:

[X]━━━━━[Y]  ← Red line showing removal
 ↑RED   ↑RED highlights

FINAL STEP: Solution Found

bt.step() {
    if (stack.isEmpty()) {
        // Check if solution is valid
        if (allRemainingZero() && isConnectedSolution()) {
            return Step.SOLVED;
        }
    }
}
doNextMove() {
    res = bt.step();
    if (res == Step.SOLVED) {
        // Highlight all islands green
        markSolved();
        LOG: "✓ SOLVED: All islands satisfied + graph connected"
    }
}

🔍 KEY VALIDATION: canAssign()

Before we try assigning count bridges to an edge, we check:

canAssign(edgeIdx, count) {
    // 1. Count must be 0, 1, or 2
    if (count < 0 || count > 2) return false;
    
    // 2. Both islands must have enough remaining need
    if (count > remaining[A] || count > remaining[B]) return false;
    
    // 3. After this assignment, each island must still be satisfiable
    remA = remaining[A] - count;
    unA = unassignedInc[A] - 1;
    if (remA > 2 * unA) return false;  // Can't get remA bridges from unA edges
    
    // 4. No crossing with existing bridges
    if (count > 0 && crossesAnyAssigned(edgeIdx)) return false;
    
    // 5. Check ALL OTHER islands too
    for (each island i) {
        if (remaining[i] > 2 * unassigned[i]) return false;
    }
    
    return true;
}

Example rejection:

Island A needs 3 bridges remaining
Island A has 1 unassigned edge remaining
Maximum bridges from 1 edge = 2 * 1 = 2
3 > 2 → IMPOSSIBLE → Reject this path

🆚 COMPARISON TABLE

Feature PureDAC DACSolver
Split visualization ✅ Same ✅ Same
Conquer strategy Greedy (priority queue) DFS Backtracking
Can undo? ❌ No ✅ Yes (red lines)
Visual feedback Green lines only Green (add) + Red (remove)
Solves all puzzles? ❌ No (greedy can fail) ✅ Yes (if solution exists)
Speed ⚡ Fast 🐌 Slower (tries many paths)
Good for teaching? ✅ Yes (simple) ⚠️ Harder to follow

🎨 VISUAL LEGEND

When you run the solvers, here's what each color means:

Color Meaning
🟦 Blue rectangle Current region being split
🟪 Purple line The cut line (where we divide)
🟢 Green tint Left/Top half after split
🟠 Orange tint Right/Bottom half after split
⬜ White thick outline Next half to recurse into (follows tree order)
🟨 Yellow 'X' Actual next split from the queue
🟢 Green highlights + line Bridge added
🔴 Red highlights + line Bridge removed (backtracking)

🧪 SIMPLE EXAMPLE WALKTHROUGH

Let's solve a tiny 2-island puzzle:

[2]────────[2]

Both islands need 2 bridges.

PureDAC:

  1. Split: Vertical cut between them (visual only)
  2. Conquer: Greedy picks island with highest need (tie: both 2)
  3. Connects them with 1 bridge: [2]━[2] (both now need 1)
  4. Conquer: Adds second bridge: [2]══[2] (both satisfied)
  5. ✅ Solved!

DACSolver:

  1. Split: Same visual cut
  2. DFS: Select edge 0 (only edge)
  3. Try count=2:
    • Check: Can we assign 2 bridges?
    • Both islands need 2 → ✅ Valid
    • Assign: edgeCounts[0] = 2
    • Draw green double line
  4. Next edge: selectNextEdge() = -1 (no more edges)
  5. Check solution:
    • All remaining = 0? ✅ Yes
    • All islands connected? ✅ Yes
  6. ✅ Solved!

💡 TIPS FOR EXPLAINING TO YOUR EVALUATOR

  1. Start with the problem: "Bridges puzzle - connect islands with correct number of bridges."

  2. Explain the Divide: "Like merge sort, we split the grid into smaller regions recursively."

  3. Show the difference:

    • "PureDAC uses greedy - simple but can fail."
    • "DACSolver uses backtracking - systematic, always finds solution if it exists."

  4. Use the visuals: "See the colors? Green tint is one half, orange is the other. White outline shows which half we split next."

  5. Explain backtracking: "Red line means we tried this bridge but it led to a dead end, so we remove it and try something else."

  6. Show the logs: Every decision is logged with a reason. You can trace exactly what the algorithm is thinking.

🔑 KEY TAKEAWAYS

PureDAC:

  • ✅ Shows DAC pattern clearly
  • ✅ Easy to understand
  • ✅ Fast
  • ❌ Might not solve hard puzzles

DACSolver:

  • ✅ Always finds solution (if exists)
  • ✅ Shows backtracking visually
  • ✅ Every decision is validated and logged
  • ❌ More complex to explain
  • ❌ Slower on large puzzles

Both algorithms split the same way. The difference is ONLY in how they make bridge decisions (conquer phase).