Project 35: "The Deep Reasoner (Claude Code)" — Algorithmic Reasoning

Project 35: “The Deep Reasoner (Claude Code)” — Algorithmic Reasoning

Attribute	Value
File	`KIRO_CLI_LEARNING_PROJECTS.md`
Main Programming Language	Python
Coolness Level	Level 4: Hardcore Tech Flex
Difficulty	Level 3: Advanced
Knowledge Area	Algorithmic Reasoning

What you’ll build: Solve a complex algorithmic problem using a scratchpad file and Opus model.

Why it teaches Reasoning: You use high-end reasoning as a tool.

Success criteria:

The solution passes a non-trivial test set.

Real World Outcome

You’ll have a Kiro workflow that solves complex algorithmic problems by:

Breaking down problems into sub-problems (problem decomposition)
Using a scratchpad to work through examples and edge cases
Switching to Opus (Claude Opus 4.5) for deep reasoning tasks
Iterating on solutions based on test failures
Generating test cases to validate correctness

Example Session:

$ kiro "Solve LeetCode #1235: Maximum Profit in Job Scheduling using dynamic programming with binary search. Use Opus for reasoning."

🧠 Deep Reasoner - Algorithmic Problem Solving
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

📋 Problem Analysis Phase (using Opus)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Switching to Claude Opus 4.5 for deep reasoning...

Problem: Maximum Profit in Job Scheduling
Inputs:
  - startTime: [1,2,3,3]
  - endTime: [3,4,5,6]
  - profit: [50,10,40,70]
Output: 120 (jobs 0 and 3)

Constraint: Cannot take two overlapping jobs.

📝 Creating Scratchpad: /tmp/job_scheduling_scratchpad.md

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SCRATCHPAD: Job Scheduling Problem
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

## Step 1: Understanding the Problem

Jobs:
Job 0: [1, 3] profit=50
Job 1: [2, 4] profit=10
Job 2: [3, 5] profit=40
Job 3: [3, 6] profit=70

Overlapping check:
- Job 0 [1,3] overlaps with Job 1 [2,4]? YES (2 < 3)
- Job 0 [1,3] overlaps with Job 2 [3,5]? NO (3 >= 3)
- Job 0 [1,3] overlaps with Job 3 [3,6]? NO (3 >= 3)

## Step 2: Brute Force Approach

Try all subsets: 2^n = 16 combinations
- {} → profit = 0
- {0} → profit = 50
- {1} → profit = 10
- {0,2} → profit = 90 (0 ends at 3, 2 starts at 3 ✓)
- {0,3} → profit = 120 (0 ends at 3, 3 starts at 3 ✓) ← MAX!

Brute force works but O(2^n) - too slow for n=50,000!

## Step 3: Dynamic Programming Insight

Key observation: If we sort jobs by end time, we can use DP!

dp[i] = max profit using jobs 0..i

For each job i:
  Option 1: Skip job i → dp[i] = dp[i-1]
  Option 2: Take job i → dp[i] = profit[i] + dp[last_compatible_job]

Finding last_compatible_job:
  - Need job j where endTime[j] <= startTime[i]
  - Binary search on sorted end times! (O(log n))

## Step 4: Algorithm Design

1. Sort jobs by end time
2. For each job i:
   - Binary search to find latest job j where endTime[j] <= startTime[i]
   - dp[i] = max(dp[i-1], profit[i] + dp[j])
3. Return dp[n-1]

Time: O(n log n) - sorting + binary search per job
Space: O(n) - DP array

## Step 5: Edge Cases to Test

- Single job → profit = job profit
- All jobs overlap → profit = max single job
- No jobs → profit = 0
- Jobs already sorted vs unsorted
- Identical start/end times

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

✅ Reasoning complete. Generating solution...

🐍 Generating Python Implementation...

