31:Taf8,function inset (b, or = o) { const off = (p, dx, dy) => ({ x: p.x + dx*or, y: p.y + dy*or }); const t = []; let lastp = null; for (let i = 0; i < b.length; i++) { const s1 = b[i]; // :: { from: { x,y }, to: { x,y }, side } const s2 = b[(i+1)%b.length]; // :: { from: { x,y }, to: { x,y }, side } if (s1.side == 'left' && s2.side == 'left') { t.push({ from: lastp, to: lastp = off(s2.to, 1, 1), }); } else if (s1.side == 'left' && s2.side == 'bottom') { t.push({ from: lastp, to: lastp = off(s1.to, 1, 1), }); t.push({ from: lastp, to: lastp = off(s2.to, 1, 1), }); } else if (s1.side == 'left' && s2.side == 'top') { t.push({ from: lastp, to: lastp = off(s1.to, 1, 1), color: '#c00', }); t.push({ from: lastp, to: lastp = off(s2.to, -1, 1), color: '#c00', }); } else if (s1.side == 'right' && s2.side == 'right') { t.push({ from: lastp, to: lastp = off(s2.to, -1, -1), }); } else if (s1.side == 'right' && s2.side == 'bottom') { t.push({ from: lastp, to: lastp = off(s1.to, -1, -1), }); t.push({ from: lastp, to: lastp = off(s2.to, 1, -1), }); } else if (s1.side == 'right' && s2.side == 'top') { t.push({ from: lastp, to: lastp = off(s1.to, -1, 1), }); t.push({ from: lastp, to: lastp = off(s2.to, -1, 1), }); } else if (s1.side == 'top' && s2.side == 'top') { t.push({ from: lastp, to: lastp = off(s2.to, -1, 1), }); } else if (s1.side == 'top' && s2.side == 'right') { t.push({ from: lastp, to: lastp = off(s1.to, -1, 1), }); t.push({ from: lastp, to: lastp = off(s2.to, -1, -1), }); } else if (s1.side == 'top' && s2.side == 'left') { t.push({ from: lastp, to: lastp = off(s1.to, 1, 1), }); t.push({ from: lastp, to: lastp = off(s2.to, 1, 1), }); } else if (s1.side == 'bottom' && s2.side == 'bottom') { t.push({ from: lastp, to: lastp = off(s2.to, 1, -1), }); } else if (s1.side == 'bottom' && s2.side == 'left') { t.push({ from: lastp, to: lastp = off(s1.to, 1, -1), }); t.push({ from: lastp, to: lastp = off(s2.to, 1, 1), }); } else if (s1.side == 'bottom' && s2.side == 'right') { t.push({ from: lastp, to: lastp = off(s1.to, -1, -1), }); t.push({ from: lastp, to: lastp = off(s2.to, -1, -1), }); } } t[0].from = lastp; return t; }32:T905,A = { const W = grid[0].length; const H = depth; const areas = []; const lookup = []; for (let y = 0; y < depth; y++) { lookup[y] = []; } function discover (x, y) { if (grid[y][x] && !lookup[y][x]) { const area = []; const boundary_lookup = []; for (let y = 0; y < depth + 1; y++) { boundary_lookup[y] = []; } areas.push(area); let b0; const todo = [ {x,y} ]; while (todo.length > 0) { var { x,y } = todo.pop(); area.push({ x,y }); lookup[y][x] = area; if (x-1 >= 0 && grid[y][x-1]) { if (!lookup[y][x-1]) todo.push({ x: x-1, y }); } else { // left bound b0 = boundary_lookup[y+1][x] = { x, y, side: 'left' }; } if (x+1 < W && grid[y][x+1]) { if (!lookup[y][x+1]) todo.push({ x: x+1, y }); } else { // right bound b0 = boundary_lookup[y][x+1] = { x: x+1, y: y+1, side: 'right' }; } if (y-1 >= 0 && grid[y-1][x]) { if (!lookup[y-1][x]) todo.push({ x, y: y-1 }); } else { // top bound b0 = boundary_lookup[y][x] = { x: x+1, y, side: 'top' }; } if (y+1 < H && grid[y+1][x]) { if (!lookup[y+1][x]) todo.push({ x, y: y+1 }); } else { // bottom bound b0 = boundary_lookup[y+1][x+1] = { x, y: y+1, side: 'bottom' }; } } area.boundary = []; // area.b0 = b0; // area.boundary_lookup = boundary_lookup; let it = 0; for (let b = b0; (area.boundary.length == 0 || !(b0.x == b.x && b0.y == b.y)) && (it++ < 1000); b = boundary_lookup[b.y][b.x]) { area.boundary.push({ from: b, to: boundary_lookup[b.y][b.x], side: boundary_lookup[b.y][b.x].side, }); } } } for (var y = 0; y < H; y++) { for (var x = 0; x < W; x++) { discover(x, y); } } return { areas, lookup }; const root = html`${grid.map((row,y) => ` ${row.map((b,x) => ` `).join(' ')} `).join('\n')}

${b ? String.fromCharCode(65 + areas.indexOf(lookup[y][x])) : ''}

`; root.value = { areas, lookup }; return root; }33:T886,viewof A2 = { const t0 = performance.now(); const k = k2; const grid = g2; const depth = d2; const W = grid[0].length; const H = depth; const areas = []; const lookup = []; for (let y = 0; y < depth; y++) { lookup[y] = []; } function discover (x, y) { if (grid[y][x] && !lookup[y][x]) { const area = []; const boundary_lookup = []; for (let y = 0; y < depth + 1; y++) { boundary_lookup[y] = []; } areas.push(area); let b0; const todo = [ {x,y} ]; while (todo.length > 0) { var { x,y } = todo.pop(); area.push({ x,y }); lookup[y][x] = area; if (x-1 >= 0 && grid[y][x-1]) { if (!lookup[y][x-1]) todo.push({ x: x-1, y }); } else { // left bound b0 = boundary_lookup[y+1][x] = { x, y, side: 'left' }; } if (x+1 < W && grid[y][x+1]) { if (!lookup[y][x+1]) todo.push({ x: x+1, y }); } else { // right bound b0 = boundary_lookup[y][x+1] = { x: x+1, y: y+1, side: 'right' }; } if (y-1 >= 0 && grid[y-1][x]) { if (!lookup[y-1][x]) todo.push({ x, y: y-1 }); } else { // top bound b0 = boundary_lookup[y][x] = { x: x+1, y, side: 'top' }; } if (y+1 < H && grid[y+1][x]) { if (!lookup[y+1][x]) todo.push({ x, y: y+1 }); } else { // bottom bound b0 = boundary_lookup[y+1][x+1] = { x, y: y+1, side: 'bottom' }; } } area.boundary = []; // area.b0 = b0; // area.boundary_lookup = boundary_lookup; let it = 0; for (let b = b0; (area.boundary.length == 0 || !(b0.x == b.x && b0.y == b.y)) && (it++ < 1000); b = boundary_lookup[b.y][b.x]) { area.boundary.push({ from: b, to: boundary_lookup[b.y][b.x], side: boundary_lookup[b.y][b.x].side, }); } } } for (var y = 0; y < H; y++) { for (var x = 0; x < W; x++) { discover(x, y); } } return timed({ areas, lookup }, performance.now() - t0, '(3) Discovered areas & boundaries'); }34:T744,viewof segments = { return md`*(What it used to be)*`; const M = N-1 const mywidths = widths.slice(1).map(line => line.slice(1)); const map = theta => theta * 3/4 + tau * 3/8; const segments = mywidths.map((line, j) => { const r = 200 * (1 - (j+.1)/mywidths.length); const r2 = 200 * (1 - (j+.9)/mywidths.length); // next var W = 0; const segs = line.map((w,i) => { const startAngle = map(W/M * tau); W += w; const endAngle = map(W/M * tau); if (seq[i+1] == 1) return `M ${r * Math.cos(endAngle)} ${r * Math.sin(endAngle)}`; const largeAngleFlag = (endAngle - startAngle <= tau/2) ? 0 : 1; return `M ${r * Math.cos(startAngle)} ${r * Math.sin(startAngle)} A ${r} ${r} 0 ${largeAngleFlag} 1 ${r * Math.cos(endAngle)} ${r * Math.sin(endAngle)} L ${r2 * Math.cos(endAngle)} ${r2 * Math.sin(endAngle)} A ${r2} ${r2} 0 ${largeAngleFlag} 0 ${r2 * Math.cos(startAngle)} ${r2 * Math.sin(startAngle)} L ${r * Math.cos(startAngle)} ${r * Math.sin(startAngle)}`; }); segs.unshift(`M ${r * Math.cos(map(0))} ${r * Math.sin(map(0))}`); return { r, segs }; }); const root = svg``; root.value = segments; return root; }35:T40d,{return; const Sx = 15; const Sy = 20; function compute_seq_layout (seq, depth = 0, offset = 0) { seq.depth = depth; seq.offset = offset; return seq.width = seq.reduce((sum, child) => sum + compute_node_layout(child, depth, offset + sum), 0); } function compute_node_layout (node, depth = 0, offset = 0) { node.depth = depth; node.offset = offset; return node.width = node.children ? compute_seq_layout(node.children, depth + 1, offset) : 1; } compute_seq_layout(k, 0); const W = Sx * k.width; const H = Sy * depth; return svg``; }36:[] 2f:{"title":"The Kolakoski Sequence","cells":[{"id":0,"value":"md`# The Kolakoski Sequence\n\nSee the [Numberphile video](https://www.youtube.com/watch?v=co5sOgZ3XcM). I mainly just wanted to re-create the rendering from the coloring book. This is somewhat complicated, due to (1) the unioning of 2-colored areas, which have to be outlined as a whole, and (2) the subsequent in-setting of that outline. For #1, I couldn't think of anything better than to 'algorithmically discover' the various areas in the grid. As for #2, I don't think there is any clever SVG trick that can be used for this, and hence I do it 'manually'.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1780,"value":"md`The \"run-length decoding\" of a sequence ${tex`\\sigma`} is defined as ${tex.block`D(\\sigma_1\\sigma_2\\sigma_3\\dots) \\triangleq 1^{\\sigma_1}2^{\\sigma_2}1^{\\sigma_3}\\dots`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1787,"value":"function decode (seq) {\n return seq.reduce((decoding, s, i) => {\n for (var j = 0; j < s; j++) decoding.push(i%2 + 1);\n return decoding;\n }, [])\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1799,"value":"md`The Kolakoski sequence ${tex`k`} is the (unique) fixed-point of this function: ${tex.block`D(k) = k`}\nAnd it can be found simply by iteratively applying ${tex`D`} to the initial value of ${tex`12`}:\n${tex.block`\\begin{aligned}\n D(12) &= 122 \\\\\n D^2(12) &= D(122) = 12211 \\\\\n D^3(12) &= D^2(122) = D(12211) = 1221121 \\\\\n \\vdots \\\\\n D^n(12) &= k = 122112122122112\\dots \\\\\n\\end{aligned}`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1832,"value":"md`Because the sequence is the fixed-point of the decoding function, it is also the fixed-point of the corresponding runtime-length *encoding* function, i.e. it *describes itself*.\n\nBy a little trick, editing the decode function a bit and representing the digits of a sequence by singleton arrays in javascript (which are then objects and hence can take properties), we can keep track of a *tree* of iterated self-description, as follows:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1829,"value":"function decode_and_link (seq, k = 1) {\n if (k <= 0) return seq;\n \n const decoded = seq.reduce((decoding, d, i) => {\n d.children = [];\n for (var j = 0; j < d[0]; j++) {\n const child = [i%2 + 1];\n child.parent = d;\n d.children.push(child);\n decoding.push(child);\n }\n return decoding;\n }, []);\n \n return decode_and_link(decoded, k-1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1887,"value":"make_depth_slider()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1846,"value":"viewof k = {\n const k = [[1], [2]];\n decode_and_link(k, depth - 1);\n const root = html`

${display_node.seq(k)}

`;\n root.value = k;\n return root;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1860,"value":"md`Viewing this as a grid of pixels, we have:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1863,"value":"viewof grid = {\n const grid = [];\n \n function traverse (node, y = 0, x = 0) {\n if (!grid[y]) grid[y] = [];\n \n const width = node.children\n ? node.children.reduce((sum, child) => sum + traverse(child, y + 1, x + sum), 0)\n : 1\n \n for (var i = 0; i < width; i++) {\n grid[y][x + i] = (node[0] == 2);\n }\n \n return width;\n }\n \n traverse(k[1])\n \n const root = html`

${grid.slice().reverse().map(row => row.map(b => b ? '2' : ' ').join(' ')).join('\\n')}

`;\n root.value = grid.reverse();\n return root;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1865,"value":"md`And then, if we (1) discover the connected areas therein, (2) inset their borders, and (3) transform to a polar coordinate system, we get a lovely little colorable rendering:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1673,"value":"{\n const R = 200;\n //(x,y) -> (R cos(x), R sin(x))\n \n const x = p => R * (1-p.y/depth) * Math.cos(tau * (3/8 + 3/4 * p.x/grid[0].length)); // p.x*15;\n const y = p => R * (1-p.y/depth) * Math.sin(tau * (3/8 + 3/4 * p.x/grid[0].length)); // p.y*15;\n \n const W = 500;\n const H = 350;\n \n const boundaries = A.areas.map(area => inset(area.boundary));\n \n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1870,"value":"md`Play around with the parameters:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1690,"value":"viewof o = slider({ min: 0, max: .5, value: .27, step: 0.01, description: 'The inset ratio.' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1890,"value":"make_depth_slider()","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"value":"tau = 2*Math.PI","pinned":false,"hidden":false,"mode":"ojs"},{"id":1743,"value":"md`(τ for the win!)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2049,"value":"{\n const Sx = Math.min(15, width / grid[0].length);\n const Sy = 20;\n \n const W = Sx * grid[0].length;\n const H = Sy * depth;\n \n const boundaries = A.areas.map(area => inset(area.boundary));\n \n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"md``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1564,"value":"{return md`*(For testing the insetting.)*`;\n const b = A.areas[3].boundary;\n const Sx = 50;\n const Sy = 50;\n \n const W = Sx * 4;\n const H = Sy * 3;\n \n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1478,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1281,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":897,"value":"html`(CSS)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":996,"value":"display_node = treewalk({\n fnode: (node, x_children) => html`\n

\n ${x_children}\n

${node[0]}

`,\n fseq: (seq, x_nodes) => html`

${x_nodes}

`,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1028,"value":"function treewalk ({ fnode, fseq }) {\n const apply = {\n seq (seq, ...A) {\n return fseq(seq, seq.map(node => apply.node(node, ...A)), ...A);\n },\n node (node, ...A) {\n return fnode(node, apply.seq(node.children || [], ...A), ...A);\n },\n };\n return apply;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1987,"value":"md``","pinned":false,"hidden":false,"mode":"ojs"},{"id":2028,"value":"html`

A faster version

(Without the visualizations of intermediate steps.)

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1955,"value":"function timed (v, t, d = '') {\n const root = md`*time: ${t}ms*\n ${d}`;\n root.value = v;\n return root;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1942,"value":"viewof d2 = slider({ min: 0, max: 25, step: 1, value: 13 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1928,"value":"viewof k2 = {\n const k = [[1], [2]];\n const t0 = performance.now();\n decode_and_link(k, d2 - 1);\n \n return timed(k, performance.now() - t0, '(1) Constructed Kolakoski sequence tree data structure');\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1944,"value":"viewof g2 = {\n const t0 = performance.now();\n \n const grid = [];\n \n function traverse (node, y = 0, x = 0) {\n if (!grid[y]) grid[y] = [];\n \n const width = node.children\n ? node.children.reduce((sum, child) => sum + traverse(child, y + 1, x + sum), 0)\n : 1\n \n for (var i = 0; i < width; i++) {\n grid[y][x + i] = (node[0] == 2);\n }\n \n return width;\n }\n \n traverse(k2[1])\n \n return timed(grid.reverse(), performance.now() - t0, '(2) Constructed pixel grid');\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1968,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":2016,"value":"viewof o2 = slider({ min: 0, max: .5, value: .26, step: 0.01 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1973,"value":"viewof b2 = {\n const t0 = performance.now();\n \n return timed(A2.areas.map(area => inset(area.boundary, o2)), performance.now() - t0, '(4) Inset area boundaries');\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1997,"value":"{\n const R = 200;\n const depth = d2; const grid = g2;\n //(x,y) -> (R cos(x), R sin(x))\n \n const x = p => R * (1-p.y/depth) * Math.cos(tau * (3/8 + 3/4 * p.x/grid[0].length)); // p.x*15;\n const y = p => R * (1-p.y/depth) * Math.sin(tau * (3/8 + 3/4 * p.x/grid[0].length)); // p.y*15;\n \n const W = 500;\n const H = 350;\n \n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"md``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1874,"value":"function make_depth_slider () {\n const slider = html``;\n const num = html``;\n \n slider.oninput = () => (viewof depth).value = slider.valueAsNumber;\n const update = () => {\n num.innerText = slider.value = (viewof depth).value;\n };\n \n (viewof depth).addEventListener(\"input\", update);\n update();\n \n return Generators.disposable(html`

${slider} depth = ${num}

`, () => {\n (viewof depth).removeEventListener(\"input\", update);\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1876,"value":"viewof depth = new View(11)","pinned":false,"hidden":false,"mode":"ojs"},{"id":535,"value":"import { View } from '@mbostock/synchronized-views'","pinned":false,"hidden":false,"mode":"ojs"},{"id":168,"value":"import { slider } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1908,"value":"md``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1751,"value":"md`### OLD / abandoned`","pinned":false,"hidden":false,"mode":"ojs"},{"id":666,"value":"function initial_part_equal (seq_a, seq_b) {\n for (var i = 0; i < Math.min(seq_a.length, seq_b.length); i++) {\n return seq_a[i] == seq_b[i];\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1920,"value":"initial_part_equal(seq, decode(seq))","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"function kol (m) {\n const n = m//+1;\n const seq = [];\n \n for (var i = 1; seq.length < n; i++) {\n var x = seq[i-1] || i;\n if (i % 2 == 1) {\n for (var j = 0; j < x && seq.length < n; j++) seq.push(1);\n } else {\n for (var j = 0; j < x && seq.length < n; j++) seq.push(2);\n }\n }\n \n return seq//.slice(1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":540,"value":"function make_N_slider () {\n const slider = html``;\n const num = html``;\n \n slider.oninput = () => (viewof N).value = slider.valueAsNumber;\n const update = () => {\n num.innerText = slider.value = (viewof N).value;\n };\n \n (viewof N).addEventListener(\"input\", update);\n update();\n \n return Generators.disposable(html`

${slider} N = ${num}

`, () => {\n (viewof N).removeEventListener(\"input\", update);\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":538,"value":"viewof N = new View(53)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1856,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":1773,"value":"viewof seq = {\n const seq = kol(N);\n const root = md`${seq.join(', ')}…`;\n root.value = seq;\n return root;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1769,"value":"make_N_slider()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1755,"value":"widths = {\n const nextline = ws => {\n var W = 0;\n const nws = [];\n for (var i = 0; i < N && W < N; i++) {\n var w = 0;\n for (var j = 0; j < seq[i]; j++) {\n w += ws.shift() || (nws.overflow = true, 0);\n }\n W += w;\n nws.push(w);\n }\n return nws;\n };\n \n const widths = [\n (new Array(N)).fill(1),\n ];\n \n while (widths[0].length > 2) {\n widths.unshift(nextline(widths[0].slice()));\n }\n \n widths.reverse();\n \n return widths;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1760,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W36","stdlib":"1","titling":"auto"}