13
\$\begingroup\$

Notation and definitions

Let \$[n] = \{1, 2, ..., n\}\$ denote the set of the first \$n\$ positive integers.

A polygonal chain is a collection of connected line segments.

The corner set of a polygonal chain is a collection of points which are the endpoints of one or more of the line segments of the chain.

Challenge

The goal of this challenge is to write a program that takes two integers, \$n\$ and \$m\$ and computes the number of non-self-intersecting polygonal chains with corner set in \$[n] \times [m]\$ that hit every point in \$[n] \times [m]\$ and are stable under \$180^\circ\$ rotation. You should count these shapes up to the symmetries of the rectangle or square.

Note: In particular, a polygon is considered to be self-intersecting.

Example

For example, for \$n=m=3\$, there are six polygonal chains that hit all nine points in \$[3] \times [3]\$ and are the same after a half-turn:

3 X 3 polygonal chains

Table of small values

 n | m | f(n,m)
---+---+-------
 1 | 2 | 1
 1 | 3 | 1
 2 | 1 | 1
 2 | 2 | 1
 2 | 3 | 5
 2 | 4 | 11
 2 | 5 | 23
 3 | 1 | 1
 3 | 2 | 5
 3 | 3 | 6
 3 | 4 | 82

Scoring

This is a challenge, so shortest code wins.

\$\endgroup\$

This question has an open bounty worth +50 reputation from Peter Kagey ending in 4 days.

This question has not received enough attention.

  • 1
    \$\begingroup\$ You say "stable under rotation by 180 degrees", but your 3x3 example seems to be stable on all 90-degree multiple rotations and reflections. Can you clarify, and give us a detailed non-square example? \$\endgroup\$ – Chas Brown Nov 5 at 2:37
  • 2
    \$\begingroup\$ Do you have any test cases for larger values? \$\endgroup\$ – Bubbler Nov 5 at 4:33
  • 3
    \$\begingroup\$ I think f(2,2)=2. There's an open chain shaped like an N and a closed chain shaped like a square. \$\endgroup\$ – Peter Taylor Nov 5 at 14:19
  • 2
    \$\begingroup\$ I'd imagine that the reason that the closed-square on a 2*2 is not counted is that it is considered to be "self-intersecting" (albeit only at a node) \$\endgroup\$ – Jonathan Allan Nov 5 at 17:19
  • 2
    \$\begingroup\$ @PeterTaylor, I don't see it that way, but I'll edit the problem to disambiguate. \$\endgroup\$ – Peter Kagey Nov 5 at 18:25
6
\$\begingroup\$

Python 3 + SymPy, 480 455 bytes

lambda w,h:len({min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w-1-p[0],p[1]),I),(lambda p:(p[0],h-1-p[1]),I),(lambda p:p[::-1],I)))for o in permutations(Q(range(w),range(h)))for s in[[*zip(o,o[1:])]]if any(x+X-w+1|y+Y-h+1for(x,y),(X,Y)in zip(o,o[::-1]))+any(gcd(x-X,y-Y)>1for(x,y),(X,Y)in s)+any((len({*u,*v})>3)*intersection(S(*u),S(*v))for u,v in Q(s,s))<1})
from math import*
from sympy import*
from itertools import*
Q=product
S=Segment
I=tuple

Try it online!

Inlined version of the previous answer below.


Python 3 + SymPy, 480 bytes

from math import*
from sympy import*
from itertools import*
Q=product
S=Segment
I=tuple
def f(w,h):
 a={1}
 for o in permutations(Q(range(w),range(h))):
  s=[*zip(o,o[1:])]
  if any(x+X-w+1|y+Y-h+1for(x,y),(X,Y)in zip(o,o[::-1]))+any(gcd(x-X,y-Y)>1for(x,y),(X,Y)in s)+any((len({*u,*v})>3)*intersection(S(*u),S(*v))for u,v in Q(s,s))<1:a.add(min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w-1-p[0],p[1]),I),(lambda p:(p[0],h-1-p[1]),I),(lambda p:p[::-1],I))))
 return~-len(a)

Try it online!

The golfed version takes too long to check the nontrivial answers. The version below has a shortcut in the conditional, so you can check that the results up to (2,4) are correct.

Python 3 + SymPy, 483 bytes

from math import*
from sympy import*
from itertools import*
Q=product
S=Segment
I=tuple
def f(w,h):
 a={1}
 for o in permutations(Q(range(w),range(h))):
  s=[*zip(o,o[1:])]
  if(any(x+X-w+1|y+Y-h+1for(x,y),(X,Y)in zip(o,o[::-1]))or any(gcd(x-X,y-Y)>1for(x,y),(X,Y)in s)+any((len({*u,*v})>3)*intersection(S(*u),S(*v))for u,v in Q(s,s)))<1:a.add(min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w-1-p[0],p[1]),I),(lambda p:(p[0],h-1-p[1]),I),(lambda p:p[::-1],I))))
 return~-len(a)

Try it online!

Ungolfed, with comments

from math import*
from sympy import*
from itertools import*
def pass_point(p1,p2): # test if the segment passes through another point
 return gcd(p1[0]-p2[0],p1[1]-p2[1]) > 1
def f(w,h):
 pts = [(i,j) for i in range(w) for j in range(h)]
 ans = set()
 for orders in permutations(pts):
  # test if the ordering has 180 degrees rotational symmetry
  if any(x1+x2!=w-1or y1+y2!=h-1for (x1,y1),(x2,y2) in zip(orders, orders[::-1])):continue
  segments = [*zip(orders, orders[1:])]
  # test if a segment passes through another point or two segments intersect
  if any(pass_point(*p)for p in segments)+any(len({*s1,*s2})==4and intersection(Segment(*s1),Segment(*s2))for s1 in segments for s2 in segments):continue
  # take minimum of 8 possible rotations/reflections
  flipH = lambda p:(w-1-p[0],p[1]); flipV = lambda p:(p[0],h-1-p[1]); flipD = lambda p:p[::-1]; nop = lambda p:p
  flipmin = min(tuple(map(lambda o:d(h(v(o))),orders))for h in (flipH,nop)for v in (flipV,nop) for d in (flipD, nop))
  ans.add(flipmin)
 print(len(ans))

Try it online!

SymPy has Geometry module that includes an intersection checker intersection that works for line segment Segment objects. This is much shorter than rolling a hand-written intersection checker based on coordinates. The intersection of two Segments is either an empty array (if they don't intersect) or an array that contains a single object (either Point or Segment, depending on the input).

\$\endgroup\$
  • \$\begingroup\$ In your top and third versions, the w-1-p[0] and h-1-p[1] can be w+~p[0] and h+~p[1], as well as the x+X-w+1|y+Y-h+1for to x-~X-w|y-~Y-h for (or x-~X-w|y+Y-h+1for). (Relevant tip) \$\endgroup\$ – Kevin Cruijssen 3 hours ago

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.