15
\$\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\$
  • \$\begingroup\$ oeis.org/A000988 \$\endgroup\$ – Jonathan Allan Feb 19 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 Feb 19 at 20:33
  • \$\begingroup\$ Related, related. \$\endgroup\$ – Grimmy Feb 19 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 Feb 20 at 7:24
  • 1
    \$\begingroup\$ What is a "one sided" polyomino? \$\endgroup\$ – RGS Feb 20 at 10:08
8
\$\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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ How did you code this in such a short amount of time..?? \$\endgroup\$ – RGS Feb 20 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\$ – Kevin Cruijssen Feb 20 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 Feb 20 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\$ – Jonathan Allan Feb 20 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\$ – Jonathan Allan Feb 20 at 15:43
5
\$\begingroup\$

JavaScript (Node.js),  269 ... 250  243 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((_,y)=>m.map((v,x)=>a|=b|=(v>>y&1)<<w+~x,b=0)|b,a=0)).flatMap(v=>v/(a&-a)||[])])?0:o[M]=++c

Try it online! (\$n=1\$ to \$n=7\$)

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((_, y) =>  //       for 0 <= y < w:
        m.map((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 = 0            //           start with b = 0
        ) | b,             //         end of inner map(); yield b
        a = 0              //         start with a = 0
      )                    //       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
|improve this answer|||||
\$\endgroup\$
  • 4
    \$\begingroup\$ a(6) in 3-4s is "rather slow" - mine takes ~ half an hour :p \$\endgroup\$ – Jonathan Allan Feb 20 at 0:04
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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I don't know Ruby, but love the method! \$\endgroup\$ – Jonathan Allan Feb 20 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!

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

R, 180 bytes

f=function(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,union(u<-u[-1],setdiff(j+-1:1i:1:-1i,v<-j:v))),2^(-any(?p-~-p)-any(?p-~p*1i))/n);F}

Try it 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.

|improve this answer|||||
\$\endgroup\$

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.