Skip to content

Instantly share code, notes, and snippets.

@mgold

mgold/.block

Last active January 5, 2017 06:05
Show Gist options
  • Save mgold/2ef3afcedd3b41cf355290e7daa7e42c to your computer and use it in GitHub Desktop.
Save mgold/2ef3afcedd3b41cf355290e7daa7e42c to your computer and use it in GitHub Desktop.
Download ZIP
Zukei Puzzle Solver
Raw
.block
license: mit
Raw
README.md

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

Raw
index.html
<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment