19
\$\begingroup\$

Context

From Wikipedia: A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge.

one-sided polyominoes are distinct when none is a translation or rotation of another (pieces that cannot be flipped over). Translating or rotating a one-sided polyomino does not change its shape.

In other words, a one sided polyomino reflected across its x or y axis is not the same as the original polyomino, but a one sided polyomino that is rotated is still considered the same polyomino

Task

Given a number n, find how many different unique one sided polyominos can be created using n number of blocks

Input

Take integer n as input for the number of blocks that exist in the polyomino

Output

An integer of the amount of unique one sided polyominos that can be generated

Examples

in -> out

4 -> 7

5 -> 18

6 -> 60

7 -> 196

More test cases can be found on the Wikipedia page and OEIS

\$\endgroup\$
7
  • \$\begingroup\$ oeis.org/A000988 \$\endgroup\$ Commented Feb 19, 2020 at 20:29
  • \$\begingroup\$ @Anush what do you think I should change it to? This is my first question here so I'm still trying to figure this out. Edit: nvm misspelling, I'll correct it \$\endgroup\$
    – Brzyrt
    Commented Feb 19, 2020 at 20:33
  • \$\begingroup\$ Related, related. \$\endgroup\$
    – Grimmy
    Commented Feb 19, 2020 at 21:02
  • 1
    \$\begingroup\$ It took me a while to figure out what one-sided means here (and I'm stilk not sure). Can you clarify in the challenge text? \$\endgroup\$
    – Luis Mendo
    Commented Feb 20, 2020 at 7:24
  • 1
    \$\begingroup\$ What is a "one sided" polyomino? \$\endgroup\$
    – RGS
    Commented Feb 20, 2020 at 10:08

7 Answers 7

9
\$\begingroup\$

Jelly,  39  37 bytes

Soon to be crushed by MATL and, quite possibly, APL

p`œc⁸ḣ1ạ§ỊẸʋƇ@;QɗƬƊṪṢƊƑƇŒṬZṚŒṪƲƬṂ$€QL

Try it online! (It's pretty slow - a(6) took ~30 minutes locally!)

To see them instead try this (L -> ŒṬ€G€j⁾¶¶).

How?

Builds all index lists, where each represents the locations of 1s on a grid of 1s and 0s, up to those for a square of side n, filters for those that have their 1s fully connected, then selects the "minimal" of each after any amount of rotation + vertical translation, and finally de-duplicates and yields the length.

   p`œc⁸ḣ1ạ§ỊẸʋƇ@;QɗƬƊṪṢƊƑƇŒṬZṚŒṪƲƬṂ$€QL - Link: integer, n
   A....B..................C............ - break down below
    
A: p`œc⁸ - Get all ways to have n 1s on an n*n grid as multidimensional indices
    `    - use n as both arguments of:
   p     -   Cartesian product -> all pairs of [1..n] - these are in sorted order
       ⁸ - chain's left argument, n
  œc     - combinations (no replacement) - ...and so each of these are in sorted order

B: ḣ1ạ§ỊẸʋƇ@;QɗƬƊṪṢƊƑƇ - Keep only the fully-connected ones (call input "All")
                     Ƈ - filter keep those for which:
                    Ƒ  -   is invariant under:
                   Ɗ   -     last three links as a monad:
                Ɗ      -       last three links as a monad:
    1                  -         one
   ḣ                   -         head to index - i.e. [firstPair] (initial "Current")
               Ƭ       -         collect up while distinct, applying:
              ɗ        -           last three links as a dyad - i.e. f(Current, All):
           @           -             with swapped arguments - i.e. f(All, Current):
          Ƈ            -               filter keep those (of All) for which:
         ʋ             -                 last four links as a dyad - i.e. f(All, Current):
     ạ                 -                   absolute difference (vectorises)
      §                -                   sum each
       Ị               -                   insignificant? (effectively "in (0,1)?")
        Ẹ              -                   any? - i.e. any are neighbours/same?
            ;          -             concatenate (the result with Current)
             Q         -             deduplicate (-> Current for the next Ƭ-loop)
                 Ṫ     -       tail
                  Ṣ    -       sort

C: ŒṬZṚŒṪƲƬṂ$€QL - Count the distinct results
             €   - for each:
            $    - last two links as a monad:
          Ƭ      -   collect up while distinct, applying:
         Ʋ       -     last four links as a monad:
   ŒṬ            -       2d array from multidimensional indices
     Z           -       transpose
      Ṛ          -       reverse (transpose + reverse = rotate 1/4 anti-clockwise)
       ŒṪ        -       truthy multidimensional indices
           Ṃ     -   minimum
              Q  - de-duplicate
               L - length
\$\endgroup\$
9
  • \$\begingroup\$ How did you code this in such a short amount of time..?? \$\endgroup\$
    – RGS
    Commented Feb 20, 2020 at 9:40
  • 1
    \$\begingroup\$ @RGS Because Jonathan is good with Jelly and golfing in general, and his answer was posted 3 hours after the challenge was posted, so plenty of time for him. I'm pretty sure writing his explanation above took most of the time. ;p \$\endgroup\$ Commented Feb 20, 2020 at 12:54
  • 1
    \$\begingroup\$ Well, you know a challenge is going to be a doozy when the Jelly answer is 39 bytes! \$\endgroup\$
    – 640KB
    Commented Feb 20, 2020 at 14:11
  • 1
    \$\begingroup\$ @RGS - the thinking & coding did actually take me more than an hour, maybe even two - I saw the question within 8 minutes of it being posted, posted a solution 2.5h later, and didn't immediately start writing the code-breakdown (see history "Forgive the lack of code-breakdown - I need a break!"). \$\endgroup\$ Commented Feb 20, 2020 at 14:14
  • 1
    \$\begingroup\$ @RGS I feel that the method employed is fairly well golfed while it's possible that there's a byte or two to find (I think I may have just spotted a save actually!). A change of method might find a more terse solution too. \$\endgroup\$ Commented Feb 20, 2020 at 15:43
5
\$\begingroup\$

JavaScript (Node.js),  269 ... 243  239 bytes

Rather slow for \$n\ge7\$, but it does find \$a(8)=704\$ in a bit more than 2 minutes on my laptop.

f=(n,m=[...o=Array(w=n)],i=c=0)=>n?m.map((r,y)=>m.map((_,x,[...m])=>!i|1<<x&~r&(m[y+1]|r/2|r*2)&&f(n-1,m,m[y]|=1<<x)))|c:[0,0,0,0].some(_=>o[M=(m=m.map(a=(_,y)=>m.map(b=(v,x)=>a|=b|=(v>>y&1)<<w+~x)|b)).flatMap(v=>v/(a&-a)||[])])?0:o[M]=++c

Try it online!

How?

Building the \$n\$-polyominos

We store the polyomino in an array \$m[\:]\$ of \$n\$ bitmasks and build all possible shapes recursively. At each iteration, a new cell adjacent to an existing cell is added.

m.map((r, y) =>            // for each bitmask r at position y:
  m.map((_, x, [...m]) =>  //   for each position x, using a copy of m[]:
    !i |                   //     always set this cell if this is the 1st iteration
    1 << x &               //     otherwise, the x-th bit
    ~r &                   //     must not be already set in the current row
    (                      //     and one of the following conditions must be met:
      m[y + 1] |           //       - the x-th bit is set in the next row
      r / 2 |              //       - the (x+1)-th bit is set in the current row
      r * 2                //       - the (x-1)-th bit is set in the current row
    ) &&                   //     if truthy:
      f(                   //       do a recursive call:
        n - 1,             //         decrement n
        m,                 //         pass the copy of m[]
        m[y] |= 1 << x     //         set the bit at (x, y)
      )                    //       end of recursive call
  )                        //   end of inner map()
)                          // end of outer map()

Applying the rotations and translations

When we have enough cells, we apply all 4 possible rotations to \$m[\:]\$, discard the empty rows and translate it horizontally so that it's 'right-justified'. We store the encountered shapes in the object \$o\$ and the number of distinct shapes in \$c\$.

[0, 0, 0, 0].some(_ =>     // repeat 4 times:
  o[                       //   we will ultimately test this entry in o
    M = (                  //     save the final matrix in M[]
                           //     1) rotate
      m = m.map(a =        //       starting with a zero'ish,
      (_, y) =>            //       for 0 <= y < w:
        m.map(b =          //         starting with b zero'ish,
        (v, x) =>          //         for each bitmask v at position x in m[]:
          a |=             //           update the global bitmask:
            b |=           //             update the row bitmask:
              (v >> y & 1) //               extract the y-th bit from v
              << w + ~x    //               and set the (w-x-1)-th bit in b accordingly
        ) | b              //         end of inner map(); yield b
      )                    //       end of outer map()
    )                      //     2) translate and crop
    .flatMap(v =>          //       for each bitmask v in m[]:
      v / (a & -a)         //         right-shift v by the position of the LSB of a
      || []                //         discard this row if it's empty
    )                      //       end of flatMap()
  ]                        //   end of lookup
) ?                        // if at least one shape was already encountered:
  0                        //   do nothing
:                          // else:
  o[M] = ++c               //   save the new shape in o and increment c
\$\endgroup\$
1
  • 5
    \$\begingroup\$ a(6) in 3-4s is "rather slow" - mine takes ~ half an hour :p \$\endgroup\$ Commented Feb 20, 2020 at 0:04
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 216 214 204 bytes

->n{*h=1,1i,-1,-1i;z=[[0i]];(r,*z=z;r.map{|c|h.map{|v|(r!=k=r|[c+v])&&(w=h.map{|y|(x=k.map{|v|v*y}).map{|g|g-x.map(&:real).min-1i*x.map(&:imag).min}.sort_by &:rect})-z==w&&z<<w[0]}})until z[0][-n];z.size}

Try it online!

5.5 seconds for n=8 on TIO.

Update: 41 seconds for n=9 on TIO

Harder Better Faster Shorter: 36 seconds for n=9 on TIO

Still golf-in-progress, the explanation refers to a previous version, the concept is still the same.

How (more or less):

->n{z=[[0+0i]]

This initializes the list of polyominos. Instead of a matrix, I will use a list of complex numbers (with integer real and imaginary part). The first entry is the monomino (0,0)

(r,*z=z;

The main loop: get a single n-omino from the list and build all possible (n+1)ominos from there:

4.times{|v|r.map{|c|

We need to iterate on all squares of r 4 times (add a new square on all sides)

(k=[*r,e=c+1i**v])==k|[]&&

First check: if we have duplicate squares, we can discard this piece. Otherwise, continue.

(w=4.times.map{|y|

Check all possible rotations

(x=k.map{|v|v*1i**y})

To rotate a piece 90 degrees, multiply all squares by i

.map{|g|g-x.map(&:real).min-1i*x.map(&:imag).min}

Then translate it so that it starts from (0,0).

.sort_by(&:rect)})-z==w&&

Sort the squares inside all 4 rotations, check if at least one is already contained in z

z<<w[0]}}) 

If not, add the first rotation to z

until z[0][-n]

Repeat until the first piece in the list has size n

;z.size}

The size of z is the final result.

\$\endgroup\$
1
  • \$\begingroup\$ I don't know Ruby, but love the method! \$\endgroup\$ Commented Feb 20, 2020 at 14:17
2
\$\begingroup\$

Wolfram Language (Mathematica), 632 bytes

Finds a(9)=2500 in 30 seconds

J=Length;Q=First;s@n_:=(p=m@{{0,0}};Do[p=S[Flatten[m@#&/@p,1]],n-2];If[n<3,1,J@p]);m@b_:=(A=B={};Do[(A=If[(X=MemberQ)[b,b[[i]]+#],A,(H=Append)[A,b[[i]]+#]])&/@{{0,1},{1,0},{-1,0},{0,-1}},{i,J@b}];A=Complement@A;Table[B=H[B,H[b,A[[j]]]],{j,J@A}];B);S@q_:=Module[{s,b,u,L,V,U,f},f={};Do[s=q[[j]];b=g[q[[j]]];u=Sort[(#-Q@b)&/@q[[j]]];{L,V,U}=v@u;f=If[Or@@(X[f,#]&/@{u,Sort[(#-Q@g@L)&/@L],Sort[(#-Q@g@V)&/@V],Sort[(#-Q@g@U)&/@U]}),f,H[f,u]],{j,J@q-1}];f];g@h_:=(o=(W=Select)[h,Last@#==(Min[Last@#&/@h])&];W[o,Q@#==(Min[Q@#1&/@o])&]);v@p_:=(x=y=z={};Do[x=H[x,{T=Last[p[[i]]],-(R=Q[p[[i]]])}];y=H[y,-{R,T}];z=H[z,{-T,R}],{i,J@p}];{x,y,z})

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 75 72 bytes

Should have been 1 byte less by replacing })}€ê with }){}, but the many nested maps/loops cause a bug in 05AB1E here (})ê} and })}€{ also doesn't work strangely enough..)

1ÝInãʒOQiyƶIô©Δ2Fø0δ.ø}2Fø€ü3}®Ā*εεÅsyøÅsM}}}˜Ùg<]εIô2Føʒà}}4FDíø})}€êÙg

