Metadata-Version: 2.4
Name: mapFolding
Version: 0.35.0
Summary: Map folding, meanders, stamp folding, semi-meanders. Experiment with algorithm transformations, and analyze computational states.
Author-email: Hunter Hogan <HunterHogan@pm.me>
Maintainer-email: Hunter Hogan <HunterHogan@pm.me>
License-Expression: CC-BY-NC-4.0
Project-URL: Context7, https://context7.com/hunterhogan/mapfolding
Project-URL: Donate, https://www.patreon.com/integrated
Project-URL: Download, https://pypi.org/project/mapFolding
Project-URL: Homepage, https://github.com/hunterhogan/mapFolding
Project-URL: Issues, https://github.com/hunterhogan/mapFolding/issues
Project-URL: Repository, https://github.com/hunterhogan/mapFolding.git
Keywords: A001415,A001417,OEIS,combinatorial geometry,combinatorics,computational combinatorics,computational geometry,map folding,meanders,stamp folding
Classifier: Development Status :: 4 - Beta
Classifier: Environment :: Console
Classifier: Intended Audience :: Education
Classifier: Intended Audience :: Science/Research
Classifier: Natural Language :: English
Classifier: Operating System :: OS Independent
Classifier: Operating System :: POSIX :: Linux
Classifier: Programming Language :: Python
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Topic :: Scientific/Engineering :: Information Analysis
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Typing :: Typed
Requires-Python: >=3.13
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: Z0Z_tools>=3.2.0
Requires-Dist: anyascii
Requires-Dist: astToolkit>=0.11.6
Requires-Dist: gmpy2
Requires-Dist: hunterMakesPy>=0.7.5
Requires-Dist: more_itertools
Requires-Dist: numba
Requires-Dist: numba_progress
Requires-Dist: numpy
Requires-Dist: oeis-tools
Requires-Dist: platformdirs
Requires-Dist: tqdm
Requires-Dist: urllib3
Provides-Extra: codon
Requires-Dist: codon-jit>=0.4.6; sys_platform == "linux" and extra == "codon"
Requires-Dist: lief; sys_platform == "linux" and extra == "codon"
Provides-Extra: development
Requires-Dist: gmpy2-stubs; extra == "development"
Requires-Dist: google-api-python-client-stubs>=1.35.0; extra == "development"
Requires-Dist: google-auth-oauthlib-stubs>=1.2.0; extra == "development"
Requires-Dist: ipykernel; extra == "development"
Requires-Dist: ipywidgets; extra == "development"
Requires-Dist: memray; sys_platform == "linux" and extra == "development"
Requires-Dist: py-spy; extra == "development"
Requires-Dist: pyarrow-stubs; extra == "development"
Requires-Dist: pytest-cov; extra == "development"
Requires-Dist: setuptools; extra == "development"
Requires-Dist: sympy; extra == "development"
Provides-Extra: ortools
Requires-Dist: ortools; extra == "ortools"
Provides-Extra: pandas
Requires-Dist: pandas; extra == "pandas"
Requires-Dist: pyarrow; extra == "pandas"
Provides-Extra: testing
Requires-Dist: ortools; extra == "testing"
Requires-Dist: pandas; extra == "testing"
Requires-Dist: pyarrow; extra == "testing"
Requires-Dist: pytest-env; extra == "testing"
Requires-Dist: pytest-xdist; extra == "testing"
Requires-Dist: pytest; extra == "testing"
Dynamic: license-file

# mapFolding

