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
Improve this question
\$\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\$ Commented Mar 21, 2021 at 20:49
  • 1
    \$\begingroup\$ By “can be placed diagonally”, you mean only a 45° angle, or at any angle? \$\endgroup\$ Commented Mar 21, 2021 at 21:00
  • 1
    \$\begingroup\$ @xigoi: I mean any angle. \$\endgroup\$ Commented Mar 21, 2021 at 21:02
  • 1
    \$\begingroup\$ Related \$\endgroup\$ Commented Mar 21, 2021 at 23:17
  • 3
    \$\begingroup\$ Does this answer your question? Tell me, how many squares are there? \$\endgroup\$ Commented Mar 23, 2021 at 11:41

8 Answers 8

Reset to default
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.

Improve this answer
\$\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\$ Commented Mar 22, 2021 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
Improve this answer
\$\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\$ Commented Mar 21, 2021 at 21:25
  • 1
    \$\begingroup\$ @Etheryte It's just very slow, since it generates a list of all groups of 4 points. \$\endgroup\$ Commented Mar 21, 2021 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\$ Commented Mar 23, 2021 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\$ Commented Mar 23, 2021 at 15:06
3
\$\begingroup\$

Charcoal, 72 bytes

Ｆ⁹⊞υＳυ≔±№ＫＡ1θＦ⁹Ｆ⌕Ａ§υι1Ｆ⁹Ｆ⌕Ａ§υλ1«Ｊ⁺κ⁻λι⁺ι⁻κμ¿ΣＫＫ«Ｊ⁺μ⁻λι⁺λ⁻κμ≧⁺ΣＫＫθ»»⎚Ｉ÷θ⁴

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

Ｆ⁹⊞υＳυ

Input the array and print it to the canvas.

≔±№ＫＡ1θ

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.

Ｆ⁹Ｆ⌕Ａ§υι1

Loop over all of the 1s in the array.

Ｆ⁹Ｆ⌕Ａ§υλ1«

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

Ｊ⁺κ⁻λι⁺ι⁻κμ

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

¿ΣＫＫ«

If there is a 1 here, then...

Ｊ⁺μ⁻λι⁺λ⁻κμ

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

≧⁺ΣＫＫθ

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

»»⎚Ｉ÷θ⁴

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

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\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\$ Commented Mar 21, 2021 at 22:38
  • 1
    \$\begingroup\$ You can save 3 bytes by removing the spaces between ) and for. \$\endgroup\$ Commented Mar 21, 2021 at 22:40
  • \$\begingroup\$ @xigoi: Thank you, I was really blind :-) \$\endgroup\$ Commented Mar 21, 2021 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\$ Commented Mar 21, 2021 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.

Improve this answer
\$\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\$ Commented Mar 21, 2021 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\$ Commented Mar 21, 2021 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\$ Commented Mar 21, 2021 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\$ Commented Mar 23, 2021 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\$ Commented Mar 23, 2021 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

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.