8
\$\begingroup\$

Background

Conway criterion is a method to test if a given polygon can tile (i.e. cover without overlapping) an infinite plane. It states that a polygon can tile the plane if the following conditions are met:

  • The given polygon does not have any holes in it.
  • It is possible to choose six consecutive1 points \$A,B,C,D,E,F\$ on its perimeter, so that
    • The boundary part of \$A\$ to \$B\$ must be equal to that of \$E\$ to \$D\$ in its size, shape, and orientation;
    • Each of the boundary parts \$BC\$, \$CD\$, \$EF\$, and \$FA\$ must have 180-degrees rotational symmetry; and
    • At least 3 out of the six points must be distinct from each other.

1) By consecutive, the six points must appear in the given order if you walk around the shape in one direction (either CW (clockwise) or CCW (counter-clockwise)). A boundary part between two consecutive points may contain zero, one, or multiple line segments.

If all the conditions are met, the given shape can tile the plane using only translation and 180-degree rotation. However, failing the condition doesn't mean the piece can't tile the plane. This happens when the tiling involves 90-degree rotations and/or reflections, or the tiling does not use 180-degree rotation at all.

The following is one example that satisfies Conway criterion:

enter image description here

with its plane tiling:

enter image description here

Task

Given a polyomino without holes as input, determine if it satisfies Conway criterion.

You can take the input in any sensible ways, including but not limited to

  • a 2D grid;
  • a list of coordinates of the cells;
  • a list of coordinates on the boundary (including non-vertices or not);
  • a list of steps starting from some point on the perimeter in NSEW notation, ...

If you use the input format that describes the perimeter (e.g. the last two formats above), you can assume that the input (the sequence of points or steps on the perimeter) is given in certain direction (either CW or CCW), but you cannot assume that it starts at any certain position.

Standard rules apply. The shortest code in bytes wins.

Test cases

The test cases are given as 2D grid, where O is a part of the polyomino and . is an empty space.

True

the example above
OO........
OOOOOOOOOO
OOOOOOOOOO
....OOOOOO
....OOOOOO
....OOOOOO
....OOOOOO
....OOOOOO

the F pentomino
.OO
OO.
.O.
one possible set of points:
  A---E=F
  |   |
+-+ +-+
|   |
B-+ D
  | |
  +-C

OOO.
O.OO
E---D-C
|     |
F +-+ +-+
| | |   |
+-+ A---B

a nonomino that can tile with or without 180 degrees rotation
.O..
.OOO
OOO.
.OO.
.O..

can you spot ABCDEF here? (hint: two points out of ABCDEF are not on the vertices)
OOOO...
.OOOO..
OO.O...
O..OOOO

how about this? (hint: AB and DE are zero-length)
...OOOO.
OO.OO...
O..OOO..
OOOO....
..OOOOOO
..OO....

False

can tile the plane, but needs 90 deg rotation
.OOO.
OO.OO

cannot tile the plane at all
OOOO
O...
O.OO
OOO.

can tile with only translation, but not with 180 degrees rotation
...O
.OOO
OOO.
..OO

\$\endgroup\$
2
  • \$\begingroup\$ Can we assume that the six indicated points can always be taken to be lattice points on the boundary? \$\endgroup\$ May 12, 2020 at 15:32
  • \$\begingroup\$ @GregMartin Yes, this can be proven. \$\endgroup\$
    – Nitrodon
    May 12, 2020 at 18:54

1 Answer 1

12
\$\begingroup\$

Python 3.8 (pre-release), 371 ... 338 336 bytes

Takes as input a list of complex numbers, denoting the boundary coordinates in counterclockwise order.

-9 bytes thanks to @ovs
-2 bytes thanks to @Bubbler

import itertools as Z
def f(P):Q=P*2;I=Q.index;L=len;return any(L({*map(complex.__sub__,T:=(J:=lambda x,y:Q[(j:=I(p[x])):I(p[y],j)+1])(0,1),U:=J(3,4)[::-1])})<2<L({*p})and(L(T)==L(U))&all((B:=J(a,-~a%6))==[B[L(B)//2]-E+B[~L(B)//2]for E in B][::-1]for a in[1,2,4,5])for S in zip(*[Q[I(i):]for i in P])for p in eval('Z.'+dir(Z)[11])(S,6))

Try it online!

\$\endgroup\$
5
  • 2
    \$\begingroup\$ 338 bytes with import itertools as Z and eval('Z.'+dir(Z)[11]) instead of combinations_with_replacement. \$\endgroup\$
    – ovs
    May 12, 2020 at 7:21
  • 1
    \$\begingroup\$ Try it online! \$\endgroup\$
    – ovs
    May 12, 2020 at 7:25
  • \$\begingroup\$ @ovs Very nice! That's a smart way of reducing extremely long function names. \$\endgroup\$ May 12, 2020 at 16:09
  • \$\begingroup\$ You still have a len. \$\endgroup\$
    – Bubbler
    May 13, 2020 at 0:00
  • \$\begingroup\$ @Bubbler Good catch :) \$\endgroup\$ May 13, 2020 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.