Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Recognize four equal sides and two equal diagonals: The Square Constellation.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Valid square by distances matches the clues
- 2Keep this true after every move: the sorted six distances fully characterize the four-point square
- 3Reach the result within O(1) time and space
Rules and pressure
- Target cost: O(1) time and space
- State rule: the sorted six distances fully characterize the four-point square
Lesson 1 of 3
Live algorithm trace
Valid square by distances
Complete execution1 of 5
Compute all six squared distances among four points.
1
compute six squared pair distances2
sort the distances3
require smallest distance > 04
require first four distances equal5
require final two distances equal6
require diagonal = 2 * sidepairDistances = 1,1,1,1,2,2
Truth to preserve / Cost target
Truth to preserve
the sorted six distances fully characterize the four-point square
Cost target
O(1) time and space
A square's six pairwise squared distances contain four equal positive sides and two equal diagonals, each twice a side. Squared distances avoid roots and orientation cases.
Your call · What should guide every step of this algorithm?