Counting symmetric grid chains

Question

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 code-golf challenge, so shortest code wins.

• Chas Brown: 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?
• Bubbler: Do you have any test cases for larger values?
• Peter Taylor: I think f(2,2)=2. There's an open chain shaped like an N and a closed chain shaped like a square.
• Jonathan Allan: 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)
• Peter Kagey: @PeterTaylor, I don't see it that way, but I'll edit the problem to disambiguate.

Answer 1

Python 3 + SymPy, _{(削除) 480 (削除ここまで) (削除) 455 (削除ここまで)} 452 bytes

lambda w,h:len({min(I(D(H(V(x)))for x in o)for H,V,D in Q((lambda p:(w+~p[0],p[1]),I),(lambda p:(p[0],h+~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|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. -3 bytes thanks to Kevin Cruijssen's tip.

---

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).

• Kevin Cruijssen: 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)