[Community Puzzle] The flight of birds - Puzzle discussion

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @Sirios,validated by @LeifTerry, @Remi and @Timinator.
If you have any issues, feel free to ping them.

#2

I also validated this puzzle ^^

EDIT : Thank you @nicola

2 Likes
#3

Could someone clarify the logic of bird-bird collisions? Bird-wall collisions make sense to me, but bird-bird collisions not so much.

  • Each time a bird approached the edge of the aviary or another bird at a specific distance from d, it changed direction while maintaining its speed and respecting the law of reflection.

“Law of reflection”

  • The reflected vector is in the same plane as the incident vector.
  • The angle of reflection is equal to the angle of incidence.

Link:
Reflection (physics) - Wikipedia

This makes me think that birds kinda behave like billard balls, but kinda not. In the particular case where two birds collide with the same velocity (ie two speed vectors that are different but have the same magnitude), they would simply exchange their speed vectors.

But:

  • What happens if two birds with different velocities collide? What are the relevant “angles of incidence” to apply the “law of reflection” to the birds?

  • What happens if two birds are already within distance less than d of each other in the input? There are no past trajectories that would explain why they didn’t change direction as soon as they were at distance exactly d of each other!

  • What happens if two birds are at distance exactly d of each other in the input? Should we “reflect” their speed vectors or are they already reflected in the input?

  • What output is expected in the following case, where two birds moving in the same direction collide because one of them is moving faster?:

100 100
20
1
2
1 10 0 -2 0
2 20 0 -1 0
#4

A bird colliding with another bird involves more challenging computations, but it is no different conceptually than colliding with a wall. An imaginary wall can be drawn in all bird/bird collisions. One bird is reflecting off one side of the imaginary wall and the other bird is reflecting off the other side of the imaginary wall.

I disagree with your statement about “exchanging” speed vectors. The problem states:

Each time a bird approached the edge of the aviary or another bird at a specific distance from d, it changed direction while maintaining its speed and respecting the law of reflection.

I don’t have anything for you on this one. This is one of the key questions you must answer to solve this puzzle.

It’s been a while since I did the puzzle. Does this happen in any test cases?

This happens in Test Case 8, but no movement is possible for any of the birds, so it doesn’t help answer your question. Does it happen in any other test cases?

Your example doesn’t appear to match your question. Shouldn’t you have the velocities the other way around?

Either way, let’s say two birds are travelling in identical directions with the trailing bird travelling at a faster speed. Assuming no other collisions, the trailing bird will change direction by 180 degrees as soon as the distance between the two birds is equal to d. The lead bird’s direction will not change as it is already moving directly away from the collision point.