[Community Puzzle] Counting Squares on Pegs

Puzzles
#21

I’m using javascript,
@Monoterpene I’m looping over all the subsets (that’s why it’s 2 for loops),
I think I missing some “unnecessary conditions” but anyway I don’t think it will help, maybe there is another approach?

#22

If I understand correctly that you are generating all combinations of 4 points from the given set, and then testing whether they form a square, your code will be too slow for the large-number-of-points cases. Yes, you need to find an approach that gets away with looking at fewer combinations.

Further hint: if I give you the coordinates of two points in the plane, how many squares have those two points as their vertices? Can you use this?

2 Likes
#23

Love this puzzle !

It looks simple at first, but has couple of "gotcha"s.
One is the identification of the squares
The other is the optimization needed for bigger sets.

Monoterpene already provided all the hints necessary

#24

Hi,

I think a test with non axis-aligned squares and a reasonable amount of points should be added to the test set, such as the example proposed by Dennis Vash. I missed the point despite it is written in the text, and I spent time looking at my fault. At first I disliked this puzzle for that, and I think an easy-to-handle example would help beginners and non-fluent English speakers to get it all, and people like me :slight_smile: .
I have to go back to the puzzle, the non aligned squares make it much more exiting now.

Thank you

1 Like
#25

I got 5 and by visual count and by my current algorhitm I also got 5, where is 6th square? I mean purely visualy. Its 3x3 array, so there is 4 disctinct 2x2 squares and 1 3x3 square. I most likely struggle to get assigment right, cant find 6th square :] Please help!

#26

You’re missing the last, non-axis aligned one:
0 1, 1 0, 2 1, 1 2

1 Like
#27

Oh wow, I didnt thought of this, so diagonal sqaures are also in equation. Thank you very much.
Cheers.

#28

So, square like this would be also in possible squares?

#29

Yes, of course.

#30

Alright, thank you. Assigment of this puzzle was very difficult for me to understand, english is not my first language.
Cheers.

#31

I feel like I have to be missing something obvious with this puzzle. Despite having checks for 2 points and checks for 3 points before adding a 3rd or 4th point respectively and presorting my points so I only need to try them in one order, I’m still timing out with only the 500 point test case. (Python3)

#32

I tried to follow the same approach like what @Monoterpene mentioned in hint in C++. But I am getting time out from 4th test case onwards. I stored all the pair of points and try to form a square using each pair as side and also used integer hash for (x,y) coordinate but still no luck. Any idea about the optimization trick for this problem?

#33

@codybumba The hint suggests that, given a pair of points, there are only two squares that could have the corresponding segment as a side. Can you compute the two other vertices of each of these two squares? Can you check whether there is a peg on these vertices?

1 Like
#34

I did same.

#35

I stored all the points in an unordered_map for checking existence of other points which can be used with the pair to form a square.

#36

Then the complexity of your algorithm should be O(n²) (no more than two nested loops on the set of points) and it should be good enough to pass. If it does not, there is an implementation problem somewhere (you can start by running it locally to know whether it is too slow or does not even terminate).