13
\$\begingroup\$

In a 9 by 9 grid some points have been marked. The task is it to make a program that counts all distinct squares that can be made using four marked points. Note that squares can also be placed diagonally (any angle).

Input can be one of the following:

  • A character string of length 81 containing two distinct characters for marked and unmarked points.
  • A one dimensional array (length 81) containing two distinct values.
  • A two dimensional array (9 by 9) with containing distinct values.

Output: The number of possible squares

You can write a full program or a function. This is code-golf. I am interested in the shortest code in every language. Standard loopholes are forbidden.

Examples:

Input:  ooo......oooooo...oooooo....oo.oo....oooooo...oooooo......ooo....................
Output: 62

Looks like: 

o o o 
o o o o o o
o o o o o o
  o o   o o
  o o o o o o
  o o o o o o
        o o o

Input:  ...ooo......ooo......ooo...ooo...oooooo.o.oooooo...ooo...ooo......ooo......ooo...
Output: 65

Input:  ...........o..o..o....................o..o..o....................o..o..o.........
Output: 6

Input:  ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Output: 540

Input:  ...........o..o.......................o.....o....................o...o...........
Output: 0
\$\endgroup\$
8
  • 1
    \$\begingroup\$ @pxeger: Thanks for the hint. I did not know that there is a sandbox. I will use for my next question. \$\endgroup\$
    – Donat
    Mar 21 at 20:49
  • 1
    \$\begingroup\$ By “can be placed diagonally”, you mean only a 45° angle, or at any angle? \$\endgroup\$
    – xigoi
    Mar 21 at 21:00
  • 1
    \$\begingroup\$ @xigoi: I mean any angle. \$\endgroup\$
    – Donat
    Mar 21 at 21:02
  • 1
    \$\begingroup\$ Related \$\endgroup\$
    – Luis Mendo
    Mar 21 at 23:17
  • 3
    \$\begingroup\$ Does this answer your question? Tell me, how many squares are there? \$\endgroup\$
    – pxeger
    Mar 23 at 11:41
6
\$\begingroup\$

JavaScript (ES6),  122  109 bytes

Saved 13 bytes thanks to @tsh!

Expects a binary matrix.

f=(m,X,Y,t=0)=>m.map((r,y)=>r.map((v,x)=>t+=v*=1/Y?(m[X-x+Y]||0)[y-Y+X]&(m[y+X-x]||0)[x+y-Y]:~-f(m,x,y)/4))|t

Try it online!


JavaScript (ES11), 103 bytes

Also suggested by @tsh

We can save 6 more bytes by using optional chaining.

f=(m,X,Y,t=0)=>m.map((r,y)=>r.map((v,x)=>t+=v*=1/Y?m[X-x+Y]?.[y-Y+X]&m[y+X-x]?.[x+y-Y]:~-f(m,x,y)/4))|t

Optional chaining is not supported on TIO.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 103: f=(m,Y,X,t=0)=>m.map((r,y)=>r.map((v,x)=>t+=v*=1/Y?m[X-x+Y]?.[y-Y+X]&m[y+X-x]?.[x+y-Y]:~-f(m,y,x)/4))|t \$\endgroup\$
    – tsh
    Mar 22 at 3:18
6
\$\begingroup\$

Jelly, 18 bytes

ŒṪÆịœc4ṗ2ạ/€QLƲ€ċ3

Try it online!

Input is a two-dimensional list of 0 and 1 (or any other falsy and truthy value).

Explanation

The idea is that for every four distinct points, we calculate the distance between each pair and if there are exactly three distinct distances (including 0), it's a square. (There are other shapes with this property, but they don't fit on a square grid; see @aPaulT's comment.)

ŒṪÆịœc4ṗ2ạ/€QLƲ€ċ3   Main monadic link
ŒṪ                   Get the coordinates of truthy points
  Æị                 Convert to complex numbers
    œc4              Get all combinations of size 4
               €     For each
              Ʋ      (
       ṗ2              Cartesian square
         ạ/            Absolute difference
           €             of each pair
            Q          Find unique items
             L         Length
              Ʋ      )
                ċ3   Count the occurences of 3
