# mapFolding: Algorithms for enumerating distinct map/stamp folding patterns 🗺️
[](https://pypi.org/project/mapFolding/)
[](https://youtu.be/g6f_miE91mk&t=4)
[](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml)
[](https://creativecommons.org/licenses/by-nc/4.0/)
---
## Quick start
```sh
pip install mapFolding
```
`OEIS_for_n` will run a computation from the command line.
```cmd
(mapFolding) C:\apps\mapFolding> OEIS_for_n A001418 5
186086600 distinct folding patterns.
Time elapsed: 1.605 seconds
```
Use `mapFolding.oeisIDfor_n()` to compute a(n) for an OEIS ID.
```python
from mapFolding import oeisIDfor_n
foldsTotal = oeisIDfor_n( 'A001418', 4 )
```
---
## Features
### 1. Simple, easy usage based on OEIS IDs
`mapFolding` directly implements some IDs from [_The On-Line Encyclopedia of Integer Sequences_](https://oeis.org/) ([BibTex](https://github.com/hunterhogan/mapFolding/blob/main/citations/oeis.bibtex) citation).
Use `getOEISids` to get the most up-to-date list of available OEIS IDs.
```cmd
(mapFolding) C:\apps\mapFolding> getOEISids
Available OEIS sequences:
A001415: Number of ways of folding a 2 X n strip of stamps.
A001416: Number of ways of folding a 3 X n strip of stamps.
A001417: Number of ways of folding a 2 X 2 X ... X 2 n-dimensional map.
A001418: Number of ways of folding an n X n sheet of stamps.
A195646: Number of ways of folding a 3 X 3 X ... X 3 n-dimensional map.
```
### 2. **Algorithm Zoo: A Historical and Performance Journey** 🦒
This package offers a comprehensive collection of map folding algorithm implementations that showcase its evolution from historical origins to high-performance computation:
- **Historical Implementations**:
- Carefully restored versions of Lunnon's 1971 original [algorithm](https://github.com/hunterhogan/mapFolding/blob/mapFolding/reference/foldings.txt) with corrections
- Atlas Autocode reconstruction in the `reference/foldings.AA` file
- **Direct Translations**:
- Python translations following the original control flow (`lunnanWhile.py`)
- NumPy-based vectorized implementations (`lunnanNumpy.py`)
- **Modern Implementations**:
- Java port adaptations (`irvineJavaPort.py`) providing cleaner procedural implementations
- Experimental JAX version (`jaxCount.py`) exploring GPU acceleration potential
- Semantically decomposed version (`flattened.py`) with clear function boundaries
- **Performance Optimized**:
- Numba-JIT accelerated implementations up to 1000× faster than pure Python (see [benchmarks](https://github.com/hunterhogan/mapFolding/blob/mapFolding/notes/Speed%20highlights.md))
- Algorithmic optimizations showcasing subtle yet powerful performance differences (`total_countPlus1vsPlusN.py`)
The `reference` directory serves as both a historical archive and an educational resource for understanding algorithm evolution.
### 3. **Algorithmic Transformation: From Readability to Speed** 🔬
The package provides a sophisticated transformation framework that bridges the gap between human-readable algorithms and high-performance computation:
- **Core Algorithm Understanding**:
- Study the functional state-transformation approach in `theDao.py` with clear, isolated functions
- Explore the semantic decomposition in `reference/flattened.py` to understand algorithm sections
- **Code Transformation Pipeline**:
- **AST Manipulation**: Analyzes and transforms the algorithm's abstract syntax tree
- **Dataclass "Shattering"**: Decomposes complex state objects into primitive components
- **Optimization Applications**: Applies domain-specific optimizations for numerical computation
- **LLVM Integration**: Extracts LLVM IR for low-level algorithmic analysis
- **Performance Breakthroughs**:
- Learn why nearly identical algorithms can have dramatically different performance (`total_countPlus1vsPlusN.py`)
- See how memory layout and increment strategy impact computation speed
- Understand the batching technique that yields order-of-magnitude improvements
### 4. **Multi-Level Architecture: From Simple API to Full Customization**
The package's architecture supports multiple levels of engagement:
- **Basic Usage**:
- Work with the high-level API in `basecamp.py` for standard computations
- Access OEIS sequence calculations with minimal code
- **Algorithm Exploration**:
- Compare different implementations in the `reference` directory to understand trade-offs
- Modify the core algorithm in `theDao.py` while preserving its functional approach
- Configure system-wide settings in `theSSOT.py` to adjust data types and performance characteristics
- **Advanced Transformation**:
- Use the `someAssemblyRequired` package to transform algorithms at the AST level
- Create optimized variants with different compilation settings using:
- `transformationTools.py` for AST manipulation
- `transformDataStructures.py` for complex data structure transformations
- `ingredientsNumba.py` for Numba-specific optimization profiles
- `synthesizeNumbaFlow.py` to orchestrate the transformation process
- **Custom Deployment**:
- Generate specialized implementations for specific dimensions
- Create optimized standalone modules for production use
- Extract LLVM IR for further analysis and optimization
The package's multi-level design allows you to start with simple API calls and progressively explore deeper optimization techniques as your computational needs grow.
## Map-folding Video
~~This caused my neurosis:~~ I enjoyed the following video, which is what introduced me to map folding.
"How Many Ways Can You Fold a Map?" by Physics for the Birds, 2024 November 13 ([BibTex](https://github.com/hunterhogan/mapFolding/blob/main/citations/Physics_for_the_Birds.bibtex) citation)
[](https://www.youtube.com/watch?v=sfH9uIY3ln4)
---
## My recovery
[](https://HunterThinks.com/support)
[](https://www.youtube.com/@HunterHogan)
[](https://creativecommons.org/licenses/by-nc/4.0/)
Raw data
{
"_id": null,
"home_page": null,
"name": "mapFolding",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": "A001415, A001416, A001417, A001418, A195646, algorithmic optimization, AST manipulation, code generation, code transformation, combinatorics, computational geometry, dataclass transformation, folding pattern enumeration, just-in-time compilation, map folding, Numba optimization, OEIS, performance optimization, source code analysis, stamp folding",
"author": null,
"author_email": "Hunter Hogan <HunterHogan@pm.me>",
"download_url": "https://files.pythonhosted.org/packages/cd/27/99969ec22825f28e6ecb6624e6246efdb172c6e5de6bc76223e4417b8520/mapfolding-0.8.2.tar.gz",
"platform": null,
"description": "# mapFolding: Algorithms for enumerating distinct map/stamp folding patterns \ud83d\uddfa\ufe0f\n\n[](https://pypi.org/project/mapFolding/)\n[](https://youtu.be/g6f_miE91mk&t=4)\n[](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml)\n\n[](https://creativecommons.org/licenses/by-nc/4.0/)\n\n---\n\n## Quick start\n\n```sh\npip install mapFolding\n```\n\n`OEIS_for_n` will run a computation from the command line.\n\n```cmd\n(mapFolding) C:\\apps\\mapFolding> OEIS_for_n A001418 5\n186086600 distinct folding patterns.\nTime elapsed: 1.605 seconds\n```\n\nUse `mapFolding.oeisIDfor_n()` to compute a(n) for an OEIS ID.\n\n```python\nfrom mapFolding import oeisIDfor_n\nfoldsTotal = oeisIDfor_n( 'A001418', 4 )\n```\n\n---\n\n## Features\n\n### 1. Simple, easy usage based on OEIS IDs\n\n`mapFolding` directly implements some IDs from [_The On-Line Encyclopedia of Integer Sequences_](https://oeis.org/) ([BibTex](https://github.com/hunterhogan/mapFolding/blob/main/citations/oeis.bibtex) citation).\n\nUse `getOEISids` to get the most up-to-date list of available OEIS IDs.\n\n```cmd\n(mapFolding) C:\\apps\\mapFolding> getOEISids\n\nAvailable OEIS sequences:\n A001415: Number of ways of folding a 2 X n strip of stamps.\n A001416: Number of ways of folding a 3 X n strip of stamps.\n A001417: Number of ways of folding a 2 X 2 X ... X 2 n-dimensional map.\n A001418: Number of ways of folding an n X n sheet of stamps.\n A195646: Number of ways of folding a 3 X 3 X ... X 3 n-dimensional map.\n```\n\n### 2. **Algorithm Zoo: A Historical and Performance Journey** \ud83e\udd92\n\nThis package offers a comprehensive collection of map folding algorithm implementations that showcase its evolution from historical origins to high-performance computation:\n\n- **Historical Implementations**:\n - Carefully restored versions of Lunnon's 1971 original [algorithm](https://github.com/hunterhogan/mapFolding/blob/mapFolding/reference/foldings.txt) with corrections\n - Atlas Autocode reconstruction in the `reference/foldings.AA` file\n\n- **Direct Translations**:\n - Python translations following the original control flow (`lunnanWhile.py`)\n - NumPy-based vectorized implementations (`lunnanNumpy.py`)\n\n- **Modern Implementations**:\n - Java port adaptations (`irvineJavaPort.py`) providing cleaner procedural implementations\n - Experimental JAX version (`jaxCount.py`) exploring GPU acceleration potential\n - Semantically decomposed version (`flattened.py`) with clear function boundaries\n\n- **Performance Optimized**:\n - Numba-JIT accelerated implementations up to 1000\u00d7 faster than pure Python (see [benchmarks](https://github.com/hunterhogan/mapFolding/blob/mapFolding/notes/Speed%20highlights.md))\n - Algorithmic optimizations showcasing subtle yet powerful performance differences (`total_countPlus1vsPlusN.py`)\n\nThe `reference` directory serves as both a historical archive and an educational resource for understanding algorithm evolution.\n\n### 3. **Algorithmic Transformation: From Readability to Speed** \ud83d\udd2c\n\nThe package provides a sophisticated transformation framework that bridges the gap between human-readable algorithms and high-performance computation:\n\n- **Core Algorithm Understanding**:\n - Study the functional state-transformation approach in `theDao.py` with clear, isolated functions\n - Explore the semantic decomposition in `reference/flattened.py` to understand algorithm sections\n\n- **Code Transformation Pipeline**:\n - **AST Manipulation**: Analyzes and transforms the algorithm's abstract syntax tree\n - **Dataclass \"Shattering\"**: Decomposes complex state objects into primitive components\n - **Optimization Applications**: Applies domain-specific optimizations for numerical computation\n - **LLVM Integration**: Extracts LLVM IR for low-level algorithmic analysis\n\n- **Performance Breakthroughs**:\n - Learn why nearly identical algorithms can have dramatically different performance (`total_countPlus1vsPlusN.py`)\n - See how memory layout and increment strategy impact computation speed\n - Understand the batching technique that yields order-of-magnitude improvements\n\n### 4. **Multi-Level Architecture: From Simple API to Full Customization**\n\nThe package's architecture supports multiple levels of engagement:\n\n- **Basic Usage**:\n - Work with the high-level API in `basecamp.py` for standard computations\n - Access OEIS sequence calculations with minimal code\n\n- **Algorithm Exploration**:\n - Compare different implementations in the `reference` directory to understand trade-offs\n - Modify the core algorithm in `theDao.py` while preserving its functional approach\n - Configure system-wide settings in `theSSOT.py` to adjust data types and performance characteristics\n\n- **Advanced Transformation**:\n - Use the `someAssemblyRequired` package to transform algorithms at the AST level\n - Create optimized variants with different compilation settings using:\n - `transformationTools.py` for AST manipulation\n - `transformDataStructures.py` for complex data structure transformations\n - `ingredientsNumba.py` for Numba-specific optimization profiles\n - `synthesizeNumbaFlow.py` to orchestrate the transformation process\n\n- **Custom Deployment**:\n - Generate specialized implementations for specific dimensions\n - Create optimized standalone modules for production use\n - Extract LLVM IR for further analysis and optimization\n\nThe package's multi-level design allows you to start with simple API calls and progressively explore deeper optimization techniques as your computational needs grow.\n\n## Map-folding Video\n\n~~This caused my neurosis:~~ I enjoyed the following video, which is what introduced me to map folding.\n\n\"How Many Ways Can You Fold a Map?\" by Physics for the Birds, 2024 November 13 ([BibTex](https://github.com/hunterhogan/mapFolding/blob/main/citations/Physics_for_the_Birds.bibtex) citation)\n\n[](https://www.youtube.com/watch?v=sfH9uIY3ln4)\n\n---\n\n## My recovery\n\n[](https://HunterThinks.com/support)\n[](https://www.youtube.com/@HunterHogan)\n\n[](https://creativecommons.org/licenses/by-nc/4.0/)\n",
"bugtrack_url": null,
"license": "CC-BY-NC-4.0",
"summary": "Map folding algorithm with code transformation framework for optimizing numerical computations",
"version": "0.8.2",
"project_urls": {
"Donate": "https://www.patreon.com/integrated",
"Homepage": "https://github.com/hunterhogan/mapFolding",
"Repository": "https://github.com/hunterhogan/mapFolding.git"
},
"split_keywords": [
"a001415",
" a001416",
" a001417",
" a001418",
" a195646",
" algorithmic optimization",
" ast manipulation",
" code generation",
" code transformation",
" combinatorics",
" computational geometry",
" dataclass transformation",
" folding pattern enumeration",
" just-in-time compilation",
" map folding",
" numba optimization",
" oeis",
" performance optimization",
" source code analysis",
" stamp folding"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "9b85da3874f3fe195d1dde897ed8a0600ad032a902298c8c7863ec6d78fee097",
"md5": "aa48cf20674e0854d702daa2fb3bbb33",
"sha256": "e08cc20dfee4f5acbd4e71e13d3857d2546daaeee99a4295f35403ff0636bc9f"
},
"downloads": -1,
"filename": "mapfolding-0.8.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "aa48cf20674e0854d702daa2fb3bbb33",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.10",
"size": 91176,
"upload_time": "2025-03-21T13:09:50",
"upload_time_iso_8601": "2025-03-21T13:09:50.053306Z",
"url": "https://files.pythonhosted.org/packages/9b/85/da3874f3fe195d1dde897ed8a0600ad032a902298c8c7863ec6d78fee097/mapfolding-0.8.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "cd2799969ec22825f28e6ecb6624e6246efdb172c6e5de6bc76223e4417b8520",
"md5": "7962c12000cd836e28ed423d68f71db6",
"sha256": "0f47dd74fc3577dd2c093ba18eaa9bbf9c479fe1336d743ba3d68a6d6543fb16"
},
"downloads": -1,
"filename": "mapfolding-0.8.2.tar.gz",
"has_sig": false,
"md5_digest": "7962c12000cd836e28ed423d68f71db6",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10",
"size": 78121,
"upload_time": "2025-03-21T13:09:51",
"upload_time_iso_8601": "2025-03-21T13:09:51.592615Z",
"url": "https://files.pythonhosted.org/packages/cd/27/99969ec22825f28e6ecb6624e6246efdb172c6e5de6bc76223e4417b8520/mapfolding-0.8.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-03-21 13:09:51",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "hunterhogan",
"github_project": "mapFolding",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "mapfolding"
}
JSON
