2e:null 2f:["$","title",null,{"children":"Penrose three coloring | Mark McClure | Observable"}] 34:T6c9,buttons = { let div = d3.create("div"); let three_button = div .append("button") .style("margin-right", "5px") .attr("class", "btn btn-quarto") .attr("id", "three_button") .text("Find three coloring") .on("click", three_color); let random_button = div .append("button") .attr("class", "btn btn-quarto") .attr("id", "random_button") .text("Randomize colors") .on("click", randomize_colors); function randomize_colors() { d3.select(tiling).selectAll("text").remove(); let new_colors = d3 .range(rhombs.length) .map(() => Math.floor(d3.randomUniform(3)())); rhombs.forEach(function (r, idx) { r.color = new_colors[idx]; }); d3.select(tiling) .selectAll("path.rhomb") .attr("fill", (d, i) => color(new_colors[i])); three_button.attr("disabled", null); random_button.attr("disabled", null); } async function three_color() { three_button.attr("disabled", true); random_button.attr("disabled", true); let colors = rhombs.map((d) => d.color); let cnt = 0; while (!check_three_color(colors)) { await Promises.delay().then(function () { colors = rhombs.map(recolor); rhombs.forEach(function (r, idx) { r.color = colors[idx]; }); d3.select(tiling) .selectAll("path.rhomb") .attr("fill", (d, i) => color(colors[i])); cnt++; }); } random_button.attr("disabled", null); // d3.select(tiling) // .append("text") // .attr("class", "responsive-stroke") // .attr("x", 0.02 * svg_width) // .attr("y", 0.04 * svg_height) // .text(`Three colored in ${cnt} generations!`); } return div.node(); }35:T428,tiling = { let xmin = 0; let xmax = phi; let ymin = -1 / phi; let ymax = 1 / phi; let svg = d3 .create("svg") .attr("viewBox", [0, 0, svg_width, svg_height]) .style("max-width", `${svg_width}px`); // .attr('width', svg_width) // .attr('height', svg_height); let x_scale = d3.scaleLinear().domain([xmin, xmax]).range([0, svg_width]); let y_scale = d3.scaleLinear().domain([ymin, ymax]).range([svg_height, 0]); let pts_to_path = d3 .line() .x(function (d) { return x_scale(d[0]); }) .y(function (d) { return y_scale(d[1]); }); svg .selectAll("path") .data(rhombs) .enter() .append("path") .attr("class", "rhomb") .attr("idx", (d, i) => i) .attr("d", function (d) { let path_string = pts_to_path(d.vertices); if (d.type == "f" || d.type == "s") { path_string = path_string + "Z"; } return path_string + "Z"; }) .attr("stroke", "black") .attr("stroke-width", 1) .attr("fill", (d) => color(d.color)); return svg.node(); }36:T657,comments = md` According to page 27 of Martin Gardner's [Penrose Tiles to Trapdoor Ciphers](https://books.google.com/books/about/Penrose_Tiles_to_Trapdoor_Ciphers.html), John Conway wondered if Penrose tiles could always be colored using only three colors in such a way that adjacent tiles never had the same color. This was [proved affirmative for Penrose Rhombs in 2000](https://www.jstor.org/stable/2589317). In 2002, I [published a stochastic algorithm](https://www.sciencedirect.com/science/article/abs/pii/S0097849302000948) that appears to do the job. This notebook implements that algorithm. The algorithm is based on a so-called [stochastic cellular automaton](https://en.wikipedia.org/wiki/Stochastic_cellular_automaton). To begin, we assign one of three possible colors to each tile randomly. Then, we allow the cellular automaton to evolve according to the following set of rules: * If the value of a cell (or tile) equals the value of a bordering cell that is closer to the origin (as measured by some arbitrary point chosen within each tile), then with 90\% probability, the cell changes value randomly to one of the other two colors. * If the value of a cell does not equal the value of a bordering cell that is closer to the origin, but does equal the value of a cell farther away from the origin, then with 10\% probability, the cell changes value. * If the value of the cell does not equal the value of any bordering cell, the cell does not change value. Note that three-colorings are stable under these rules. The hope is that three-colorings are attractive equilibria.`37:T4a0,// This is the main function that's called recursively in response to // a push of the 'Find three coloring' button. function recolor(r) { let neighbors = rhombs.filter((r2) => r.neighbors.indexOf(r2.idx) > -1); let current_color = r.color; if (neighbors.map((d) => d.color).indexOf(current_color) == -1) { return current_color; } let color_choices, new_color; if (current_color == 0) { color_choices = [1, 2]; } else if (current_color == 1) { color_choices = [0, 2]; } else if (current_color == 2) { color_choices = [0, 1]; } let choice = d3.randomUniform()(); let rnorm = norm1(r.centroid); let smaller_neighbors = neighbors.filter((r2) => norm1(r2.centroid) < rnorm); if (smaller_neighbors.map((d) => d.color).indexOf(current_color) > -1) { if (choice < 0.45) { new_color = color_choices[0]; } else if (choice < 0.9) { new_color = color_choices[1]; } else { new_color = current_color; } } else { if (choice < 0.05) { new_color = color_choices[0]; } else if (choice < 0.1) { new_color = color_choices[1]; } else { new_color = current_color; } } return new_color; }38:T11b1,// Merge the triangles into rhombs and compute the resulting adjacencies. // This is the computationally intensive portion. rhombs = { // How close two points should be to be considered the same let tol = 0.01; // A list to hold all the rhombs let rhombs = []; // We'll do a double loop (certainly, this could benefit from a QuadTree). // i will range over all the triangles; j will range from i+1 to triangles.length // Of course, if j>i but already matches with a previous triangle, we can cross // it off our list. That's the purpose of found_indices. let found_indices = []; for (let i = 0; i < triangles.length; i++) { let Ti = triangles[i]; let found = false; for (let j = i + 1; j < triangles.length; j++) { if (found_indices.indexOf(i) == -1) { let Tj = triangles[j]; // Two type a's could join to form a skinny rhomb if (Ti.type == 'a' && Tj.type == 'a') { if ( dist1(Ti.vertices[1], Tj.vertices[1]) + dist1(Ti.vertices[2], Tj.vertices[2]) < tol ) { found_indices.push(j); rhombs.push({ type: 's', vertices: [ Ti.vertices[2], Ti.vertices[0], Ti.vertices[1], Tj.vertices[0] ] }); found = true; break; } // Two type o's could join to form a fat rhomb. } else if (Ti.type == 'o' && Tj.type == 'o') { if ( dist1(Ti.vertices[0], Tj.vertices[0]) + dist1(Ti.vertices[2], Tj.vertices[2]) < tol ) { found_indices.push(j); rhombs.push({ type: 'f', vertices: [ Ti.vertices[2], Ti.vertices[1], Ti.vertices[0], Tj.vertices[1] ] }); found = true; break; } } } else { found = true; } } // We do see some triangles on the border that would match with // triangles outside the border. if (!found) { rhombs.push(Ti); } } // Make sure that all polygons (rhombs and triangles) are positively // oriented. Should speed up adjacency testing later. rhombs.forEach(function(r, idx) { // r.idx = idx; if ( r.type == 'a' && r.vertices.filter(v => Math.abs(v[1]) < tol).length == 2 ) { r.vertices.sort().reverse(); } else if (!leftOf(...r.vertices)) { r.vertices.reverse(); if (r.type == 'a') { let vv = r.vertices; r.vertices = [vv[1], vv[2], vv[0]]; } } }); // Use symmetry to extend the tiling. Note that a few of the triangles on the // bottom edge are 1/2 of a rhomb obtained after reflection. let bottom_half_rhombs = []; let upper_rhombs = []; rhombs.forEach(function(r) { let vv = r.vertices; // The half-rhombs are type 'o' or 'a'. if (r.type == 'o' || r.type == 'a') { // and their y-coordinates of the first and third vertices are zero if (Math.abs(vv[0][1]) < tol && Math.abs(vv[2][1]) < tol) { // if (vv.filter(v => Math.abs(v[1]) < tol).length == 2) { r.vertices.sort().reverse(); r.vertices.push([vv[1][0], -vv[1][1]]); r.vertices = vv; bottom_half_rhombs.push(r); } else { // Other 'o's and 'a's are treated more easily upper_rhombs.push(r); } } else { // All the 'f's and 's's are treated more easily upper_rhombs.push(r); } }); // The upper_rhombs can simply be reflected let new_rhombs = upper_rhombs.map(function(r) { let r2 = { type: r.type }; r2.vertices = r.vertices.map(([x, y]) => [x, -y]).reverse(); return r2; }); rhombs = rhombs.concat(new_rhombs); // Compute centroids and prepare the neighborhood rhombs.forEach(function(r, idx) { r.idx = idx; let x0 = d3.mean(r.vertices.map(d => d[0])); let y0 = d3.mean(r.vertices.map(d => d[1])); r.centroid = [x0, y0]; r.neighbors = []; r.color = Math.floor(d3.randomUniform(3)()); }); // Compute adjacencies for (let i = 0; i < rhombs.length; i++) { let p1 = rhombs[i].vertices; for (let j = i + 1; j < rhombs.length; j++) { let p2 = rhombs[j].vertices; if (adjacent(p1, p2)) { rhombs[i].neighbors.push(j); rhombs[j].neighbors.push(i); } } } return rhombs; }39:[] 32:{"id":"a2308cef4b6bb2e1","slug":"penrose-three-coloring","title":"Penrose three coloring","thumbnail":"e675d6ac51cb2459d32a0d32ad1b6a223816c52d5220c167263cd1429da65d54","access_level":"public","create_time":"$D2020-02-22T19:45:04.381Z","update_time":"$D2025-05-28T13:37:24.322Z","view_time":null,"first_public_time":"$D2020-02-22T21:29:22.989Z","has_unpublished_edits":null,"fork":true,"stars":30,"starred":false,"owner":{"type":"team","id":"d771c8ae812d5130","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":"starter_2024"},"version":1029,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c3301e515dd08a41","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":null}],"members":[{"type":"individual","id":"c3301e515dd08a41","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":7,"collection":{"id":"690a783fef281f79","slug":"math","title":"Math","owner":{"id":"d771c8ae812d5130","login":"mcmcclur","name":"Mark McClure"}},"type":"notebook","body":{"title":"Penrose three coloring","cells":[{"id":0,"value":"# Penrose three coloring\n\nAn implementation of [a stochastic algorithm](https://www.sciencedirect.com/science/article/abs/pii/S0097849302000948) to three color Penrose rhombs.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"topmatter","database":"$undefined"},{"id":793,"value":"viewof n = {\n let choices = [\n { label: \"Just a few rhombs\", value: 7 },\n { label: \"More rhombs\", value: 11 },\n { label: \"Even more rhombs\", value: 13 },\n { label: \"Too many rhombs\", value: 15 }\n ];\n return Inputs.radio(choices, { format: (o) => o.label, value: choices[1] });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":800,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":954,"value":"md`## Comments`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":860,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":877,"value":"md`## Code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":880,"value":"md`### Coloring the tiles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":862,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":886,"value":"// Iterate until this returns true\nfunction check_three_color(colors) {\n for (let i = 0; i < colors.length; i++) {\n if (\n rhombs[i].neighbors.map(d => rhombs[d].color).indexOf(rhombs[i].color) >\n -1\n ) {\n return false;\n }\n }\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":892,"value":"// Assign the colors\nfunction color(c) {\n if (c == 0) {\n return \"#e41a1c\";\n } else if (c == 1) {\n return \"#377eb8\";\n } else {\n return \"#ffff33\";\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":894,"value":"md`### Construct the tiling\n\nThe initial stage of the construction is similar to the triangle dissection approach Described by Gardner. I implemented that in [this simpler notebook](https://observablehq.com/@mcmcclur/penrose-tiling). Significant post processing is required, though, to merge the triangles into rhombs and compute the adjacency graph of the resulting rhombic tiling. I'm certain that portion could benefit from optimization using a QuadTree. I haven't bothered with that yet as the results here are sufficient for my purposes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"triangles = {\n let triangles = [S];\n for (let i = 0; i < n.value; i++) {\n triangles = triangles.map(dissect(i)).reduce(function (a, c) {\n return a.concat(c);\n }, []);\n }\n return triangles;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":903,"value":"phi = (Math.sqrt(5) + 1) / 2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":906,"value":"// The initial triangle\nS = ({\n vertices: [[phi, 0], [phi / 2, Math.sin(Math.PI / 5)], [0, 0]],\n type: 'o'\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"function dissect(i) {\n let i_dissect = function(T) {\n let T1, T2;\n let [p, q, r] = T.vertices;\n if (T.type == 'a') {\n if (i % 2 == 0) {\n let new_point = [\n (phi * q[0] + p[0]) * (2 - phi),\n (phi * q[1] + p[1]) * (2 - phi)\n ];\n T1 = {\n vertices: [r, new_point, q],\n type: 'a'\n };\n T2 = {\n vertices: [r, new_point, p],\n type: 'o'\n };\n return [T1, T2];\n } else {\n return [T];\n }\n } else if (T.type == 'o') {\n if (i % 2 == 1) {\n let new_point = [\n (phi * r[0] + p[0]) * (2 - phi),\n (phi * r[1] + p[1]) * (2 - phi)\n ];\n T1 = {\n vertices: [r, new_point, q],\n type: 'o'\n };\n T2 = {\n vertices: [p, q, new_point],\n type: 'a'\n };\n return [T1, T2];\n } else {\n return [T];\n }\n }\n };\n\n return i_dissect;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":899,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":910,"value":"md`### A few computational utilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"function dist1(point1, point2) {\n let [a1, b1] = point1;\n let [a2, b2] = point2;\n return Math.abs(a1 - a2) + Math.abs(b1 - b2);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":541,"value":"function norm1(p) {\n return Math.abs(p[0]) + Math.abs(p[1]);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":284,"value":"function leftOf([x0, y0], [x1, y1], [x, y]) {\n return x1 * (y - y0) + x * (y0 - y1) + x0 * (y1 - y) > 0;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"function adjacent(p1, p2) {\n let tol = 0.01;\n for (let i = 0; i < p1.length; i++) {\n for (let j = p2.length; j > 0; j--) {\n if (\n dist1(p1[i], p2[j % p2.length]) +\n dist1(p1[(i + 1) % p1.length], p2[j - 1]) <\n tol\n ) {\n return true;\n }\n }\n }\n return false;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":771,"value":"// svg_width = 0.8 * width\nsvg_width = 800","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":773,"value":"svg_height = (2 * svg_width) / phi ** 2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 33:"$32:body"