Old school D3 from simpler times

All examples By author By category About

mgold

Full window Github gist

Zukei Puzzle Solver

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

<!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>

https://d3js.org/d3.v4.min.js