Extremely slow brute-force, so is only able to output up to \$a(4)\$ on TIO.

Try it online or verify the first few results.

Explanation:

Step 1: Create all possible \$n^2\$-sized list using 0s and 1s, consisting of \$n\$ amount of 1s:

1Ý          # Push pair [0,1]
  In        # Push the squared input
    ã       # Cartesian power
ʒ           # Filter this list of lists by:
   i        #  If
 O          #  the sum of the current list
  Q         #  is equal to the (implicit) input-integer:
            #   Continue with the check in step 2 below
            #  (implicit else: implicitly use the implicit input for the filter;
            #   this is only truthy for edge case n=1, which fails step 2 due to the `ü3`)

Try just this first step online (without trailing i).

Step 2: Filter it further to only keep single polynominos, using a flood-fill approach:

 y          #   Push the current list again
  ƶ         #   Multiply each value by its 1-based index
   Iô       #   Convert the list to an input-by-input block
     ©      #   Store this block in variable `®` (without popping)
 Δ          #   Loop until the result no longer changes to flood-fill the matrix:
  2Fø0δ.ø}  #    Add a border of 0s around the matrix:
  2F     }  #     Loop 2 times:
    ø       #      Zip/transpose; swapping rows/columns
      δ     #      Map over each row:
     0 .ø   #       Add a leading/trailing 0
  2Fø€ü3}   #    Convert it into overlapping 3x3 blocks: 
  2F    }   #     Loop 2 times again:
    ø       #      Zip/transpose; swapping rows/columns
     €      #      Map over each inner list:
      ü3    #       Convert it to a list of overlapping triplets
  ®Ā        #    Push matrix `®` and convert all its positive values back to 1s
    *       #    Multiply each 3x3 block by this matrix of 0s/1s (so 0s will remain 0s)
  εεÅsyøÅsM #    Get the largest value from the horizontal/vertical cross of each 3x3 block:
  εε        #     Nested map over each 3x3 block:
    Ås      #       Pop and push its middle row
      y     #       Push the 3x3 block again
       ø    #       Zip/transpose; swapping rows/columns
        Ås  #       Pop and push its middle rows as well (the middle column)
          M #       Push the flattened maximum of the entire (scoped) stack,
            #       which is the flattened maximum of the cross of the current 3x3 block
  }}        #     Close the nested map
 }˜         #   After the flood-fill loop: flatten the block to a list
   Ù        #   Uniquify its values
    g       #   Pop and push its length
     <      #   Decrease it by 1 to account for the 0s
            #   (only 1 is truthy in 05AB1E, so only single islands remain)
]           # Close both the if-statement and filter

