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

Revisions

  1. mgold revised this gist Jan 5, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    Dan Meyer [asked](https://twitter.com/ddmeyer/status/815737837190410241) 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.
    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:

  2. mgold revised this gist Jan 5, 2017. 2 changed files with 62 additions and 11 deletions.
    12 changes: 12 additions & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +1,13 @@
    Dan Meyer [asked](https://twitter.com/ddmeyer/status/815737837190410241) 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.

    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](http://blockbuilder.org)
    61 changes: 50 additions & 11 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -7,6 +7,7 @@
    .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>

    @@ -58,9 +59,29 @@
    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")
    @@ -86,8 +107,14 @@
    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){
    return Math.abs(a-b) <= 0.00001;
    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]); })
    @@ -102,24 +129,34 @@
    }
    }

    var yellows = pick(["#FCDC3B", "#FFE600","#FBEC5D", "#CDAD00", "#FFFF00"]);
    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").selectAll("path").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){
    d3.select(this).attr("display", i == state-1 ? null : "none")
    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();

    }
    }

    @@ -159,14 +196,12 @@
    lengths = d3.range(4).map(function(idx){
    return pythag(hull[idx], hull[(idx+1)%4]);
    })
    debugger
    if (lengths[0] == lengths[2]
    && lengths[1] == lengths[3]){
    allLengthsEqual = lengths[0] == lengths[1];
    rightAngles = nearlyEqual(
    slope(hull[0], hull[1]),
    -1/slope(hull[1], hull[2])
    ) // bug: does not account for vertical slopes (div by 0)
    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;
    @@ -185,6 +220,9 @@
    .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)")

    }
    }
    @@ -197,11 +235,12 @@

    var state = 0;
    var number_of_states = 5;
    d3.select("body").on("click", function(){
    d3.select("body").on("click", nextState)
    function nextState(){
    state += 1;
    state %= number_of_states;
    render(state);
    })
    }
    render(state);

    </script>
  3. mgold revised this gist Jan 5, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -118,7 +118,7 @@
    computeAndRenderSolution(points);
    }
    solution.selectAll("g").each(function(d, i){
    d3.select(this).attr("display", i == state ? null : "none")
    d3.select(this).attr("display", i == state-1 ? null : "none")
    })
    }
    }
  4. mgold revised this gist Jan 5, 2017. 1 changed file with 74 additions and 16 deletions.
    90 changes: 74 additions & 16 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -6,7 +6,7 @@
    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: blue; stroke-width: 6px; }
    .solution path { fill: none; stroke-width: 5px; }
    </style>
    </head>

    @@ -57,6 +57,11 @@

    var solution = svg.append("g")
    .attr("class", "solution")
    var parallelograms = solution.append("g")
    var rhombuses = solution.append("g")
    var rectangles = solution.append("g")
    var squares = solution.append("g")

    var circles = svg.append("g")
    .attr("class", "circles")
    var points = [];
    @@ -78,19 +83,43 @@
    && 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 nearlyEqual = function(a, b){
    return Math.abs(a-b) <= 0.00001;
    }
    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"]);
    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(showSolution){
    if (showSolution){
    computeAndRenderSolution(points);
    }else{
    var render = function(state){
    if (state == 0){
    circles.selectAll("circle").remove();
    solution.selectAll("path").remove();
    solution.selectAll("g").selectAll("path").remove();
    points = generateNewPuzzle();
    renderPuzzle(points);

    }else{
    if (state == 1){
    computeAndRenderSolution(points);
    }
    solution.selectAll("g").each(function(d, i){
    d3.select(this).attr("display", i == state ? null : "none")
    })
    }
    }

    @@ -127,24 +156,53 @@
    var p4 = points[w];
    var hull = d3.polygonHull([p1, p2, p3, p4]);
    if (hull.length == 4){
    solution.append("path")
    .datum(hull)
    .attr("d", line)
    lengths = d3.range(4).map(function(idx){
    return pythag(hull[idx], hull[(idx+1)%4]);
    })
    debugger
    if (lengths[0] == lengths[2]
    && lengths[1] == lengths[3]){
    allLengthsEqual = lengths[0] == lengths[1];
    rightAngles = nearlyEqual(
    slope(hull[0], hull[1]),
    -1/slope(hull[1], hull[2])
    ) // bug: does not account for vertical slopes (div by 0)
    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())

    }
    }
    }
    }
    }
    }
    }


    var showingSolution = false;

    var state = 0;
    var number_of_states = 5;
    d3.select("body").on("click", function(){
    showingSolution = !showingSolution;
    render(showingSolution);
    state += 1;
    state %= number_of_states;
    render(state);
    })
    render(showingSolution);
    render(state);

    </script>
    </body>
  5. mgold revised this gist Jan 4, 2017. 1 changed file with 20 additions and 25 deletions.
    45 changes: 20 additions & 25 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -14,6 +14,7 @@
    <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")
    @@ -115,35 +116,29 @@
    }

    var computeAndRenderSolution = function(points){
    var points_at_distance = d3.map();
    for (var i = 0; i < points.length; i++){
    for (var j = i+1; j < points.length; j++){ // i and j are distinct
    var dist = pythag(points[i], points[j])
    var val = points_at_distance.get(dist) || [];
    val.push([points[i], points[j]]);
    points_at_distance.set(dist, val);
    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){
    solution.append("path")
    .datum(hull)
    .attr("d", line)
    }
    }
    }
    }
    }

    points_at_distance.each(function(pairs, dist){
    for (var i = 0; i < pairs.length; i++){
    for (var j = i+1; j < pairs.length; j++){ // i and j are distinct
    var pair1 = pairs[i];
    var pair2 = pairs[j];
    if (allDistinct(pair1, pair2)){
    if ( pythag(pair1[0], pair2[0]) == pythag(pair1[1], pair2[1])
    && pythag(pair1[0], pair2[1]) == pythag(pair1[1], pair2[0])
    ){
    solution.append("path")
    .datum([pair1[0], pair1[1], pair2[0], pair2[1]])
    .attr("d", line)
    }
    }
    }
    }
    })
    }



    var showingSolution = false;
    d3.select("body").on("click", function(){
    showingSolution = !showingSolution;
  6. mgold revised this gist Jan 3, 2017. 1 changed file with 56 additions and 9 deletions.
    65 changes: 56 additions & 9 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -6,6 +6,7 @@
    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: blue; stroke-width: 6px; }
    </style>
    </head>

    @@ -54,46 +55,92 @@
    .attr("x2", s_px)

    var solution = svg.append("g")
    .attr("class", "path")
    .attr("class", "solution")
    var circles = svg.append("g")
    .attr("class", "circles")
    var points = [];

    var coinFlip = function(){
    return Math.random() < 0.5;
    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 line = d3.line()
    .x(function(d) { return s(d[0]); })
    .y(function(d) { return s(d[1]); })

    var render = function(showSolution){
    if (showSolution){
    computeAndRenderSolution(points);
    }else{
    circles.selectAll("circle").remove();
    solution.selectAll("circle").remove();
    solution.selectAll("path").remove();
    points = generateNewPuzzle();
    renderPuzzle(points);

    }
    }


    var generateNewPuzzle = function(){
    var new_points = []
    for (var i = 0; i < grid_resolution; i++){
    for (var j = 0; j < grid_resolution; j++){
    if (coinFlip()){
    if (randomChoice()){
    new_points.push([i,j])
    }
    }
    }
    return points;
    return new_points;
    }

    var renderPuzzle = function(points){
    points.forEach(function(p){
    circles.append("circle")
    .attr("r", "16px")
    .attr("cx", s_px(p[0]))
    .attr("cy", s_px(p[1]))
    .attr("cx", s(p[0]))
    .attr("cy", s(p[1]))
    })
    }

    var computeAndRenderSolution = function(points){
    var points_at_distance = d3.map();
    for (var i = 0; i < points.length; i++){
    for (var j = i+1; j < points.length; j++){ // i and j are distinct
    var dist = pythag(points[i], points[j])
    var val = points_at_distance.get(dist) || [];
    val.push([points[i], points[j]]);
    points_at_distance.set(dist, val);
    }
    }

    points_at_distance.each(function(pairs, dist){
    for (var i = 0; i < pairs.length; i++){
    for (var j = i+1; j < pairs.length; j++){ // i and j are distinct
    var pair1 = pairs[i];
    var pair2 = pairs[j];
    if (allDistinct(pair1, pair2)){
    if ( pythag(pair1[0], pair2[0]) == pythag(pair1[1], pair2[1])
    && pythag(pair1[0], pair2[1]) == pythag(pair1[1], pair2[0])
    ){
    solution.append("path")
    .datum([pair1[0], pair1[1], pair2[0], pair2[1]])
    .attr("d", line)
    }
    }
    }
    }
    })
    }

  7. mgold revised this gist Jan 3, 2017. 1 changed file with 10 additions and 5 deletions.
    15 changes: 10 additions & 5 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -65,31 +65,36 @@

    var render = function(showSolution){
    if (showSolution){
    computeAndRenderSolution();
    computeAndRenderSolution(points);
    }else{
    circles.selectAll("circle").remove();
    solution.selectAll("circle").remove();
    points = [];
    generateNewPuzzle();
    points = generateNewPuzzle();
    renderPuzzle(points);

    }
    }


    var generateNewPuzzle = function(){
    var new_points = []
    for (var i = 0; i < grid_resolution; i++){
    for (var j = 0; j < grid_resolution; j++){
    if (coinFlip()){
    points.push([i,j])
    new_points.push([i,j])
    }
    }
    }
    return points;
    }

    var renderPuzzle = function(points){
    points.forEach(function(p){
    circles.append("circle")
    .attr("r", "16px")
    .attr("cx", s_px(p[0]))
    .attr("cy", s_px(p[1]))
    })

    }

    var showingSolution = false;
  8. mgold revised this gist Jan 3, 2017. 1 changed file with 71 additions and 14 deletions.
    85 changes: 71 additions & 14 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -4,43 +4,100 @@
    <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: gray;, stroke-width: 2px }
    .grid line { stroke: #aaa; stroke-width: 5px }
    .circles circle { fill: #444444; }
    </style>
    </head>

    <body>
    <script>
    // Feel free to change or delete any of the code you see in this editor!
    var grid_resolution = 5;
    var grid_size = 400;

    var w = 960, h = 500;
    var svg = d3.select("body").append("svg")
    .attr("width", 960)
    .attr("height", 500)
    .attr("width", w)
    .attr("height", h)
    .append("g")
    .attr("transform", "translate("+((w-grid_size)/2)+","+((h-grid_size)/2)+")")

    var grid_resolution = 5;
    var s = d3.scaleLinear()
    .domain([0, grid_resolution-1])
    .range([0, 400])
    .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")
    .data(d3.range(grid_resolution))
    .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)

    svg.append("text")
    .text("Edit the code below to change me!")
    .attr("y", 200)
    .attr("x", 120)
    .style("font-size", 36)
    .style("font-family", "monospace")

    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", "path")
    var circles = svg.append("g")
    .attr("class", "circles")
    var points = [];

    var coinFlip = function(){
    return Math.random() < 0.5;
    }

    var render = function(showSolution){
    if (showSolution){
    computeAndRenderSolution();
    }else{
    circles.selectAll("circle").remove();
    solution.selectAll("circle").remove();
    points = [];
    generateNewPuzzle();
    }
    }


    var generateNewPuzzle = function(){
    for (var i = 0; i < grid_resolution; i++){
    for (var j = 0; j < grid_resolution; j++){
    if (coinFlip()){
    points.push([i,j])
    }
    }
    }
    points.forEach(function(p){
    circles.append("circle")
    .attr("r", "16px")
    .attr("cx", s_px(p[0]))
    .attr("cy", s_px(p[1]))
    })

    }

    var showingSolution = false;
    d3.select("body").on("click", function(){
    showingSolution = !showingSolution;
    render(showingSolution);
    })
    render(showingSolution);

    </script>
    </body>
  9. mgold created this gist Jan 3, 2017.
    1 change: 1 addition & 0 deletions .block
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    license: mit
    1 change: 1 addition & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    Built with [blockbuilder.org](http://blockbuilder.org)
    46 changes: 46 additions & 0 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    <!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: gray;, stroke-width: 2px }
    </style>
    </head>

    <body>
    <script>
    // Feel free to change or delete any of the code you see in this editor!
    var svg = d3.select("body").append("svg")
    .attr("width", 960)
    .attr("height", 500)

    var grid_resolution = 5;
    var s = d3.scaleLinear()
    .domain([0, grid_resolution-1])
    .range([0, 400])

    var s_px = function(x){ return s(x) + "px"; }

    var grid = svg.append("g")
    .attr("class", "grid")

    grid.append("g")
    .attr("class", "horizontal")
    .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)

    svg.append("text")
    .text("Edit the code below to change me!")
    .attr("y", 200)
    .attr("x", 120)
    .style("font-size", 36)
    .style("font-family", "monospace")

    </script>
    </body>