mapFolding

mapFolding is a typed Python research package for exact enumeration of map foldings, stamp foldings, semi-meanders, and meanders. It provides counting algorithms, access to their computation states, and tools for transforming readable algorithm source into specialized implementations.

A map-folding problem asks how many ways the labeled panels of a map can be stacked while preserving their connections. A strip of stamps is the one-dimensional case. Related meander problems count configurations of non-self-intersecting curves crossing a line or ray.

Earlier versions of this project computed the terms for 2 × 19 and 2 × 20 stamp strips, extending OEIS A001415.

Research with mapFolding

You can use the package to calculate sequence terms, dissect an algorithm's state, develop a different counting method, or study the effects of source transformations. The main routes through the code are:

The module, function, and class docstrings explain parameters, state layouts, mathematical relationships, and implementation details. Use them when choosing an experiment or following a computation through the package.

Counting and sequence access

The main counting functions are in mapFolding.basecamp; sequence functions are in mapFolding.oeis.

For example, (2, 6) describes a 2 × 6 map, and (2, 2, 2) describes a three-dimensional map with eight panels. Dimensions count panels along each axis.

Map dimensions and OEIS indices

For A007822, countFoldsSymmetric uses an even-length computational strip to count the symmetric foldings of the odd-length strip in the sequence description. makeMapShape supplies that computational shape.

Meanders and computation state

countMeanders('semi', n) computes A000682, and countMeanders('meanders', n) computes the open-meander sequence A005316. The 'closed' selector computes A005315 using the corresponding odd-index open-meander term.

The returned state retains the boundary position and transfer counts for inspection. Read the completed count from its totalMeanders property:

state.totalMeanders

totalMeanders sums the active lookup counts and countAddend, which retains completed contributions removed by pruning. The property reflects the current state; before counting finishes, its value represents intermediate counts rather than the final sequence term.

You can also supply an existing StateMeanders through the state argument to continue that computation. See the state and counting-function docstrings for the relevant fields and behavior.

Sequence formulas and reference data

oeisIDfor_n dispatches to a folding, symmetric-folding, or meander algorithm, or to an exact formula connecting related sequences. For sequences with selectable identities, its f argument chooses a formula. The formulas and their docstrings are in oeis/byFormula.py.

The getOEISids console command lists registered sequences and usage examples. The registry also includes related sequences used as reference data; consult oeisIDfor_n and byFormula for computation support. The OEIS_for_n command evaluates a supported term from its sequence identifier and index.

OEIS metadata and b-files are loaded when the metadata module is imported. Local files have a 30-day freshness interval; missing or stale entries trigger a request to oeis.org, and stale data remains available if a refresh fails.

Algorithm experiments

The package includes several approaches to the same combinatorial problems:

• Map folding: insertion-search algorithms derived from Lunnon's work, including variants that apply symmetry restrictions from his theorems.
• Meanders: transfer-matrix counting based on Jensen's approach, with dictionary, NumPy, Pandas, Polars, and pruning variants.
• Permutation generation: stamp-folding and meander algorithms based on Sawada and Li's work, with experimental bilateral variants.
• Elimination: possible leaf positions, pile assignments, and constraint propagation in mapFolding._e.

Counting entry points accept a flow preference. Omit it to use the default route. Available variants and dispatch rules change as the research develops; basecamp.py and the relevant easyRun runner show the current choices.

The transformation pipeline in kitAST can inline functions, decompose state dataclasses, specialize initialized values for a map shape, and prepare Numba or Linux Codon jobs. RecipeJob.py describes job configuration; easyRun/synthesizeModules.py coordinates module regeneration. For changes that should survive regeneration, edit the source algorithm or its transformation.

General-purpose transformation tools developed alongside this project live in astToolkit and astToolFactory. The transformations retained here serve mapFolding algorithms and jobs.

Computation cost and saved results

Exact enumeration becomes expensive quickly. Running time, memory use, and the appropriate implementation depend on the problem and its size; measure smaller cases before committing to a long computation.

Pass pathLikeWrite to a counting function to save the total. An existing directory receives a generated filename; an explicit filename is also supported. The destination is write-tested before counting, leaving a test value until the result replaces it. An existing target file is rejected. These output files save totals; they do not checkpoint a running search.

