🐢 Squirtle

Advanced Subset Sum Optimization Toolkit using Backtracking Techniques

███████╗ ██████╗ ██╗   ██╗██╗██████╗ ████████╗██╗     ███████╗
██╔════╝██╔═══██╗██║   ██║██║██╔══██╗╚══██╔══╝██║     ██╔════╝
███████╗██║   ██║██║   ██║██║██████╔╝   ██║   ██║     █████╗
╚════██║██║▄▄ ██║██║   ██║██║██╔══██╗   ██║   ██║     ██╔══╝
███████║╚██████╔╝╚██████╔╝██║██║  ██║   ██║   ███████╗███████╗
╚══════╝ ╚══▀▀═╝  ╚═════╝ ╚═╝╚═╝  ╚═╝   ╚═╝   ╚══════╝╚══════╝

A production-grade CLI tool and NPM package for solving, analyzing, benchmarking, and visualizing the Subset Sum Problem using multiple advanced optimization techniques.

✨ Features

• 8 Algorithm Implementations — From naive brute-force to Meet-in-the-Middle
• Performance Benchmarking — Compare algorithms with detailed metrics
• Recursion Tree Visualization — Beautiful ANSI-colored tree rendering
• Algorithm Racing — Race algorithms head-to-head
• Educational Mode — Learn about backtracking, pruning, and optimization
• Dataset Generation — Random, worst-case, sparse, and dense datasets
• Stress Testing — Push algorithms to their limits
• Parallel Execution — Distribute work across CPU cores
• Programmatic API — Use as an NPM package in your own projects

📦 Installation

# Global CLI installation
npm install -g squirtle

# Local project dependency
npm install squirtle

🚀 CLI Usage

Solve a Subset Sum Problem

squirtle solve --set 3,34,4,12,5,2 --target 9
squirtle solve --set 1,2,3,4,5,6,7,8 --target 15 --algo branch-bound
squirtle solve --set 1,5,11,5 --target 11 --all

Benchmark Algorithms

squirtle benchmark dataset.json
squirtle benchmark --size 10,15,20,25

Compare Algorithms

squirtle compare --set 1,2,3,4,5,6,7,8,9,10 --target 25 -a naive branch-bound meet-in-middle

Visualize Recursion Tree

squirtle visualize --set 1,2,3,4 --target 6
squirtle visualize --set 2,3,5,7 --target 10 --depth 5

Generate Datasets

squirtle generate --size 20 --type random --output data.json
squirtle generate --size 15 --type worst-case
squirtle generate --size 30 --type dense --count 5

Stress Test

squirtle stress --start 5 --end 30 --step 5
squirtle stress --algo branch-bound,heuristic --timeout 5000

Race Algorithms

squirtle race --set 1,2,3,4,5,6,7,8,9,10,11,12 --target 30

Educational Explanations

squirtle explain recursion
squirtle explain pruning
squirtle explain branch-bound
squirtle explain meet-in-middle
squirtle explain states

📚 Programmatic API

import { solveSubset, autoSolve, compareAlgorithms } from 'squirtle';

// Basic solve
const result = solveSubset(
  { set: [3, 34, 4, 12, 5, 2], target: 9 },
  'branch-bound'
);
console.log(result.found);       // true
console.log(result.subsets[0]);  // [4, 5] or [3, 4, 2]

// Auto-select best algorithm
const auto = autoSolve({ set: [1, 5, 11, 5], target: 11 });

// Compare algorithms
const comparison = compareAlgorithms(
  { set: [2, 3, 7, 8, 10], target: 11 },
  ['naive', 'branch-bound', 'meet-in-middle']
);

🧠 Algorithms

| Algorithm | Time Complexity | Space | Best For | |-----------|----------------|-------|----------| | Naive Backtracking | O(2^n) | O(n) | Small sets, baseline | | Optimized Backtracking | O(2^n) | O(n) | Small-medium sets | | Pruned DFS | O(2^n)* | O(n) | Medium sets with good pruning | | Branch and Bound | O(2^n)* | O(n) | Skewed targets | | Memoization Hybrid | O(n×target) | O(n×target) | Small targets | | Meet-in-the-Middle | O(2^(n/2)×n) | O(2^(n/2)) | n ≤ 40 | | Heuristic Search | O(2^n)* | O(n) | Large solvable instances | | Parallel Backtracking | O(2^n / p) | O(n×p) | Multi-core systems |

*With pruning, average case is significantly better than worst case.

📊 Performance Metrics

Every solve operation tracks:

• Execution Time — Wall-clock time in milliseconds
• Recursive Calls — Total function invocations
• Branches Explored — Search tree nodes visited
• Branches Pruned — Subtrees eliminated early
• Max Recursion Depth — Deepest point in search tree
• Memory Used — Heap memory consumed
• Solution Count — Number of valid subsets found
• Branching Factor — Average children per node

🏗️ Project Structure

squirtle/
├── src/
│   ├── algorithms/       # All 8 algorithm implementations
│   ├── benchmark/        # Benchmarking engine
│   ├── cli/              # CLI commands (Commander.js)
│   ├── core/             # Core solver engine
│   ├── types/            # TypeScript type definitions
│   ├── utils/            # Formatting, metrics, generators
│   ├── visualization/    # Tree renderer, splash screen
│   ├── workers/          # Worker thread implementation
│   └── index.ts          # Public API exports
├── tests/                # Vitest test suites
├── examples/             # Usage examples and datasets
├── package.json
├── tsconfig.json
├── tsup.config.ts
└── vitest.config.ts

🧪 Testing

# Run all tests
npm test

# Watch mode
npm run test:watch

# Type checking
npm run lint

🔨 Development

# Clone and install
git clone <repo-url>
cd squirtle
npm install

# Build
npm run build

# Run CLI locally
node dist/cli/index.js solve --set 1,2,3,4,5 --target 9

🤝 Contributing

1. Fork the repository
2. Create a feature branch (git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add amazing feature')
4. Push to the branch (git push origin feature/amazing-feature)
5. Open a Pull Request

Guidelines

• Write tests for new algorithms or features
• Follow existing code style and TypeScript conventions
• Update documentation for CLI changes
• Add benchmark cases for new algorithms

📄 License

MIT © 2025