[![PyPI](https://img.shields.io/pypi/v/mapFolding.svg)](https://pypi.org/project/mapFolding/)
[![Python versions](https://img.shields.io/pypi/pyversions/mapFolding.svg)](https://pypi.org/project/mapFolding/)
[![Python Tests](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml/badge.svg)](https://github.com/hunterhogan/mapFolding/actions/workflows/pythonTests.yml)
[![License: CC BY-NC 4.0](https://img.shields.io/badge/license-CC%20BY--NC%204.0-blue.svg)](https://github.com/hunterhogan/mapFolding/blob/main/LICENSE)

Exact enumeration tools for map folding, stamp folding, semi-meanders, and meanders.

`mapFolding` is a typed Python research package for counting distinct foldings of one- and multidimensional maps. It provides:

- stable dispatch functions for ordinary, rotationally symmetric, and divided computations;
- native algorithms for map folding, semi-meanders, and meanders;
- a unified interface to 33 implemented [OEIS](https://oeis.org/) sequences, including exact formula relationships;
- readable source algorithms, generated optimized implementations, and optional NumPy, Numba, Pandas, and Codon routes; and
- cross-implementation tests against known sequence values.

Earlier versions of this project were used to compute new terms for [OEIS A001415](https://oeis.org/A001415), the number of ways to fold a `2 × n` strip of stamps.

This is exact combinatorial enumeration: running time and memory requirements grow quickly. Start with small inputs. The supported high-level interfaces are in `mapFolding.basecamp` and `mapFolding.oeis`; other modules include evolving research code.

## Quick start

Quick start your exploration of a new-to-you algorithm? Quick start your idea for improving an algorithm? Quick start your dissection of an algorithm's states?

Considering the versatility and sophistication of this package, you can accomplish many things quickly, but a "Quick start" section doesn't make sense.

## Public interfaces

| Goal                                           | Interface                                                |
| ---------------------------------------------- | -------------------------------------------------------- |
| Count all foldings of a map                    | `mapFolding.basecamp.countFolds(mapShape, ...)`          |
| Count rotationally symmetric foldings          | `mapFolding.basecamp.countFoldsSymmetric(mapShape, ...)` |
| Count semi-meanders or meanders                | `mapFolding.basecamp.countMeanders(kind, n, ...)`        |
| Calculate any implemented OEIS term            | `mapFolding.oeis.oeisIDfor_n(oeisID, n, ...)`            |
| Convert a map-folding OEIS index to dimensions | `mapFolding.oeis.makeMapShape(oeisID, n)`                |
| Retrieve cached known values                   | `mapFolding.oeis.getValuesKnown(oeisID)`                 |
| List implemented sequences                     | `getOEISids`                                             |

`oeisIDfor_n` dispatches to the appropriate folding algorithm, meander algorithm, symmetric-folding algorithm, or exact formula. Run `getOEISids` for the current list and descriptions of all supported sequences.

The map-folding sequence mappings are:

| OEIS ID                             | Problem                               | `mapShape` for index `n` |
| ----------------------------------- | ------------------------------------- | ------------------------ |
| [A000136](https://oeis.org/A000136) | Strip of `n` labeled stamps           | `(1, n)`                 |
| [A001415](https://oeis.org/A001415) | `2 × n` strip                         | `(2, n)`                 |
| [A001416](https://oeis.org/A001416) | `3 × n` strip                         | `(3, n)`                 |
| [A001417](https://oeis.org/A001417) | `n`-dimensional `2 × ⋯ × 2` map       | `(2,) * n`               |
| [A195646](https://oeis.org/A195646) | `n`-dimensional `3 × ⋯ × 3` map       | `(3,) * n`               |
| [A001418](https://oeis.org/A001418) | `n × n` sheet                         | `(n, n)`                 |
| [A007822](https://oeis.org/A007822) | Symmetric foldings of `2n + 1` stamps | `(1, 2 * n)`             |

For A007822, pass `(1, 2 * n)` to `countFoldsSymmetric`; the function's computational shape differs from the `2n + 1` stamps in the sequence description.

OEIS metadata and b-files are cached locally for 30 days. Missing or stale entries are refreshed from `oeis.org`; stale cached data remains available if a refresh fails.

## Algorithm selection and long computations

Assume this is always out of date.

Leave `flow=''` for the default implementation. The alternate selectors exist for research, validation, and performance comparisons:

| Interface             | Supported `flow` values                                                                           |
| --------------------- | ------------------------------------------------------------------------------------------------- |
| `countFolds`          | `''`, `daoOfMapFolding`, `numba`, `theorem2`, `theorem2Codon`, `theorem2Numba`, `theorem2Trimmed` |
| `countFoldsSymmetric` | `''`, `asynchronous`, `theorem2`, `theorem2Codon`, `theorem2Numba`, `theorem2Trimmed`             |
| `countMeanders`       | `''`, `matrixMeanders`, `matrixNumPy`, `matrixPandas`                                             |

The Numba, Pandas, and Codon selectors require their corresponding extras. For OEIS sequences with multiple exact identities, the `f` argument to `oeisIDfor_n` selects a formula; leaving it empty uses the default route.

Pass `pathLikeWrite` to a counting function to preserve a result. An existing directory receives a generated filename such as `p2x6.totalFolds`; an explicit target file is also supported. The destination is write-tested before computation, and an existing target is not overwritten.

`countFolds` can split work with an integer, `computationDivisions='cpu'`, or `computationDivisions='maximum'`. Dividing this algorithm repeats substantial work and is usually slower, so leave `computationDivisions=None` unless you are deliberately studying the parallel implementation.

## Repository guide

This is a little out of date.

| Path                                                                                                    | Role                                                                         |
| ------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------- |
| [`mapFolding/basecamp.py`](https://github.com/hunterhogan/mapFolding/blob/main/mapFolding/basecamp.py)  | Stable high-level dispatch for folding and meander computations              |
| [`mapFolding/oeis/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/oeis)               | OEIS dispatch, formulas, metadata, and cached values                         |
| [`mapFolding/algorithms/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/algorithms)   | Handwritten source algorithms                                                |
| [`mapFolding/synthesized/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/synthesized) | Generated implementations; regenerate these instead of editing them directly |
| [`mapFolding/kitAST/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/kitAST)           | Project-specific AST transformations and module generators                   |
| [`mapFolding/_e/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/_e)                   | Experimental elimination-based algorithms and analysis                       |
| [`mapFolding/tests/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/tests)             | Main correctness, dispatch, filesystem, and parameter tests                  |
| [`mapFolding/reference/`](https://github.com/hunterhogan/mapFolding/tree/main/mapFolding/reference)     | Historical implementations, completed jobs, notes, and research artifacts    |
| [`easyRun/`](https://github.com/hunterhogan/mapFolding/tree/main/easyRun)                               | Benchmark and exploration harnesses                                          |

General-purpose transformation primitives developed alongside this project now live in [astToolkit](https://github.com/hunterhogan/astToolkit) and [astToolFactory](https://github.com/hunterhogan/astToolFactory). The transformation pipeline retained here is specific to generating and validating `mapFolding` implementations.

## Installation

`mapFolding` requires Python 3.13 or newer.

```console
pip install mapFolding
```

To avoid bloat, some packages are optional:

| Extra         | Purpose                                                             |
| ------------- | ------------------------------------------------------------------- |
| `pandas`      | Pandas and Arrow meander implementation                             |
| `codon`       | [Codon](https://docs.exaloop.io/)-compiled implementations on Linux |
| `ortools`     | Experimental constraint-propagation work                            |
| `testing`     | Test dependencies                                                   |
| `development` | Broader development and analysis dependencies                       |

For example:

```console
pip install "mapFolding[codon,pandas]"
```

## Development, or to have the archives, notes, and other supplemental materials

Create and activate a virtual environment, then install both development extras:

```console
git clone https://github.com/hunterhogan/mapFolding.git
cd mapFolding
python -m venv .venv
pip install -e ".[development,testing]"
```

The test suite compares independent implementations with known OEIS values and stored data samples. When adding an algorithm variant, begin with [`mapFolding/tests/test_computations.py`](https://github.com/hunterhogan/mapFolding/blob/main/mapFolding/tests/test_computations.py) and register the new flow beside the existing implementations.

## Citation

To cite this software, use the metadata in [`CITATION.cff`](https://github.com/hunterhogan/mapFolding/blob/main/CITATION.cff). BibTeX files for the mathematical literature are collected in [`citations/`](https://github.com/hunterhogan/mapFolding/tree/main/citations).

## Research references

### Sur les Chevauchements des Permutations

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Sade1949.bib)
- PDF: [OEIS](https://oeis.org/A000108/a000108_17.pdf)

### Folding a strip of stamps

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Koehler1968.bib)
- DOI: [10.1016/S0021-9800(68)80048-1](https://doi.org/10.1016/S0021-9800(68)80048-1)

### A map-folding problem

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Lunnon1968.bib)
- DOI: [10.1090/S0025-5718-1968-0221957-8](https://doi.org/10.1090/S0025-5718-1968-0221957-8)
- PDF: [American Mathematical Society](https://pubs.ams.org/journals/mcom/1968-22-101/S0025-5718-1968-0221957-8/S0025-5718-1968-0221957-8.pdf)

### Multi-dimensional map-folding

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Lunnon.bib)
- DOI: [10.1093/comjnl/14.1.75](https://doi.org/10.1093/comjnl/14.1.75)
- PDF: [Oxford Academic](https://academic.oup.com/comjnl/article-pdf/14/1/75/1020149/140075.pdf)
- [Java implementation](https://github.com/archmageirvine/joeis/blob/9e2bd5f6b5a51bc40833c19ca04555ec12044edc/src/irvine/oeis/a001/A001415.java) by Sean A. Irvine.

### A transfer matrix approach to the enumeration of plane meanders

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Jensen.bib) [TeX Source with precise formulas for AI agents.](https://arxiv.org/src/cond-mat/0008178)
- DOI: [10.1088/0305-4470/33/34/301](https://doi.org/10.1088/0305-4470/33/34/301)
- Free preprint: [arXiv:cond-mat/0008178](https://arxiv.org/abs/cond-mat/0008178)
- [C# implementation described](https://oeis.org/A005316/a005316.cs.txt) by Andrew Howroyd. [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Howroyd.bib)

### Stamp Foldings, Semi-Meanders, and Open Meanders: Fast Generation Algorithms

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Sawada2012.bib)
- DOI: [10.37236/2404](https://doi.org/10.37236/2404)
- PDF: [The Electronic Journal of Combinatorics](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p43/pdf)

### Foldings and meanders

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/Legendre2014.bib) [TeX Source with precise formulas for AI agents.](https://arxiv.org/src/1302.2025)
- PDF: [The Australasian Journal of Combinatorics](https://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p275.pdf)
- Free preprint: [arXiv:1302.2025](https://arxiv.org/abs/1302.2025)

### jOEIS: Java Online Encyclopedia of Integer Sequences

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/jOEIS.bib)
- [Code repository.](https://github.com/archmageirvine/joeis)

### The Online Encyclopedia of Integer Sequences

- [BibTeX citation.](https://github.com/hunterhogan/mapFolding/blob/main/citations/oeis.bib)
- [Available at oeis.org.](https://oeis.org)

## Computing new values

- Folds of multidimensional map (2, 2, 2, 2, 2, 2, 2, 2), which is [A001417(8)](https://oeis.org/A001417): estimated 14 days with my current hardware and a non-published algorithm.
- Folds of multidimensional map (2, 21), which is [A001415(21)](https://oeis.org/A001415): estimated 6 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
- Folds of multidimensional map (2, 22), which is [A001415(22)](https://oeis.org/A001415): estimated 15 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
- Folds of multidimensional map (3, 15), which is [A001416(15)](https://oeis.org/A001416): estimated 11 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
- Semi-meanders with 46 crossings, which is [A000682(46)](https://oeis.org/A000682): estimated 1–2 hours if I had 64 GB of system memory.

Computation times assume:

1. No power interruptions. (I don't have a UPS, and in the last two months the longest gap between power interruptions was 8 days 6 hours.)
2. No system crashes.
3. Single-core computations are given priority over other tasks.
4. The core of single-core computations is regularly boosted.
5. No heat issues.

## Status reminders

1. Acceleration
    1. Building Py 3.14z (tail-call) is not working.
    2. Codon: new release, new features.
2. Remote execution
    1. Google Colab: memmap causes everything to go to "disk" and the physical memory is unused.
    2. GitHub Codespaces: ignores memmap and terminates on OOM.
3. astToolkit: figure out a better container system than Ingredients Module, Ingredients Function, etc.
4. Dao of map folding
    1. Overhaul how I store and access type metadata for ndarray and other containers. Affects:
        1. StateMapFolding
        2. Shatter dataclass
        3. ast transformations
    2. Run 2^8 without a crash or power outage.
    3. Compute (2, 21), (2, 22), and (3, 15).
5. Symmetric 1xn
    1. Symmetry algorithm is too slow.
    2. Asynchronous + accelerated doesn't work yet.
6. Matrix Meanders
    1. I need a lot more tools in kitAST.
    2. I hate `getTotalBuckets` but it _should_ be a brilliant function.
7. Permutations
    1. The base algorithm is a dumpster fire.
    2. Bilateral concurrent can't produce a folding, but uses too much memory and is too slow to count folds.
8. Reduce arches: slower than counting by hand.
9. _e
    1. Constraint propagation or SAT
        1. ortools won't apply concurrency, and I don't know how to think about divisions of the problem space that actually reduce computation time.
        2. Understanding other packages is harder than a self-enema with a firehouse.
    2. 2^n-dimensional (aka elimination by crease)
        1. Computation algorithms needed for: conditional predecessors, conditional successors,
           DomainLeaf首零Plus零 in dimension零, the range of a pile (aka pile options, aka choices
           leaf), pinPile二ByCrease, pinPile二Ante首ByCrease, and pinPile零Ante首零AfterDepth4.
        2. Acceleration.
        3. Bug in `boxOfFunctionsReduction2上nDimensional`.
        4. Finish collecting 2^7 data.
        5. Fastest algorithm for 2^5. Can't complete 2^6. I mean, wtf?
        6. `PermutationSpace` and its OOP structure: I don't really know what I am doing.
        7. The reduce-it concept is strong: reorient more code around it. Resolve the tension with `PermutationSpace._solidifyLeafSpace()`.
    3. Elimination: atrophied.
    4. Insert leaves: But for the data storage, it would be powerful. IDK anything about data compression. I lost the code I wrote for the notation I created to store graphs, and it seems I am too stupid to recreate or reverse engineer my own code from my own files AND OTHER FUNCTIONS. fml. Ironically, LLMs can't figure it out either because I guess my idea was novel. F.M.L.

Hunter, this list is incomplete: you quit writing after you got upset. Resume at mapFolding.kitAST.

1. Research 1
    1. Finish run D11.
    2. Start partial runs in the R series.
    3. Make NumPy version.
    4. 2-sequence representation, 3-sequence representation, or something else?
    5. Hypothesis: relationships are best described by the sum of n and hypothetical n, modulated by parity.

## My recovery

[![2011 August: Homeless since](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://raw.githubusercontent.com/hunterhogan/mapFolding/refs/heads/main/.github/CC-BY-NC-4.0.png)](https://creativecommons.org/licenses/by-nc/4.0/)
