# Counting polystrips

Polystrips are a subset of polyominoes conforming to the following rules:

• each piece consist of 1 or more cells
• no cell can have more than two neighbours
• the cells should not enclose a hole

Free polyominoes are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over). Translating, rotating, reflecting, or glide reflecting a free polyomino does not change its shape (Wikipedia)

For example, there are 30 free heptastrips (polystrips with length 7). Here are all of them, packed into a 14x15 grid.

Image credit: Miroslav Vicher

## Goal

Write a program / function that takes a positive integer n as input and enumerates the distinct free n-polystrips.

• n=1 --> 1 (A single square)

• n=2 --> 1 (There is only one possible 2-polystrip made of 2 squares)

• n=3 --> 2 (One is composed of 3 squares joined in a line and the other one is L-shaped)

• n=4 --> 3 (One straight, one L-shaped and one Z-shaped)

• . . .

## Test cases:

n   polystrips

1   1
2   1
3   2
4   3
5   7
6   13
7   30
8   64
9   150
10  338
11  794
12  1836
13  4313
14  10067
15  23621


## Scoring

This is , so the shorter code is better. I would highly appreciate detailed explanations of the algorithm and the code.

## Partial reference implementation in J

I decided to describe each piece in "vector" format and I only need n-2 blocks to describe an n-polystrip piece (there is only 1 2-polystrip and it's returned explicitly). The blocks describe the relative direction: 0 - no change; 1 - turn left; 2 - turn right. It doesn't matter which direction one will start but only to indicate where the next cell is to be put. There can be any number of consecutive 0s, but 1s and 2s are always single. This implementation is partial, because it doesn't account for the holes - solutions for n>6 count the pieces with holes too.

Try it online!

• Relevant OEIS. (But doesn't exclude holes.) Feb 17 '18 at 8:30
• @ Martin Ender Thank you, I didn't know it. Feb 17 '18 at 8:42
• Just to be sure, I assume that if you fill a 3x3 grid except for the center and one corner that also counts as a hole (101010 in your sample notation) ? Feb 17 '18 at 10:59
• Perhaps a good question for math.SE Dec 20 '19 at 12:24
• Did you know that now this is oeis.org/A333313? You can ask the author (who is a fellow golfer) to add your name in the OEIS entry. Aug 29 '20 at 12:20

# Python 3, 480433406364309299 295 bytes

Looked like a good point to start my PPCG career (or not?).

def C(s):
S,*a={''},0,1;n=d=r=1
for c in s:d=c*d*1jor d;n+=d;a+=n,;r*=not{n}&S;x,*a=a;S|={x+t+u*1jfor t in A for u in A}
return r
from itertools import*;A=-1,0,1;n,y=int(input())-2,0;x={*filter(C,product(*[A]*n))}
while x:s=x.pop();S=*(-u for u in s),;x-={s[::-1],S,S[::-1]}-{s};y+=1
print(y)


Try it online!

Edits:

• Inlined D and X, and tweaked a little bit on some golfable spots.
• Applied more tricks, mainly set-related ones.
• Changed into program form, and changed to using complex numbers instead of arbitrary number m. (Complex numbers are really a strong but often ignored golfy feature; adapted from xnor's solution for another challenge)
• Changed the LFR string representation to -1,0,1 tuples and sacrificed execution time for crazy amount of byte reduction(!). Now the solution is theoretically correct but timeouts before outputting the result for 15.
• One-lined the loop thanks to Jonathan Frech, then I found the much better alternative for calculating r. FINALLY UNDER 300 BYTES!!!
• Surprisingly 1j can stick to anything else without confusing the parser (-2B), and not has insanely low precedence (-2B).

Obsolete version (480 bytes):

def C(s):
m=999;a=[0,1];n=d=1
D={'F':{},'L':{1:m,m:-1,-1:-m,-m:1},'R':{1:-m,-m:-1,-1:m,m:1}}
X=lambda x:{x+~m,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x-~m}
for c in s:
d=D[c].get(d,d);n+=d;a+=n,
if n in set().union(*map(X,a[:-3])):return 0
return 1
def f(n):
if n<3:return 1
x={*'LF'}
for _ in range(3,n):x={s+c for s in x for c in({*'LRF'}-{s[-1]})|{'F'}}
y={*x}
for s in x:
if s in y:S=s.translate(str.maketrans('LR','RL'));y-={s[::-1],S,S[::-1]}-{s}
return sum(map(C,y))


Try it online!

t = str.maketrans('LR','RL')

# hole checking function
def check(s):
m = 999   # (imaginary) board size enough to fit all generated polyominoes
a = [0,1] # previous path
n = 1     # current cell
d = 1     # current direction
# dict for direction change
D = {'F':{}, 'L':{1:m, m:-1, -1:-m, -m:1}, 'R':{1:-m, -m:-1, -1:m, m:1}}
# used to 'blur' all cells in path into 3x3
X = lambda x: {x-m-1,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x+m+1}
for c in s:
d = D[c].get(d,d) # change direction
n += d            # move current cell
# the polyomino has a hole if the current cell touches previous cells (including diagonally; thus the blurring function)
if n in set().union(*map(X,a[:-2])): return False
a.append(n)       # add current cell to the path
return True

# main function
def f(n):
if n < 3: return 1
x = {*'LF'}
# generate all polystrips using the notation similar to the reference
for _ in range(3, n): x = {s+c for s in x for c in ({*'LRF'}-{s[-1]})|{'F'}}
y = {*x}
for s in x:
if s in y:
S = s.translate(t)
y -= {s[::-1], S, S[::-1]} - {s}
# finally filter out holey ones
return sum(map(check,y))


Try it online!

m = 999 is chosen because it takes exponential time to count everything, and it's already taking ~8s to calculate n = 1..15. Maybe it's fine to save 1 byte by using 99 instead. We don't need this anymore, and now it's guaranteed to be correct for arbitrary input size, thanks to complex number built-in.

• Welcome to PPCG! Definitely an impressive way to start your PPCG career. :) Feb 21 '18 at 8:53
• Welcome to PPCG and thanks for this solution! I had already given up expecting to see a solution :) Feb 21 '18 at 8:56
• Looked like a good point to start my PPCG career (or not?). Well, this is a surprisingly short solution to this most of us wouldn't even think could ever be, even the ungolfed version looks surprisingly simple, but, eh, maybe this is an average way to start your PPCG career, right? :) Feb 24 '18 at 20:30
• @Erik That line was half a joke :) But yeah, the solution is even surprising to me - I never expected myself to pull out ~36% reduction from original submission. Feb 25 '18 at 7:14
• Feb 26 '18 at 12:00

