16
\$\begingroup\$

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.

Heptastrips

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Relevant OEIS. (But doesn't exclude holes.) \$\endgroup\$ – Martin Ender Feb 17 '18 at 8:30
  • \$\begingroup\$ @ Martin Ender Thank you, I didn't know it. \$\endgroup\$ – Galen Ivanov Feb 17 '18 at 8:42
  • 2
    \$\begingroup\$ 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) ? \$\endgroup\$ – Ton Hospel Feb 17 '18 at 10:59
  • \$\begingroup\$ @Ton Hospel Yes, exactly - this is the only heptastrip piece with a hole. \$\endgroup\$ – Galen Ivanov Feb 17 '18 at 11:50
11
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to PPCG! Definitely an impressive way to start your PPCG career. :) \$\endgroup\$ – Martin Ender Feb 21 '18 at 8:53
  • 3
    \$\begingroup\$ Welcome to PPCG and thanks for this solution! I had already given up expecting to see a solution :) \$\endgroup\$ – Galen Ivanov Feb 21 '18 at 8:56
  • 3
    \$\begingroup\$ 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? :) \$\endgroup\$ – Erik the Outgolfer Feb 24 '18 at 20:30
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Bubbler Feb 25 '18 at 7:14
  • 1
    \$\begingroup\$ Possible 303 bytes. \$\endgroup\$ – Jonathan Frech Feb 26 '18 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.