# Matrix Chain Multiplication Optimizer šā”
A **hacker-style** interactive visualizer for the Matrix Chain Multiplication problem using Dynamic Programming. This tool demonstrates the classic algorithm with colorful terminal output, live computation visualization, and detailed step-by-step analysis.
## šÆ What is Matrix Chain Multiplication?
The Matrix Chain Multiplication problem is a classic dynamic programming problem that finds the optimal way to parenthesize a chain of matrix multiplications to minimize the total number of scalar multiplications.
**Example**: For matrices Aā(5Ć4), Aā(4Ć6), Aā(6Ć2), Aā(2Ć7)
- Bad parenthesization: `((Aā Ć Aā) Ć Aā) Ć Aā` = 240 + 60 + 84 = **384 operations**
- Optimal parenthesization: `Aā Ć ((Aā Ć Aā) Ć Aā)` = 48 + 84 + 140 = **272 operations**
## āØ Features
- šØ **Colorful hacker-style interface** with ASCII art banner
- š **Live computation visualization** showing each DP step
- š **Beautiful table displays** for cost and split matrices
- šÆ **Optimal parenthesization output**
- š **Two input modes**: Quick paste or step-by-step interactive
- ā” **Real-time scanning effects** for enhanced user experience
## š Installation
### Option 1: Direct Installation
```bash
# Clone the repository
git clone <repository-url>
cd matrixchain
# Install dependencies
pip install colorama
# Run the program
python -m matrixchain
```
### Option 2: Package Installation
```bash
# Install as a package
pip install -e .
# Run from anywhere
matrixchain
```
## š® Usage
### Quick Start
```bash
python -m matrixchain
```
### Input Formats
**Method 1: Quick Paste**
```
Enter matrix dimensions P as space-separated integers.
Example for matrices A1 (5x4), A2 (4x6), A3 (6x2), A4 (2x7):
5 4 6 2 7 (this is P0 P1 P2 P3 P4)
[#] Paste dims (or press Enter to input step-by-step): 5 4 6 2 7
```
**Method 2: Interactive Input**
```
[#] Number of matrices (n): 4
Enter rows of A1 (or P0): 5
Enter cols of A1 (or P1): 4
Enter rows of A2 (or P1): 4
Enter cols of A2 (or P2): 6
...
```
### Example Session
```
__ __ _ _ _ _ _ _
| \/ | __ _| |_ _ __| | | |_ __ (_) |_(_) ___ _ __
| |\/| |/ _` | __| '__| | | | '_ \| | __| |/ _ \| '_ \
| | | | (_| | |_| | | |_| | | | | | |_| | (_) | | | |
|_| |_|\__,_|\__|_| \___/|_| |_|_|\__|_|\___/|_| |_|
Matrix Chain Multiplication Optimizer
============================================================
Dimensions P = [5, 4, 6, 2, 7] (matrices = 4)
[INFO] Initializing...
[INFO] Checking multiplication paths...
[SCAN] Enumerating chain lengths...
[SCAN] Evaluating possible splits...
[HIT] Possible optimization detected...
[INFO] Calculating minimal cost path...
[+] Starting DP computation...
[SCAN] DP[1,2] via k=1 -> cost=120
[HIT] DP[1,2] = 120 (k=1)
[SCAN] DP[2,3] via k=2 -> cost=48
[HIT] DP[2,3] = 48 (k=2)
...
[LOOT] Minimal Multiplication Cost Table (mTable)
+---------------+---------------+---------------+---------------+
| | A1 | A2 | A3 |
+---------------+---------------+---------------+---------------+
| A1 | 0 | 120 | 168 |
| A2 | -- | 0 | 48 |
| A3 | -- | -- | 0 |
+---------------+---------------+---------------+---------------+
[LOOT] Optimal Parenthesization
A1 x ((A2 x A3) x A4)
[+] Minimum multiplication cost: 272
[+] Mission Complete
```
## š§® Algorithm Details
The program implements the classic **Dynamic Programming** solution:
1. **State Definition**: `m[i][j]` = minimum cost to multiply matrices from i to j
2. **Recurrence**: `m[i][j] = min(m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1])` for all k
3. **Base Case**: `m[i][i] = 0` (single matrix requires no multiplication)
4. **Reconstruction**: Uses split table `s[i][j]` to build optimal parenthesization
**Time Complexity**: O(nĀ³)
**Space Complexity**: O(nĀ²)
## š Project Structure
```
matrixchain/
āāā matrixchain/
ā āāā __init__.py # Package initialization
ā āāā __main__.py # Module entry point
ā āāā core.py # Main algorithm and UI logic
āāā setup.py # Package setup configuration
āāā pyproject.toml # Modern Python packaging
āāā README.md # This file
āāā LICENSE # MIT License
```
## š ļø Requirements
- **Python**: 3.7+
- **Dependencies**:
- `colorama` - For cross-platform colored terminal output
## šØ Features Breakdown
### Visual Elements
- **ASCII Art Banner**: Eye-catching startup screen
- **Color-coded Output**: Different colors for different types of information
- **Progress Indicators**: Live scanning effects during computation
- **Formatted Tables**: Professional-looking cost and split matrices
### Algorithm Features
- **Complete DP Implementation**: Full matrix chain multiplication solver
- **Parenthesization Reconstruction**: Shows optimal grouping
- **Step-by-step Visualization**: See each DP computation in real-time
- **Input Validation**: Robust error handling for user input
## š¤ 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
## š Educational Use
This project is perfect for:
- **Algorithm Visualization**: Understanding how DP works step-by-step
- **Computer Science Education**: Teaching optimization problems
- **Interview Preparation**: Classic DP problem implementation
- **Performance Analysis**: Comparing different parenthesizations
## š License
This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.
## šØāš» Author
**Chauhan Pruthviraj**
## š Acknowledgments
- Classic Dynamic Programming algorithm for Matrix Chain Multiplication
- Colorama library for cross-platform terminal colors
- ASCII art generation tools
---
*Happy optimizing! š*
Raw data
{
"_id": null,
"home_page": null,
"name": "matrixchain",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": null,
"keywords": "matrix, multiplication, dynamic-programming, algorithm, visualization, education",
"author": "Chauhan Pruthviraj",
"author_email": "Chauhan Pruthviraj <chauhanpruthviraj309@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/dc/ae/bde4a84ea20bff2d5e3abf1229d5b62627f57a2fa221425ec11ee39edea3/matrixchain-1.0.1.tar.gz",
"platform": null,
"description": "# Matrix Chain Multiplication Optimizer \ud83d\udd17\u26a1\r\n\r\nA **hacker-style** interactive visualizer for the Matrix Chain Multiplication problem using Dynamic Programming. This tool demonstrates the classic algorithm with colorful terminal output, live computation visualization, and detailed step-by-step analysis.\r\n\r\n## \ud83c\udfaf What is Matrix Chain Multiplication?\r\n\r\nThe Matrix Chain Multiplication problem is a classic dynamic programming problem that finds the optimal way to parenthesize a chain of matrix multiplications to minimize the total number of scalar multiplications.\r\n\r\n**Example**: For matrices A\u2081(5\u00d74), A\u2082(4\u00d76), A\u2083(6\u00d72), A\u2084(2\u00d77)\r\n- Bad parenthesization: `((A\u2081 \u00d7 A\u2082) \u00d7 A\u2083) \u00d7 A\u2084` = 240 + 60 + 84 = **384 operations**\r\n- Optimal parenthesization: `A\u2081 \u00d7 ((A\u2082 \u00d7 A\u2083) \u00d7 A\u2084)` = 48 + 84 + 140 = **272 operations**\r\n\r\n## \u2728 Features\r\n\r\n- \ud83c\udfa8 **Colorful hacker-style interface** with ASCII art banner\r\n- \ud83d\udd0d **Live computation visualization** showing each DP step\r\n- \ud83d\udcca **Beautiful table displays** for cost and split matrices\r\n- \ud83c\udfaf **Optimal parenthesization output**\r\n- \ud83d\udcdd **Two input modes**: Quick paste or step-by-step interactive\r\n- \u26a1 **Real-time scanning effects** for enhanced user experience\r\n\r\n## \ud83d\ude80 Installation\r\n\r\n### Option 1: Direct Installation\r\n```bash\r\n# Clone the repository\r\ngit clone <repository-url>\r\ncd matrixchain\r\n\r\n# Install dependencies\r\npip install colorama\r\n\r\n# Run the program\r\npython -m matrixchain\r\n```\r\n\r\n### Option 2: Package Installation\r\n```bash\r\n# Install as a package\r\npip install -e .\r\n\r\n# Run from anywhere\r\nmatrixchain\r\n```\r\n\r\n## \ud83c\udfae Usage\r\n\r\n### Quick Start\r\n```bash\r\npython -m matrixchain\r\n```\r\n\r\n### Input Formats\r\n\r\n**Method 1: Quick Paste**\r\n```\r\nEnter matrix dimensions P as space-separated integers.\r\nExample for matrices A1 (5x4), A2 (4x6), A3 (6x2), A4 (2x7):\r\n 5 4 6 2 7 (this is P0 P1 P2 P3 P4)\r\n\r\n[#] Paste dims (or press Enter to input step-by-step): 5 4 6 2 7\r\n```\r\n\r\n**Method 2: Interactive Input**\r\n```\r\n[#] Number of matrices (n): 4\r\n Enter rows of A1 (or P0): 5\r\n Enter cols of A1 (or P1): 4\r\n Enter rows of A2 (or P1): 4\r\n Enter cols of A2 (or P2): 6\r\n ...\r\n```\r\n\r\n### Example Session\r\n```\r\n __ __ _ _ _ _ _ _\r\n| \\/ | __ _| |_ _ __| | | |_ __ (_) |_(_) ___ _ __\r\n| |\\/| |/ _` | __| '__| | | | '_ \\| | __| |/ _ \\| '_ \\\r\n| | | | (_| | |_| | | |_| | | | | | |_| | (_) | | | |\r\n|_| |_|\\__,_|\\__|_| \\___/|_| |_|_|\\__|_|\\___/|_| |_|\r\n\r\n Matrix Chain Multiplication Optimizer\r\n============================================================\r\n\r\nDimensions P = [5, 4, 6, 2, 7] (matrices = 4)\r\n\r\n[INFO] Initializing...\r\n[INFO] Checking multiplication paths...\r\n[SCAN] Enumerating chain lengths...\r\n[SCAN] Evaluating possible splits...\r\n[HIT] Possible optimization detected...\r\n[INFO] Calculating minimal cost path...\r\n\r\n[+] Starting DP computation...\r\n\r\n[SCAN] DP[1,2] via k=1 -> cost=120\r\n[HIT] DP[1,2] = 120 (k=1)\r\n[SCAN] DP[2,3] via k=2 -> cost=48\r\n[HIT] DP[2,3] = 48 (k=2)\r\n...\r\n\r\n[LOOT] Minimal Multiplication Cost Table (mTable)\r\n+---------------+---------------+---------------+---------------+\r\n| | A1 | A2 | A3 |\r\n+---------------+---------------+---------------+---------------+\r\n| A1 | 0 | 120 | 168 |\r\n| A2 | -- | 0 | 48 |\r\n| A3 | -- | -- | 0 |\r\n+---------------+---------------+---------------+---------------+\r\n\r\n[LOOT] Optimal Parenthesization\r\nA1 x ((A2 x A3) x A4)\r\n\r\n[+] Minimum multiplication cost: 272\r\n\r\n[+] Mission Complete\r\n```\r\n\r\n## \ud83e\uddee Algorithm Details\r\n\r\nThe program implements the classic **Dynamic Programming** solution:\r\n\r\n1. **State Definition**: `m[i][j]` = minimum cost to multiply matrices from i to j\r\n2. **Recurrence**: `m[i][j] = min(m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1])` for all k\r\n3. **Base Case**: `m[i][i] = 0` (single matrix requires no multiplication)\r\n4. **Reconstruction**: Uses split table `s[i][j]` to build optimal parenthesization\r\n\r\n**Time Complexity**: O(n\u00b3)\r\n**Space Complexity**: O(n\u00b2)\r\n\r\n## \ud83d\udcc1 Project Structure\r\n\r\n```\r\nmatrixchain/\r\n\u251c\u2500\u2500 matrixchain/\r\n\u2502 \u251c\u2500\u2500 __init__.py # Package initialization\r\n\u2502 \u251c\u2500\u2500 __main__.py # Module entry point\r\n\u2502 \u2514\u2500\u2500 core.py # Main algorithm and UI logic\r\n\u251c\u2500\u2500 setup.py # Package setup configuration\r\n\u251c\u2500\u2500 pyproject.toml # Modern Python packaging\r\n\u251c\u2500\u2500 README.md # This file\r\n\u2514\u2500\u2500 LICENSE # MIT License\r\n```\r\n\r\n## \ud83d\udee0\ufe0f Requirements\r\n\r\n- **Python**: 3.7+\r\n- **Dependencies**:\r\n - `colorama` - For cross-platform colored terminal output\r\n\r\n## \ud83c\udfa8 Features Breakdown\r\n\r\n### Visual Elements\r\n- **ASCII Art Banner**: Eye-catching startup screen\r\n- **Color-coded Output**: Different colors for different types of information\r\n- **Progress Indicators**: Live scanning effects during computation\r\n- **Formatted Tables**: Professional-looking cost and split matrices\r\n\r\n### Algorithm Features\r\n- **Complete DP Implementation**: Full matrix chain multiplication solver\r\n- **Parenthesization Reconstruction**: Shows optimal grouping\r\n- **Step-by-step Visualization**: See each DP computation in real-time\r\n- **Input Validation**: Robust error handling for user input\r\n\r\n## \ud83e\udd1d Contributing\r\n\r\n1. Fork the repository\r\n2. Create a feature branch (`git checkout -b feature/amazing-feature`)\r\n3. Commit your changes (`git commit -m 'Add amazing feature'`)\r\n4. Push to the branch (`git push origin feature/amazing-feature`)\r\n5. Open a Pull Request\r\n\r\n## \ud83d\udcda Educational Use\r\n\r\nThis project is perfect for:\r\n- **Algorithm Visualization**: Understanding how DP works step-by-step\r\n- **Computer Science Education**: Teaching optimization problems\r\n- **Interview Preparation**: Classic DP problem implementation\r\n- **Performance Analysis**: Comparing different parenthesizations\r\n\r\n## \ud83d\udcc4 License\r\n\r\nThis project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.\r\n\r\n## \ud83d\udc68\u200d\ud83d\udcbb Author\r\n\r\n**Chauhan Pruthviraj**\r\n\r\n## \ud83d\ude4f Acknowledgments\r\n\r\n- Classic Dynamic Programming algorithm for Matrix Chain Multiplication\r\n- Colorama library for cross-platform terminal colors\r\n- ASCII art generation tools\r\n\r\n---\r\n\r\n*Happy optimizing! \ud83d\ude80*\r\n",
"bugtrack_url": null,
"license": null,
"summary": "Hacker-style Matrix Chain Multiplication visualizer",
"version": "1.0.1",
"project_urls": {
"Bug Reports": "https://github.com/Pruthviraj36/matrixchain/issues",
"Homepage": "https://github.com/Pruthviraj36/matrixchain",
"Source Code": "https://github.com/Pruthviraj36/matrixchain"
},
"split_keywords": [
"matrix",
" multiplication",
" dynamic-programming",
" algorithm",
" visualization",
" education"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "411b905a7e96456c0694fad3171b706648bf518d61993ba0e3ff82108b2efe3d",
"md5": "f7e12a9c96bc758dd830e91260737f27",
"sha256": "38551a1a34432584ec7a6583a663cf958207de0b4dd1046d2769be65853e8645"
},
"downloads": -1,
"filename": "matrixchain-1.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "f7e12a9c96bc758dd830e91260737f27",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 8646,
"upload_time": "2025-08-11T11:18:41",
"upload_time_iso_8601": "2025-08-11T11:18:41.587247Z",
"url": "https://files.pythonhosted.org/packages/41/1b/905a7e96456c0694fad3171b706648bf518d61993ba0e3ff82108b2efe3d/matrixchain-1.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "dcaebde4a84ea20bff2d5e3abf1229d5b62627f57a2fa221425ec11ee39edea3",
"md5": "ddb4c8eaaa90a351d655316eb615312c",
"sha256": "b687de3cdd4e26b6c2bccb5436502aff10ab6a5a4d486611ce8a2961382b97f8"
},
"downloads": -1,
"filename": "matrixchain-1.0.1.tar.gz",
"has_sig": false,
"md5_digest": "ddb4c8eaaa90a351d655316eb615312c",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 8340,
"upload_time": "2025-08-11T11:18:42",
"upload_time_iso_8601": "2025-08-11T11:18:42.668596Z",
"url": "https://files.pythonhosted.org/packages/dc/ae/bde4a84ea20bff2d5e3abf1229d5b62627f57a2fa221425ec11ee39edea3/matrixchain-1.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-08-11 11:18:42",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Pruthviraj36",
"github_project": "matrixchain",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [
{
"name": "colorama",
"specs": [
[
">=",
"0.4.0"
]
]
}
],
"lcname": "matrixchain"
}
JSON
