28:null 29:["$","title",null,{"children":"Gift Exchange | David Kirkby | Observable"}] 2e:T525,function generateExchange(names, numGifts, vetoGroups, {randomSeed}) { const rng = d3.randomLcg(randomSeed); const R = d3.randomInt.source(rng); const n = names.length; const order = d3.shuffler(rng)(d3.range(n)); const givesTo = Array.from({length: n}, i => [ ]); const getsFrom = Array.from({length: n}, i => [ ]); for(let giver=0; giver < n; ++giver) { for(let j=0; j < numGifts; ++j) { const remaining = d3.range(n) .filter(i => { if(i == giver) return false; if(givesTo[giver].includes(i)) return false; if(getsFrom[i].length == numGifts) return false; for(const group of vetoGroups) { if(group.includes(names[giver]) && group.includes(names[i])) return false; } return true; }); if(remaining.length == 0) throw new Error("This seed does not have a solution. Try a different one."); const receiver = remaining[R(remaining.length)()]; givesTo[giver].push(receiver); getsFrom[receiver].push(giver); } } // Check constraints. for(let i=0; i < n; ++i) { if(!givesTo[i].length == numGifts) throw new Error("Failed givesTo constraint"); if(!getsFrom[i].length == numGifts) throw new Error("Failed getsFrom constraint"); } return { order, givesTo, getsFrom }; }2f:T425,function computeMotion(exchange, rampSteps) { // Build a flat list of targets that the wheel will visit. const {order, givesTo, getsFrom} = exchange; const targets = [ { giver:order[0], target:order[0] } ]; order.forEach(giver => givesTo[giver].forEach(target => targets.push({ giver, target }))); // Build a list of motion for each transition between targets. const n = order.length; const steps = [ ]; const R = tabulateRamp(rampSteps).map(x => n * x); const V0 = R[0]; for(let i = 0; i < targets.length - 1; ++i) { const {target:from} = targets[i], {giver, target:to} = targets[i + 1]; const dist = (to > from) ? to - from : to + n - from; const spinSteps = Math.round(dist / V0); const spinV = dist / spinSteps; const deltas = new Array(spinSteps).fill(spinV).concat(R); const total = d3.sum(deltas); const final = (from + total) % n; const motion = [ from ]; for(const delta of deltas) motion.push(motion[motion.length - 1] + delta); steps.push({giver, from, to, motion}); } return steps; }30:Tde0,function* animatedWheel(names, steps, {w=1194, h=834, fontSize=85, bgLines=["GIFT", "", "EXCHANGE"]}={}) { const {round, PI} = Math; const r = 0.8 * w; const dphi = 2 * PI / names.length, dphiDeg = 360 / names.length; const svg = d3.create("svg") .attr("viewBox", [0, 0, w, h]) .style("font", "10px sans-serif"); const g0 = svg.append("g") .attr("transform", `translate(${w-r}, ${h/2})`) .attr("fill", "black") .attr("text-anchor", "middle") .attr("font-size", fontSize) .attr("font-weight", "bold"); const g = g0.append("g") .attr("transform", `rotate(${90-dphiDeg/2})`); g.append("circle") .attr("r", r) .attr("fill", "silver"); const bg = g.append("g") .attr("font-size", 2.5 * fontSize) .attr("fill", "#ccc"); bg.selectAll("text") .data(bgLines) .join("text") .attr("dy", (_,i) => `${(i - (bgLines.length - 1)/2) + 0.35}em`) .text(line => line); const centerText = g0.append("text") .attr("dy", "0.35em") .text("???"); const arrow = g0.append("text") .attr("transform", `translate(${0.38*r},0)`) .attr("dy", "0.35em") .text("?") .style("cursor", "pointer") .on("click", clickHandler); const slots = g.append("g"); const recvrNames = g.append("g") .attr("text-anchor", "middle") .attr("font-size", fontSize) .attr("font-weight", "bold") .style("display", "none"); const r1 = 0.45 * r, r2 = 0.98 * r, rtext = (r1 + r2) / 2; for(let i = 0; i < names.length; ++i) { const arcer = d3.arc() .startAngle(i * dphi) .endAngle((i + 1) * dphi) .innerRadius(r1) .outerRadius(r2) .cornerRadius(8) .padAngle(PI / 180); slots.append("path") .attr("fill", nameColor(i)) .attr("d", arcer()); } for(let i = 0; i < names.length; ++i) { recvrNames.append("text") .attr("fill", "white") .attr("dy", "0.35em") .attr("transform", `rotate(${180/PI*(i+0.5)*dphi - 90}) translate(${rtext},0)`) .text(names[i]); } function setIndex(idx) { const angle = 90 - dphiDeg * (idx + 0.5); g.attr("transform", `rotate(${angle})`); } setIndex(steps[0].from); function setGiver(idx) { centerText.text(names[idx]); } let currentStep = 0, nextStep = currentStep; let currentGiver = steps[0].giver, nextGiver = currentGiver; setGiver(currentGiver); function clickHandler() { if(nextStep > currentStep) { console.log("Ignoring click while busy"); } else if(nextStep == steps.length) { console.log("All done."); } else { nextGiver = steps[nextStep].giver; if(nextGiver != currentGiver) { setGiver(nextGiver); arrow.text("?"); recvrNames.style("display", "none"); currentGiver = nextGiver; } else if(currentStep < steps.length) { nextStep = currentStep + 1; console.log(`Start advancing to step ${nextStep}...`); } } } while(true) { if(nextStep > currentStep) { arrow.text("⇨").style("cursor", "wait"); recvrNames.style("display", "block"); const {giver, from, to, motion} = steps[currentStep]; console.log(`Advancing the wheel from ${from} to ${to} in ${motion.length} steps...`); for(const idx of motion) { setIndex(idx); yield svg.node(); } console.log(`Done advancing to step ${nextStep}`); arrow.style("cursor", "pointer"); currentStep = nextStep; } else { yield svg.node(); } } }31:[] 2c:{"id":"bd520786886bab60","slug":"gift-exchange","title":"Gift Exchange","thumbnail":"916e0c29ecf67d00cd40135d4834aec00f518d1920cdd48d1f774da719147f86","access_level":"public","create_time":"$D2022-12-31T16:38:40.813Z","update_time":"$D2023-01-01T15:00:13.751Z","view_time":null,"first_public_time":"$D2022-12-31T18:33:43.468Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"82762c8496f321fe","login":"dkirkby","name":"David Kirkby","avatar_url":"https://avatars-next.observableusercontent.com/5b2c32ac920111620eb8369d40c1cd0353430f60391a4e246bc9822ab20f6f2f","tier":"starter_2024"},"version":222,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"b31e222c78b643d7","login":"dkirkby","name":"David Kirkby","avatar_url":"https://avatars-next.observableusercontent.com/5b2c32ac920111620eb8369d40c1cd0353430f60391a4e246bc9822ab20f6f2f","tier":null}],"members":[{"type":"individual","id":"b31e222c78b643d7","login":"dkirkby","name":"David Kirkby","avatar_url":"https://avatars-next.observableusercontent.com/5b2c32ac920111620eb8369d40c1cd0353430f60391a4e246bc9822ab20f6f2f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"f06c4a16f464ed7b","slug":"fun","title":"Fun","owner":{"id":"82762c8496f321fe","login":"dkirkby","name":"David Kirkby"}},"type":"notebook","body":{"title":"Gift Exchange","cells":[{"id":0,"value":"# Gift Exchange\n\nGenerate a random gift exchange between a group of people and animate the results. Here is an example where the [main Game of Throne characters](https://en.wikipedia.org/wiki/List_of_Game_of_Thrones_characters) each give and receive three gifts, but never with someone with the same last name. Click on the question mark to reveal the first recipient. Repeated clicks cycle through the whole sequence.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":170,"value":"wheel = animatedWheel(names, motionSteps, {fontSize:50})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"## Configuration\n\nSpecify the names of people exchanging gifts, the number of gifts each gives and receives, and any groups that should not give to each other:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"names = [\n // main GOT characters who appear in at least 4 seasons based on\n // https://en.wikipedia.org/wiki/List_of_Game_of_Thrones_characters\n \"Jaime Lannister\",\n \"Cersei Lannister\",\n \"Daenerys Targaryen\",\n \"Jorah Mormont\",\n \"Jon Snow\",\n \"Sansa Stark\",\n \"Arya Stark\",\n \"Theon Greyjoy\",\n \"Bran Stark\",\n \"Sandor Clegane\",\n \"Tyrion Lannister\",\n \"Petyr Baelish\",\n \"Davos Seaworth\",\n \"Samwell Tarly\",\n \"Stannis Baratheon\",\n \"Melisandre\",\n \"Bronn\",\n \"Varys\",\n \"Margaery Tyrell\",\n \"Tywin Lannister\",\n \"Tormund Giantsbane\",\n \"Brienne of Tarth\",\n \"Gilly\",\n \"Missandei\",\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"numGifts = 3","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"vetoGroups = [\n [ \"Jaime Lannister\", \"Cersei Lannister\", \"Tyrion Lannister\", \"Tywin Lannister\" ],\n [ \"Sansa Stark\", \"Arya Stark\", \"Bran Stark\" ],\n]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"## Randomized Exchange\n\nAn exchange is a table with one row per person giving and one column per gift recipient, for example:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":150,"value":"table = html`\n ${exchange.order.map(i => html.fragment`\n \n \n ${exchange.givesTo[i].map(j => html.fragment`\n `)}`)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"A valid exchange must satisfy several constraints:\n - Row constraints: you cannot give to yourself or to the same person twice. Some specified combinations may also be vetoed.\n - Column constraints: each person must receive exactly the same number of gifts, specified here by `numGifts = ${numGifts}`.\n\nA random seed determines which exchange we generate but not all seeds satisfy the constraints, so you might need to try more than one:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":29,"value":"generateExchange(names, numGifts, vetoGroups, {randomSeed:1})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"exchange = generateExchange(names, numGifts, vetoGroups, {randomSeed:2})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"## Animated Wheel\n\nAlthough the sequence of gift exchanges is generated in advance, it can be fun to reveal it with an animated spinning wheel (even though spinning a real wheel would not satisfy our constraints). First, pre-tabulate a gradual slowing down of the wheel over one complete rotation using a sigmoid function for the angular speed:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":47,"value":"function rampFunction(x) {\n return 1 - (1 + Math.sin((x - 0.5) * Math.PI)) / 2;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":49,"value":"function tabulateRamp(rampSteps) {\n const dx = d3.range(rampSteps).map(i => rampFunction(i / rampSteps));\n const sum = d3.sum(dx);\n return dx.map(x => x / sum);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"viewof rampSteps = Inputs.range([100, 200], {label: \"Number of spin-down steps\", step: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"rampPlot = {\n const angles = [0].concat(...d3.cumsum(tabulateRamp(rampSteps).map(x => 360 * x)));\n return Plot.plot({\n x: { label: \"Time step (sec)\" },\n y: { label: \"Rotation angle (deg)\" },\n marks: [\n Plot.frame(),\n Plot.dot(angles, { x: (_,i) => i/60, y: dtheta => dtheta, r:1 }),\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"Increasing the number of spin-down steps lowers the initial angular speed, which we hold constant for up to one revolution before the final spin down revolution:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":94,"value":"omegaPlot = {\n const omega = tabulateRamp(rampSteps).map(x => 360 * x);\n return Plot.plot({\n x: { label: \"Time step (sec)\" },\n y: { label: \"Rotation speed (deg / sec)\" },\n marks: [\n Plot.frame(),\n Plot.dot(omega, { x: (_,i) => i / 60, y: w => 60 * w, r:1 }),\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"We can now pre-tabulate the angular motion of the wheel over the full sequence of gift exchanges for efficient animation. Here are the first 5 spins for our example exchange:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":117,"value":"motionPlot = {\n const n = names.length;\n let angles = [ ];\n motionSteps.slice(0,5).forEach(({motion}) => {\n const update = motion.map(a => (a % n) / n * 360);\n angles = angles.concat(...update);\n });\n return Plot.plot({\n x: { label: \"Time step (sec)\" },\n y: { label: \"Rotation Angle (deg)\" },\n marks: [\n Plot.frame(),\n Plot.dot(angles.slice(0,5000), { x: (_,i) => i / 60, y: a => a, r:1 }),\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"motionSteps = computeMotion(exchange, rampSteps)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"## Wheel Graphics\n\nUse SVG to draw the wheel since this allows us to rotate the wheel by only changing a single value in the resulting document, which specifies the wheel rotation angle via a transform attribute. We also specify a cyclical color scheme to use around the wheel. See the wheel in action at the top of this document.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":157,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"function nameColor(idx) {\n return d3.interpolateSinebow(idx / (names.length - 1));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":153,"value":"html = htl.html","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2d:"$2c:body"

${names[i]}

→

${names[j]}