2d:null 2e:["$","title",null,{"children":"Four-color world map with Clingo | Fil | Observable"}] 33:T73c,// https://observablehq.com/@mbostock/cheysson-color-palettes patterns = () => svg` `34:[] 31:{"id":"9add498ba8d9f403","slug":"4-color-clingo","title":"Four-color world map with Clingo","thumbnail":"7d7d73b2bdd985fd27696d4ae783baf3dd573274dd3cfdf302a94d0dfdb56f86","access_level":"public","create_time":"$D2021-04-11T11:10:46.320Z","update_time":"$D2024-07-11T17:34:41.706Z","view_time":null,"first_public_time":"$D2021-04-11T12:56:22.465Z","fork":{"id":"587493f9d9532237","slug":"clingo","title":"Hello Clingo","owner":{"id":"1765d529f9f48b74","login":"cmudig","name":"CMU Data Interaction Group"}},"stars":6,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":494,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"a80e17434f44ee0d","slug":"geo","title":"Geo","owner":{"id":"da2a32154638c457","login":"fil","name":"Fil"}},"type":"notebook","body":{"title":"Four-color world map with Clingo","cells":[{"id":0,"value":"md`# Four-color world map with Clingo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":278,"value":"map = {\n const features = topojson.feature(world, {\n type: \"GeometryCollection\",\n geometries\n });\n const projection = world.objects.countries\n ? d3.geoBertin1953()\n : d3.geoAlbersUsa();\n const height = width * 0.7;\n const svg = d3.create(\"svg\").attr(\"viewBox\", [0, 0, width, height]);\n const path = d3.geoPath(\n projection.fitExtent(\n [\n [10, 10],\n [width - 10, height - 10]\n ],\n features\n )\n );\n svg.append(patterns);\n svg\n .append(\"g\")\n .style(\"stroke\", \"#333\")\n .style(\"stroke-width\", 0.5)\n .selectAll()\n .data(features.features)\n .join(\"path\")\n .attr(\"d\", path)\n .style(\"fill\", color);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":422,"value":"viewof topo = Inputs.select(\n new Map([\n [\n \"110m\",\n \"https://cdn.jsdelivr.net/npm/visionscarto-world-atlas@0.1.0/world/110m.json\"\n ],\n [\n \"50m\",\n \"https://cdn.jsdelivr.net/npm/visionscarto-world-atlas@0.1.0/world/50m.json\"\n ],\n [\"US States\", \"https://cdn.jsdelivr.net/npm/us-atlas@3/states-10m.json\"],\n [\"US Counties\", \"https://cdn.jsdelivr.net/npm/us-atlas@3/counties-10m.json\"]\n ]),\n { label: \"topology source\" }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"viewof n = Inputs.select([3, 4, 5, 6, 9], {\n label: \"number of colors\",\n value: 4\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":439,"value":"viewof colorType = Inputs.radio([\"textures\", \"fills\"], {\n label: \"colors\",\n value: \"textures\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"viewof program = Inputs.textarea({\n label: \"Clingo program:\",\n width: \"100%\",\n rows: 40,\n value: `% Number of colors to use\n#const n = ${n}.\n\n% Enumerate possible colors for each node\n{ color(X,1..n) } = 1 :- node(X).\n\n% Constraint: two connected countries can't have the same color\n:- edge(X,Y), color(X,C), color(Y,C).\n\n% Nodes\nnode(${edges\n .map((d, i) => (d.length ? `${i}` : \"\"))\n .filter((d) => d)\n .join(\";\")}).\n\n% (Directed) Edges\n${edges\n .flatMap(\n (d, i) => (\n (d = d.filter((j) => j !== i)),\n d.length ? `edge(${i},(${d.join(\";\")})).` : \"\"\n )\n )\n .filter((d) => d)\n .join(\"\\n\")}\n\n% Return\n#show color/2.`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":377,"value":"---\n\nHuge thanks to Dominik Moritz for the “[Hello, Clingo](https://observablehq.com/@cmudig/clingo)” notebook. See also this map colored by [a simpler algorithm](https://observablehq.com/@mbostock/map-coloring) (9 colors), and Éric Mauvière’s [implementation](https://observablehq.com/@ericmauviere/map-coloring-france-6-colors-for-35-000-municipalities) of the Welsh-Powell algorithm (which colors French communes with 6 colors).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":13,"value":"result = run(program, 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":282,"value":"color = {\n const fills = d3.schemePastel1;\n const colors = new Map();\n\n if (!result.Call[0].Witnesses) return \"#888\";\n\n result.Call[0].Witnesses[0].Value.forEach((r) => {\n const [, i, c] = r.match(/(\\d+),(\\d+)/);\n colors.set(+i, +c);\n });\n return Object.assign(\n (_, i) => (colors.has(i) ? color(colors.get(i)) : \"#eee\"),\n { map: colors }\n );\n\n function color(c) {\n return colorType === \"textures\"\n ? `url(#diverging-12541021-${c})`\n : fills[c % fills.length];\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"md`---\n_geo_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":332,"value":"geometries = (\n world.objects.countries ??\n world.objects.counties ??\n world.objects.states\n).geometries.filter((d) => d.id !== \"010\") // removes Antarctica","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"edges = topojson.neighbors(geometries)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"world = d3.json(topo)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"d3 = require(\"d3@7\", \"d3-geo-projection@3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":412,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"version = \"0.1.1\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"run = {\n const clingo = await require(`clingo-wasm@${version}`)\n await clingo.init(`https://cdn.jsdelivr.net/npm/clingo-wasm@${version}/dist/clingo.wasm`)\n return clingo.run\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"