# 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:

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

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

# Python 3 + SymPy, 480455 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!

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

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).
• 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) – Kevin Cruijssen Nov 15 '19 at 14:35