# Counting overlapping objects

Consider a NxN pixel grid with up to M objects drawn on it, either squares or diamonds:

The objects may overlap, so recognition is hard. The task is to give the minimal possible numbers of objects per shape that can be "seen" in the picture and tell how many squares, how many diamonds, and how many objects with unknown shape there are.

You can find a reference algorithm that solves the problem here.

Here are some examples with their intended numbers (nsquare, ndiamond, nunknown). The examples with nunknown = 1 are those with pixels that may either come from a square or a diamond (highlighted in black, but not bearing any information that may be used). The program with shortest mean runtime in terms of grid size N wins!

And this is a simple test case generator:

let N = 10

// initialize the grid
let grid = Array.from(Array(N), () => new Array(N));

// choose a random number of objects <= M
let n = Math.ceil(Math.random()*M)

// create objects
while (n-- > 0) {

// choose random position, but not on the border of the grid
var i = Math.ceil((N-2)*Math.random())
var j = Math.ceil((N-2)*Math.random())

if (Math.random() > 0.5) {
// draw a square
for (var k = -1; k <=1; k++) {
for (var l = -1; l <=1; l++) {
grid[i+k][j+l] = 1
}
}
} else {
// draw a diamond
for (var k = -1; k <=1; k++) {
for (var l = -1; l <=1; l++) {
if (!(k && l)) {
grid[i+k][j+l] = 1
}
}
}
}
}


Some small test cases: • For a 3x9 rect, the middle 3x3 are all unknown? Promised it can be built with the two shapes?
– l4m2
Feb 9, 2022 at 17:07
• Welcome to Code Golf! I think this is going to require some clarification. E.g., in the (2,0,1) examples, why isn't it 3 or 5 squares? Since the very center pixel could be the center of a square centered around it, overlapping with the other two. And the two pixels on either side of it could also be the center of a square, unless they're not allowed to touch, which doesn 't seem to be specified in the question. Feb 9, 2022 at 17:09
• @l4m2: Promised! Feb 9, 2022 at 17:46
• @taRadvylfsriksushilani: It's not 3 squares (3,0,0) or 2 squares and 1 diamond (2,1,0) because it could be either of both. It's not 5 squares because 2 of them would be completely hidden and could not be "seen". Everything is allowed to touch or overlap. Feb 9, 2022 at 17:50
• What is $f\left(\begin{matrix}*&*&*&{}&{}\\ *&*&*&b&{}\\ *&*&*&*&*\\ {}&a&*&*&*\\ {}&{}&*&*&*\end{matrix}\right)$? The $a$ can be square or cross
– l4m2
Feb 9, 2022 at 17:52

import Data.Bits
import Data.List
listFromPair=uncurry((.pure).(:))
sisSubsetOfp=s.&.p==s
bsum=foldl(.|.)0::[Integer]->Integer
numbers n p=let
w=[0..n-3]
diamond=[1,n+0,n+1,n+2,2*n+1]
square=diamond++[0,2,2*n,2*n+2]
solutions=sortOn length$filter((p==).bsum)$subsequences$filter(isSubsetOfp)[bsum[bit(r*n+c+d)|d<-s]|r<-w,c<-w,s<-[diamond,square]] minlength=length$solutions!!0
best=takeWhile((minlength==).length)solutions
numb=map minimum.transpose\$map(map length.listFromPair.partition((9==).popCount))best
in numb++[minlength-sum numb]


Try it online!