12
\$\begingroup\$

As some of you may remember, Peter, who was a picky eater is now puzzled Peter.

This time Peter got some puzzles as a present from his Aunt. He has tried a lot, but has failed to solve the puzzles. Peter needs your help to solve them.

Each one of the puzzle has 2 pieces. To solve the puzzle, you must tell the number of ways piece 1 can fit into the empty spaces in Piece 2. We can safely assume that both the pieces cannot be rotated.

For example,

Piece 1:
.#
##
.#

Piece 2: 

#..#######
#.##..####
###..##...
####.#####
##.#######
##......##
##.....###
########..

There is only 1 possible way to fit Piece one into Piece 2:

#..#######
#.##*.####
###**##...
####*#####
##.#######
##......##
##.....###
########..

Hence, the output must be \$1\$.

Input

You may take the input as a binary matrix of 1's and 0's, or as a string with empty spaces and filled spaces as characters of your choice.

Piece 1 is not always a solid piece, it may or may not be connected.

Output

An integer \$n\$ for the number of ways to fit Piece 1 in Piece 2. If there are no ways, you may return \$0\$ or any other non-integer value.

Test Cases

All inputs formatted as a 2d array, with each inner array representing a row in the puzzle. 0 represents empty gap, 1 represents filled space.

Piece 1: [[0, 1], [1, 1], [0, 1]]
Piece 2: [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0, 0]]
Output: 1

Piece 1: [[1, 0], [1, 1], [0, 1]]
Piece 2: [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 0, 1, 1, 0, 0]]
Output: 1

Piece 1: [[1, 1]]
Piece 2: [[0, 1, 0, 1], [1, 1, 0, 0], [0, 0, 0, 0], [1, 1, 0, 1]]
Output: 4

Piece 1: [[1, 1, 1]]
Piece 2: [[0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0]]
Output: 4

Piece 1: [[0, 1, 1, 0, 1, 1, 0], [1, 0, 0, 1, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0]]
Piece 2: [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
Output: 1

Piece 1: [[1, 0, 0], [1, 1, 1]]
Piece 2: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Output: 42

Piece 1: [[1, 0, 1], [1, 1, 1]]
Piece 2: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Output: 35

Piece 1: [[0, 0, 1], [1, 0, 0], [0, 1, 0]]
Piece 2: [[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1]]
Output: 1

Piece 1: [[1]]
Piece 2: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Output: 0 (Or any other non-integer value)

Winning criteria

this is so shortest answer, in each language wins.

\$\endgroup\$
6
  • 5
    \$\begingroup\$ @Shaggy We can safely assume that both the pieces cannot be rotated. \$\endgroup\$
    – user100690
    Commented Jun 28, 2021 at 13:01
  • \$\begingroup\$ May I throw an exception for last testcases? \$\endgroup\$
    – tsh
    Commented Jun 29, 2021 at 2:17
  • 1
    \$\begingroup\$ May first piece contain extra padding? ("...\n.#.\n..." for example) May I assume the second piece is always larger (both width and height) than the first one? \$\endgroup\$
    – tsh
    Commented Jun 29, 2021 at 2:40
  • 1
    \$\begingroup\$ Suggest a test case where the number of fits of the piece and its 180degree rotation are not the same, such as [[1, 1], [1, 0]], [[0, 0], [0, 1]] \$\endgroup\$
    – att
    Commented Jun 29, 2021 at 6:30
  • 1
    \$\begingroup\$ Is Peter's Aunt named May, by any chance? \$\endgroup\$
    – DLosc
    Commented Jun 30, 2021 at 0:32

11 Answers 11

9
\$\begingroup\$

MATL, 11 bytes

Thanks to @att for pointing out a mistake, now corrected.

,XP!]&2Y+~z

Inputs piece 1, then piece 2 as binary matrices.

Try it online! Or verify all test cases.

Explanation

Convolution is the key to success

This computes the 2D-convolution of piece 2 and a vertically and horizontally flipped version of piece 1, keeping only the results that assume no zero padding of piece 2. What the convolution does is:

  • Piece 1 is flipped vertically and horizontally, which undoes the previous flipping of this piece; then
  • it is shifted in the two dimensions, traversing all positions so that it doesn't move "outside" of piece 2. For each position,
  • corresponding entries of both pieces are multiplied, and
  • the sum of all those products is computed.

Piece 1 fits in a given position if and only if the sum computed as above is 0, meaning that all 1 entries of piece 1 coincide with a 0 of piece 2.

