Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Very interesting puzzle, but i have problems when there are a lot of points.
I use brute force, with different conditions.
Of course i understand that there is some tricks, but i don’t see them
Can you help me with direction?
Same issue here. I remove all “impossible” combinations of points and check if 4 points make a square with only integer calculations. So i guess the brute force approach is wrong here? (Python3)
yep, i also remove all “impossible” combinations (point coordinate<0, point%1!=0)
if value of searching coordinate< coordinate X in massive, break;
and this is not enought.
i think there is some tricky move. or some conditions that can help
(C# but i think there is no difference)
I have troubles understanding the request. What do they mean with “in how many ways can the farmer pick 4 distinct positions to form a square?”? Does it mean that if I have already used a position like (2, 3) then I won’t be able to use it for any other of my squares?
it means that if you used position (2,3) in square, in another square you can also use this point.
if request has conditions like you said maximum of squares in variant where 1750 points was 437.
So I don’t understand what they mean with 4 distinct points, because if I use 4 distinct point to form all the possible squares in the example with 50 points I end up with 187 possible distinct combinations. Can you please help me understand the request maybe with a basic example?
You can reuse pegs but you can’t count the same set of 4 pegs as separate squares by changing the order of the pegs (eg a square using pegs 0,1,2,3 is the same as a square using pegs 3,2,1,0).
Never mind, I had the formula to check if it’s a square messed up 
It works now
Think about how many points define the remaining square coordinates (more or less) uniquely. Brute-forcing by nesting four loops will definitely be too slow!
If you are stuck on getting the code to run faster after this, it may be helpful to know that it is much faster to determine whether an element is present in certain types of objects than others (O(n) vs O(1)) – so which type of object you store the points in is important. I don’t want to give too much away, but hopefully that should enable you to find the necessary information to solve this puzzle for the larger cases too!
Thank you for your advise.
For other seekers one more advise: “Make your program easier,delete unnecessary conditions”.
I get 6 for that input (numbers are index of the peg in the input):
(0, 1, 3, 4)
(0, 2, 6, 8)
(1, 2, 4, 5)
(1, 3, 5, 7)
(3, 4, 6, 7)
(4, 5, 7, 8)
1 Like
6 squares:
{X=0,Y=0} {X=1,Y=0} {X=1,Y=1} {X=0,Y=1}
{X=0,Y=0} {X=2,Y=0} {X=2,Y=2} {X=0,Y=2}
{X=0,Y=1} {X=1,Y=1} {X=1,Y=2} {X=0,Y=2}
{X=1,Y=0} {X=2,Y=0} {X=2,Y=1} {X=1,Y=1}
{X=1,Y=0} {X=2,Y=1} {X=1,Y=2} {X=0,Y=1}
{X=1,Y=1} {X=2,Y=1} {X=2,Y=2} {X=1,Y=2}
1 Like
wow great thanks!
Getting hard time to understand the instructions,
Can someone give a good example of squares count?
For the next input:
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Does it output 5?
Hey,
currently I using brute force - taking all 4 points combinations (using 2 for loops) and checking if they make a square (every combinations is unique).
Of course I’m getting timeout with 500 points, and suggestion how to solve this puzzle?
Read the comment of Monoterpene and next comment after him
trust me I read all comments before I post
I’m not sure what you mean by checking all 4-point combinations with 2 for loops – if this is by picking all 2-point combinations (possible at that point) within each of the loops, it seems equivalent to nesting 4 loops. As I hinted at above, you can get away with looping over fewer than 4 points (but still making sure that the other points are in the allowed set).
Apologies if I’ve misunderstood what you mean.
Which language are you using?