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:
Built with blockbuilder.org
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
.grid line { stroke: #aaa; stroke-width: 5px }
.circles circle { fill: #444444; }
.solution path { fill: none; stroke-width: 5px; }
.solution text { font-family: sans-serif; font-size: 36px; user-select: none; cursor: default }
</style>
</head>
<body>
<script>
var grid_resolution = 5;
var grid_size = 400;
Math.TAU = Math.PI * 2;
var w = 960, h = 500;
var svg = d3.select("body").append("svg")
.attr("width", w)
.attr("height", h)
.append("g")
.attr("transform", "translate("+((w-grid_size)/2)+","+((h-grid_size)/2)+")")
var s = d3.scaleLinear()
.domain([0, grid_resolution-1])
.range([0, grid_size])
var s_px = function(x){ return s(x) + "px"; }
// create the grid
var grid = svg.append("g")
.attr("class", "grid")
grid.append("g")
.attr("class", "horizontal")
.selectAll("line")
.data(d3.range(grid_resolution))
.enter()
.append("line")
.attr("x1", s.range()[0] + "px")
.attr("x2", s.range()[1] + "px")
.attr("y1", s_px)
.attr("y2", s_px)
grid.append("g")
.attr("class", "vertical")
.selectAll("line")
.data(d3.range(grid_resolution))
.enter()
.append("line")
.attr("y1", s.range()[0] + "px")
.attr("y2", s.range()[1] + "px")
.attr("x1", s_px)
.attr("x2", s_px)
var solution = svg.append("g")
.attr("class", "solution")
var parallelograms = solution.append("g")
.style("display", "none")
parallelograms.append("text")
.text("Parallelograms")
.attr("transform", "translate(-272, 368)")
.style("fill", "#FFDC00")
var rhombuses = solution.append("g")
.style("display", "none")
rhombuses.append("text")
.text("Rhombuses")
.attr("transform", "translate(-249, 368)")
.style("fill", "#ff1500")
var rectangles = solution.append("g")
.style("display", "none")
rectangles.append("text")
.text("Rectangles")
.attr("transform", "translate(-249, 368)")
.style("fill", "#002eff")
var squares = solution.append("g")
.style("display", "none")
squares.append("text")
.text("Squares")
.attr("transform", "translate(-203, 368)")
.style("fill", "#5500ff")
var circles = svg.append("g")
.attr("class", "circles")
var points = [];
var randomChoice = function(){
return Math.random() < 0.32928;
}
var pythag = function(p1, p2){
var dx = p2[0] - p1[0]
var dy = p2[1] - p1[1]
return Math.sqrt(dx*dx + dy*dy);
}
var distinct = function(p1, p2){
return p1[0] != p2[0] || p1[1] != p2[1]
}
var allDistinct = function(pair1, pair2){
return distinct(pair1[0], pair2[0])
&& distinct(pair1[0], pair2[1])
&& distinct(pair1[1], pair2[0])
&& distinct(pair1[1], pair2[1])
}
var slope = function(p1, p2){
return (p2[1] - p1[1]) / (p2[0] - p1[0])
}
var vectorSub = function(p1, p2){
return [p1[0] - p2[0], p1[1] - p2[1]]
}
var nearlyEqual = function(a, b){
if(a*b == 0) debugger
return ( Math.abs(a-b) <= 0.00001
||(a == 0 && b == 1)
||(b == 1 && a == 1))
}
var line = d3.line()
.x(function(d) { return s(d[0]); })
.y(function(d) { return s(d[1]); })
function pick(arr){
var i = 0;
return function(){
var ret = arr[i];
i = (i+1)%arr.length;
return ret;
}
}
var yellows = pick(["#FCDC3B", "#FFE600","#FBEC5D", "#CDAD00", "#FFFF00", "#FFF68F", "#BAAF07"]);
var reds = pick(["#FF6666", "#C73F17", "#9D1309", "#EE2C2C", "#CD4F39"]);
var blues = pick(["#0276FD", "#1874CD", "#36648B", "#003EFF", "#75A1D0"]);
var purples = pick(["#6600FF", "#8968CD", "#AB82FF", "#6959CD"])
var render = function(state){
if (state == 0){
circles.selectAll("circle").remove();
solution.selectAll("g")
.style("display", "none")
.selectAll("path").remove();
points = generateNewPuzzle();
renderPuzzle(points);
}else{
if (state == 1){
computeAndRenderSolution(points);
}
var skip = false;
solution.selectAll("g").each(function(d, i){
var current = i == state-1;
var elem = d3.select(this);
elem.style("display", current ? null : "none")
if (current && elem.selectAll("path").empty()){
skip = true;
}
})
if (skip) return nextState();
}
}
var generateNewPuzzle = function(){
var new_points = []
for (var i = 0; i < grid_resolution; i++){
for (var j = 0; j < grid_resolution; j++){
if (randomChoice()){
new_points.push([i,j])
}
}
}
return new_points;
}
var renderPuzzle = function(points){
points.forEach(function(p){
circles.append("circle")
.attr("r", "16px")
.attr("cx", s(p[0]))
.attr("cy", s(p[1]))
})
}
var computeAndRenderSolution = function(points){
var n = points.length;
for (var i = 0; i < n; i++){
var p1 = points[i];
for (var j = i+1; j < n; j++){
var p2 = points[j];
for (var k = j+1; k < n; k++){
var p3 = points[k];
for (var w = k+1; w < n; w++){
var p4 = points[w];
var hull = d3.polygonHull([p1, p2, p3, p4]);
if (hull.length == 4){
lengths = d3.range(4).map(function(idx){
return pythag(hull[idx], hull[(idx+1)%4]);
})
if (lengths[0] == lengths[2]
&& lengths[1] == lengths[3]){
allLengthsEqual = lengths[0] == lengths[1];
var v1 = vectorSub(hull[0], hull[1]);
var v2 = vectorSub(hull[2], hull[1])
var rightAngles = Math.abs(v1[0]*v2[0] + v1[1]*v2[1]) < 0.001;
var layer, color;
if (allLengthsEqual && rightAngles){
layer = squares;
color = purples;
}else if (rightAngles){
layer = rectangles;
color = blues;
}else if (allLengthsEqual){
layer = rhombuses;
color = reds;
}else{
layer = parallelograms;
color = yellows;
}
layer.append("path")
.datum(hull)
.attr("d", function(ps){ return line(ps) + "Z"})
.style("stroke", color())
// I'd love to inset the outlines a bit,
// but this approach doesn't center them
//.attr("transform", "scale(0.98)")
}
}
}
}
}
}
}
var state = 0;
var number_of_states = 5;
d3.select("body").on("click", nextState)
function nextState(){
state += 1;
state %= number_of_states;
render(state);
}
render(state);
</script>
</body>