,      % Do twice
  XP   %   Implicitly inputs piece 1 the first time. Flip vertically
  !    %   Transpose
]      % End
&2Y+   % Implicitly inputs piece 2. 2D convolution, only 'valid' part
~z     % Number of zeros. Implicitly displays the result
\$\endgroup\$
4
  • \$\begingroup\$ phew thats small, can you explain how does it work? \$\endgroup\$
    – user100752
    Commented Jun 28, 2021 at 15:09
  • 1
    \$\begingroup\$ @EliteDaMyth Done! \$\endgroup\$
    – Luis Mendo
    Commented Jun 28, 2021 at 15:17
  • \$\begingroup\$ Fails for e.g. [1, 1; 1, 0], [0, 0; 0, 1] \$\endgroup\$
    – att
    Commented Jun 29, 2021 at 6:27
  • \$\begingroup\$ @att Thank you! I forgot that convolution flips one input. Corrected now \$\endgroup\$
    – Luis Mendo
    Commented Jun 29, 2021 at 8:41
5
\$\begingroup\$

J, 23 bytes

4 :'+/,x(-:y<]);._3~$y'

Try it online!

(Tacit for 24b: [:+/@,](]-:<)"2([;._3~$))

For each tile u;._3~ of the size of the piece $y, is no position blocked? (Tile still equal to itself -: when comparing each position from the piece with the tile y<]?) Sum the result +/,.

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Unicode), 24 bytes

Anonymous infix lambda taking Piece 1 as left argument Boolean matrix of needed positions, and Piece 2 as right argument Boolean matrix of available positions. Requires 0-based indexing (⎕IO←0).

{≢⍸∧/⍵[(⍳1+⍵-⍥⍴⍺)∘.+⍸⍺]}

Try it online! (using a polyfill for since TIO is stuck on version 17.1)

{} "dfn"; left and right arguments are and :

⍵[] index into to get the elements at the following positions:

  ⍸⍺ list of true-coordinates in

  ()∘.+ outer sum (i.e. all addition combinations with):

   ⍵-⍥⍴⍺ the difference in shapes between Piece 2 and Piece 1

   1+ increment

    all indices of an array of that size

∧/ AND-reduction along the trailing axis (computes where all required slots are available)

 indices of available placements

 tally those


I'm a bot, so my owner posted this for me.

\$\endgroup\$
1
  • \$\begingroup\$ APLcart has become sentient. we are doomed \$\endgroup\$
    – Razetime
    Commented Jun 29, 2021 at 6:48
3
\$\begingroup\$

JavaScript (ES6), 95 bytes

Expects two binary matrices as (a)(b).

a=>b=>b.map((r,y)=>r.map((_,x)=>t+=!a.some((r,Y)=>r.some((v,X)=>v&(b[y+Y]||0)[x+X]!=0))),t=0)|t

Try it online!

Or 92 bytes with optional chaining (doesn't work on TIO).

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

Python 3, 85 109 bytes

from numpy import*
from scipy.signal import*
lambda a,b:sum(correlate(a,b,'valid')<1)

correlate needs scipy.signal for 2d arrays and will give back 0 for matching positions, using numpy.count_nonzero with the condition will give back the number of zeroes which is the expected result.

Edit1: changed count_nonzero to sum, removed array conversions

Try it online!

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Great approach :-D You can shorten count_nonzero to sum; and I think correlate to convolve \$\endgroup\$
    – Luis Mendo
    Commented Jun 28, 2021 at 15:23
  • 3
    \$\begingroup\$ Also, no need to convert to array, or to import Numpy tio.run/… \$\endgroup\$
    – Luis Mendo
    Commented Jun 28, 2021 at 15:26
  • \$\begingroup\$ I forgot that convolution flips one of the inputs horizontally and vertically (see @att's comment in my answer). Sorry about that. You may need to go back to correlate \$\endgroup\$
    – Luis Mendo
    Commented Jun 29, 2021 at 8:42
  • \$\begingroup\$ @LuisMendo well it does have the same result for counting the zeroes, is it really not working the same in this case? \$\endgroup\$ Commented Jun 29, 2021 at 9:21
  • 1
    \$\begingroup\$ No, because convolution flips (reverses) one of the inputs. For exampe this should give 1 (it does with correlate) \$\endgroup\$
    – Luis Mendo
    Commented Jun 29, 2021 at 9:33
3
\$\begingroup\$

Jelly, 19 bytes

ṡ€ZL$}¹ṡL}Z€Ẏa€¬Ȧ€S

Try it online!

-1 byte thanks to Nick Kennedy

ṡ€ZL$}¹ṡL}Z€Ẏa€¬Ȧ€S    Main Link; accept piece 2 on the left and piece 1 on the right
ṡ€                     Get all overlapping slices of piece 2 of length
  ZL$}                 Width of piece 1
      ¹                (Identity)
       ṡ               Slice this into overlapping pieces of length
        L}             Height of piece 1
          Z€           Transform each to get it to the correct orientation
            Ẏ          Flatten once; we now have a list of 2D blocks in piece 2
             a€        Logical AND with piece 1 (vectorizing); gives intersection areas
               ¬       Logical NOT (vectorize)
                Ȧ€     For each chunk, check if all are truthy (i.e. none were truthy initially; 1 if it fits, 0 otherwise)
                  S    Sum; count number of positions that fit
\$\endgroup\$
1
2
\$\begingroup\$

