mapFolding


NamemapFolding JSON
Version 0.8.2 PyPI version JSON
download
home_pageNone
SummaryMap folding algorithm with code transformation framework for optimizing numerical computations
upload_time2025-03-21 13:09:51
maintainerNone
docs_urlNone
authorNone
requires_python>=3.10
licenseCC-BY-NC-4.0
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
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            # mapFolding: Algorithms for enumerating distinct map/stamp folding patterns πŸ—ΊοΈ

[![pip install mapFolding](https://img.shields.io/badge/pip%20install-mapFolding-gray.svg?colorB=3b434b)](https://pypi.org/project/mapFolding/)
[![Static Badge](https://img.shields.io/badge/stinkin'%20badges-don't%20need-b98e5e)](https://youtu.be/g6f_miE91mk&t=4)
[![Python Tests](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml/badge.svg)](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml)
![Static Badge](https://img.shields.io/badge/issues-I%20have%20them-brightgreen)
[![License: CC-BY-NC-4.0](https://img.shields.io/badge/License-CC_BY--NC_4.0-3b434b)](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)

[![How Many Ways Can You Fold a Map?](https://i.ytimg.com/vi/sfH9uIY3ln4/hq720.jpg)](https://www.youtube.com/watch?v=sfH9uIY3ln4)

---

## My recovery

[![Static Badge](https://img.shields.io/badge/2011_August-Homeless_since-blue?style=flat)](https://HunterThinks.com/support)
[![YouTube Channel Subscribers](https://img.shields.io/youtube/channel/subscribers/UC3Gx7kz61009NbhpRtPP7tw)](https://www.youtube.com/@HunterHogan)

[![CC-BY-NC-4.0](https://github.com/hunterhogan/mapFolding/blob/main/CC-BY-NC-4.0.svg)](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[![pip install mapFolding](https://img.shields.io/badge/pip%20install-mapFolding-gray.svg?colorB=3b434b)](https://pypi.org/project/mapFolding/)\n[![Static Badge](https://img.shields.io/badge/stinkin'%20badges-don't%20need-b98e5e)](https://youtu.be/g6f_miE91mk&t=4)\n[![Python Tests](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml/badge.svg)](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml)\n![Static Badge](https://img.shields.io/badge/issues-I%20have%20them-brightgreen)\n[![License: CC-BY-NC-4.0](https://img.shields.io/badge/License-CC_BY--NC_4.0-3b434b)](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[![How Many Ways Can You Fold a Map?](https://i.ytimg.com/vi/sfH9uIY3ln4/hq720.jpg)](https://www.youtube.com/watch?v=sfH9uIY3ln4)\n\n---\n\n## My recovery\n\n[![Static Badge](https://img.shields.io/badge/2011_August-Homeless_since-blue?style=flat)](https://HunterThinks.com/support)\n[![YouTube Channel Subscribers](https://img.shields.io/youtube/channel/subscribers/UC3Gx7kz61009NbhpRtPP7tw)](https://www.youtube.com/@HunterHogan)\n\n[![CC-BY-NC-4.0](https://github.com/hunterhogan/mapFolding/blob/main/CC-BY-NC-4.0.svg)](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"
}
        
Elapsed time: 0.42185s