match-sticks

A program that enumerates certain constrained sets of match sticks (edges of a certain graph on the standard integer lattice points in R^2).

Description

(This problem was communicated to me by Kyle Ormsby)

The problem is to enumerate all possible configurations of edges between the integer points of a rectangle in R^2, subject to some mysterious constraints that arise in homotopy theory.

Consider the 2x2 rectange of integer points with lower left corner at the origin in R^2:

*  *  *

*  *  *

*  *  *

We're interested in the unit length edges connecting these points (which must therefor be either vertical or horizontal).

An "Edge Set" in this context is a set of such edges:

*--*  *
|
*  *--*

*  *--*

We say an edge set is "valid" if three conditions hold:

1. If a vertical edge v is in the set, then all the vertical edges to the left of v are also present in the set.
2. Same as (1) with horizontal edges, but replace "left" with "below".
3. Each unit square in the grid must not have 3 edges present, i.e. 0, 1, 2, and 4 are admissible.

Examples

The first (emtpy) edge set above is valid in this sense, and the second is invalid (because there is a horizontal edge in the upper-left with no horizontal edges below it).

This is also a non-valid edge set: (while attempting to fix the one above by adding edges below the problematic one, we've made the upper-left square have 3 edges)

*--*  *
|
*--*--*

*--*--*

And, finally, this is a non-trivial valid edge set:

*--*  *
|  |
*--*--*

*--*--*

In fact, there are XXX valid edge sets on the 2x2 grid.

Questions

Given an n x m rectangle,

1. How many valid edge sets are there?
2. Enumerate all valid edge sets in the rectangle.
3. Exhibit a generating function whose coefficients count valid edge sets.
4. Exhibit the number of valid edge sets as a positive sum.

Installation

This package requires Python 3.7+. The main modules do not have any requirements beyond the Python standard library. In addition, pytest is required if you want to run tests. We use flake8 and mypy for code analysis.

To check what python you have, try:

$ python3 --version
Python 3.7.6

To install and run the code in a virtual environment, run the following commands, assuming your python 3.7+ interpreter is called python3:

$ cd match-sticks
$ python3 -m venv .venv
$ source .venv/bin/activate
$ python3 -m pip install -r requirements.txt
$ python3 -m pip install -e .

Now you can run the program:

$ python3 main.py --help
usage: main.py [-h] [-v] WIDTH HEIGHT

positional arguments:
  WIDTH          width of the grid
  HEIGHT         height of the grid

optional arguments:
  -h, --help     show this help message and exit
  -v, --verbose  pretty print enumerated edge sets
  --profile         dump profiler statistics
  --loglevel LEVEL  logging level to emit: DEBUG, INFO, WARNING (default),
                    ERROR

To count (and print) valid edge sets on the 2x1 grid:

$ python3 main.py --verbose 1 1

1:
*  *

*  *

2:
*  *

*--*

3:
*  *
|
*  *

4:
*--*

*--*

5:
*  *
|
*--*

6:
*  *
|  |
*  *

7:
*--*
|  |
*--*

By setting the log level to INFO you can see how many total edge set combinations were checked during execution:

$ python main.py --loglevel INFO 2 4
INFO:Enumerating valid edge sets on 2 x 4 grid
INFO:Total candidate edge sets checked: 4194304
2359

Testing and Verification

To test:

$ python -m pytest

To lint/typecheck:

$ flake8 . --count --show-source --statistics
$ mypy .

TODO

• make initial package commit
• get GitHub CI working
• write a README description of the edge set constraints
• extend validation to include forall unitsquare. (num. edges on unitsquare) != 3
• write a naive brute force enumerator
• test naive edge_set validator
• [.] write a recursive enumerator
• validate results of enumeration using generator function formula
• write an edge set counter that does not explicitly construct or enumerate edge sets

Acknowledgements

The original problem was communicated to me by Kyle Ormsby (http://people.reed.edu/~ormsbyk/). The counting algorithm in toms_algorithm.py is due to Tom Edgar (https://www.plu.edu/math/staff/tom-edgar/).