Python 3, 138 bytes

lambda a,b,l=len:sum(all(q&p^1for Q,P in zip(a,b[i:])for q,p in zip(Q,P[j:]))for i in range(l(b)-l(a)+1)for j in range(l(b[0])-l(a[0])+1))

Try it online!

Ungolfed :

def f(a,b):
  s=0 # intitialise the counter
  for i in range(len(b)-len(a)+1): # iterate through all the lines
    for j in range(len(b[0])-len(a[0])+1): # iterate through all the column
      # verify if the piece can fit
      if all(a[k][l]&b[i+k][j+l]^1 for k in range(len(a))for l in range(len(a[0]))):
        s+=1 # increase the counter
  return s  # return the counter

Try it online!

  • q&p^1 will be equal to 1 only if at most 1 of q and p is equal to 1
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 165 bytes

(a,b,d=b[z=0][L='length'],F=a.flat())=>b.flat().map((e,i)=>z+=b.slice(i/d,i/d+a[L]).flatMap((l,c)=>l.slice(i%d,i%d+a[0][L])).every((l,c,A)=>A[L]==F[L]&&!l|F[c]<l))|z

Try it online!

This feels too long.

Calculate the number of items in flattened b (second piece) that satisfy the conditions: the a-sized tile with that item as the top-left corner is equal to a and fits in b.

Credits: @EliteDaMyth (see comments)

\$\endgroup\$
2
  • \$\begingroup\$ putting z=0 in d=b[z=0][L], saves 2 bytes \$\endgroup\$
    – user100752
    Commented Jun 28, 2021 at 15:32
  • \$\begingroup\$ similarly, putting L='length' in d=b[z=0][L='length'] saves 2 more bytes \$\endgroup\$
    – user100752
    Commented Jun 28, 2021 at 15:36
0
\$\begingroup\$

Charcoal, 46 bytes

≔⟦⟧ηWS⊞ηιWS⊞υ⁺ι⭆θ#Fη⊞υ#IΣ⭆υ⭆ι⬤η⬤ν№⁺π§§υ⁺κξ⁺μρ.

Try it online! Link is to verbose version of code. Takes input as two newline-terminated lists of strings of . and any other character. Explanation:

≔⟦⟧ηWS⊞ηι

Input piece 1.

WS⊞υ⁺ι⭆θ#Fη⊞υ#

Input piece 2, but pad it so that piece 1 can't accidentally wrap around (this is slightly golfier than calculating the positions that won't wrap around).

IΣ⭆υ⭆ι⬤η⬤ν№⁺π§§υ⁺κξ⁺μρ.

Count the number of possible positions of piece 1 in piece 2 where for all of the overlapping squares at least one of them is a ..

\$\endgroup\$
0
\$\begingroup\$

JavaScript, 108 bytes

a=>b=>[...b.matchAll(`(?=${a.replace(/./sg,c=>[`[
21]{${b.search`
`-a.search`
`+1}}`,'.',1][+c])})`)].length

f = 

a=>b=>[...b.matchAll(`(?=${a.replace(/./sg,c=>[`[
21]{${b.search`
`-a.search`
`+1}}`,'.',1][+c])})`)].length

testcases = `
Piece 1: [[0, 1], [1, 1], [0, 1]]
Piece 2: [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0, 0]]
Output: 1

Piece 1: [[1, 0], [1, 1], [0, 1]]
Piece 2: [[1, 0, 0, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 0, 1, 1, 0, 0]]
Output: 1

Piece 1: [[1, 1]]
Piece 2: [[0, 1, 0, 1], [1, 1, 0, 0], [0, 0, 0, 0], [1, 1, 0, 1]]
Output: 4

Piece 1: [[1, 1, 1]]
Piece 2: [[0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 0, 0]]
Output: 4

Piece 1: [[0, 1, 1, 0, 1, 1, 0], [1, 0, 0, 1, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0]]
Piece 2: [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
Output: 1

Piece 1: [[1, 0, 0], [1, 1, 1]]
Piece 2: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Output: 42

Piece 1: [[1, 0, 1], [1, 1, 1]]
Piece 2: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
Output: 35

Piece 1: [[0, 0, 1], [1, 0, 0], [0, 1, 0]]
Piece 2: [[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0], [1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1]]
Output: 1

Piece 1: [[1]]
Piece 2: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Output: 0 (Or any other non-integer value)
`.trim().split('\n\n').map(t => t.split('\n').map(l => JSON.parse(l.replace(/^.*:|\(.*$/g, '')))).map(([a, b, e]) => [a.map(l => l.map(n => '12'[n]).join('')).join('\n'), b.map(l => l.map(n => '12'[n]).join('')).join('\n'), e]);

testcases.forEach(([a, b, e]) => { console.log(f(a)(b) === e, f(a)(b)); });

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes

Count[ListCorrelate@##,0,2]&

Try it online!

\$\endgroup\$

Your Answer

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