2f:T4a7,# Gerrymandering Hexapolis by algorithm A few days after the [NYTimes posted a fun, educational game](https://www.nytimes.com/interactive/2022/01/27/us/politics/congressional-gerrymandering-redistricting-game-2022.html) to illustrate gerrymandering, I posted [a notebook](https://observablehq.com/@mcmcclur/setting-up-hexapolis) that sets up the game board to invite Observable programmers to try it themselves. This notebook implements a simple random search approach together with a modified flip-step algorithm that can improve the results a bit. While the code does not attain the optimum partitions, it can generate *a lot* of maps that are close. ## Hexapolis In it's initial state, just the base Hexapolis map is displayed; the "Best purple" and "Best yellow" options are disabled. When you push the "Start random redistricting" button, the notebook starts generating random partitions of Hexapolis into nine districts of equal size 15. On average, only a little more than 1 percent of these meet the legal requirement that at least two districts be predominantly minority. Once, a legal redistricting is found, the status is reported and the other map display options are enabled.30:T970,button = { reset; let button = Inputs.button(state.button_text[state.button_pushes]); d3.select(button) .select("button") .on("click", function () { let cnt = 0; state.button_pushes = (state.button_pushes + 1) % 2; d3.select(button) .select("button") .text(state.button_text[state.button_pushes]); if (state.button_pushes == 1) { let intervalID = setInterval(function () { let this_try = random_precincts(); if (this_try.minority_cnt >= 2) { all_results.push(this_try); if (this_try.purple_cnt > results[1].purple_cnt) { results[1] = this_try; d3.select(viewof show) .select("input[value='1']") .property("disabled", false); d3.select(info) .select("#purple_info") .text(`Best purple: ${this_try.purple_cnt} purple districts`) .style("background-color", "purple") .transition() .duration(500) .style("background-color", "white"); if (show.label == "Best purple") { let container = d3.select(map); container.selectAll("svg").remove(); container.append(() => setup_hexmap(this_try.precincts)); } } if (this_try.yellow_cnt > results[2].yellow_cnt) { results[2] = this_try; d3.select(viewof show) .select("input[value='2']") .property("disabled", false); d3.select(info) .select("#yellow_info") .text(`Best yellow: ${this_try.yellow_cnt} yellow districts`) .style("background-color", "yellow") .transition() .duration(500) .style("background-color", "white"); if (show.label == "Best yellow") { let container = d3.select(map); container.selectAll("svg").remove(); container.append(() => setup_hexmap(this_try.precincts)); } } } cnt++; d3.select(info).select("#cnt_info").text(`${cnt} maps sampled`); }); intervalIDs.push(intervalID); } else { intervalIDs.forEach((id) => clearInterval(id)); } }); return button; }31:T6c2,function random_precincts(optimize_color = false) { let assoc = new Map(); assoc.set(undefined, 1); let precincts; while (assoc.has(undefined)) { precincts = all_indices.map(([i, j]) => ({ id: `precinct_${i}_${j}`, i: i, j: j, color: pair_in_array([i, j], purple) ? "purple" : "yellow", minority: pair_in_array([i, j], minorities) ? true : false, neighbors: [ [i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1], [i - 1, j + 1], [i + 1, j - 1] ] .filter(([i0, j0]) => pair_in_array([i0, j0], all_indices)) .map(([i0, j0]) => `precinct_${i0}_${j0}`) })); // Failed // let so_far = get_first_15(); // so_far.forEach((p) => (p.district = 1)); let so_far = []; for (let i = 1; i <= 9; i++) { try { let boundary = get_boundary_precincts(so_far, precincts); let new15 = get15(boundary, so_far, precincts); so_far = so_far.concat(new15); new15.forEach((p) => (p.district = i)); } catch (e) { ("pass"); } } assoc = d3.group(precincts, (o) => o.district); } let groups = d3.group(precincts, (p) => p.district); let purple_cnt = 0; let yellow_cnt = 0; let minority_cnt = 0; groups.forEach(function (g) { if (g.filter((p) => p.minority).length > 7) { minority_cnt++; } let gg = d3.group(g, (p) => p.color); let p = gg.get("purple"); let y = gg.get("yellow"); if (!y) { purple_cnt++; } else if (p && p.length > y.length) { purple_cnt++; } else { yellow_cnt++; } }); let new_result = { purple_cnt, yellow_cnt, minority_cnt, precincts }; return new_result; }32:Tb9a,function improve2(input, color) { let best_result = _.cloneDeep(input); let precincts = _.cloneDeep(best_result.precincts); for (let i = 0; i < 500; i++) { let precincts0 = _.cloneDeep(precincts); let districts0 = d3.group(precincts0, (p) => p.district); let choice1 = random(1, 9)(); let district1 = districts0.get(choice1); let choice2 = random(choice1 + 1, 10)(); let district2 = districts0.get(choice2); let border12 = get_border(choice1, choice2, precincts0); if (border12.length > 0) { let border21 = get_border(choice2, choice1, precincts0); let p1 = border12[random(0, border12.length)()]; p1.district = choice2; let p2 = border21[random(0, border21.length)()]; p2.district = choice1; let new_district1 = precincts0.filter((o) => o.district == choice1); let rest1 = set_difference(precincts0, new_district1); let test1; try { test1 = get15([new_district1[0]], rest1, precincts0).length == 15; } catch { test1 = false; } let new_district2 = precincts0.filter((o) => o.district == choice2); let rest2 = set_difference(precincts0, new_district2); let test2; try { test2 = get15([new_district2[0]], rest2, precincts0).length == 15; } catch { test2 = false; } if (test1 && test2) { precincts = precincts0; let groups = d3.group(precincts, (p) => p.district); let purple_cnt = 0; let yellow_cnt = 0; let minority_cnt = 0; groups.forEach(function (g) { if (g.filter((p) => p.minority).length > 7) { minority_cnt++; } let gg = d3.group(g, (p) => p.color); let p = gg.get("purple"); let y = gg.get("yellow"); if (!y) { purple_cnt++; } else if (p && p.length > y.length) { purple_cnt++; } else { yellow_cnt++; } }); if (minority_cnt >= 2) { let new_result = { purple_cnt, yellow_cnt, minority_cnt, precincts }; new_results.push(new_result); // let indicator1 = // color == "purple" ? best_result.purple_cnt : best_result.yellow_cnt; // let indicator2 = color == "purple" ? purple_cnt : yellow_cnt; // if (indicator1 < indicator2) { // best_result = new_result; // } if ( score(best_result.precincts, color) < score(new_result.precincts, color) ) { best_result = new_result; } } } } } return best_result; function get_border(i, j, precints_in) { let groups = d3.group(precints_in, (p) => p.district); let jids = groups.get(j).map((p) => p.id); return groups .get(i) .filter((p) => _.intersection(p.neighbors, jids).length > 0); } }33:Tbc9,function improve(input, color) { let changed = false; let precincts = _.cloneDeep(input.precincts); for (let i = 0; i < random(16, 32)(); i++) { let precincts0 = _.cloneDeep(precincts); let districts0 = d3.group(precincts0, (p) => p.district); let choice1 = random(1, 9)(); let district1 = districts0.get(choice1); let choice2 = random(choice1 + 1, 10)(); let district2 = districts0.get(choice2); let border12 = get_border(choice1, choice2, precincts0); if (border12.length > 0) { let border21 = get_border(choice2, choice1, precincts0); let p1 = border12[random(0, border12.length)()]; p1.district = choice2; let p2 = border21[random(0, border21.length)()]; p2.district = choice1; let new_district1 = precincts0.filter((o) => o.district == choice1); let rest1 = set_difference(precincts0, new_district1); let test1; try { test1 = get15([new_district1[0]], rest1, precincts0).length == 15; } catch { test1 = false; } let new_district2 = precincts0.filter((o) => o.district == choice2); let rest2 = set_difference(precincts0, new_district2); let test2; try { test2 = get15([new_district2[0]], rest2, precincts0).length == 15; } catch { test2 = false; } if (test1 && test2) { precincts = precincts0; // atry.push(precincts); } } } let groups = d3.group(precincts, (p) => p.district); let purple_cnt = 0; let yellow_cnt = 0; let minority_cnt = 0; groups.forEach(function (g) { if (g.filter((p) => p.minority).length > 7) { minority_cnt++; } let gg = d3.group(g, (p) => p.color); let p = gg.get("purple"); let y = gg.get("yellow"); if (!y) { purple_cnt++; } else if (p && p.length > y.length) { purple_cnt++; } else { yellow_cnt++; } }); let original_score, new_score; // let idx = color == "purple" ? 1 : 2; if (minority_cnt >= 2) { // original_score = score(results[idx].precincts, color); // new_score = score(precincts, color); // if (original_score < new_score) { let indicator1 = color == "purple" ? input.purple_cnt : input.yellow_cnt; let indicator2 = color == "purple" ? purple_cnt : yellow_cnt; if (indicator1 < indicator2) { // results[idx].precincts = precincts; // results[idx].purple_cnt = purple_cnt; // results[idx].yellow_cnt = yellow_cnt; // results[idx].minority_cnt = minority_cnt; changed = true; } } if (changed) { return { purple_cnt, yellow_cnt, minority_cnt, precincts }; } else { return input; } // return [choice1, choice2, district1, district2]; function get_border(i, j, precints_in) { let groups = d3.group(precints_in, (p) => p.district); let jids = groups.get(j).map((p) => p.id); return groups .get(i) .filter((p) => _.intersection(p.neighbors, jids).length > 0); } }34:T41b,function score(precincts, color) { let groups = d3.group(precincts, (p) => p.district); let purple_proportions = []; let yellow_proportions = []; let minority_cnt = 0; groups.forEach(function (g) { if (g.filter((p) => p.minority).length > 7) { minority_cnt++; } let gg = d3.group(g, (p) => p.color); let p = gg.get("purple"); let y = gg.get("yellow"); if (!y) { purple_proportions.push(1); } else if (!p) { yellow_proportions.push(1); } else if (p.length > y.length) { purple_proportions.push(p.length / 15); } else { yellow_proportions.push(y.length / 15); } }); if (minority_cnt >= 2) { if (color == "yellow") { return ( yellow_proportions.length - 2 * d3.mean(yellow_proportions) + d3.mean(purple_proportions) ); } else if (color == "purple") { return ( purple_proportions.length - 2 * d3.mean(purple_proportions) + d3.mean(yellow_proportions) ); } } else { return 0; } } 35:[{"id":"eaf6b1d02c7ea6763ea62fc5f665530de040e1e332a53ebd01e0454be6c998710fcc18139a350355f279302b6ab9871119913c3e81508bfda14446e4ee1d22ac","href":"https://static.observableusercontent.com/files/eaf6b1d02c7ea6763ea62fc5f665530de040e1e332a53ebd01e0454be6c998710fcc18139a350355f279302b6ab9871119913c3e81508bfda14446e4ee1d22ac","name":"hexapolis_init.json","type":"application/json","lastModified":1644025526869.429,"size":22256},{"id":"9b59031389ba3d6130b4a9544101da8f2de66b7f9a19e76f3930189a49cdc2efdeab856ce321c2d0188223588c5ddb09d903da36a879699cff9a89ed471b2aeb","href":"https://static.observableusercontent.com/files/9b59031389ba3d6130b4a9544101da8f2de66b7f9a19e76f3930189a49cdc2efdeab856ce321c2d0188223588c5ddb09d903da36a879699cff9a89ed471b2aeb","name":"purple_distribution.svg","type":"image/svg+xml","lastModified":1644670411341.034,"size":4605},{"id":"4766f7896d118f172d7fac523d0887d483cd7a271658a2d311c855a56943cd4b15282f3a9109c442d938d52356f5d236e67254b059ec8f6cbc8336988a6e1aa3","href":"https://static.observableusercontent.com/files/4766f7896d118f172d7fac523d0887d483cd7a271658a2d311c855a56943cd4b15282f3a9109c442d938d52356f5d236e67254b059ec8f6cbc8336988a6e1aa3","name":"improved_yellow_5to6.json","type":"application/json","lastModified":1644340042232.166,"size":24016}] 2d:{"title":"Gerrymandering Hexapolis by algorithm","cells":[{"id":0,"value":"$2f","pinned":false,"hidden":false,"mode":"md"},{"id":98,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":64,"value":"viewof show = {\n reset;\n let choices = [\n { value: 0, label: \"Basemap\" },\n { value: 1, label: \"Best purple\" },\n { value: 2, label: \"Best yellow\" }\n ];\n let show = Inputs.radio(choices, {\n label: \"Map display:\",\n format: (o) => o.label,\n value: choices[0],\n disabled: true //results[1].purple_cnt == 0 || results[2].yellow_cnt == 0\n });\n d3.select(show).select(\"input[value='0']\").property(\"disabled\", false);\n return show;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":532,"value":"info = {\n reset;\n let info = d3.create(\"div\");\n\n let cnt_info = info\n .append(\"div\")\n .attr(\"id\", \"cnt_info\")\n .style(\"margin-right\", \"10px\")\n .style(\"width\", \"150px\")\n .style(\"height\", \"20px\")\n .style(\"padding\", \"5px\")\n .style(\"display\", \"inline-block\");\n let purple_info = info\n .append(\"div\")\n .attr(\"id\", \"purple_info\")\n .style(\"margin-right\", \"10px\")\n .style(\"width\", \"230px\")\n .style(\"height\", \"20px\")\n .style(\"padding\", \"5px\")\n .style(\"display\", \"inline-block\");\n let yellow_info = info\n .append(\"div\")\n .attr(\"id\", \"yellow_info\")\n .style(\"width\", \"230px\")\n .style(\"height\", \"20px\")\n .style(\"padding\", \"5px\")\n .style(\"display\", \"inline-block\");\n\n return info.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":46,"value":"map = {\n let container = d3.create(\"div\").attr(\"class\", \"container\");\n container.append(() => setup_hexmap(results[show.value].precincts));\n return container.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":613,"value":"While random, the random number generated is seeded to provide reproducible results. You can set the seed using the slider below:","pinned":false,"hidden":false,"mode":"md"},{"id":528,"value":"viewof s = (reset, Inputs.range([0, 1], { step: 0.000001, label: \"Seed:\" }))","pinned":false,"hidden":false,"mode":"ojs"},{"id":567,"value":"viewof reset = {\n let reset = Inputs.button(\"Reset\");\n d3.select(reset).on(\"click\", function () {\n intervalIDs.forEach((id) => clearInterval(id));\n });\n return reset;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":618,"value":"When using the default seed, the first legal map is found after 27 iterations. The purple map is subsequently improved to 7 purple districts after around 270 iterations. the yellow map improves to 4 yellow districts after around 330 iterations and then again to 5 at around 1350 iterations. The purple map doesn't improve again until over 4000 iterations.\n\nChanging the seed, of course, changes the timing and order of these events.","pinned":false,"hidden":false,"mode":"md"},{"id":641,"value":"## Further analysis\n\nNote that all the legal results are stored in an array called `all_results`, which allows us to analyze the results a bit. For example, a run of 108610 samples produced a legal map just under 1% of the time. Of those 1055 maps, though, only 525 were unique resulting in an overall success rate of around 0.48%. A distribution of the number of purple districts for those 525 unique, legal maps looks something like so:","pinned":false,"hidden":false,"mode":"md"},{"id":891,"value":"FileAttachment(\"purple_distribution.svg\").image()\n\n// Plot.plot({\n// y: { grid: true },\n// marks: [\n// Plot.barY(\n// all_results,\n// Plot.groupX({ y: \"proportion\" }, { x: \"purple_cnt\" })\n// ),\n// Plot.ruleY([0])\n// ]\n// })","pinned":false,"hidden":false,"mode":"ojs"},{"id":914,"value":"Thus, the technique most often produces a map with 6 purple districts. The most \"fair\" type of map (with 5 purple districts) is generated only about 24% of the time. It appears that the technique is unlikely to ever achieve the optimum yellow map with only 2 purple districts.\n\nYou can also visualize any of the maps in list using the `setup_hexmap` function. For example, here's how to visualize the most recently generated map:","pinned":false,"hidden":false,"mode":"md"},{"id":1142,"value":"{\n if (all_results.length > 0) {\n return setup_hexmap(all_results.slice(-1)[0].precincts);\n } else {\n return \"Re-execute the code block below (after some legal maps have been generated) to see the most recently generated districts.\";\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":902,"value":"## Improving existing maps\n\nAfter over a hundred thousand runs generating over 500 distinct, legal maps, the best purple district I've seen generated contained 8 purple districts - one short of the optimal 9. The yellow situation is even worse, as the best legal map I've seen generated contains 5 yellow districts - two short of the the optimal 7.","pinned":false,"hidden":false,"mode":"md"},{"id":1632,"value":"unique_groups = {\n let groups = d3.group(\n all_results, // .filter((o) => o.minority_cnt >= 2),\n (o) => o.yellow_cnt\n );\n let grouped_unique = new Map();\n let keys = Array.from(groups.keys()).sort();\n keys.forEach((k) =>\n grouped_unique.set(\n k,\n _.uniqBy(groups.get(k), districts_to_unique_id).slice(0, 239)\n )\n );\n return grouped_unique;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1646,"value":"improve2(unique_groups.get(4)[0], \"purple\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1199,"value":"{\n if (improved) {\n return setup_hexmap(improved.precincts);\n } else {\n return setup_hexmap(\n (await FileAttachment(\"improved_yellow_5to6.json\").json()).precincts\n );\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1665,"value":"improved","pinned":true,"hidden":false,"mode":"ojs"},{"id":1268,"value":"// setup_hexmap(all_results[0].precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1308,"value":"// all_results.slice(0, 2).map(async function (r) {\n// if (r.purple_cnt > r.yellow_cnt) {\n// let improved = await improve_more(r, \"purple\", 200);\n// if (improved.purple_cnt > r.purple_cnt) {\n// // all_results.push(improved);\n// return improved;\n// }\n// }\n// })","pinned":true,"hidden":false,"mode":"ojs"},{"id":1403,"value":"// setup_hexmap(five_to_six[14].precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1444,"value":"setup_hexmap(five_to_six[12].precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1500,"value":"new_results","pinned":true,"hidden":false,"mode":"ojs"},{"id":1441,"value":"new_results = []","pinned":true,"hidden":false,"mode":"ojs"},{"id":1567,"value":"five_to_six.filter((o) => o.yellow_cnt == 6)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1570,"value":"seven_to_eight.filter((o) => o.purple_cnt == 8)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1280,"value":"// seven_to_eight = Promise.all(\n// unique_groups\n// .get(3)\n// .slice(0, 40)\n// .map((r) =>\n// r.purple_cnt > r.yellow_cnt\n// ? improve2(r, \"purple\")\n// : improve2(r, \"yellow\")\n// )\n// )\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":1627,"value":"setup_hexmap(seven_to_eight[1].precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1532,"value":"unique_groups","pinned":true,"hidden":false,"mode":"ojs"},{"id":1245,"value":"## Code","pinned":false,"hidden":false,"mode":"md"},{"id":1195,"value":"improved = {\n if (results[1].precincts) {\n return improve_more(results[2], \"yellow\", 500);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1233,"value":"// This file contains just the initial map and dummy yellow and\n// purple maps that will be overwritten by the code.\nresults = (reset, FileAttachment(\"hexapolis_init.json\").json())","pinned":true,"hidden":false,"mode":"ojs"},{"id":1229,"value":"all_results = (reset, [])\n\n// all_results = FileAttachment(\"five_thirty_eight.json\").json()","pinned":true,"hidden":false,"mode":"ojs"},{"id":933,"value":"function districts_to_unique_id(p) {\n let districts = d3.group(p.precincts, (o) => o.district);\n return d3\n .range(1, 10)\n .map((i) =>\n districts\n .get(i)\n .map((o) => [o.i, o.j])\n .sort()\n )\n .sort()\n .flat(2)\n .map((i) => (i < 10 ? `0${i}` : `${i}`))\n .join(\"\");\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1624,"value":"all_results","pinned":true,"hidden":false,"mode":"ojs"},{"id":1330,"value":"d3.sum(Array.from(unique_groups.values()).map((a) => a.length))","pinned":true,"hidden":false,"mode":"ojs"},{"id":1554,"value":"Array.from(unique_groups.values()).flat()","pinned":true,"hidden":false,"mode":"ojs"},{"id":270,"value":"state = (reset,\n{\n button_pushes: 0,\n button_text: [\"Start random redistricting\", \"Stop random redistricting\"]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":223,"value":"intervalIDs = []","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":1063,"value":"results","pinned":true,"hidden":false,"mode":"ojs"},{"id":28,"value":"function get_boundary_precincts(deleted, precincts) {\n let remaining = set_difference(precincts, deleted);\n let deleted_ids = deleted.map((o) => o.id);\n return remaining.filter(\n (o) =>\n o.neighbors.length < 6 ||\n _.intersection(\n deleted_ids,\n o.neighbors.map((o) => o.id)\n ).length > 0\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1548,"value":"get15([all_precincts[3]], [], all_precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":12,"value":"function get15(start, avoid, all_precincts) {\n let precincts_left = set_difference(all_precincts, avoid);\n let precincts_start = set_difference(start, avoid);\n // let output = [precincts_start[random(0, precincts_start.length)()]];\n let output = [random_choice(precincts_start)];\n //let output = [random_choice(precincts_left)];\n\n let cnt = 0;\n while (output.length < 15 && cnt++ < 16) {\n let neighbors = set_difference(\n get_all_neighbors(output, all_precincts),\n avoid\n );\n output = output.concat(neighbors);\n if (output.length > 15) {\n console.log(output.length);\n output = output.slice(0, 15);\n } else if (cnt > 12) {\n throw \"Not found\";\n }\n }\n return output;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1172,"value":"async function improve_more(input, color, n) {\n let current = _.cloneDeep(input);\n for (let i = 0; i < n; i++) {\n await Promises.delay().then(function () {\n let this_try = improve(current, color);\n let indicator1 =\n color == \"purple\" ? current.purple_cnt : current.yellow_cnt;\n let indicator2 =\n color == \"purple\" ? this_try.purple_cnt : this_try.yellow_cnt;\n if (indicator1 < indicator2) {\n current = this_try;\n current.improvement_iterations = i;\n }\n });\n }\n return current;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1394,"value":"// setup_hexmap(all_results[2].precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1380,"value":"// setup_hexmap(atry.precincts)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1432,"value":"console.log(\"-----\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1374,"value":"// atry = improve2(all_results[3], \"yellow\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1187,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":997,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":972,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":969,"value":"// Version that generates crazier shapes but never seems to\n// generate 9 separate districts\nfunction get_first_15() {\n // let precincts_left = set_difference(all_precincts, avoid);\n // let precincts_start = set_difference(start, avoid);\n // let output = [precincts_start[random(0, precincts_start.length)()]];\n // let output = [random_choice(precincts_start)];\n let output = [random_choice(all_precincts)];\n let cnt = 0;\n while (output.length < 15 && cnt++ < 16) {\n let neighbors = get_all_neighbors(output, all_precincts);\n // console.log(neighbors);\n output.push(random_choice(neighbors));\n if (output.length > 15) {\n output = output.slice(0, 15);\n } else if (cnt > 16) {\n throw \"Not found\";\n }\n }\n return output;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"function get_all_neighbors(input_precincts, all_precincts) {\n let inputs_ids = input_precincts.map((o) => o.id);\n let all_neighbor_ids = input_precincts\n .map((o) => o.neighbors)\n .flat()\n .filter((id) => inputs_ids.indexOf(id) == -1);\n let all_neighbors = Array.from(new Set(all_neighbor_ids)).map(\n (id) => all_precincts.filter((o) => o.id == id)[0]\n );\n\n return all_neighbors;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":32,"value":"function set_difference(in_set, out_set) {\n return in_set.filter((o) => out_set.map((p) => p.id).indexOf(o.id) == -1);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"function pair_in_array([i, j], A) {\n return _.findIndex(A, (pair) => pair[0] == i && pair[1] == j) > -1;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":20,"value":"function random_choice(list) {\n let c = random(0, list.length)();\n return list[c];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"random = {\n reset;\n let random = d3.randomInt;\n let source = d3.randomLcg(s);\n random = random.source(source);\n return random;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":26,"value":"import {\n all_indices,\n purple,\n yellow,\n minorities,\n setup_hexmap,\n all_precincts\n} from \"@mcmcclur/setting-up-hexapolis\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":3,"value":"polygonClipping = require(\"polygon-clipping\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1663,"value":"all_results","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}