Try just the first two steps online.

Step 3: Convert each valid lists to matrices, and slash of any rows/columns of 0s to have the actual polynominos:

ε           # Map over each inner list
 Iô         #  Convert it to an n-by-n block
   2F       #  Inner loop 2 times:
     ø      #   Zip/transpose; swapping rows/columns
      ʒ     #   Filter this list of rows by:
       à    #    Get the maximum of the row (so if it only contains 0s, it'll be removed)
      }     #   Close the filter
    }       #  Close the inner loop

Try just the first three steps online.

Step 4: Remove all duplicated rotations, by converting each polynomino to a quartet of its four sorted rotations, and then uniquify that list of quartets.

 4F         #  Inner loop 4 times:
   D        #   Duplicate the current polynomino-matrix
    íø      #   Rotate it 90 degrees counterclockwise:
    í       #    Reverse each inner row
     ø      #    Zip/transpose the matrix; swapping rows/columns
  })        #  After the loop: wrap the four rotations on the stack into a list

            # Explanation if the 05AB1E bug mentioned at the top wasn't present:
    {       #  Sort the quartet of rotations
}Ù          # After the map: uniquify the list of polynomino-rotations

            # Actual explanation with bug:
}€          # After the map: open a new map:
  ê         #  Sort and uniquify each quartet
   Ù        # After the map: uniquify the list of distinct polynomino-orientations

