# Peter is Puzzled!

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.

• @Shaggy We can safely assume that both the pieces cannot be rotated.
– user100690
Commented Jun 28, 2021 at 13:01
• May I throw an exception for last testcases?
– tsh
Commented Jun 29, 2021 at 2:17
• 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?
– tsh
Commented Jun 29, 2021 at 2:40
• 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]]
– att
Commented Jun 29, 2021 at 6:30
• Is Peter's Aunt named May, by any chance? Commented Jun 30, 2021 at 0:32

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

### 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
• phew thats small, can you explain how does it work?
– user100752
Commented Jun 28, 2021 at 15:09
• @EliteDaMyth Done! Commented Jun 28, 2021 at 15:17
• Fails for e.g. [1, 1; 1, 0], [0, 0; 0, 1]
– att
Commented Jun 29, 2021 at 6:27
• @att Thank you! I forgot that convolution flips one input. Corrected now Commented Jun 29, 2021 at 8:41

# 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 +/,. # 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. • APLcart has become sentient. we are doomed Commented Jun 29, 2021 at 6:48 # 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). # 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! • Great approach :-D You can shorten count_nonzero to sum; and I think correlate to convolve Commented Jun 28, 2021 at 15:23 • Also, no need to convert to array, or to import Numpy tio.run/… Commented Jun 28, 2021 at 15:26 • 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 Commented Jun 29, 2021 at 8:42 • @LuisMendo well it does have the same result for counting the zeroes, is it really not working the same in this case? Commented Jun 29, 2021 at 9:21 • No, because convolution flips (reverses) one of the inputs. For exampe this should give 1 (it does with correlate) Commented Jun 29, 2021 at 9:33 # 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
• -1 byte Commented Jul 4, 2021 at 18:08

# 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

# 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)

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

# Charcoal, 46 bytes

≔⟦⟧ηＷＳ⊞ηιＷＳ⊞υ⁺ι⭆θ#Ｆη⊞υ#ＩΣ⭆υ⭆ι⬤η⬤ν№⁺π§§υ⁺κξ⁺μρ.

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:

≔⟦⟧ηＷＳ⊞ηι

Input piece 1.

ＷＳ⊞υ⁺ι⭆θ#Ｆη⊞υ#

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

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

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

# 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)); });

# Wolfram Language (Mathematica), 28 bytes

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

Try it online!