Metadata-Version: 2.4
Name: pydp-engine
Version: 0.1.0
Summary: An intelligent, declarative Dynamic Programming engine for Python.
Author: PyDP
License: MIT
Project-URL: Homepage, https://github.com/pydp/pydp
Keywords: dynamic-programming,memoization,algorithms,dp,optimization
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: MIT License
Classifier: Topic :: Scientific/Engineering
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Requires-Python: >=3.9
Description-Content-Type: text/markdown
Provides-Extra: viz
Requires-Dist: graphviz>=0.20; extra == "viz"
Requires-Dist: matplotlib>=3.5; extra == "viz"
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"

# PyDP — an intelligent, declarative Dynamic Programming engine

PyDP lets you write Dynamic Programming solutions by declaring **only the
recurrence relation**. The engine handles memoization, dependency analysis,
execution order, memory-optimization analysis, statistics, and visualization
automatically.

> Describe the recurrence. Let the engine handle everything else.

```python
from pydp import dp

@dp
def fib(solve, n):
    if n < 2:
        return n
    return solve(n - 1) + solve(n - 2)

fib(30)                 # 832040 — memoized automatically
print(fib.stats.summary())
```

## Install

```bash
pip install -e .          # from this repo
# optional graph/plot rendering:
pip install -e ".[viz]"
```

Requires Python 3.9+. Zero required dependencies.

## The core idea

A recurrence is a function whose **first parameter is a `solve` handle** used to
request sub-states. You never write a cache, allocate a table, choose an
iteration order, or add base-case bookkeeping — you express the math, and PyDP
builds the machinery.

```python
@dp
def grid_paths(solve, r, c):
    if r == 0 or c == 0:
        return 1
    return solve(r - 1, c) + solve(r, c - 1)

grid_paths(10, 10)      # 184756
```

Multi-argument states, string arguments, and (frozen) list arguments all work —
state keys are normalized to hashable form automatically.

## What you get for free after any run

Every `DPProblem` exposes artifacts from its most recent run:

| Attribute        | What it holds                                             |
| ---------------- | --------------------------------------------------------- |
| `.stats`         | `PerformanceStats` — states, cache hits/misses, depth, time |
| `.graph`         | `DependencyGraph` — every `state -> dependency` edge      |
| `.table`         | the realized memo table `{state: value}`                  |
| `.tree`          | the full recursion tree (parent → children)               |
| `.storage()`     | recommended storage backing (array / sparse / dict)       |

```python
fib(20)
fib.stats.states_explored      # 21
fib.stats.hit_rate             # fraction of lookups served from cache
fib.graph.dependencies_of(6)   # {5, 4}
fib.graph.topological_order()  # dependencies-first evaluation order
```

## Execution strategies

The same recurrence runs top-down (default), bottom-up (iterative), or parallel
with no code change.

| Strategy       | How it evaluates                                             |
| -------------- | ----------------------------------------------------------- |
| `"top-down"`   | demand-driven recursion + memoization (default)             |
| `"bottom-up"`  | discovers the DAG, topologically orders it, iterates (depth 1) |
| `"parallel"`   | evaluates topological *layers* concurrently in a thread pool |
| `"auto"`       | currently resolves to top-down                              |

```python
fib(100, strategy="bottom-up")     # 354224848179261915075
fib.stats.max_recursion_depth      # 1

fib(100, strategy="parallel", workers=8)   # same answer, layered concurrency

@dp(strategy="bottom-up")
def knap(solve, i, cap): ...
```

Deep recurrences that would overflow the C stack run inside an enlarged-stack
worker thread, so `strategy="top-down"` also handles chains thousands deep.
Genuinely cyclic recurrences raise `CyclicDependencyError` instead of hanging.

### Parallel execution

`strategy="parallel"` groups states into dependency **layers** via
`graph.topological_layers()` — every state in a layer depends only on earlier
layers, so a whole layer is evaluated concurrently. Workers get a read-only view
of already-computed values, so results are deterministic regardless of thread
scheduling.

```python
fib.graph.topological_layers()   # [[0, 1], [2], [3], ...]
```

