R, 180 168 bytes
f=\(n,o={},v=0,u=0,`:`=c,`~`=sort,`?`=diff){for(j in u)F=F+`if`(length(p<-~j:o)<n,f(n,p,v,setdiff(c(u=u[-1],j+-1:1i:1:-1i),v<-j:v)),2^(-any(?p-~-p)-any(?p-~p*1i))/n);F}
Attempt This Online!
How about a golfy implementation of a more or less real world algorithm of counting polyominoes?
This code is a variation of Redelmeier's method published back in 1981 (link). Obviously, here lots of speed optimizations have been sacrificed in favor of golf, but it still manages to calculate all \$n\$ up to 9 in about 17 s on TIO (and even finishes \$n = 10\$ when run alone), yet allowing for a quite nice byte count.
Explanation
The method works by performing a recursive depth-first search up to the indicated length \$n\$. The key point is that we never store the list of found polyominoes. Instead, we check for symmetries, and if the current polyomino is symmetric, add only a fraction of the score, so that the total of all polyominoes having the same unique shape would add up to 1.
The algorithm starts by initializing the parent polyomino \$o\$ as empty (NULL
), the set of visited cells \$v\$, and untried cells \$u\$ containing only the origin. The coordinates of the cells are represented by complex numbers.
for(j in u)
- Iterate through the untried set. At each iteration, the current cell is \$j\$.
u<-u[-1]
- Remove the current cell from the untried set.
v<-c(j, v)
- Add it to the visited set.
p<-sort(c(j, o))
- Grow the current polyomino \$p\$ by adding \$j\$ to the parent \$o\$. Sort for later use.
if(length(p)<n)
- If the polyomino has not yet reached the maximum length,
f(n,p,v,...)
- Invoke the recursive call with modified arguments. The new untried set (...
) is constructed as follows.
Add new neighbors to the untried set. When we are at the origin, the next iteration will involve the cells labeled 1-4
in the scheme below. However, the new neighbors exclude already visited cells, therefore when enumerating neighbors for cell 1
, only the cells 5-7
will be added, as the origin had already been visited.
. . . . . . .
. . 6 2 . . .
. 5 1 0 3 . .
. . 7 4 . . .
. . . . . . .
So, the new untried set is defined as \$u \cup\ \{j-1,j+i,j+1,j-i\} \setminus v\$.
If the length \$n\$ has already been reached, count the polyomino and return.
2^(-any(diff(p-sort(-p)))-any(diff(p-sort(p*1i))))/n
- This is our symmetry evaluation.
As we are interested in one-sided polyominoes, luckily, only two checks corresponding to 90 and 180 degree rotations are needed, no reflections involved. The rotations with complex numbers are very simple (\$ \times i\$ for 90 degrees, and \$ \times -1\$ for 180 degrees), but then we need to align the shapes to compare them. For this purpose, we sort the polyomino cells, and subtract one from another. If both represent the same shape under different translations from the origin, the resulting vector will consist of identical entries, so that all diff
will be zero.
Now, if a polyomino is invariant under 180 degree rotation, we will encounter this shape twice, so that gains a multipler of \$1/2\$.
If it is also invariant under 90 degree rotation, we will find it 4 times, and the multiplier becomes \$1/4\$.
In Redelmeier's work, there are additional restrictions disallowing inclusion of certain cells, in order to guarantee that each different rotation ("fixed" polyomino) we be counted exactly once. But these checks take precious bytes, so we skip them. In our case, each fixed polyomino is counted \$n\$ times - once for every possible starting point. So, we can handle this simply by dividing the result by \$n\$.
Finally, we make use of heavy operator overloading to turn the code into a lunatic mess for some rather modest byte savings.