[Community Puzzle] Windmill problem

Puzzles
#1

https://www.codingame.com/training/medium/windmill-problem

Send your feedback or ask for help here!

Created by @Maurice_Moss,validated by @bbb000bbbyyy,@Niako and @JBM.
If you have any issues, feel free to ping them.

#2

I can pass all test cases except ‘Smarter approach required’. So how should I optimize the algorithm to pass this test case?

#3

Movement of the straight line is repeating in a cycle. You need not follow it to cycle a million times to reach the ending.

1 Like
#4

I really enjoyed this puzzle. Very simple to describe, somewhat medium effort to conceptualize the graphical solutions, medium effort to come up with a brute force solution, more creative thinking to come up with solution for test #6, and good effort to implement the clever and efficient solution.
NOTE: I was wondering if this puzzle could be extended to work in three dimensions, where you are given K points in 3D, a P pair of start points (with one point marked with a pivot counter of 2, the other as pivot counter of 1) for a plane that can pivot around the two points, and N number of pivots. The plane would need to rotate clockwise when looking at it from the X-axis, and if the plane is perpendicular to the X-axis, then rotate clockwise as seen from the Y-axis. As the plane pivots, you look for the next point that touches the plane. The point that had counter of 2 is now released, and the other two points become the pivoting line for the plan, with their pivot counter incremented by one. Keep doing this for N pivots.
The output would be the index of the ending point, with a list of points with the number of times it was a pivot.
Then extend this for N-dimensions.
That would be cool. :slight_smile:

2 Likes
#5

I enjoyed it too, first you think about how to deal with your angles, then about how to optimize your algorithm. Very nice.

#6

Loved it!
First I had to redo my work to get even close to a solution. Then I had to optimize to be able to handle the harder cases. I feel as if I learned a lot doing this one, thanks for the nice puzzle!

#7

Cool idea. But, wouldn’t it make more sense to …

  1. Receive inputs P1, P2
  2. Rotate plane clockwise on the emerging axis, ie: looking from P1 → P2
  3. We hit our P3
  4. Shift the points, discarding oldest : P1=P2, P2=P3, P3=??, (giving a new axis of rotation)
  5. Return to (1)

Just coded it up and it works very nicely. Am currently using it to animate a 2D slice of 3D Perlin Noise … basically, I’m treating the plane as a grid, and then looking up each pixel value in the noise field (with wraparound)

Animates very nicely… I’m placing 0,0 at the midpoint of P1-P2. You can see each P1-P2 line in the 2D animation as the closer you are to that line the slower the values change. The P1-P2 line of ‘no change’ always passes through the centre of the 2D image.

thanks for the idea : )