countFolds can divide work using an integer, computationDivisions='cpu', or computationDivisions='maximum'. Tasks repeat substantial preparatory work, so division can increase elapsed time. Leave computationDivisions=None unless task division is part of your experiment; see the function's docstring for the tradeoffs.

Repository guide

Citation and references

To cite this software, use CITATION.cff. The mathematical and implementation references below have BibTeX entries in citations/.

Folding and meander algorithms

• Albert Sadé (1949), Sur les Chevauchements des Permutations. PDF · BibTeX.
• John E. Koehler (1968), Folding a strip of stamps. DOI · BibTeX.
• W. F. Lunnon (1968), A map-folding problem. DOI · PDF · BibTeX.
• W. F. Lunnon (1971), Multi-dimensional map-folding. The basis for the multidimensional counting algorithms. DOI · PDF · BibTeX.
• Iwan Jensen (2000), A transfer matrix approach to the enumeration of plane meanders. The transfer-matrix method underlying the matrix-meander algorithms. DOI · Preprint · TeX source · BibTeX.
• Joe Sawada and Roy Li (2012), Stamp Foldings, Semi-Meanders, and Open Meanders: Fast Generation Algorithms. Permutation-based generation methods used in the experimental permutation algorithms. DOI · PDF · BibTeX.
• Stéphane Legendre (2014), Foldings and meanders. Relationships between folding and meander sequences, with folding-validity conditions. PDF · Preprint · TeX source · BibTeX.

Related research

• Nathan Clisby and Iwan Jensen (2012), A new transfer-matrix algorithm for exact enumerations: self-avoiding polygons on the square lattice. Further transfer-matrix techniques for exact counting, demonstrated on lattice polygons. DOI · Preprint · BibTeX.
• Yiyang Jia, Jun Mitani, and Ryuhei Uehara (2020), Valid Orderings of Layers When Simple-Folding a Map. A linear-time test for whether a supplied layer ordering is valid under simple folding, providing context for the role of the folding model in validity tests. DOI · Article and PDF · BibTeX.

Sequence data and other implementations

• The On-Line Encyclopedia of Integer Sequences. Sequence definitions, known values, formulas, and computation records. OEIS · BibTeX.
• jOEIS: Java Online Encyclopedia of Integer Sequences. Repository · Sean A. Irvine's A001415 implementation · BibTeX.
• Andrew Howroyd's meander implementation. C# source and description · BibTeX.

Installation

mapFolding requires Python 3.13 or newer. Install the published package from PyPI:

pip install mapFolding

NumPy and Numba are included in the base dependencies. Optional extras add other implementations and development tools:

For example:

pip install "mapFolding[pandas,polars]"

Development and supplemental materials

Clone the repository to work on the algorithms or access its archives, notes, and research materials:

git clone https://github.com/hunterhogan/mapFolding.git
cd mapFolding
python -m venv .venv

Activate the environment before installing. On PowerShell:

. .\.venv\Scripts\Activate.ps1
$env:PYTHONUTF8 = '1'
$env:PYTHONIOENCODING = 'utf-8'

On a POSIX shell:

. .venv/bin/activate

Then install the development and testing extras:

pip install -e ".[development,testing]"

Run project commands from the repository root with the environment active. For example, to check the main counting implementations:

pytest mapFolding/tests/test_computations.py

The tests compare algorithm variants with known OEIS values and exercise generated jobs. When adding a counting implementation, extend the relevant test cases in test_computations.py; supporting behavior has its own tests in mapFolding/tests and mapFolding/_e/tests.

Computation targets

These are my computation plans and estimates for my hardware, including work with unpublished algorithms.

• Folds of multidimensional map (2, 2, 2, 2, 2, 2, 2, 2), which is A001417(8): estimated 14 days with my current hardware and a non-published algorithm.
• Folds of multidimensional map (2, 21), which is A001415(21): 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): 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): estimated 11 days with my current hardware and one of the compiled "Theorem 2" algorithm versions.
• Semi-meanders with 50 crossings, which is A000682(50): 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.

Maintainer's working notes

This is my ongoing to-do list across this package and related projects. It records experiments, unresolved problems, and reminders to myself.

1. Acceleration
   1. 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.

My recovery