This is a pre-production deployment of Warehouse. Changes made here affect the production instance of PyPI (pypi.python.org).
Help us improve Python packaging - Donate today!

Set of enumerators of multiple types of polyominoes (snake, tree, etc.)

Project Description

The files of this repository allows one to enumerate polyominoes based on Jensen’s algorithm. The code is written in Python, but it has been optimized using Cython.

Dependencies

Python module dependencies

Roadmap

  • Update the docstring in polyenum package (enumerators, data_structures modules).
  • Enhance –north-snake option implementation. The criterion for exluding invalid north snake candidate can be enhanced using the fact that for any row of a north snake the pattern x...0...x cannot be found. Since the algorithm builds polyominoes column after column, it would be a good idea to make all of the “left snakes” and rotate the results.
  • Creates a test suite.
  • Implements Knuth’s algorithm for the minimum connectivity problem (see comment in source code). This will improve significantly the speed when enumerating polyominoes.
  • Takes into account symmetry to improve speed of algorithm. It will also allow to generate free/fixed/one-sided polyominoes. Currently, only fixed polyominoes are generated.
  • Add other types of installers (MacPorts, Homebrew, Windows, Debian package, ArchLinux).
  • Add a script for extracting statistics and classifying.
  • Add a script for drawing.
  • Improve speed for enumerating partially directed snakes (it uses a Python boolean list instead of a bool*). Moreover, the enumeration columnwise could discard more configurations than by looking only at the pillars.

Howto use

The script polyenum is used to call the enumeration code. You can ./scripts/polyenum --help for help.

From git repository

In order for the script to run properly, the Cython library has to be compiled. It’s done by doing:

$ ./configure
$ make

and then, polyenum will be available under ./scripts directory.

Example

Enumerating all polyominoes of given area

Let the area of the polyominoes be 4. Finding all the polyominoes (not inscribed in a particular rectangle) of area 4 is done as follows:

$ ./polyenum -a 4 --fixed
Fixed polyomino enumeration.
XXXX

X
X
X
X

XX
XX

X--
XXX

XX
-X
-X

XXX
X--

XX
X-
X-

-X-
XXX

-X
XX
-X

-XX
XX-

-X
XX
X-

--X
XXX

-X
-X
XX

XX-
-XX

X-
XX
-X

XXX
-X-

X-
XX
X-

XXX
--X

X-
X-
XX

Time elapsed: 0.000782012939453125 seconds
Number of polyominoes: 19

More examples can be found reading polyenum’s man page (man ./doc/polyenum.1).

Installing

From PyPi dist release

Simply do:

python2.7 setup.py install

From git repository

The script can be installed on your system. This is useful since it provides bash tab completion capability for the script. To install, simply do:

$ ./configure
$ make
# make install

NOTE: Most of the installation process is done by python. On some platforms, python may install scripts under a directory which is not in your $PATH bash environnement variable.

Bash Completion

In order to install bash completion, do the following

$ BASH_COMPLETION_DIR=$p ./configure
$ make
# make install

where $p is the path to the directory where bash-completion scripts are installed on your system.

Release History

Release History

This version
History Node

0.1-1

Download Files

Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
polyenum-0.1-1.linux-x86_64.tar.gz (93.3 kB) Copy SHA256 Checksum SHA256 2.7 Dumb Binary Sep 14, 2014
polyenum-0.1_1-py2.7-linux-x86_64.egg (97.4 kB) Copy SHA256 Checksum SHA256 2.7 Egg Sep 14, 2014
polyenum-0.1-1.tar.gz (142.1 kB) Copy SHA256 Checksum SHA256 Source Sep 14, 2014

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting