Counting polystrips

Question

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 code-golf, 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!

Answer 1

Python 3, 480 433 406 364 309 299 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!

Ungolfed solution with comments:

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}
    # remove duplicates (mirror, head-to-tail, mirror of head-to-tail) but retain self
    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.

Answer 2

APL (Dyalog Unicode), ⁷⁰ 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)

Answer 3

Scala, 2277 1710 bytes*:

Modified from @Bubbler's answer.

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.