def jobScheduling(startTime, endTime, profit):
    # Combine and sort jobs by end time
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    n = len(jobs)

    # Binary search for last compatible job
    def find_last_compatible(i):
        left, right = 0, i - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if jobs[mid][1] <= jobs[i][0]:  # endTime[mid] <= startTime[i]
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        return result

    # DP array
    dp = [0] * n
    dp[0] = jobs[0][2]  # First job profit

    for i in range(1, n):
        # Option 1: Skip job i
        skip = dp[i - 1]

        # Option 2: Take job i
        take = jobs[i][2]  # Current job profit
        last_compatible = find_last_compatible(i)
        if last_compatible != -1:
            take += dp[last_compatible]

        dp[i] = max(skip, take)

    return dp[n - 1]

✅ Solution generated: solution.py

🧪 Generating Test Cases...

# Test 1: Example from problem
assert jobScheduling([1,2,3,3], [3,4,5,6], [50,10,40,70]) == 120

# Test 2: All overlapping jobs
assert jobScheduling([1,1,1], [2,3,4], [5,6,4]) == 6

# Test 3: No overlapping jobs
assert jobScheduling([1,2,3], [2,3,4], [5,6,4]) == 15

# Test 4: Single job
assert jobScheduling([1], [2], [100]) == 100

# Test 5: Two identical jobs
assert jobScheduling([1,1], [2,2], [50,50]) == 50

Running tests...
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Test 1: PASSED (120 == 120)
✅ Test 2: PASSED (6 == 6)
✅ Test 3: PASSED (15 == 15)
✅ Test 4: PASSED (100 == 100)
✅ Test 5: PASSED (50 == 50)

All tests passed! ✓

📊 Complexity Analysis:
├─ Time: O(n log n) - sorting + binary search
├─ Space: O(n) - DP array
└─ Verified against 50,000 job test set ✓

💡 Key Insights (from scratchpad):
1. Sorting by end time enables DP
2. Binary search finds last compatible job in O(log n)
3. Trade-off: Skip vs Take each job

Would you like me to:
1. Add more test cases?
2. Optimize space to O(1)?
3. Explain the binary search in more detail?

What You See:

Step-by-step problem breakdown in scratchpad file
Opus-powered reasoning for algorithm design
Generated Python solution with binary search optimization
Comprehensive test suite with edge cases
Complexity analysis and verification

The Core Question You’re Answering

“How can AI leverage extended reasoning (Claude Opus) and structured scratchpad files to solve problems that require multi-step logical deduction?”

This project teaches metacognitive problem-solving: using an AI system that knows when to slow down and think deeply. Switching to Opus for hard problems is analogous to a developer pausing to whiteboard a solution before coding.

Concepts You Must Understand First

Stop and research these before coding:

Dynamic Programming Fundamentals
- What is overlapping subproblems and optimal substructure?
- How do you identify when DP is applicable?
- What is the difference between top-down (memoization) and bottom-up (tabulation)?
- Book Reference: “Introduction to Algorithms” (CLRS) - Ch. 15
Binary Search and Divide-and-Conquer
- How does binary search achieve O(log n) time?
- What invariants must be maintained during binary search?
- When is binary search applicable (sorted data, monotonic function)?
- Book Reference: “Algorithms” by Sedgewick & Wayne - Ch. 3.1
Problem Decomposition Strategies
- How do you break a complex problem into smaller sub-problems?
- What is the “simplify and generalize” technique?
- How do you identify base cases vs recursive cases?
- Book Reference: “How to Solve It” by George Pólya - Ch. 1-2
Complexity Analysis
- How do you calculate time complexity (Big-O notation)?
- What is the difference between time complexity and space complexity?
- How do you identify bottlenecks (profiling, asymptotic analysis)?
- Book Reference: “Grokking Algorithms” by Aditya Bhargava - Ch. 1-2

Questions to Guide Your Design

Before implementing, think through these:

