add method to find a surrounding of a polyomino with isometric copies of itself

[seblabbe]

This ticket adds some code based on the tiling solver class and dancing links solver to find a surrounding of a polyomino with copies of itself. An example is below:

sage: from sage.combinat.tiling import Polyomino
sage: H = Polyomino([(-1, 1), (-1, 4), (-1, 7), (0, 0), (0, 1), (0, 2),
....: (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 1), (1, 2),
....: (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 2),
....: (2, 3), (2, 5), (2, 6), (2, 8)])
sage: H.show2d()

sage: %time solution = H.self_surrounding(10, ncpus=8)
CPU times: user 1.69 s, sys: 1.08 s, total: 2.77 s
Wall time: 3.85 s
sage: G = sum([p.show2d() for p in solution], Graphics())
sage: G

See: https://user-images.githubusercontent.com/2339795/216875696-aef5396f-e30f-4e85-b4f5-85f5a841b797.pngeesch%27s_problem

Component: combinatorics

Author: Sébastien Labbé

Branch/Commit: 9d36ca5

Reviewer: Travis Scrimshaw, Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/29160

[seblabbe]

comment:1

Attachment: H.png

[seblabbe]

Description changed:

--- 
+++ 
@@ -12,7 +12,9 @@
 ![](https://github.com/sagemath/sage/files/ticket29160/H.png)

-sage: solution = H.self_surrounding(8) +sage: %time solution = H.self_surrounding(10, ncpus=8) +CPU times: user 1.69 s, sys: 1.08 s, total: 2.77 s +Wall time: 3.85 s sage: G = sum([p.show2d() for p in solution], Graphics()) sage: G

[seblabbe]

Attachment: G.png

[seblabbe]

New commits:

4b9e10d	finding a surrounding of a polyomino with copies of itself
402f1c2	29160: adding random colors to output

[seblabbe]

Branch: u/slabbe/29160

[seblabbe]

Commit: 402f1c2

[seblabbe]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-This ticket adds some code based on the tiling solver class and dancing links solver to surround a polyomino with copies of itself. An example is below:
+This ticket adds some code based on the tiling solver class and dancing links solver to find a surrounding of a polyomino with copies of itself. An example is below:

sage: from sage.combinat.tiling import Polyomino @@ -20,3 +20,5 @@

 ![](https://github.com/sagemath/sage/files/ticket29160/G.png)
+
+See: https://en.wikipedia.org/wiki/Heesch%27s_problem

[tscrim]

comment:4

A few little things:

     - ``dimension`` -- integer (default: ``None``), dimension of the space, 
       if ``None``, it is guessed from the ``coords`` if ``coords`` is non
-      empty.
+      empty

                 raise ValueError("dimension(={}) must be provided for"
-                             " the empty polyomino".format(dimension))
+                                 " the empty polyomino".format(dimension))

-Return whether self is strictly inside of other.
+Return whether ``self`` is strictly inside of ``other``.

and other similar changes.

         OUTPUT:

-            polyomino
+        polyomino

         return Polyomino(self.frozenset() & other.frozenset(),
-                color=self._color, dimension=self._dimension)
+                         color=self._color, dimension=self._dimension)

         OUTPUT:

-            set of 3d polyominoes
+        set of 3d polyominoes

-        Using a Polyomino as input ::
+        Using a Polyomino as input::

-        - ``orientation_preserving`` -- bool (optional, default: ``True``),
-          If True, the group of isometries of the `n`-cube is restricted to
-          those that preserve the orientation, i.e. of determinant 1.
+        - ``orientation_preserving`` -- bool (optional, default: ``True``);
+          if ``True``, the group of isometries of the `n`-cube is restricted
+          to those that preserve the orientation, i.e. of determinant 1

-        S = set()
-        for cano in all_distinct_cano:
-            for t in cano.translated_copies_intersection(box=box):
-                S.add(t)
-        return S
+        return set([t for cano in all_distinct_cano
+                    for t in cano.translated_copies_intersection(box=box)])

     def self_surrounding(self, radius, remove_incomplete_copies=True,
-            ncpus=None):
+                         ncpus=None):

         OUTPUT:

-            list of polyominoes
+        list of polyominoes

            raise Exception('No solution was found with radius={}, '
            'this tile can not be surrounded by itself'.format(radius))

I don't like the fact that this raises a general Exception. I think it should be more specific like a ValueError.

Some of these are PEP8 and could amount to more of bikeshedding, but I think it is good to try and follow them. There are a few other such PEP8 code changes that could be done too beyond those I mentioned here.

[seblabbe]

comment:5

Thanks Travis for your careful reading. I agree with your comments. I will work on it.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 402f1c2 to 9cf100b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9cf100b

29160: style improvements (PEP8-like) after review

[seblabbe]

comment:8

Each time, I searched and fixed similar issues in the same file.

[mkoeppe]

comment:9

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[fchapoton]

comment:10

La patchbot se plaint un petit peu :

+src/sage/combinat/tiling.py:446:15: E701 multiple statements on one line (colon)

et ca serait gentil de briser cette ligne en deux.

[seblabbe]

comment:11

ok, je fais ça la semaine prochaine.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

66b2f8b	finding a surrounding of a polyomino with copies of itself
0c8bd47	29160: adding random colors to output
fcfe62f	29160: style improvements (PEP8-like) after review
9d36ca5	29160:one statement per line

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9cf100b to 9d36ca5

[seblabbe]

comment:13

J'ai trouvé le double statement sur une même ligne. Je l'ai mis sur deux lignes séparées.

J'ai fait un rebase sur une version plus récente de Sage que j'utilise sur cette machine (9.1.rc1).

Needs review.

Sébastien

[seblabbe]

Reviewer: Travis Scrimshaw, Frédéric Chapoton

[fchapoton]

comment:15

ok, allons-y

[vbraun]

Changed branch from u/slabbe/29160 to 9d36ca5