13
\$\begingroup\$

Inspired by certain puzzles on Flow Free: Warps.

Background

We all know that L-triominos can't tile the 3x3 board, and P-pentominos can't tile the 5x5 board. But the situation changes if we allow the board to wrap around in both dimensions:

L-triominos can tile 3x3 toroidal grid

The 3rd tile wraps around through all four edges.

┌ ┌─┐ ┐
  │ │3 
┌─┤ └─┐
│ │2  │
│ └─┬─┘
│1  │  
└───┘ ┘

P-pentominos can tile the 5x5 toroidal grid

The 5th tile wraps around through all four edges.

┌ ┌───┬─┐ ┐
  │   │ │
┌─┘   │ └─┐
│  1  │2  │
├─────┤   │
│  3  │   │
│   ┌─┴─┬─┤
│   │   │ │
└─┬─┘   │ ╵
  │  4  │5
└ └─────┘ ┘

Note that, in both cases, wrapping around in only one dimension doesn't allow such tiling.

In case the Unicode version is hard to read, here is the ASCII version:

3 2 3
1 2 2
1 1 3

5 1 1 2 5
1 1 1 2 2
3 3 3 2 2
3 3 4 4 5
5 4 4 4 5

Challenge

Given a polyomino and the size (width and height) of the toroidal grid, determine if the polyomino can tile the toroidal grid. The polyomino can be flipped and/or rotated.

A polyomino can be given in a variety of ways:

  • A list of coordinates representing each cell of polyomino
  • A 2D grid with on/off values of your choice (in this case, you cannot assume that the size of the grid defining the polyomino matches that of the toroidal grid)

The output (true or false) can be given using the truthy/falsy values in your language of choice, or two distinct values to indicate true/false respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

The polyomino is given as the collection of # symbols.

Truthy

# (singleton, a.k.a. monomino)
5x7 (or any size)
--------
## (domino)
4x3 (or any even size)
--------
#
## (L-triomino)
3x3 (as shown above)
--------
##
### (P-pentomino)
5x5 (as shown above)
--------
##
 ## (Z-tetromino)
4x4 (left as an exercise to the reader)
--------
###
#
# (V-pentomino)
5x5
--------
####
   #
   ### (a polyomino larger than the grid is possible)
4x4
--------
###
  ###
    ### (single polyomino can cover the entire grid, and can wrap multiple times)
3x3

Falsy

## (domino)
3x5 (or any odd sizes)
--------
###
#
1x8
--------
# #
### (U-pentomino)
5x5
\$\endgroup\$
  • \$\begingroup\$ Nice challenge. I find the ASCII art hard to read, could you add the alternative of having 1, 2, 3, etc as each of the # shapes given in the two corresponding examples? \$\endgroup\$ – Jonathan Allan Jun 18 at 11:54
  • \$\begingroup\$ @JonathanAllan I added a pure ASCII version of the top two examples, though I doubt I understood your request correctly. (Or do you want something like this?) \$\endgroup\$ – Bubbler Jun 19 at 2:09
  • \$\begingroup\$ what you posted is perfect, thanks \$\endgroup\$ – Jonathan Allan Jun 19 at 11:54
8
\$\begingroup\$

Python 2, 300 265 163 bytes

-35 bytes after suggestions from @xnor, @ovs, and largely @user202729 (removing evenly divisible check allowed for a one-liner + lambda)

-102 bytes following encouragement + general suggestions by @user202729