Model Selection Strategy
- When should you use Opus (slow, expensive, deep reasoning)?
- When should you use Sonnet (fast, cheaper, good for most tasks)?
- How do you detect that a problem requires deep reasoning?
- How do you balance cost vs solution quality?
Scratchpad Design
- What should go in the scratchpad (examples, edge cases, algorithm sketches)?
- How do you structure the scratchpad (markdown sections, code blocks)?
- How do you prevent the scratchpad from growing too large (context limits)?
- How do you use the scratchpad to validate the final solution?
Test Case Generation
- How do you generate edge cases (empty input, single element, all same values)?
- How do you generate stress tests (large n, worst-case inputs)?
- How do you verify correctness (test against brute force, known solutions)?
- How do you measure coverage (all branches, all edge cases)?
Solution Validation
- How do you verify time complexity matches the theoretical analysis?
- How do you test on large inputs (n=50,000, n=100,000)?
- How do you handle time limit exceeded (TLE) failures?
- How do you iterate when tests fail (analyze failure, refine algorithm)?

Thinking Exercise

Exercise: Solve a Two-Pointer Problem with Scratchpad

Problem: “Three Sum - Find all unique triplets in an array that sum to zero”

# Input: nums = [-1, 0, 1, 2, -1, -4]
# Output: [[-1, -1, 2], [-1, 0, 1]]

Scratchpad Template:

## Step 1: Understand the Problem
- Input: Array of integers (may have duplicates)
- Output: All unique triplets that sum to 0
- Constraint: No duplicate triplets in result

## Step 2: Examples and Edge Cases
Example 1: [-1, 0, 1, 2, -1, -4]
  Sort: [-4, -1, -1, 0, 1, 2]
  Fix -4: need two numbers that sum to 4 → no solution
  Fix -1: need two numbers that sum to 1 → (-1, 0, 1) ✓ and (-1, 2, -1) ✓

Edge cases:
- All zeros: [0, 0, 0] → [[0, 0, 0]]
- No solution: [1, 2, 3] → []
- Duplicates: [-1, -1, 0, 1, 1] → [[-1, 0, 1]]

## Step 3: Brute Force
Try all triplets: O(n³)
for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      if nums[i] + nums[j] + nums[k] == 0:
        result.append([nums[i], nums[j], nums[k]])

Too slow for n=3000!

## Step 4: Optimized Approach
Sort array: O(n log n)
Fix first element, use two pointers for remaining: O(n²)

Questions to answer:

How do you avoid duplicate triplets (skip same values)?
How do you move the two pointers (left++, right–)?
What is the time complexity (O(n²) after sorting)?
How do you test this (unit tests, large inputs)?

The Interview Questions They’ll Ask

“Explain the difference between using Claude Sonnet vs Claude Opus. When would you choose each?”
“How would you design a scratchpad system that prevents context overflow (scratchpad growing too large)?”
“Walk me through how you’d debug a dynamic programming solution that passes small tests but fails large ones.”
“How would you validate that an AI-generated algorithm matches the claimed time complexity?”
“Explain how you’d use test-driven development with AI code generation (write tests first, then generate solution).”
“How would you prevent AI from overfitting to test cases (generating code that passes tests but is wrong)?”

Hints in Layers

Hint 1: Opus Model Selection Use Opus when:

Problem requires multi-step logical reasoning (DP, graph algorithms)
Problem has non-obvious insights (greedy choice, invariant)
Initial Sonnet solution fails tests and you need deeper analysis
You need detailed explanations for teaching/understanding

Use Sonnet when:

Problem is straightforward (two-pointer, hash map)
You need fast iteration (testing multiple approaches)
Cost is a concern (Opus is 5x more expensive)

Hint 2: Scratchpad Structure

# Problem: [Title]

## Step 1: Problem Understanding
[Restate in own words, identify constraints]

## Step 2: Examples (3-5 examples, including edge cases)
[Work through examples by hand]