# APL (Dyalog Unicode), 70 65 bytes

+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳2↓⎕⍴3


Try it online!

Full program version of the code below, thanks to Adám.

# APL (Dyalog Unicode), 70 bytes

{+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳3⍴⍨0⌈⍵-2}


Try it online!

### How it works

The code above is equivalent to the following definition:

gen←{2-,⍳3⍴⍨0⌈⍵-2}
canonicalize←{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
test←{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{+/test¨∪canonicalize¨gen⍵}


This works like the Python solution, but in a different order. It generates LFR-strips of length n-2, canonicalizes each strip, takes ∪nique strips, tests each strip if it touches itself (1 if not touching, 0 otherwise), and sums +/ the boolean result.

### gen

{2-,⍳3⍴⍨0⌈⍵-2}
{            }  ⍝ ⍵←input number n
0⌈⍵-2   ⍝ x←max(0, n-2)
3⍴⍨        ⍝ x copies of 3
,⍳           ⍝ multi-dimensional indexes; x-th cartesian power of [1,2,3]
⍝ (⍳ gives x-dimensional hypercube; , flattens it)
2-             ⍝ compute 2-k for each k in the array

⍝ in each strip, ¯1, 0, 1 corresponds to R, F, L respectively


### canonicalize

{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
{                  }  ⍝ ⍵←single strip
⍵(-⍵)   ⍝ nested array of ⍵ and its LR-flip
(⊢,⌽¨)        ⍝ concatenate their head-to-tail flips to the above
(⊃∘⍋  )              ⍝ find the index of the lexicographically smallest item
⊃⊢               ⍝ take that item


### test

{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{                                  }  ⍝ ⍵←single strip
0j1*⍵   ⍝ power of i; direction changes
×\        ⍝ cumulative product; directions
0 1,    ⍝ initial position(0) and direction(1)
+\        ⍝ cumulative sum; tile locations
(  ⊢{           }¨,\)   ⍝ test with current tile(⍺) and all tiles up to ⍺(⍵):
¯3↓⍵        ⍝ x←⍵ with last 3 tiles removed
⍺-            ⍝ relative position of each tile of x from ⍺
2≤|              ⍝ test if each tile of x is at least 2 units away
∧/                 ⍝ all(...for each tile in x)
∧/        ⍝ all(...for each position in the strip)

• -5