lambda l,w,h:all(w*h-len({((e-(p&4)*e//2)*1j**p+p/8+p/8/w*1j)%w%(1j*h)for e in l for p in c})for c in combinations(range(8*w*h),w*h/len(l)))
from itertools import*

Takes input as a list of complex coordinates of each cell of the polyomino. Outputs False for Truthy and True for Falsey (quirky de Morgan optimization).

Try it online with many testcases. Since this brute-forces, I have commented out a few cases to run fast enough for TIO.

Thoroughly commented:

lambda l,w,h:
    all(                        # we want any configuration to work, but De Morgan gives any(L==len) <==> not all(L!=len) <==> not all(L-len)
        w*h-len(                      # if two polyominos in a configuration overlap, then there are duplicate cells
                                    #   so the length of the set is less
                {                   # create a set consisting of each possible position+orientation of L/len(l) polyominos:
                    (                   # here, e is a single cell of the given polyomino
                        (               # reflect e across the imaginary axis if p >= 4 (mod 8)
                            e-          # e-e.real*2 = e-e//.5 reflects across the Im axis
                            p&4             # Only reflect if the 2^2 bit is nonzero: gives 4* or 0* following
                            *e//2           # floor(z) = z.real when z is complex, so
                        )                   # e//2 (floor division) gives z.real/2 (complex floor division only works in Python 2)
                        *1j**p          # rotate depending on the 2^0 and 2^1 bits. i**x is cyclic every 4
                        +p/8              # translate horizontally (real component) by p>>3 (mod this later)
                        +p/8/w*1j           # translate vertically (im component) by p>>3 / w
                    )%w%(1j*h)          # mod to within grid (complex mods only work in Python 2)
                    for e in l      # find where each cell e of the given polyomino goes
                    for p in c      # do this for each c (each set of position+orientation integers)
                }
        )
        for c in combinations(           # iterate c over all sets of w*h/len(l) distinct integers from 0 to 8*L-1
            range(8*w*h)              # each of these 8*L integers corresponds to a single position/orientation of a polyomino
                                    # Bits 2^0 and 2^1 give the rotation, and 2^2 gives the reflection
                                    # The higher bits give the position from 0 to L=w*h-1  ==> (0,0) to (w-1,h-1)
            ,w*h/len(l)        # w*h/len(l) is the number of polyominos needed since len(l) is the number of cells per polyomino
                                    # can't switch to *[range(8*w*h)]*(w*h/len(l)) because Python 3 does not allow short complex operations as above
        )
    )
from itertools import*

A new 169-byte solution that replaces combinations with recursion:

g=lambda l,w,h,k=[]:all(g(l,w,h,k+[((e-(p&4)*e//2)*1j**p+p/8+p/8/w*1j)%w%(1j*h)for e in l])for p in range(8*w*h))if w*h>len(k)else len(set(k))-w*h
from itertools import*

This has the advantage of removing combinations (12 characters on its own) and one for loop, but the self-invocation takes many bytes. Currying would not save length.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Because of the weird way Python handles complex mod, you can actually do e%w%(1j*h) in place of (e.real%w,e.imag%h). \$\endgroup\$ – xnor Jun 18 at 9:09
  • \$\begingroup\$ k-k.imag*2jfor ... is 2 bytes shorter than k.conjugate()for .... (Or 2*k.real-k for ... at the same length) \$\endgroup\$ – ovs Jun 18 at 10:37
  • \$\begingroup\$ @user202729 Thanks for all the suggestions! I ended up being able to reduce many nested comprehensions (the sum(p,[])'s sole purpose was to undo a nest, and range(8*L) combines 3 loops), so string-replace-exec became unnecessary. I'm not sure what your last comment does because it reflects the translation, not the whole polyomino, but I think it's irrelevant now. \$\endgroup\$ – fireflame241 Jun 19 at 20:57
  • \$\begingroup\$ @user202729 Oh, I reasoned out that /8j would work because it's just a vertical shift in the opposite direction, but complex divisor also changes it to normal division instead of floor division. It would be great if there was a way to distribute out the p/8 somehow \$\endgroup\$ – fireflame241 Jun 20 at 8:08
  • \$\begingroup\$ Fixed (same number of bytes after using combinations) \$\endgroup\$ – fireflame241 Jun 20 at 8:22
6
\$\begingroup\$

JavaScript (ES7), 233 bytes

Takes input as (w)(h)(p), where \$p\$ is a binary matrix describing the polyomino. Returns \$0\$ or \$1\$.

Similar to my original answer, but uses a more complex expression to update the cells of the matrix instead of explicitly rotating the polyomino.

w=>h=>g=(p,m=Array(w*h).fill(o=1))=>+m.join``?(R=i=>i--?m.map((F,X)=>(F=k=>p.map((r,y)=>r.map((v,x)=>k|=v?m[Z=i&2?p[0].length+~x:x,~~(X/w+(i&1?Z:W))%h*w+(X+(i&1?W:Z))%w]^=1:0,W=i&4?p.length+~y:y))&&k)(F()||g(p,m)))|!o||R(i):0)(8):o=0

Try it online!


JavaScript (ES7),  311 ... 252  250 bytes

Takes input as (w)(h)(p), where \$p\$ is a binary matrix describing the polyomino. Returns a Boolean value.

Not quite as desperately long as I was expecting. :p

w=>h=>g=(p,m=Array(w*h).fill(o=1),P)=>+m.join``?[...13**7+''].some(i=>(p.sort(_=>i-7).map((r,y)=>r.map((v,x)=>(P[x]=P[x]||[])[y]=v),P=[]),m.map((F,X)=>(F=k=>P.map((r,y)=>r.map((v,x)=>k|=v?m[~~(X/w+y)%h*w+(X+x)%w]^=1:0))&&k)(F()||g(p,m))),p=P,!o)):o=0

Try it online!

How?

The following code builds all possible transformations \$P\$ of the polyomino \$p\$:

[...13 ** 7 + '']         // this expands to ['6','2','7','4','8','5','1','7']
.some(i =>                // for each value i in the above list:
  ( p.sort(_ => i - 7)    //   reverse the rows of p[], except when i = '8'
    .map((r, y) =>        //   for each row r[] at position y in m[]:
      r.map((v, x) =>     //     for each value v at position x in r[]:
        ( P[x] =          //       transpose p[y][x]
          P[x] || [] )    //              to P[x][y]
        [y] = v           //
      ),                  //     end of inner map()
      P = []              //     start with an empty array
    )                     //   end of outer map()
    (...)                 //   more fun things happen here!
    p = P,                //   get ready for the next transformation
    !o                    //   success if o is cleared
  )                       //
)                         // end of some()

We use a flat array of \$w\times h\$ entries to describe the matrix. All of them are initially set to \$1\$.

The function \$F\$ inserts the polyomino in the matrix at the position \$(X,Y)\$ by XOR'ing the cells. It returns \$0\$ if the operation was done without setting any cell back to \$1\$.

F = k =>                  // expects k undefined for the first call
  P.map((r, y) =>         // for each row r[] at position y in P[]:
    r.map((v, x) =>       //   for each value v at position x in r[]:
      k |=                //     update k:
        v ?               //       if v is set:
          m[~~(X / w + y) //         toggle the value at (X + x, Y + Y),
            % h * w +     //         taking the wrapping around into account
            (X + x) % w   //
          ] ^= 1          //         k is set if the result is not 0
        :                 //       else:
          0               //         leave k unchanged
    )                     //   end of inner map()
  ) && k                  // end of outer map(); return k

For each position \$(X,Y)\$ in the matrix:

  • We do a first call to \$F\$. If successful, it is followed by a recursive call to the main function \$g\$.

  • We just need to call \$F\$ a second time to remove the polyomino -- or to clear the mess if it was inserted at an invalid position.

Hence the code:

F(F() || g(p, m))

The recursion stops when there's no more \$1\$'s in the matrix (success) or there's no more valid position for the polyomino (failure).

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

Charcoal, 120 115 bytes

NθNηWS⊞υ⌕Aι#≔⟦⟧ζFθFηF²«≔EθEη⁰εFLυF§υμ¿λ§≔§ε⁺κν﹪⁺ιμη¹§≔§ε⁺ιμ﹪⁺κνη¹F²F²⊞ζ↨⭆⎇μ⮌εε⪫⎇ν⮌ξξω²»≔…ζ¹υFυFζF¬&ικ⊞υ|ικ⁼⊟υ⊖X²×θη

Try it online! Link is to verbose version of code. Takes inputs in the order width, height, newline-terminated polyomino and outputs a Charcoal boolean i.e. - only if the polyomino tiles the torus. Explanation:

NθNη

Input the size of the grid.

WS⊞υ⌕Aι#

Input the polyomino and convert it to a list of horizontal indices.

≔⟦⟧ζ

Start building up a list of polyomino placements.

FθFηF²«

Loop through each vertical and horizontal offset and direction.

≔EθEη⁰ε

Start with an empty grid.

FLυF§υμ

Loop over each cell of the polyomino...

¿λ§≔§ε⁺κν﹪⁺ιμη¹§≔§ε⁺ιμ﹪⁺κνη¹

... place the optionally transposed cell in the grid, but offset by the outer indices.

F²F²⊞ζ↨⭆⎇μ⮌εε⪫⎇ν⮌ξξω²

For each of four reflections of the grid, push the grid to the list of placements, represented as a base 2 integer (e.g. a grid with just the bottom right square filled would be 1 etc.)

»≔…ζ¹υFυ

Start a breadth first search using the first placement.

Fζ

Loop over each placement.

F¬&ικ

If this placement does not overlap the grid so far...

⊞υ|ικ

... then push the merged grid to the list of grids.

⁼⊟υ⊖X²×θη

Check whether we pushed a completed grid. (This must be the last entry because any incomplete grid must by definition have fewer polyominoes and would therefore have been discovered earlier.)

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