# 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.) Commented Feb 17, 2018 at 8:30
• @ Martin Ender Thank you, I didn't know it. Commented Feb 17, 2018 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) ? Commented Feb 17, 2018 at 10:59
• Perhaps a good question for math.SE Commented Dec 20, 2019 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. Commented Aug 29, 2020 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. :) Commented Feb 21, 2018 at 8:53
• Welcome to PPCG and thanks for this solution! I had already given up expecting to see a solution :) Commented Feb 21, 2018 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? :) Commented Feb 24, 2018 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. Commented Feb 25, 2018 at 7:14
• Commented Feb 26, 2018 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
Commented Dec 20, 2019 at 7:13

# Scala, 2277 1710 bytes*:

### Golfed version

Try it online!

import scala.collection.mutable.Set

object Main {
def checkSeq(s: String): Boolean = {
val max = BigInt(9).pow(9)
var a = Seq(BigInt(0), BigInt(1))
var n = BigInt(1)
var d = BigInt(1)
val dirs = Map(
'F' -> Map[BigInt, BigInt](),
'L' -> Map(BigInt(1) -> max, max -> BigInt(-1), BigInt(-1) -> -max, -max -> BigInt(1)),
'R' -> Map(BigInt(1) -> -max, -max -> BigInt(-1), BigInt(-1) -> max, max -> BigInt(1))
)
val adj = (x: BigInt) => Set(x - max - 1, x - max, x - max + 1, x - 1, x, x + 1, x + max - 1, x + max, x + max + 1)

s.foreach { c =>
d = dirs(c).getOrElse(d, d)
n += d
val v1 = if (a.length > 2) a.slice(0, a.length - 2).map(adj) else Seq()
val s1 = if (v1.isEmpty) Set[BigInt]() else v1.reduce(_ ++ _)
if (s1.contains(n)) return false
a = a :+ n
}
true
}

def f(n: Int): Int = {
if (n < 3) return 1

var x = Set("L", "F")
(3 until n).foreach { _ =>
x = x.flatMap { seq =>
val chars = Set('L', 'R', 'F') - seq.last + 'F'
chars.map(c => seq + c)
}
}

var y = x.clone()
x.foreach { seq =>
if (y.contains(seq)) {
val trSeq = seq.replace("L", "#").replace("R", "L").replace("#", "R")
val s1 = Set(seq.reverse, trSeq, trSeq.reverse)
y --= s1.diff(Set(seq))
}
}

y.count(checkSeq)
}

def main(args: Array[String]): Unit = {
val t1 = System.nanoTime()
(1 to 15).foreach { i =>
val t2 = System.nanoTime()
val res = f(i)
val t3 = System.nanoTime()
println(s"$i$res ${t3 - t2}ns") } val t4 = System.nanoTime() println(s"Total time:${(t4 - t1) / 1000000.0}ms")
}
}



### Ungolfed version

Try it online!

import scala.collection.mutable.Set

object Main {
def checkSequence(s: String): Boolean = {
val maxValue = BigInt(9).pow(9)
var a = Seq(BigInt(0), BigInt(1))
var n = BigInt(1)
var d = BigInt(1)
val directions = Map(
'F' -> Map[BigInt, BigInt](),
'L' -> Map[BigInt, BigInt](BigInt(1) -> maxValue, maxValue -> BigInt(-1), BigInt(-1) -> -maxValue, -maxValue -> BigInt(1)),
'R' -> Map[BigInt, BigInt](BigInt(1) -> -maxValue, -maxValue -> BigInt(-1), BigInt(-1) -> maxValue, maxValue -> BigInt(1))
)
val calculateAdjacent = (x: BigInt) => Set(x - maxValue - 1, x - maxValue, x - maxValue + 1, x - 1, x, x + 1, x + maxValue - 1, x + maxValue, x + maxValue + 1)   // return a set

for (c <- s) {
d = directions(c).getOrElse(d, d)
n += d
val var1 = if (a.length > 2) a.slice(0, a.length - 2).map(calculateAdjacent) else Seq()
val set1 = if (var1.isEmpty) Set[BigInt]() else var1.reduce(_ ++ _)
if (set1.contains(n)) {
return false
}
a = a :+ n
}
true
}

def f(n: Int): Int = {
if (n < 3) {
return 1
}

var x = Set("L", "F")
for (i <- 3 until n) {
val newSet = Set[String]()
for (sequence <- x) {
var characters = Set('L', 'R', 'F') - sequence.last
characters += 'F'
for (character <- characters) {
newSet += sequence + character
}
}
x = newSet
}

var y = x.clone()
for (sequence <- x) {
if (y.contains(sequence)) {
val translatedSequence = sequence.replace("L", "#").replace("R", "L").replace("#", "R") //exchange 'L' and 'R' in sequence
val set1 = Set(sequence.reverse, translatedSequence, translatedSequence.reverse)
val set2 = Set(sequence)
val setDifference = set1.diff(set2)
y --= setDifference
}
}

y.count(checkSequence)
}

def main(args: Array[String]): Unit = {
val t1 = System.nanoTime()
for (i <- 1 to 15) {
val t2 = System.nanoTime()
val result = f(i)
val t3 = System.nanoTime()
println(i + " " + result + " " + (t3 - t2) + "ns")
}
val t4 = System.nanoTime()
val elapsedMs = (t4 - t1) / 1000000.0
println("Total time: " + elapsedMs + "ms")
}
}


* Rather long in bytes, but computes solutions up to and including $$\n=15\$$ around 15 seconds on TIO.

• Great answer, but all answers to code-golf challenges must show at least some golfing effort. An easy way to achieve it is to remove all unnecessary spaces and newlines, and use shorter variable names. (You can still keep the ungolfed version in the answer; just be sure to put the golfed one at the top.) Commented Apr 7, 2023 at 3:52