Dan Meyer asked programers to make a Zukei solver. So I did.
Click the drawing to cycle from unsolved problem, to parallelograms, to rhombuses, to rectangles, to squares. The outlines will occlude each other; different colors help keep different shapes visually distinguishable. If there are none of a particular state, that stage is skipped, including skipping an entire puzzle.
There’s a fair amount of code keeping track of generating the puzzle, switching between states, and drawing. But the core mathematical algorithm for recognizing shapes is:
- Iterate over each unique quadruple of points. This is asymptotically inefficient, but n is about a dozen.
- For each quadruple, find the convex hull. D3 has a ready-to-use implementation, and this is constant time for four points.
- If the hull has only three points, skip this quadruple. Otherwise, compute the side lengths.
- If a pair of opposite sides are not the same length, skip: it’s not a parallelogram.
- Otherwise, determine if there is a right angle (dot product of angles from one vertex to its neighbors will be zero), and if two adjacent sides are equal. These two booleans allow classification as square, rectangle, rhombus, or (only) parallelogram.
Built with blockbuilder.org