## Step 3: Brute Force
[Naive O(n²) or O(2^n) solution, analyze why it's slow]

## Step 4: Optimization Insight
[Key observation that leads to faster solution]

## Step 5: Algorithm Design
[Pseudocode or step-by-step description]

## Step 6: Complexity Analysis
[Time and space complexity with justification]

## Step 7: Edge Cases
[List all edge cases to test]

Hint 3: Test Generation Strategy Generate tests in this order:

Example from problem statement (sanity check)
Edge cases (empty, single element, all same)
Boundary cases (min/max values, size limits)
Stress tests (large n, worst-case complexity)
Random tests (fuzzing for unexpected bugs)

Hint 4: Solution Validation Loop

1. Generate solution using Opus + scratchpad
2. Run tests (example + edge + stress)
3. If all pass → done ✓
4. If some fail:
   a. Analyze failure (wrong output, TLE, crash)
   b. Add failing case to scratchpad
   c. Ask Opus to refine solution
   d. Go to step 2

Hint 5: Complexity Verification

import time

# Test time complexity empirically
for n in [100, 1000, 10000, 100000]:
    input_data = generate_test_input(n)
    start = time.time()
    result = jobScheduling(input_data)
    elapsed = time.time() - start
    print(f"n={n:6d} time={elapsed:.4f}s")

# Expected for O(n log n):
# n=100 time=0.0001s
# n=1000 time=0.0012s (10x input → ~10x time)
# n=10000 time=0.015s (10x input → ~13x time)
# n=100000 time=0.20s (10x input → ~13x time)

Books That Will Help

Topic	Book	Chapter
Dynamic programming	“Introduction to Algorithms” (CLRS)	Ch. 15 (Dynamic Programming)
Problem-solving strategies	“How to Solve It” by George Pólya	Ch. 1-2 (Understanding, Devising a Plan)
Algorithm design	“Algorithms” by Sedgewick & Wayne	Ch. 3-6 (Sorting, Searching, DP)
Complexity analysis	“Grokking Algorithms” by Aditya Bhargava	Ch. 1-2 (Big-O Notation)
Competitive programming	“Competitive Programming 4” by Steven Halim	Ch. 3 (Problem Solving Paradigms)
Interview prep	“Cracking the Coding Interview” by Gayle McDowell	Ch. 8-9 (DP, Recursion)

Common Pitfalls & Debugging

Problem 1: “Solution passes small tests but gets Time Limit Exceeded (TLE) on large inputs”

Why: Algorithm is O(n³) or O(2^n), too slow for n=50,000
Fix: Analyze complexity in scratchpad, find O(n log n) or O(n²) solution
Quick test: Run on n=100, n=1000, n=10000 and measure time scaling

Problem 2: “Opus generates a solution but doesn’t explain the key insight”

Why: Opus jumps to solution without showing reasoning steps
Fix: Ask Opus to “work through examples in the scratchpad first, then generate code”
Pattern: Always request scratchpad-driven reasoning before code

Problem 3: “Generated solution is correct but hard to understand (no comments, cryptic variable names)”

Why: Optimization prioritized over readability
Fix: Ask for “readable solution with comments explaining each step”
Example: Change dp[i] = max(dp[i-1], p[i] + dp[f(i)]) to include comment explaining skip vs take

Problem 4: “Tests pass but solution fails on edge case not in test suite”

Why: Incomplete test coverage (missing edge case)
Fix: Add property-based testing or fuzz testing
Example: Use Hypothesis library to generate random test inputs

Problem 5: “Binary search has off-by-one error (infinite loop or wrong answer)”

Why: Incorrect loop invariant (left <= right vs left < right)
Fix: Trace through binary search by hand on small example
Debugging: Print left, right, mid at each iteration to see what’s wrong

Problem 6: “Opus uses too much context analyzing the problem (exceeds token limit)”

Why: Scratchpad includes too much detail (full trace of all examples)
Fix: Summarize examples instead of full traces
Pattern: “Show 2-3 key examples, not all 10 test cases”