Note: because the recurrence body is Python, the GIL bounds CPU-bound speedup;
the win is real for GIL-releasing work (I/O, NumPy), and the layering is exactly
what a process-based backend would consume.

## Static AST analysis

`analyze()` reads the recurrence's **source** (before it runs) and infers its
structure — solve handle, state parameters, base cases, and recursive calls:

```python
from pydp import analyze

fib = ...  # a @dp problem
print(analyze(fib).summary())
# Solve handle    : solve
# State parameters: n     (1-D)
# Base cases      : 1   -> if n < 2: return n  @line 4
# Recursive calls : 2   -> solve(n - 1), solve(n - 2)
```

It degrades gracefully (`source_available == False`) when source isn't
retrievable, e.g. lambdas or REPL-defined functions.

## Analysis & optimization

```python
from pydp import analyze_memory, estimate_complexity, suggestions

fib(50)
analyze_memory(fib)       # O(n)=51 -> O(2) via rolling array
estimate_complexity(fib)  # time~O(n*k), space~O(2)
suggestions(fib)          # human-readable optimization hints
```

`analyze_memory` inspects the realized dependency graph: if every state only
reaches back `k` steps, it reports that memory can be reduced to `O(k)` with a
rolling array (and the analogous axis reduction for N-D grids).

## Visualization

```python
from pydp import recursion_tree, dependency_text, heatmap_text, to_graphviz

fib(7)
print(recursion_tree(fib))     # ASCII recursion tree ("cached" nodes marked)
print(dependency_text(fib))    # text dependency listing
print(heatmap_text(fib))       # visited-state heatmap (1-D and 2-D)

to_graphviz(fib, "fib_graph")  # PNG via the optional 'viz' extra
```

## Educational mode

```python
from pydp import explain
fib(15)
print(explain(fib))
```

Narrates the state space, dependency structure, a valid evaluation order, why
memoization helped, the complexity estimate, and optimization suggestions.

## Template library

Ready-made problems, each returning a full `DPProblem` (so you still get stats,
graphs, and analysis):

```python
from pydp import templates as T

T.fibonacci()(20)
T.coin_change([1, 2, 5])(11)                       # 3
T.rod_cutting([1,5,8,9,10,17,17,20])(8)            # 22
T.solve_knapsack([1,3,4,5], [1,4,5,7], 7)[0]       # 9
T.solve_lcs("AGGTAB", "GXTXAYB")[0]                # 4
T.solve_edit_distance("sunday", "saturday")[0]     # 3
T.solve_lis([10,9,2,5,3,7,101,18])[0]              # 4
T.solve_matrix_chain([40,20,30,10,30])[0]          # 26000
```

### DP domains

Beyond the classic 1-D/2-D problems, the library ships one representative of
each major DP domain, so you can see how the engine handles each shape:

```python
# Tree DP — max-weight independent set on a rooted tree
T.solve_tree_independent_set({0:[1,2,3], 1:[4], 2:[], 3:[], 4:[]},
                             {0:10, 1:5, 2:3, 3:4, 4:8})[0]      # 18

# Interval DP — minimum palindrome-partition cuts
T.solve_palindrome_partition("aab")[0]                          # 1

# Bitmask DP — Travelling Salesman shortest tour
T.solve_tsp([[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]])[0]  # 80

# Digit DP — count integers in [0, N] avoiding a digit
T.solve_count_without_digit(20, forbidden_digit=3)[0]           # 19
```

## Run the tour

```bash
python examples/demo.py
```

## Tests

```bash
pip install pytest
python -m pytest
```

61 tests cover the engine, all three execution strategies, cycle detection, the
AST and runtime analysis modules, and every template (including the tree /
interval / bitmask / digit-DP domains, the latter validated against brute force).

## Architecture

| Layer                | Module            |
| -------------------- | ----------------- |
| API / decorator      | `engine.dp`       |
| Core engine          | `engine.DPProblem`|
| State normalization  | `state`           |
| Dependency analysis  | `graph`           |
| Static AST analysis  | `analyze`         |
| Storage analysis     | `storage`         |
| Optimizer            | `optimize`        |
| Visualization        | `visualize`       |
| Educational mode     | `explain`         |
| Template library     | `templates`       |

## License

MIT