\$\endgroup\$
4
  • \$\begingroup\$ I can't tell whether it runs very slow or gets stuck in an endless loop for the input where every value is 1. \$\endgroup\$
    – Etheryte
    Mar 21 at 21:25
  • 1
    \$\begingroup\$ @Etheryte It's just very slow, since it generates a list of all groups of 4 points. \$\endgroup\$
    – xigoi
    Mar 21 at 21:27
  • 1
    \$\begingroup\$ There are other configurations of four points with three distinct distances besides the square and rhombus (though I don't think any of them fit on a square grid either): puzzling.stackexchange.com/questions/63039/… \$\endgroup\$
    – aPaulT
    Mar 23 at 14:59
  • \$\begingroup\$ @aPaulT That's right. Four of them contain an equilateral triangle, and one consists of four vertices of a pentagon; you can't make either of those on a square grid. \$\endgroup\$
    – xigoi
    Mar 23 at 15:06
3
\$\begingroup\$

Charcoal, 72 bytes

F⁹⊞υSυ≔±№KA1θF⁹F⌕A§υι1F⁹F⌕A§υλ1«J⁺κ⁻λι⁺ι⁻κμ¿ΣKK«J⁺μ⁻λι⁺λ⁻κμ≧⁺ΣKKθ»»⎚I÷θ⁴

Try it online! Link is to verbose version of code. Takes input as an array of 9 strings of 1s and neutral characaters. Explanation:

F⁹⊞υSυ

Input the array and print it to the canvas.

≔±№KA1θ

Initialise the count to the negation of the number of 1s on the canvas. This is because the algorithm below counts each 1 as a single 0×0 square, which we don't want.

F⁹F⌕A§υι1

Loop over all of the 1s in the array.

F⁹F⌕A§υλ1«

Loop over all of the 1s in the array again.

J⁺κ⁻λι⁺ι⁻κμ

Treat the two pairs of coordinates as two adjacent corners on a square, and jump to where the third corner would be.

¿ΣKK«

If there is a 1 here, then...

J⁺μ⁻λι⁺λ⁻κμ

... jump to where the fourth corner would be, and...

≧⁺ΣKKθ

... if that's also a 1 then increment the count of squares found.

»»⎚I÷θ⁴

Since squares have four pairs of adjacent corners, divide the count by 4.

\$\endgroup\$
2
\$\begingroup\$

Jelly (cairdcoinheringaahing's fork), 17 bytes

ŒṪœc4ṗ2ạ/ṢɱQLƲ€ċ3

A modification of my Jelly answer. Instead of calculating the Euclidean distances, it simply calculates the two differences of coordinates and then sorts them to make the uniquification order-insensitive.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 121 110 99 bytes

->m{(0..80).sum{|x|(1..8-k=x%9).sum{|w|(0..k).count{|t|[0,w+9*t,9*w-t,t*8+w*10].all?{|z|m[x+z]}}}}}

Try it online!

Accepts a boolean array in input.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 133 bytes

lambda g,r=range:sum(g[x][y]*g[x+a][y+b]*g[x+b][y-a]*g[x+a+b][y-a+b]for a in r(1,9)for b in r(9-a)for x in r(9-a-b)for y in r(a,9-b))

Try it online!

Expects a two dimensional array of booleans.

Shortend by 3 bytes thanks to xigoi.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ It's funny that TIO still considers Python 3.8 a pre-release when there is already a release of Python 3.9.1. \$\endgroup\$
    – xigoi
    Mar 21 at 22:38
  • 1
    \$\begingroup\$ You can save 3 bytes by removing the spaces between ) and for. \$\endgroup\$
    – xigoi
    Mar 21 at 22:40
  • \$\begingroup\$ @xigoi: Thank you, I was really blind :-) \$\endgroup\$
    – Donat
    Mar 21 at 22:45
  • \$\begingroup\$ My first approach used the walrus operator, so I needed 3.8. Yes funny, that this version is still considered a pre-release. \$\endgroup\$
    – Donat
    Mar 21 at 22:50
0
\$\begingroup\$

Perl 5, 127 bytes

sub{0+map{$a=$_;map{$b=$_;map{//;grep{$_[$'][$_]&$_[$'+$a][$_+$b]&$_[$'+$b][$_-$a]&$_[$'+$a+$b][$_-$a+$b]}$a..8}0..8}0..8}1..8}

Try it online!

Expects a two dimensional array containing values 0 or 1.

\$\endgroup\$
5
  • 5
    \$\begingroup\$ Usually don't answer your own posts after only an hour. Its more polite to give other people a chance to answer for a few days. \$\endgroup\$
    – Noodle9
    Mar 21 at 21:36
  • 1
    \$\begingroup\$ @Noodle9 - I don't necessarily feel that this should be any sort of real convention here; it's entirely possible that the answer can be golfed, and I've seen multiple answers in the same language for other challenges. Sometimes, I've even seen the challenger post an answer with the challenge, suggesting that "you can use my answer in «language» as a guideline to a working algorithm". \$\endgroup\$ Mar 21 at 21:48
  • 4
    \$\begingroup\$ @JeffZeitlin This should rather be discussed on meta. The current consensus (currently +24/-0) is that it should be avoided. \$\endgroup\$
    – Arnauld
    Mar 21 at 22:18
  • \$\begingroup\$ @Noodle9: Sorry, I did not want to be unfair. I have seen that it is even possible to post a solution together with the question. This encouraged me to add an answer some short time later. There was also much room for improvement in the first version of my answer. \$\endgroup\$
    – Donat
    Mar 23 at 9:00
  • 1
    \$\begingroup\$ @Donat You posted another answer right after I posted this comment. In the very language, Python, that I was going to post an answer in. So then I didn't bother. \$\endgroup\$
    – Noodle9
    Mar 23 at 9:14
0
\$\begingroup\$

MATLAB, 168 Bytes

function o=q(I)
o=0;for i=2:9
for j=0:9-i
for k=0:9-i
a=I((1:i)+j,(1:i)+k);a(2:i-1,2:i-1)=0;o=o+floor(sum(a&rot90(a,2)&rot90(a,1)&rot90(a,3),'all')/4);end
end
end

A different approach. Takes a 9x9 array of 1s and 0s. Loop through every square submatrix from size 2 to 9, and rotate that submatrix three times and take the boolean combination of all 4 (original + 3 rotations). The sum of all truthy values on the edges divided by 4 rounded down is the number of squares that are in that submatrix. By looking only at the edges, you avoid capturing smaller submatrices in the middle (e.g. 2x2 in the middle of a 4x4). This method captures all squares by using the rotational symmetry of a square. It may not be the golfiest, but it was fun

\$\endgroup\$

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