Try just the first four steps online.

Step 5: Get the amount of unique polynominos left, and output it as result:

g           # Pop and push the length
            # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Python, 396 319 bytes

saved 77 bytes thanks to @Deadcode

Modified from @Kirill L.'s answer.

The golfed version, Try it online!

import numpy as np
def f(n,o=[],v=[0],u=[0]):
    F=0
    for j in u:
        p=sorted(o+[j])
        if len(p)<n:u=u[1:];v=[j]+v;F+=f(n,p,v,list(set(u).union(set(np.array(j)+np.array([-1,1j,1,-1j]))-set(v))))
        else:F+=(2**(-any(np.diff(np.array(p)-np.sort(-np.array(p))))-any(np.diff(np.array(p)-np.sort(np.array(p)*1j))))/n)
    return F

The ungolfed version:

import numpy as np

def f(n, o=None, v=None, u=None):
    if o is None:
        o = []
    if v is None:
        v = [0]
    if u is None:
        u = [0]
    F = 0
    for j in u:
        p = sorted(o + [j])
        if len(p) < n:
            u = u[1:]
            v = [j] + v
            F += f(
                n,
                p,
                v,
                list(set(u).union(set(np.array(j) + np.array([-1, 1j, 1, -1j])) - set(v)))
            )
        else:
            var1 = any(np.diff(np.array(p) - np.sort(-np.array(p))))
            var2 = any(np.diff(np.array(p) - np.sort(np.array(p) * 1j)))
            F += (2 ** (-var1 - var2) / n)
    return F


expected = []
for n in range(1, 10):
    expected.append(round(f(n)))
print(expected)
\$\endgroup\$
1
  • \$\begingroup\$ Golfing the whitespace makes it 319 bytes: Try it online! \$\endgroup\$
    – Deadcode
    Commented Apr 8, 2023 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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