10
\$\begingroup\$

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

3x3 grid of black squares ("squares")square    3x3 grid with black squares forming a plus symbol ("diamonds")diamond

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

s list of test cases containing 12 different grid configurations

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:

enter image description here

\$\endgroup\$
28
  • \$\begingroup\$ For a 3x9 rect, the middle 3x3 are all unknown? Promised it can be built with the two shapes? \$\endgroup\$
    – l4m2
    Feb 9, 2022 at 17:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Feb 9, 2022 at 17:09
  • \$\begingroup\$ @l4m2: Promised! \$\endgroup\$ Feb 9, 2022 at 17:46
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Feb 9, 2022 at 17:50
  • \$\begingroup\$ What is \$f\left(\begin{matrix}*&*&*&{}&{}\\ *&*&*&b&{}\\ *&*&*&*&*\\ {}&a&*&*&*\\ {}&{}&*&*&*\end{matrix}\right)\$? The \$a\$ can be square or cross \$\endgroup\$
    – l4m2
    Feb 9, 2022 at 17:52

1 Answer 1

2
\$\begingroup\$

Haskell, O(2ⁿ)

import Data.Bits
import Data.List
listFromPair=uncurry((.pure).(:))
s`isSubsetOf`p=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(`isSubsetOf`p)[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!

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.