Skip to content

Instantly share code, notes, and snippets.

@abahgat

abahgat/2023day20.ipynb

Last active December 21, 2023 20:10
Show Gist options
  • Save abahgat/f2275f1d4d24efd89820346bea05265c to your computer and use it in GitHub Desktop.
Save abahgat/f2275f1d4d24efd89820346bea05265c to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code 2023 Day 20
Display the source blob
Display the rendered blob
Raw
2023day20.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": [],
"collapsed_sections": [
"0bi6UD_gA4OA"
],
"authorship_tag": "ABX9TyMUZY1O43fVv/e/AuZkuHVH",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/abahgat/f2275f1d4d24efd89820346bea05265c/2023day20.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"# Day 20: Pulse Propagation"
],
"metadata": {
"id": "DN9A25PF__m0"
}
},
{
"cell_type": "markdown",
"source": [
"## Setup"
],
"metadata": {
"id": "3shlQ2dOAoY1"
}
},
{
"cell_type": "markdown",
"source": [
"### Sample"
],
"metadata": {
"id": "hN1ERBynAz-x"
}
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "I1b2WjNq_8mJ"
},
"outputs": [],
"source": [
"sample_loop1000 = \"\"\"broadcaster -> a, b, c\n",
"%a -> b\n",
"%b -> c\n",
"%c -> inv\n",
"&inv -> a\"\"\"\n",
"sample_loop32m = \"\"\"broadcaster -> a\n",
"%a -> inv, con\n",
"&inv -> b\n",
"%b -> con\n",
"&con -> output\"\"\""
]
},
{
"cell_type": "markdown",
"source": [
"### Parse"
],
"metadata": {
"id": "PJmL_R9nA1sw"
}
},
{
"cell_type": "code",
"source": [
"from typing import Dict, List, Set\n",
"from dataclasses import dataclass\n",
"from functools import cached_property\n",
"\n",
"@dataclass\n",
"class Graph:\n",
" transitions: Dict[str, List[str]]\n",
" inputs: Dict[str, Set[str]]\n",
" types: Dict[str, str] # Node name to type\n",
"\n",
"def parse(s):\n",
" transitions: Dict[str, List[str]] = {}\n",
" types: Dict[str, str] = {}\n",
" inputs: Dict[str, Set[str]] = defaultdict(set)\n",
" for l in s.splitlines():\n",
" source, dest = l.split(' -> ')\n",
" source_prefix, source_suffix = source[:1], source[1:]\n",
" if source_prefix in ['%', '&']:\n",
" types[source_suffix] = source_prefix\n",
" source = source_suffix\n",
" transitions[source] = dest.split(', ')\n",
" for d in transitions[source]:\n",
" inputs[d].add(source)\n",
" return Graph(transitions, inputs, types)"
],
"metadata": {
"id": "jLo30rAZAu1L"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"### Input"
],
"metadata": {
"id": "0bi6UD_gA4OA"
}
},
{
"cell_type": "code",
"source": [
"inputstr = \"\"\"%db -> cq\n",
"%rj -> gp, nd\n",
"%ff -> bk\n",
"%rc -> gp\n",
"%bk -> tv\n",
"%xz -> tf, bn\n",
"%gs -> bn\n",
"%ps -> rs, gp\n",
"%jr -> gp, cg\n",
"&pm -> vf\n",
"%pn -> pp, rt\n",
"%nv -> jr\n",
"%rs -> nv\n",
"%kz -> mj\n",
"%nd -> rc, gp\n",
"%nm -> rt, db\n",
"%dg -> rt, xl\n",
"%vg -> gn\n",
"%hc -> vr\n",
"%ft -> lf, bn\n",
"%mj -> hc, cz\n",
"%vb -> ft\n",
"%qd -> cz, sz\n",
"%pp -> rt\n",
"%cq -> rt, vg\n",
"%sr -> vb\n",
"%lf -> vx, bn\n",
"%lh -> pn, rt\n",
"%ls -> sl, cz\n",
"%tv -> gp, rj\n",
"%tf -> sr, bn\n",
"&mk -> vf\n",
"%bs -> rt, lh\n",
"%vx -> bn, gs\n",
"&bn -> fs, bv, vb, mk, sr, bz, cf\n",
"%rr -> ls\n",
"%bv -> xz\n",
"%hp -> bs, rt\n",
"&pk -> vf\n",
"%cg -> rq\n",
"%gn -> rt, dg\n",
"&cz -> hc, kz, rr, hf, sh\n",
"%sl -> cz, kz\n",
"broadcaster -> sh, nm, ps, fs\n",
"%cf -> bv\n",
"&vf -> rx\n",
"&rt -> pk, xl, nm, vg, db\n",
"%xl -> hp\n",
"%sh -> rr, cz\n",
"%bz -> cf\n",
"%fz -> dn, cz\n",
"&gp -> rs, nv, pm, cg, ff, bk, ps\n",
"%fs -> bz, bn\n",
"&hf -> vf\n",
"%vr -> cz, qd\n",
"%rq -> gp, ff\n",
"%sz -> cz, fz\n",
"%dn -> cz\"\"\""
],
"metadata": {
"id": "n17xBur3A6RQ"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"## Part 1"
],
"metadata": {
"id": "Vxw5Gp2CzdvB"
}
},
{
"cell_type": "code",
"source": [
"from typing import Set, Tuple\n",
"from collections import defaultdict\n",
"from dataclasses import field\n",
"\n",
"@dataclass\n",
"class Pulse:\n",
" source: str\n",
" high: bool\n",
" destination: str\n",
"\n",
" def __str__(self):\n",
" return \" \".join([\n",
" self.source, '-high->' if self.high else '-low->', self.destination])\n",
"\n",
"@dataclass\n",
"class GraphState:\n",
" flip_flop_ons: Set[str] = field(default_factory=lambda: set())\n",
" conj_hi_mem: Dict[str, Set[str]] = field(default_factory=lambda: defaultdict(set))\n",
"\n",
"@dataclass\n",
"class GraphOutcome:\n",
" state: GraphState\n",
" pulses: List[Pulse]\n",
"\n",
"def process_pulse(pulse: Pulse,\n",
" graph: Graph,\n",
" state: GraphState) -> List[Pulse]:\n",
" node = pulse.destination\n",
" send_high: bool = pulse.high\n",
"\n",
" if node not in graph.transitions:\n",
" return []\n",
"\n",
" node_type = graph.types.get(pulse.destination, None)\n",
" if node_type == '%': # Flip-flop\n",
" if pulse.high:\n",
" return []\n",
" if node in state.flip_flop_ons:\n",
" state.flip_flop_ons.remove(node)\n",
" send_high = False\n",
" else:\n",
" state.flip_flop_ons.add(node)\n",
" send_high = True\n",
" elif node_type == '&': # Conjunction\n",
" memory = state.conj_hi_mem[node]\n",
" memory.add(pulse.source) if pulse.high else memory.discard(pulse.source)\n",
" send_high = graph.inputs[node] != memory\n",
"\n",
" return [Pulse(node, send_high, next_node) for next_node in graph.transitions[node]]\n",
"\n",
"def run_graph(graph: Graph, state: GraphState) -> GraphOutcome:\n",
" past_pulses = []\n",
" pending_pulses = [Pulse('button', False, 'broadcaster')]\n",
" while pending_pulses:\n",
" active_pulse = pending_pulses.pop(0)\n",
" new_pulses = process_pulse(active_pulse, graph, state)\n",
" pending_pulses += new_pulses\n",
" past_pulses.append(active_pulse)\n",
" return GraphOutcome(state, past_pulses)\n",
"\n",
"def tally(pulses: List[Pulse]) -> Tuple[int, int]:\n",
" his, los = 0, 0\n",
" for p in pulses:\n",
" if p.high:\n",
" his += 1\n",
" else:\n",
" los += 1\n",
" return (his, los)\n",
"\n",
"def part1(s: str) -> int:\n",
" graph = parse(s)\n",
" state = GraphState()\n",
" totpulses = []\n",
" for _ in range(0, 1000):\n",
" outcome = run_graph(graph, state)\n",
" totpulses.extend(outcome.pulses)\n",
" state = outcome.state\n",
" his, los = tally(totpulses)\n",
" return his * los\n",
"\n",
"outcome = run_graph(parse(sample_loop1000), GraphState())\n",
"print(tally(outcome.pulses))\n",
"\n",
"state = GraphState()\n",
"for i in range(0, 4):\n",
" o = run_graph(parse(sample_loop32m), state)\n",
" for p in o.pulses:\n",
" print(p)\n",
" print()\n",
" print(state)\n",
" print()\n",
"\n",
"print(\"First sample\", part1(sample_loop1000))\n",
"print(\"Second sample\", part1(sample_loop32m))\n",
"print(\"Part 1\", part1(inputstr))"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Iu2JYtJi0Cov",
"outputId": "dbda7c69-4ce3-4cec-d375-3852a05549d0"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"(4, 8)\n",
"button -low-> broadcaster\n",
"broadcaster -low-> a\n",
"a -high-> inv\n",
"a -high-> con\n",
"inv -low-> b\n",
"con -high-> output\n",
"b -high-> con\n",
"con -low-> output\n",
"\n",
"GraphState(flip_flop_ons={'a', 'b'}, conj_hi_mem=defaultdict(<class 'set'>, {'inv': {'a'}, 'con': {'a', 'b'}}))\n",
"\n",
"button -low-> broadcaster\n",
"broadcaster -low-> a\n",
"a -low-> inv\n",
"a -low-> con\n",
"inv -high-> b\n",
"con -high-> output\n",
"\n",
"GraphState(flip_flop_ons={'b'}, conj_hi_mem=defaultdict(<class 'set'>, {'inv': set(), 'con': {'b'}}))\n",
"\n",
"button -low-> broadcaster\n",
"broadcaster -low-> a\n",
"a -high-> inv\n",
"a -high-> con\n",
"inv -low-> b\n",
"con -low-> output\n",
"b -low-> con\n",
"con -high-> output\n",
"\n",
"GraphState(flip_flop_ons={'a'}, conj_hi_mem=defaultdict(<class 'set'>, {'inv': {'a'}, 'con': {'a'}}))\n",
"\n",
"button -low-> broadcaster\n",
"broadcaster -low-> a\n",
"a -low-> inv\n",
"a -low-> con\n",
"inv -high-> b\n",
"con -high-> output\n",
"\n",
"GraphState(flip_flop_ons=set(), conj_hi_mem=defaultdict(<class 'set'>, {'inv': set(), 'con': set()}))\n",
"\n",
"First sample 32000000\n",
"Second sample 11687500\n",
"Part 1 680278040\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## Part 2\n",
"\n",
"> The final machine responsible for moving the sand down to Island Island has a module attached named rx. The machine turns on when a **single low pulse** is sent to `rx`.\n",
">\n",
"> Reset all modules to their default states. Waiting for all pulses to be fully handled after each button press, **what is the fewest number of button presses required to deliver a single low pulse to the module named `rx`**?\n",
"\n",
"Graph's too large, it will take too many iterations to run in full. Closed form solution?"
],
"metadata": {
"id": "9kubHlqDm0FE"
}
},
{
"cell_type": "code",
"source": [
"import graphviz as gv\n",
"\n",
"def plot(graph: Graph):\n",
" g = gv.Digraph() # engine='neato'\n",
" for source, destinations in graph.transitions.items():\n",
" for destination in destinations:\n",
" g.edge(source, destination)\n",
" for node, typ in graph.types.items():\n",
" if typ == '&':\n",
" g.node(node, shape='house')\n",
" elif typ == '%':\n",
" g.node(node, shape='triangle')\n",
" return g\n",
"\n",
"plot(parse(inputstr))"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 1000
},
"id": "R6xnYLp8oVOf",
"outputId": "c9ae0139-b067-4a7f-9f73-8fc69d968e60"
},
"execution_count": null,
"outputs": [
{
"output_type": "execute_result",
"data": {
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.43.0 (0)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"1572pt\" height=\"1736pt\"\n viewBox=\"0.00 0.00 1572.00 1736.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 1732)\">\n<title>%3</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-1732 1568,-1732 1568,4 -4,4\"/>\n<!-- db -->\n<g id=\"node1\" class=\"node\">\n<title>db</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"161,-1728 122.01,-1693.5 199.99,-1693.5 161,-1728\"/>\n<text text-anchor=\"middle\" x=\"161\" y=\"-1701.3\" font-family=\"Times,serif\" font-size=\"14.00\">db</text>\n</g>\n<!-- cq -->\n<g id=\"node2\" class=\"node\">\n<title>cq</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"161,-1646 123.11,-1611.5 198.89,-1611.5 161,-1646\"/>\n<text text-anchor=\"middle\" x=\"161\" y=\"-1619.3\" font-family=\"Times,serif\" font-size=\"14.00\">cq</text>\n</g>\n<!-- db&#45;&gt;cq -->\n<g id=\"edge1\" class=\"edge\">\n<title>db&#45;&gt;cq</title>\n<path fill=\"none\" stroke=\"black\" d=\"M161,-1693.21C161,-1683.72 161,-1669.41 161,-1656.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"164.5,-1656.07 161,-1646.07 157.5,-1656.07 164.5,-1656.07\"/>\n</g>\n<!-- vg -->\n<g id=\"node19\" class=\"node\">\n<title>vg</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"181,-1564 142.01,-1529.5 219.99,-1529.5 181,-1564\"/>\n<text text-anchor=\"middle\" x=\"181\" y=\"-1537.3\" font-family=\"Times,serif\" font-size=\"14.00\">vg</text>\n</g>\n<!-- cq&#45;&gt;vg -->\n<g id=\"edge37\" class=\"edge\">\n<title>cq&#45;&gt;vg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M163.7,-1611.21C166.32,-1600.71 170.42,-1584.3 173.98,-1570.1\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"177.41,-1570.81 176.44,-1560.26 170.61,-1569.11 177.41,-1570.81\"/>\n</g>\n<!-- rt -->\n<g id=\"node46\" class=\"node\">\n<title>rt</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"179,-1305.56 152,-1318 125,-1305.56 125.03,-1285.44 178.97,-1285.44 179,-1305.56\"/>\n<text text-anchor=\"middle\" x=\"152\" y=\"-1296.3\" font-family=\"Times,serif\" font-size=\"14.00\">rt</text>\n</g>\n<!-- cq&#45;&gt;rt -->\n<g id=\"edge36\" class=\"edge\">\n<title>cq&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M154.08,-1611.43C147.18,-1600.19 137.04,-1581.66 133,-1564 113.44,-1478.51 133.8,-1373.68 145.28,-1326.34\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"148.75,-1326.91 147.78,-1316.36 141.96,-1325.21 148.75,-1326.91\"/>\n</g>\n<!-- rj -->\n<g id=\"node3\" class=\"node\">\n<title>rj</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1368,-508 1335.51,-473.5 1400.49,-473.5 1368,-508\"/>\n<text text-anchor=\"middle\" x=\"1368\" y=\"-481.3\" font-family=\"Times,serif\" font-size=\"14.00\">rj</text>\n</g>\n<!-- nd -->\n<g id=\"node16\" class=\"node\">\n<title>nd</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1368,-426 1329.01,-391.5 1406.99,-391.5 1368,-426\"/>\n<text text-anchor=\"middle\" x=\"1368\" y=\"-399.3\" font-family=\"Times,serif\" font-size=\"14.00\">nd</text>\n</g>\n<!-- rj&#45;&gt;nd -->\n<g id=\"edge3\" class=\"edge\">\n<title>rj&#45;&gt;nd</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1368,-473.21C1368,-463.72 1368,-449.41 1368,-436.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1371.5,-436.07 1368,-426.07 1364.5,-436.07 1371.5,-436.07\"/>\n</g>\n<!-- gp -->\n<g id=\"node51\" class=\"node\">\n<title>gp</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1294,-244.56 1267,-257 1240,-244.56 1240.03,-224.44 1293.97,-224.44 1294,-244.56\"/>\n<text text-anchor=\"middle\" x=\"1267\" y=\"-235.3\" font-family=\"Times,serif\" font-size=\"14.00\">gp</text>\n</g>\n<!-- rj&#45;&gt;gp -->\n<g id=\"edge2\" class=\"edge\">\n<title>rj&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1356.92,-473.46C1346.05,-462.54 1329.74,-444.51 1320,-426 1292.03,-372.86 1277.27,-303.19 1270.92,-266.02\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1274.35,-265.31 1269.28,-256.01 1267.44,-266.44 1274.35,-265.31\"/>\n</g>\n<!-- ff -->\n<g id=\"node4\" class=\"node\">\n<title>ff</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1429,-754 1395.4,-719.5 1462.6,-719.5 1429,-754\"/>\n<text text-anchor=\"middle\" x=\"1429\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">ff</text>\n</g>\n<!-- bk -->\n<g id=\"node6\" class=\"node\">\n<title>bk</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1394,-672 1355.01,-637.5 1432.99,-637.5 1394,-672\"/>\n<text text-anchor=\"middle\" x=\"1394\" y=\"-645.3\" font-family=\"Times,serif\" font-size=\"14.00\">bk</text>\n</g>\n<!-- ff&#45;&gt;bk -->\n<g id=\"edge4\" class=\"edge\">\n<title>ff&#45;&gt;bk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1424.28,-719.21C1419.38,-708.02 1411.55,-690.11 1405.07,-675.31\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1408.28,-673.9 1401.06,-666.14 1401.86,-676.71 1408.28,-673.9\"/>\n</g>\n<!-- rc -->\n<g id=\"node5\" class=\"node\">\n<title>rc</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1349,-344 1313.81,-309.5 1384.19,-309.5 1349,-344\"/>\n<text text-anchor=\"middle\" x=\"1349\" y=\"-317.3\" font-family=\"Times,serif\" font-size=\"14.00\">rc</text>\n</g>\n<!-- rc&#45;&gt;gp -->\n<g id=\"edge5\" class=\"edge\">\n<title>rc&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1337.94,-309.21C1324.72,-296.31 1302.36,-274.49 1286.27,-258.8\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1288.55,-256.13 1278.95,-251.65 1283.66,-261.14 1288.55,-256.13\"/>\n</g>\n<!-- tv -->\n<g id=\"node30\" class=\"node\">\n<title>tv</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1394,-590 1358.81,-555.5 1429.19,-555.5 1394,-590\"/>\n<text text-anchor=\"middle\" x=\"1394\" y=\"-563.3\" font-family=\"Times,serif\" font-size=\"14.00\">tv</text>\n</g>\n<!-- bk&#45;&gt;tv -->\n<g id=\"edge6\" class=\"edge\">\n<title>bk&#45;&gt;tv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1394,-637.21C1394,-627.72 1394,-613.41 1394,-600.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1397.5,-600.07 1394,-590.07 1390.5,-600.07 1397.5,-600.07\"/>\n</g>\n<!-- xz -->\n<g id=\"node7\" class=\"node\">\n<title>xz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"803,-836 765.11,-801.5 840.89,-801.5 803,-836\"/>\n<text text-anchor=\"middle\" x=\"803\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">xz</text>\n</g>\n<!-- tf -->\n<g id=\"node31\" class=\"node\">\n<title>tf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"803,-754 770.51,-719.5 835.49,-719.5 803,-754\"/>\n<text text-anchor=\"middle\" x=\"803\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">tf</text>\n</g>\n<!-- xz&#45;&gt;tf -->\n<g id=\"edge7\" class=\"edge\">\n<title>xz&#45;&gt;tf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M803,-801.21C803,-791.72 803,-777.41 803,-764.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"806.5,-764.07 803,-754.07 799.5,-764.07 806.5,-764.07\"/>\n</g>\n<!-- bn -->\n<g id=\"node35\" class=\"node\">\n<title>bn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"820,-1146.56 793,-1159 766,-1146.56 766.03,-1126.44 819.97,-1126.44 820,-1146.56\"/>\n<text text-anchor=\"middle\" x=\"793\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">bn</text>\n</g>\n<!-- xz&#45;&gt;bn -->\n<g id=\"edge8\" class=\"edge\">\n<title>xz&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M812.05,-828.11C818.76,-839.46 827.36,-856.09 831,-872 851.41,-961.22 818.77,-1069.81 801.98,-1116.65\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"798.65,-1115.59 798.48,-1126.18 805.22,-1118.01 798.65,-1115.59\"/>\n</g>\n<!-- gs -->\n<g id=\"node8\" class=\"node\">\n<title>gs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"754,-262 716.11,-227.5 791.89,-227.5 754,-262\"/>\n<text text-anchor=\"middle\" x=\"754\" y=\"-235.3\" font-family=\"Times,serif\" font-size=\"14.00\">gs</text>\n</g>\n<!-- gs&#45;&gt;bn -->\n<g id=\"edge9\" class=\"edge\">\n<title>gs&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M735.97,-245.73C688.92,-261.94 566,-312.81 566,-402 566,-978 566,-978 566,-978 566,-1026.36 563.64,-1047.96 598,-1082 640.42,-1124.02 711.86,-1135.84 755.48,-1139.02\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"755.48,-1142.52 765.68,-1139.64 755.91,-1135.54 755.48,-1142.52\"/>\n</g>\n<!-- ps -->\n<g id=\"node9\" class=\"node\">\n<title>ps</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1087,-1246 1049.11,-1211.5 1124.89,-1211.5 1087,-1246\"/>\n<text text-anchor=\"middle\" x=\"1087\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">ps</text>\n</g>\n<!-- rs -->\n<g id=\"node14\" class=\"node\">\n<title>rs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1179,-1164 1145.4,-1129.5 1212.6,-1129.5 1179,-1164\"/>\n<text text-anchor=\"middle\" x=\"1179\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">rs</text>\n</g>\n<!-- ps&#45;&gt;rs -->\n<g id=\"edge10\" class=\"edge\">\n<title>ps&#45;&gt;rs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1099.41,-1211.21C1114.89,-1197.75 1141.53,-1174.58 1159.69,-1158.79\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1162.12,-1161.32 1167.37,-1152.11 1157.53,-1156.04 1162.12,-1161.32\"/>\n</g>\n<!-- ps&#45;&gt;gp -->\n<g id=\"edge11\" class=\"edge\">\n<title>ps&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1082.49,-1211.39C1078,-1185.51 1078,-1117.09 1078,-1060 1078,-1060 1078,-1060 1078,-402 1078,-349.71 1095.08,-334 1133,-298 1160.24,-272.14 1201.08,-256.19 1230.67,-247.71\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1231.88,-251.01 1240.63,-245.02 1230.06,-244.25 1231.88,-251.01\"/>\n</g>\n<!-- jr -->\n<g id=\"node10\" class=\"node\">\n<title>jr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1194,-1000 1161.51,-965.5 1226.49,-965.5 1194,-1000\"/>\n<text text-anchor=\"middle\" x=\"1194\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">jr</text>\n</g>\n<!-- cg -->\n<g id=\"node40\" class=\"node\">\n<title>cg</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1238,-918 1200.11,-883.5 1275.89,-883.5 1238,-918\"/>\n<text text-anchor=\"middle\" x=\"1238\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">cg</text>\n</g>\n<!-- jr&#45;&gt;cg -->\n<g id=\"edge13\" class=\"edge\">\n<title>jr&#45;&gt;cg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1199.93,-965.21C1206.34,-953.56 1216.76,-934.62 1225.07,-919.51\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1228.17,-921.13 1229.92,-910.68 1222.04,-917.76 1228.17,-921.13\"/>\n</g>\n<!-- jr&#45;&gt;gp -->\n<g id=\"edge12\" class=\"edge\">\n<title>jr&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1191.56,-965.45C1185.83,-939.72 1172,-871.62 1172,-814 1172,-814 1172,-814 1172,-402 1172,-343.29 1219,-287.02 1246.89,-258.81\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1249.52,-261.12 1254.19,-251.61 1244.61,-256.14 1249.52,-261.12\"/>\n</g>\n<!-- pm -->\n<g id=\"node11\" class=\"node\">\n<title>pm</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1088.24,-167.56 1060,-180 1031.76,-167.56 1031.79,-147.44 1088.21,-147.44 1088.24,-167.56\"/>\n<text text-anchor=\"middle\" x=\"1060\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">pm</text>\n</g>\n<!-- vf -->\n<g id=\"node45\" class=\"node\">\n<title>vf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"573,-95.56 546,-108 519,-95.56 519.03,-75.44 572.97,-75.44 573,-95.56\"/>\n<text text-anchor=\"middle\" x=\"546\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">vf</text>\n</g>\n<!-- pm&#45;&gt;vf -->\n<g id=\"edge14\" class=\"edge\">\n<title>pm&#45;&gt;vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1031.63,-157.14C944.52,-145.27 680.86,-109.37 583.05,-96.05\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"583.41,-92.56 573.03,-94.68 582.47,-99.5 583.41,-92.56\"/>\n</g>\n<!-- pn -->\n<g id=\"node12\" class=\"node\">\n<title>pn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"105,-918 66.01,-883.5 143.99,-883.5 105,-918\"/>\n<text text-anchor=\"middle\" x=\"105\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">pn</text>\n</g>\n<!-- pp -->\n<g id=\"node25\" class=\"node\">\n<title>pp</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"67,-836 28.01,-801.5 105.99,-801.5 67,-836\"/>\n<text text-anchor=\"middle\" x=\"67\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">pp</text>\n</g>\n<!-- pn&#45;&gt;pp -->\n<g id=\"edge15\" class=\"edge\">\n<title>pn&#45;&gt;pp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99.88,-883.21C94.49,-871.88 85.84,-853.66 78.76,-838.76\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"81.84,-837.08 74.39,-829.55 75.52,-840.09 81.84,-837.08\"/>\n</g>\n<!-- pn&#45;&gt;rt -->\n<g id=\"edge16\" class=\"edge\">\n<title>pn&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99.68,-913.79C91.31,-943.42 76,-1004.86 76,-1058 76,-1142 76,-1142 76,-1142 76,-1194.69 111.11,-1248.29 133.6,-1277.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"131.15,-1279.75 140.12,-1285.37 136.61,-1275.37 131.15,-1279.75\"/>\n</g>\n<!-- nv -->\n<g id=\"node13\" class=\"node\">\n<title>nv</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1179,-1082 1140.01,-1047.5 1217.99,-1047.5 1179,-1082\"/>\n<text text-anchor=\"middle\" x=\"1179\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">nv</text>\n</g>\n<!-- nv&#45;&gt;jr -->\n<g id=\"edge17\" class=\"edge\">\n<title>nv&#45;&gt;jr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1181.02,-1047.21C1182.96,-1036.88 1185.97,-1020.83 1188.6,-1006.79\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1192.12,-1007.04 1190.52,-996.57 1185.24,-1005.75 1192.12,-1007.04\"/>\n</g>\n<!-- rs&#45;&gt;nv -->\n<g id=\"edge18\" class=\"edge\">\n<title>rs&#45;&gt;nv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1179,-1129.21C1179,-1119.72 1179,-1105.41 1179,-1092.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1182.5,-1092.07 1179,-1082.07 1175.5,-1092.07 1182.5,-1092.07\"/>\n</g>\n<!-- kz -->\n<g id=\"node15\" class=\"node\">\n<title>kz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"162,-836 124.11,-801.5 199.89,-801.5 162,-836\"/>\n<text text-anchor=\"middle\" x=\"162\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">kz</text>\n</g>\n<!-- mj -->\n<g id=\"node22\" class=\"node\">\n<title>mj</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"234,-754 192.31,-719.5 275.69,-719.5 234,-754\"/>\n<text text-anchor=\"middle\" x=\"234\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">mj</text>\n</g>\n<!-- kz&#45;&gt;mj -->\n<g id=\"edge19\" class=\"edge\">\n<title>kz&#45;&gt;mj</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171.71,-801.21C182.95,-788.72 201.72,-767.86 215.72,-752.31\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"218.46,-754.5 222.55,-744.73 213.26,-749.82 218.46,-754.5\"/>\n</g>\n<!-- nd&#45;&gt;rc -->\n<g id=\"edge20\" class=\"edge\">\n<title>nd&#45;&gt;rc</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1365.44,-391.21C1362.93,-380.64 1359,-364.09 1355.61,-349.82\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1358.98,-348.87 1353.26,-339.95 1352.17,-350.49 1358.98,-348.87\"/>\n</g>\n<!-- nd&#45;&gt;gp -->\n<g id=\"edge21\" class=\"edge\">\n<title>nd&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1375.51,-391.38C1388.55,-371.51 1412.23,-328.02 1393,-298 1373.6,-267.71 1333.93,-253.02 1304.26,-246.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1304.75,-242.56 1294.23,-243.88 1303.27,-249.4 1304.75,-242.56\"/>\n</g>\n<!-- nm -->\n<g id=\"node17\" class=\"node\">\n<title>nm</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"352,-1246 306.51,-1211.5 397.49,-1211.5 352,-1246\"/>\n<text text-anchor=\"middle\" x=\"352\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">nm</text>\n</g>\n<!-- nm&#45;&gt;db -->\n<g id=\"edge23\" class=\"edge\">\n<title>nm&#45;&gt;db</title>\n<path fill=\"none\" stroke=\"black\" d=\"M348.96,-1244.11C344.84,-1273.15 338,-1328.56 338,-1376 338,-1542 338,-1542 338,-1542 338,-1616.9 250.68,-1666.51 198.7,-1689.4\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"197.26,-1686.21 189.44,-1693.36 200.01,-1692.64 197.26,-1686.21\"/>\n</g>\n<!-- nm&#45;&gt;rt -->\n<g id=\"edge22\" class=\"edge\">\n<title>nm&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M335.82,-1234.01C326.94,-1237.83 315.99,-1242.18 306,-1246 266.36,-1261.17 220.27,-1277.85 188.76,-1288.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"187.47,-1285.11 179.06,-1291.56 189.66,-1291.76 187.47,-1285.11\"/>\n</g>\n<!-- dg -->\n<g id=\"node18\" class=\"node\">\n<title>dg</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"257,-1400 218.01,-1365.5 295.99,-1365.5 257,-1400\"/>\n<text text-anchor=\"middle\" x=\"257\" y=\"-1373.3\" font-family=\"Times,serif\" font-size=\"14.00\">dg</text>\n</g>\n<!-- dg&#45;&gt;rt -->\n<g id=\"edge24\" class=\"edge\">\n<title>dg&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M241.96,-1365.25C224.47,-1352.76 195.42,-1332.01 175.07,-1317.48\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"176.85,-1314.45 166.68,-1311.48 172.78,-1320.14 176.85,-1314.45\"/>\n</g>\n<!-- xl -->\n<g id=\"node47\" class=\"node\">\n<title>xl</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"253,-1246 217.81,-1211.5 288.19,-1211.5 253,-1246\"/>\n<text text-anchor=\"middle\" x=\"253\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">xl</text>\n</g>\n<!-- dg&#45;&gt;xl -->\n<g id=\"edge25\" class=\"edge\">\n<title>dg&#45;&gt;xl</title>\n<path fill=\"none\" stroke=\"black\" d=\"M256.71,-1365.07C256.12,-1342.53 254.74,-1290.13 253.84,-1255.93\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"257.33,-1255.43 253.57,-1245.52 250.33,-1255.61 257.33,-1255.43\"/>\n</g>\n<!-- gn -->\n<g id=\"node41\" class=\"node\">\n<title>gn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"219,-1482 180.01,-1447.5 257.99,-1447.5 219,-1482\"/>\n<text text-anchor=\"middle\" x=\"219\" y=\"-1455.3\" font-family=\"Times,serif\" font-size=\"14.00\">gn</text>\n</g>\n<!-- vg&#45;&gt;gn -->\n<g id=\"edge26\" class=\"edge\">\n<title>vg&#45;&gt;gn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M186.12,-1529.21C191.51,-1517.88 200.16,-1499.66 207.24,-1484.76\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"210.48,-1486.09 211.61,-1475.55 204.16,-1483.08 210.48,-1486.09\"/>\n</g>\n<!-- hc -->\n<g id=\"node20\" class=\"node\">\n<title>hc</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"276,-672 238.11,-637.5 313.89,-637.5 276,-672\"/>\n<text text-anchor=\"middle\" x=\"276\" y=\"-645.3\" font-family=\"Times,serif\" font-size=\"14.00\">hc</text>\n</g>\n<!-- vr -->\n<g id=\"node54\" class=\"node\">\n<title>vr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"316,-590 279.71,-555.5 352.29,-555.5 316,-590\"/>\n<text text-anchor=\"middle\" x=\"316\" y=\"-563.3\" font-family=\"Times,serif\" font-size=\"14.00\">vr</text>\n</g>\n<!-- hc&#45;&gt;vr -->\n<g id=\"edge27\" class=\"edge\">\n<title>hc&#45;&gt;vr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M281.39,-637.21C287.13,-625.74 296.4,-607.21 303.9,-592.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"307.17,-593.48 308.51,-582.97 300.91,-590.35 307.17,-593.48\"/>\n</g>\n<!-- ft -->\n<g id=\"node21\" class=\"node\">\n<title>ft</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"904,-508 871.51,-473.5 936.49,-473.5 904,-508\"/>\n<text text-anchor=\"middle\" x=\"904\" y=\"-481.3\" font-family=\"Times,serif\" font-size=\"14.00\">ft</text>\n</g>\n<!-- lf -->\n<g id=\"node27\" class=\"node\">\n<title>lf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"923,-426 890.51,-391.5 955.49,-391.5 923,-426\"/>\n<text text-anchor=\"middle\" x=\"923\" y=\"-399.3\" font-family=\"Times,serif\" font-size=\"14.00\">lf</text>\n</g>\n<!-- ft&#45;&gt;lf -->\n<g id=\"edge28\" class=\"edge\">\n<title>ft&#45;&gt;lf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M906.56,-473.21C909.09,-462.57 913.06,-445.87 916.46,-431.54\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"919.9,-432.18 918.81,-421.64 913.09,-430.57 919.9,-432.18\"/>\n</g>\n<!-- ft&#45;&gt;bn -->\n<g id=\"edge29\" class=\"edge\">\n<title>ft&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M908.04,-503.87C914.39,-533.61 926,-595.21 926,-648 926,-978 926,-978 926,-978 926,-1029.48 908.38,-1042.81 875,-1082 861.74,-1097.57 843.42,-1111.05 827.46,-1121.08\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"825.61,-1118.11 818.88,-1126.29 829.24,-1124.09 825.61,-1118.11\"/>\n</g>\n<!-- mj&#45;&gt;hc -->\n<g id=\"edge30\" class=\"edge\">\n<title>mj&#45;&gt;hc</title>\n<path fill=\"none\" stroke=\"black\" d=\"M239.66,-719.21C245.69,-707.74 255.42,-689.21 263.29,-674.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"266.59,-675.45 268.14,-664.97 260.39,-672.2 266.59,-675.45\"/>\n</g>\n<!-- cz -->\n<g id=\"node42\" class=\"node\">\n<title>cz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"395,-900.56 368,-913 341,-900.56 341.03,-880.44 394.97,-880.44 395,-900.56\"/>\n<text text-anchor=\"middle\" x=\"368\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">cz</text>\n</g>\n<!-- mj&#45;&gt;cz -->\n<g id=\"edge31\" class=\"edge\">\n<title>mj&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M240.37,-748.87C249.18,-770.66 266.67,-809 290,-836 303.01,-851.05 320.57,-864.54 335.74,-874.71\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"334.05,-877.78 344.34,-880.3 337.86,-871.92 334.05,-877.78\"/>\n</g>\n<!-- vb -->\n<g id=\"node23\" class=\"node\">\n<title>vb</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"754,-590 715.01,-555.5 792.99,-555.5 754,-590\"/>\n<text text-anchor=\"middle\" x=\"754\" y=\"-563.3\" font-family=\"Times,serif\" font-size=\"14.00\">vb</text>\n</g>\n<!-- vb&#45;&gt;ft -->\n<g id=\"edge32\" class=\"edge\">\n<title>vb&#45;&gt;ft</title>\n<path fill=\"none\" stroke=\"black\" d=\"M773.92,-555.38C801.56,-540.64 851.43,-514.04 880.74,-498.4\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"882.66,-501.35 889.83,-493.56 879.36,-495.17 882.66,-501.35\"/>\n</g>\n<!-- qd -->\n<g id=\"node24\" class=\"node\">\n<title>qd</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"334,-508 295.01,-473.5 372.99,-473.5 334,-508\"/>\n<text text-anchor=\"middle\" x=\"334\" y=\"-481.3\" font-family=\"Times,serif\" font-size=\"14.00\">qd</text>\n</g>\n<!-- qd&#45;&gt;cz -->\n<g id=\"edge33\" class=\"edge\">\n<title>qd&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M342.2,-500.84C348.21,-512.31 356.15,-528.76 361,-544 375.25,-588.77 380,-601.01 380,-648 380,-732 380,-732 380,-732 380,-781.19 374.43,-838.56 370.88,-870.12\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"367.39,-869.82 369.72,-880.16 374.34,-870.62 367.39,-869.82\"/>\n</g>\n<!-- sz -->\n<g id=\"node56\" class=\"node\">\n<title>sz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"334,-426 297.71,-391.5 370.29,-391.5 334,-426\"/>\n<text text-anchor=\"middle\" x=\"334\" y=\"-399.3\" font-family=\"Times,serif\" font-size=\"14.00\">sz</text>\n</g>\n<!-- qd&#45;&gt;sz -->\n<g id=\"edge34\" class=\"edge\">\n<title>qd&#45;&gt;sz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M334,-473.21C334,-463.72 334,-449.41 334,-436.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"337.5,-436.07 334,-426.07 330.5,-436.07 337.5,-436.07\"/>\n</g>\n<!-- pp&#45;&gt;rt -->\n<g id=\"edge35\" class=\"edge\">\n<title>pp&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M61.68,-831.79C53.31,-861.42 38,-922.86 38,-976 38,-1142 38,-1142 38,-1142 38,-1192.54 52.91,-1206.15 84,-1246 94.1,-1258.94 108.03,-1270.53 120.65,-1279.54\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"118.89,-1282.57 129.12,-1285.35 122.85,-1276.8 118.89,-1282.57\"/>\n</g>\n<!-- sr -->\n<g id=\"node26\" class=\"node\">\n<title>sr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"754,-672 720.4,-637.5 787.6,-637.5 754,-672\"/>\n<text text-anchor=\"middle\" x=\"754\" y=\"-645.3\" font-family=\"Times,serif\" font-size=\"14.00\">sr</text>\n</g>\n<!-- sr&#45;&gt;vb -->\n<g id=\"edge38\" class=\"edge\">\n<title>sr&#45;&gt;vb</title>\n<path fill=\"none\" stroke=\"black\" d=\"M754,-637.21C754,-627.72 754,-613.41 754,-600.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"757.5,-600.07 754,-590.07 750.5,-600.07 757.5,-600.07\"/>\n</g>\n<!-- vx -->\n<g id=\"node34\" class=\"node\">\n<title>vx</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"923,-344 884.01,-309.5 961.99,-309.5 923,-344\"/>\n<text text-anchor=\"middle\" x=\"923\" y=\"-317.3\" font-family=\"Times,serif\" font-size=\"14.00\">vx</text>\n</g>\n<!-- lf&#45;&gt;vx -->\n<g id=\"edge39\" class=\"edge\">\n<title>lf&#45;&gt;vx</title>\n<path fill=\"none\" stroke=\"black\" d=\"M923,-391.21C923,-381.72 923,-367.41 923,-354.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"926.5,-354.07 923,-344.07 919.5,-354.07 926.5,-354.07\"/>\n</g>\n<!-- lf&#45;&gt;bn -->\n<g id=\"edge40\" class=\"edge\">\n<title>lf&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M929.59,-419.31C941.18,-447.68 964,-510.59 964,-566 964,-978 964,-978 964,-978 964,-1030.71 944.84,-1045.31 907,-1082 885.14,-1103.2 854,-1118.32 829.78,-1127.81\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"828.34,-1124.61 820.21,-1131.4 830.8,-1131.16 828.34,-1124.61\"/>\n</g>\n<!-- lh -->\n<g id=\"node28\" class=\"node\">\n<title>lh</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"139,-1000 103.81,-965.5 174.19,-965.5 139,-1000\"/>\n<text text-anchor=\"middle\" x=\"139\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">lh</text>\n</g>\n<!-- lh&#45;&gt;pn -->\n<g id=\"edge41\" class=\"edge\">\n<title>lh&#45;&gt;pn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M134.41,-965.21C129.7,-954.12 122.19,-936.45 115.94,-921.74\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"118.99,-919.98 111.86,-912.14 112.55,-922.71 118.99,-919.98\"/>\n</g>\n<!-- lh&#45;&gt;rt -->\n<g id=\"edge42\" class=\"edge\">\n<title>lh&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M136.47,-997.56C135.14,-1008.79 133.66,-1023.16 133,-1036 128.45,-1124.27 141.57,-1229 148.3,-1275.14\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"144.88,-1275.95 149.82,-1285.32 151.8,-1274.92 144.88,-1275.95\"/>\n</g>\n<!-- ls -->\n<g id=\"node29\" class=\"node\">\n<title>ls</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"332,-1082 298.4,-1047.5 365.6,-1047.5 332,-1082\"/>\n<text text-anchor=\"middle\" x=\"332\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">ls</text>\n</g>\n<!-- ls&#45;&gt;cz -->\n<g id=\"edge44\" class=\"edge\">\n<title>ls&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M334.36,-1047.37C340,-1022 354.37,-957.34 362.38,-921.27\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"365.8,-922.02 364.56,-911.5 358.97,-920.5 365.8,-922.02\"/>\n</g>\n<!-- sl -->\n<g id=\"node43\" class=\"node\">\n<title>sl</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"294,-1000 260.4,-965.5 327.6,-965.5 294,-1000\"/>\n<text text-anchor=\"middle\" x=\"294\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">sl</text>\n</g>\n<!-- ls&#45;&gt;sl -->\n<g id=\"edge43\" class=\"edge\">\n<title>ls&#45;&gt;sl</title>\n<path fill=\"none\" stroke=\"black\" d=\"M326.88,-1047.21C321.42,-1035.74 312.62,-1017.21 305.5,-1002.21\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"308.56,-1000.5 301.11,-992.97 302.24,-1003.51 308.56,-1000.5\"/>\n</g>\n<!-- tv&#45;&gt;rj -->\n<g id=\"edge46\" class=\"edge\">\n<title>tv&#45;&gt;rj</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1390.49,-555.21C1386.91,-544.19 1381.22,-526.67 1376.45,-512.01\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1379.76,-510.87 1373.34,-502.44 1373.1,-513.03 1379.76,-510.87\"/>\n</g>\n<!-- tv&#45;&gt;gp -->\n<g id=\"edge45\" class=\"edge\">\n<title>tv&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1398.91,-555.47C1416.15,-516.73 1469.8,-380.15 1410,-298 1385.35,-264.14 1337.48,-250.01 1303.94,-244.13\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1304.46,-240.67 1294.04,-242.56 1303.36,-247.58 1304.46,-240.67\"/>\n</g>\n<!-- tf&#45;&gt;sr -->\n<g id=\"edge47\" class=\"edge\">\n<title>tf&#45;&gt;sr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M796.39,-719.21C789.08,-707.27 777.09,-687.7 767.73,-672.41\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"770.51,-670.25 762.3,-663.55 764.54,-673.91 770.51,-670.25\"/>\n</g>\n<!-- tf&#45;&gt;bn -->\n<g id=\"edge48\" class=\"edge\">\n<title>tf&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M813.77,-743.12C836.64,-767.96 888,-830.79 888,-894 888,-978 888,-978 888,-978 888,-1035.22 843.35,-1090.12 815.27,-1118.99\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"812.44,-1116.88 807.84,-1126.43 817.39,-1121.83 812.44,-1116.88\"/>\n</g>\n<!-- mk -->\n<g id=\"node32\" class=\"node\">\n<title>mk</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"832.24,-167.56 804,-180 775.76,-167.56 775.79,-147.44 832.21,-147.44 832.24,-167.56\"/>\n<text text-anchor=\"middle\" x=\"804\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">mk</text>\n</g>\n<!-- mk&#45;&gt;vf -->\n<g id=\"edge49\" class=\"edge\">\n<title>mk&#45;&gt;vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M775.4,-153.24C727.29,-140.19 630.4,-113.9 579.3,-100.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"579.99,-96.6 569.42,-97.35 578.16,-103.35 579.99,-96.6\"/>\n</g>\n<!-- bs -->\n<g id=\"node33\" class=\"node\">\n<title>bs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"180,-1082 142.11,-1047.5 217.89,-1047.5 180,-1082\"/>\n<text text-anchor=\"middle\" x=\"180\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">bs</text>\n</g>\n<!-- bs&#45;&gt;lh -->\n<g id=\"edge51\" class=\"edge\">\n<title>bs&#45;&gt;lh</title>\n<path fill=\"none\" stroke=\"black\" d=\"M174.47,-1047.21C168.55,-1035.67 158.98,-1016.98 151.27,-1001.93\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"154.2,-999.99 146.53,-992.68 147.97,-1003.18 154.2,-999.99\"/>\n</g>\n<!-- bs&#45;&gt;rt -->\n<g id=\"edge50\" class=\"edge\">\n<title>bs&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M176.76,-1079.3C174.93,-1090.57 172.68,-1105.07 171,-1118 163.69,-1174.26 157.28,-1240.65 154.11,-1275.28\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"150.62,-1275.07 153.2,-1285.35 157.59,-1275.71 150.62,-1275.07\"/>\n</g>\n<!-- vx&#45;&gt;gs -->\n<g id=\"edge53\" class=\"edge\">\n<title>vx&#45;&gt;gs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M900.56,-309.38C869.15,-294.51 812.25,-267.57 779.35,-252\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"780.5,-248.67 769.96,-247.56 777.5,-255 780.5,-248.67\"/>\n</g>\n<!-- vx&#45;&gt;bn -->\n<g id=\"edge52\" class=\"edge\">\n<title>vx&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M933.98,-334.42C955.69,-360.29 1002,-422.67 1002,-484 1002,-978 1002,-978 1002,-978 1002,-1031.36 982.49,-1047.24 942,-1082 909.69,-1109.74 862.6,-1125.06 830.05,-1132.88\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"829,-1129.53 820.03,-1135.17 830.55,-1136.36 829,-1129.53\"/>\n</g>\n<!-- bn&#45;&gt;vb -->\n<g id=\"edge56\" class=\"edge\">\n<title>bn&#45;&gt;vb</title>\n<path fill=\"none\" stroke=\"black\" d=\"M766,-1138.89C728.04,-1135.79 659.44,-1124.28 623,-1082 592.32,-1046.41 604,-1024.99 604,-978 604,-978 604,-978 604,-730 604,-657.48 685.92,-603.67 728.68,-580.52\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"730.44,-583.56 737.66,-575.8 727.18,-577.36 730.44,-583.56\"/>\n</g>\n<!-- bn&#45;&gt;sr -->\n<g id=\"edge58\" class=\"edge\">\n<title>bn&#45;&gt;sr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M781.81,-1126.26C762.85,-1102.23 724.56,-1050.3 705,-1000 687.97,-956.21 686,-942.99 686,-896 686,-896 686,-896 686,-812 686,-757.82 718.74,-700.83 738.78,-671.02\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"741.74,-672.89 744.54,-662.67 735.98,-668.91 741.74,-672.89\"/>\n</g>\n<!-- bn&#45;&gt;mk -->\n<g id=\"edge57\" class=\"edge\">\n<title>bn&#45;&gt;mk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M820.31,-1137.55C859.11,-1132.82 930.72,-1119.34 978,-1082 1020.23,-1048.65 1040,-1031.81 1040,-978 1040,-978 1040,-978 1040,-320 1040,-226.11 908.91,-184.96 842.13,-170.09\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"842.51,-166.6 832,-167.93 841.05,-173.44 842.51,-166.6\"/>\n</g>\n<!-- bv -->\n<g id=\"node37\" class=\"node\">\n<title>bv</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"783,-918 744.01,-883.5 821.99,-883.5 783,-918\"/>\n<text text-anchor=\"middle\" x=\"783\" y=\"-891.3\" font-family=\"Times,serif\" font-size=\"14.00\">bv</text>\n</g>\n<!-- bn&#45;&gt;bv -->\n<g id=\"edge55\" class=\"edge\">\n<title>bn&#45;&gt;bv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M793.79,-1126.43C795.41,-1095.68 798.51,-1018.35 793,-954 792.18,-944.38 790.6,-933.97 788.94,-924.65\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"792.35,-923.88 787.06,-914.7 785.48,-925.18 792.35,-923.88\"/>\n</g>\n<!-- cf -->\n<g id=\"node44\" class=\"node\">\n<title>cf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"749,-1000 713.81,-965.5 784.19,-965.5 749,-1000\"/>\n<text text-anchor=\"middle\" x=\"749\" y=\"-973.3\" font-family=\"Times,serif\" font-size=\"14.00\">cf</text>\n</g>\n<!-- bn&#45;&gt;cf -->\n<g id=\"edge60\" class=\"edge\">\n<title>bn&#45;&gt;cf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M789.25,-1126.19C782.02,-1099.56 766.02,-1040.67 756.52,-1005.68\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"759.79,-1004.38 753.79,-995.65 753.04,-1006.21 759.79,-1004.38\"/>\n</g>\n<!-- bz -->\n<g id=\"node49\" class=\"node\">\n<title>bz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"670,-1082 632.11,-1047.5 707.89,-1047.5 670,-1082\"/>\n<text text-anchor=\"middle\" x=\"670\" y=\"-1055.3\" font-family=\"Times,serif\" font-size=\"14.00\">bz</text>\n</g>\n<!-- bn&#45;&gt;bz -->\n<g id=\"edge59\" class=\"edge\">\n<title>bn&#45;&gt;bz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M772.13,-1126.43C750.21,-1112.17 715.81,-1089.79 693.08,-1075.01\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"694.71,-1071.89 684.41,-1069.38 690.89,-1077.76 694.71,-1071.89\"/>\n</g>\n<!-- fs -->\n<g id=\"node52\" class=\"node\">\n<title>fs</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"749,-1246 715.4,-1211.5 782.6,-1211.5 749,-1246\"/>\n<text text-anchor=\"middle\" x=\"749\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">fs</text>\n</g>\n<!-- bn&#45;&gt;fs -->\n<g id=\"edge54\" class=\"edge\">\n<title>bn&#45;&gt;fs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M789.79,-1157.85C784.2,-1170.81 774.21,-1189.17 765.34,-1202.93\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"762.44,-1200.97 759.72,-1211.21 768.23,-1204.9 762.44,-1200.97\"/>\n</g>\n<!-- rr -->\n<g id=\"node36\" class=\"node\">\n<title>rr</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"382,-1164 348.4,-1129.5 415.6,-1129.5 382,-1164\"/>\n<text text-anchor=\"middle\" x=\"382\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">rr</text>\n</g>\n<!-- rr&#45;&gt;ls -->\n<g id=\"edge61\" class=\"edge\">\n<title>rr&#45;&gt;ls</title>\n<path fill=\"none\" stroke=\"black\" d=\"M375.26,-1129.21C367.8,-1117.27 355.56,-1097.7 346.01,-1082.41\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"348.74,-1080.18 340.47,-1073.55 342.8,-1083.89 348.74,-1080.18\"/>\n</g>\n<!-- bv&#45;&gt;xz -->\n<g id=\"edge62\" class=\"edge\">\n<title>bv&#45;&gt;xz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M785.7,-883.21C788.34,-872.64 792.48,-856.09 796.05,-841.82\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"799.48,-842.5 798.51,-831.95 792.69,-840.8 799.48,-842.5\"/>\n</g>\n<!-- hp -->\n<g id=\"node38\" class=\"node\">\n<title>hp</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"219,-1164 180.01,-1129.5 257.99,-1129.5 219,-1164\"/>\n<text text-anchor=\"middle\" x=\"219\" y=\"-1137.3\" font-family=\"Times,serif\" font-size=\"14.00\">hp</text>\n</g>\n<!-- hp&#45;&gt;bs -->\n<g id=\"edge63\" class=\"edge\">\n<title>hp&#45;&gt;bs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M213.74,-1129.21C208.18,-1117.81 199.22,-1099.43 191.94,-1084.48\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"194.97,-1082.72 187.44,-1075.26 188.68,-1085.78 194.97,-1082.72\"/>\n</g>\n<!-- hp&#45;&gt;rt -->\n<g id=\"edge64\" class=\"edge\">\n<title>hp&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M212.15,-1158.06C200.23,-1185.98 175.65,-1243.58 161.89,-1275.83\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"158.53,-1274.77 157.83,-1285.34 164.97,-1277.52 158.53,-1274.77\"/>\n</g>\n<!-- pk -->\n<g id=\"node39\" class=\"node\">\n<title>pk</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"256,-167.56 229,-180 202,-167.56 202.03,-147.44 255.97,-147.44 256,-167.56\"/>\n<text text-anchor=\"middle\" x=\"229\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">pk</text>\n</g>\n<!-- pk&#45;&gt;vf -->\n<g id=\"edge65\" class=\"edge\">\n<title>pk&#45;&gt;vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M256.03,-155.03C313.33,-142.38 446.97,-112.87 510.82,-98.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"511.8,-102.14 520.81,-96.56 510.29,-95.3 511.8,-102.14\"/>\n</g>\n<!-- rq -->\n<g id=\"node55\" class=\"node\">\n<title>rq</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"1429,-836 1392.71,-801.5 1465.29,-801.5 1429,-836\"/>\n<text text-anchor=\"middle\" x=\"1429\" y=\"-809.3\" font-family=\"Times,serif\" font-size=\"14.00\">rq</text>\n</g>\n<!-- cg&#45;&gt;rq -->\n<g id=\"edge66\" class=\"edge\">\n<title>cg&#45;&gt;rq</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1263.36,-883.38C1299.82,-868.11 1366.65,-840.11 1403.3,-824.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1404.91,-827.89 1412.78,-820.79 1402.2,-821.43 1404.91,-827.89\"/>\n</g>\n<!-- gn&#45;&gt;dg -->\n<g id=\"edge68\" class=\"edge\">\n<title>gn&#45;&gt;dg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M224.12,-1447.21C229.51,-1435.88 238.16,-1417.66 245.24,-1402.76\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"248.48,-1404.09 249.61,-1393.55 242.16,-1401.08 248.48,-1404.09\"/>\n</g>\n<!-- gn&#45;&gt;rt -->\n<g id=\"edge67\" class=\"edge\">\n<title>gn&#45;&gt;rt</title>\n<path fill=\"none\" stroke=\"black\" d=\"M214.39,-1447.21C203.69,-1422.11 176.9,-1359.34 162.14,-1324.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"165.3,-1323.24 158.15,-1315.42 158.86,-1325.99 165.3,-1323.24\"/>\n</g>\n<!-- cz&#45;&gt;kz -->\n<g id=\"edge70\" class=\"edge\">\n<title>cz&#45;&gt;kz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M340.89,-884.16C310.03,-872.88 258.17,-853.65 214,-836 205.59,-832.64 196.47,-828.84 188.26,-825.35\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"189.36,-822.02 178.79,-821.31 186.61,-828.45 189.36,-822.02\"/>\n</g>\n<!-- cz&#45;&gt;hc -->\n<g id=\"edge69\" class=\"edge\">\n<title>cz&#45;&gt;hc</title>\n<path fill=\"none\" stroke=\"black\" d=\"M356.39,-880.03C347.52,-868.76 335.58,-852.17 328,-836 303.4,-783.49 288.31,-717.05 281.1,-679.46\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"284.47,-678.4 279.2,-669.21 277.58,-679.68 284.47,-678.4\"/>\n</g>\n<!-- cz&#45;&gt;rr -->\n<g id=\"edge71\" class=\"edge\">\n<title>cz&#45;&gt;rr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M368.96,-912.8C371.45,-956.14 378.08,-1071.66 380.8,-1119.16\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"377.31,-1119.42 381.38,-1129.2 384.3,-1119.02 377.31,-1119.42\"/>\n</g>\n<!-- sh -->\n<g id=\"node48\" class=\"node\">\n<title>sh</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"453,-1246 415.11,-1211.5 490.89,-1211.5 453,-1246\"/>\n<text text-anchor=\"middle\" x=\"453\" y=\"-1219.3\" font-family=\"Times,serif\" font-size=\"14.00\">sh</text>\n</g>\n<!-- cz&#45;&gt;sh -->\n<g id=\"edge73\" class=\"edge\">\n<title>cz&#45;&gt;sh</title>\n<path fill=\"none\" stroke=\"black\" d=\"M379.03,-908.39C384.85,-920.09 390.57,-938.16 395,-954 420.68,-1045.75 446.85,-1156.5 453.08,-1201.5\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"449.61,-1201.94 454.22,-1211.47 456.56,-1201.14 449.61,-1201.94\"/>\n</g>\n<!-- hf -->\n<g id=\"node53\" class=\"node\">\n<title>hf</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"538,-736.56 511,-749 484,-736.56 484.03,-716.44 537.97,-716.44 538,-736.56\"/>\n<text text-anchor=\"middle\" x=\"511\" y=\"-727.3\" font-family=\"Times,serif\" font-size=\"14.00\">hf</text>\n</g>\n<!-- cz&#45;&gt;hf -->\n<g id=\"edge72\" class=\"edge\">\n<title>cz&#45;&gt;hf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M395.23,-884.46C417.98,-875.24 449.84,-859.23 470,-836 489.54,-813.47 500.4,-780.52 505.95,-757.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"509.41,-758.34 508.21,-747.81 502.58,-756.79 509.41,-758.34\"/>\n</g>\n<!-- sl&#45;&gt;kz -->\n<g id=\"edge75\" class=\"edge\">\n<title>sl&#45;&gt;kz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M285.34,-965.37C263.77,-938.89 207.33,-869.63 178.89,-834.73\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"181.33,-832.19 172.3,-826.64 175.91,-836.61 181.33,-832.19\"/>\n</g>\n<!-- sl&#45;&gt;cz -->\n<g id=\"edge74\" class=\"edge\">\n<title>sl&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M303.98,-965.21C315.67,-952.57 335.28,-931.38 349.72,-915.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"352.51,-917.9 356.73,-908.19 347.37,-913.15 352.51,-917.9\"/>\n</g>\n<!-- cf&#45;&gt;bv -->\n<g id=\"edge80\" class=\"edge\">\n<title>cf&#45;&gt;bv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M753.59,-965.21C758.3,-954.12 765.81,-936.45 772.06,-921.74\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"775.45,-922.71 776.14,-912.14 769.01,-919.98 775.45,-922.71\"/>\n</g>\n<!-- rx -->\n<g id=\"node59\" class=\"node\">\n<title>rx</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"546\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"546\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">rx</text>\n</g>\n<!-- vf&#45;&gt;rx -->\n<g id=\"edge81\" class=\"edge\">\n<title>vf&#45;&gt;rx</title>\n<path fill=\"none\" stroke=\"black\" d=\"M546,-75.17C546,-66.92 546,-56.15 546,-46.26\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"549.5,-46.02 546,-36.02 542.5,-46.02 549.5,-46.02\"/>\n</g>\n<!-- rt&#45;&gt;db -->\n<g id=\"edge86\" class=\"edge\">\n<title>rt&#45;&gt;db</title>\n<path fill=\"none\" stroke=\"black\" d=\"M141.11,-1313.44C120.1,-1338.76 76,-1398.95 76,-1458 76,-1542 76,-1542 76,-1542 76,-1599.82 118.98,-1657.32 143.81,-1685.72\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"141.29,-1688.15 150.58,-1693.25 146.5,-1683.48 141.29,-1688.15\"/>\n</g>\n<!-- rt&#45;&gt;nm -->\n<g id=\"edge84\" class=\"edge\">\n<title>rt&#45;&gt;nm</title>\n<path fill=\"none\" stroke=\"black\" d=\"M179.21,-1286.76C206.83,-1276.2 250.33,-1260.42 288,-1246 298.55,-1241.96 310.18,-1237.34 320.73,-1233.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"322.25,-1236.54 330.44,-1229.82 319.84,-1229.97 322.25,-1236.54\"/>\n</g>\n<!-- rt&#45;&gt;vg -->\n<g id=\"edge85\" class=\"edge\">\n<title>rt&#45;&gt;vg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M153.37,-1317.52C156.08,-1349.39 162.63,-1421.6 171,-1482 172.72,-1494.45 175.1,-1508.32 177.1,-1519.38\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"173.69,-1520.15 178.94,-1529.34 180.57,-1518.87 173.69,-1520.15\"/>\n</g>\n<!-- rt&#45;&gt;pk -->\n<g id=\"edge82\" class=\"edge\">\n<title>rt&#45;&gt;pk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M124.57,-1290.7C101.58,-1282.53 69.21,-1268.05 48,-1246 12.71,-1209.31 0,-1192.91 0,-1142 0,-1142 0,-1142 0,-320 0,-227.57 128.47,-185.53 192.96,-170.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"193.76,-173.65 202.73,-168.01 192.2,-166.82 193.76,-173.65\"/>\n</g>\n<!-- rt&#45;&gt;xl -->\n<g id=\"edge83\" class=\"edge\">\n<title>rt&#45;&gt;xl</title>\n<path fill=\"none\" stroke=\"black\" d=\"M170.52,-1285.24C187.85,-1272.38 213.7,-1253.18 231.84,-1239.72\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"234.1,-1242.39 240.04,-1233.62 229.93,-1236.77 234.1,-1242.39\"/>\n</g>\n<!-- xl&#45;&gt;hp -->\n<g id=\"edge87\" class=\"edge\">\n<title>xl&#45;&gt;hp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M248.41,-1211.21C243.7,-1200.12 236.19,-1182.45 229.94,-1167.74\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"232.99,-1165.98 225.86,-1158.14 226.55,-1168.71 232.99,-1165.98\"/>\n</g>\n<!-- sh&#45;&gt;rr -->\n<g id=\"edge88\" class=\"edge\">\n<title>sh&#45;&gt;rr</title>\n<path fill=\"none\" stroke=\"black\" d=\"M443.42,-1211.21C432.08,-1198.43 412.96,-1176.89 399.07,-1161.23\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"401.6,-1158.81 392.34,-1153.65 396.36,-1163.46 401.6,-1158.81\"/>\n</g>\n<!-- sh&#45;&gt;cz -->\n<g id=\"edge89\" class=\"edge\">\n<title>sh&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M446.96,-1211.47C433.29,-1175.4 404.86,-1053.53 377,-954 374.08,-943.56 370.6,-932.15 368.07,-922.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"371.41,-921.14 365.76,-912.18 364.58,-922.71 371.41,-921.14\"/>\n</g>\n<!-- bz&#45;&gt;cf -->\n<g id=\"edge90\" class=\"edge\">\n<title>bz&#45;&gt;cf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M680.65,-1047.21C693.47,-1034.24 715.18,-1012.25 730.7,-996.53\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"733.21,-998.97 737.75,-989.39 728.23,-994.05 733.21,-998.97\"/>\n</g>\n<!-- fz -->\n<g id=\"node50\" class=\"node\">\n<title>fz</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"393,-344 357.81,-309.5 428.19,-309.5 393,-344\"/>\n<text text-anchor=\"middle\" x=\"393\" y=\"-317.3\" font-family=\"Times,serif\" font-size=\"14.00\">fz</text>\n</g>\n<!-- fz&#45;&gt;cz -->\n<g id=\"edge92\" class=\"edge\">\n<title>fz&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M397.59,-339.84C404.8,-369.53 418,-431.07 418,-484 418,-732 418,-732 418,-732 418,-783.53 394.62,-840.33 379.84,-871.11\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"376.66,-869.63 375.38,-880.14 382.94,-872.72 376.66,-869.63\"/>\n</g>\n<!-- dn -->\n<g id=\"node57\" class=\"node\">\n<title>dn</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"449,-262 410.01,-227.5 487.99,-227.5 449,-262\"/>\n<text text-anchor=\"middle\" x=\"449\" y=\"-235.3\" font-family=\"Times,serif\" font-size=\"14.00\">dn</text>\n</g>\n<!-- fz&#45;&gt;dn -->\n<g id=\"edge91\" class=\"edge\">\n<title>fz&#45;&gt;dn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M400.55,-309.21C408.94,-297.23 422.7,-277.57 433.42,-262.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"436.45,-264.03 439.32,-253.83 430.72,-260.02 436.45,-264.03\"/>\n</g>\n<!-- gp&#45;&gt;ff -->\n<g id=\"edge97\" class=\"edge\">\n<title>gp&#45;&gt;ff</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1294.07,-243.15C1329.89,-248.58 1393.26,-262.76 1434,-298 1473.39,-332.07 1488,-349.92 1488,-402 1488,-568 1488,-568 1488,-568 1488,-622.32 1458.35,-681.04 1441.09,-710.62\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1437.91,-709.11 1435.77,-719.49 1443.91,-712.71 1437.91,-709.11\"/>\n</g>\n<!-- gp&#45;&gt;bk -->\n<g id=\"edge98\" class=\"edge\">\n<title>gp&#45;&gt;bk</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1263.86,-256.02C1258.47,-285.02 1248,-348.2 1248,-402 1248,-486 1248,-486 1248,-486 1248,-554.78 1321.53,-607.53 1364.22,-632.36\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1362.65,-635.49 1373.08,-637.37 1366.1,-629.4 1362.65,-635.49\"/>\n</g>\n<!-- gp&#45;&gt;ps -->\n<g id=\"edge99\" class=\"edge\">\n<title>gp&#45;&gt;ps</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1245.49,-247.39C1220.13,-255.78 1178.59,-271.81 1151,-298 1113.08,-334 1096,-349.71 1096,-402 1096,-1060 1096,-1060 1096,-1060 1096,-1110.85 1096,-1170.68 1092.83,-1201.44\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1089.36,-1201.01 1091.51,-1211.39 1096.29,-1201.93 1089.36,-1201.01\"/>\n</g>\n<!-- gp&#45;&gt;pm -->\n<g id=\"edge95\" class=\"edge\">\n<title>gp&#45;&gt;pm</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1239.94,-228.2C1201.55,-214.29 1131.46,-188.89 1091.01,-174.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1092,-170.87 1081.41,-170.76 1089.62,-177.45 1092,-170.87\"/>\n</g>\n<!-- gp&#45;&gt;nv -->\n<g id=\"edge94\" class=\"edge\">\n<title>gp&#45;&gt;nv</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1248.34,-248.7C1229.26,-258.4 1199.82,-275.7 1181,-298 1148.29,-336.76 1134,-351.28 1134,-402 1134,-896 1134,-896 1134,-896 1134,-942.99 1139.07,-955.13 1153,-1000 1157.06,-1013.07 1163.29,-1027.09 1168.63,-1038.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1165.59,-1039.82 1173.2,-1047.19 1171.85,-1036.68 1165.59,-1039.82\"/>\n</g>\n<!-- gp&#45;&gt;rs -->\n<g id=\"edge93\" class=\"edge\">\n<title>gp&#45;&gt;rs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1294.05,-239.96C1341.3,-241.23 1439.96,-249.95 1504,-298 1546.68,-330.03 1564,-348.64 1564,-402 1564,-978 1564,-978 1564,-978 1564,-1130.24 1305.08,-1141.73 1211.91,-1140.94\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1211.69,-1137.44 1201.65,-1140.8 1211.6,-1144.44 1211.69,-1137.44\"/>\n</g>\n<!-- gp&#45;&gt;cg -->\n<g id=\"edge96\" class=\"edge\">\n<title>gp&#45;&gt;cg</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1258.83,-253.31C1243.07,-280.3 1210,-343.86 1210,-402 1210,-732 1210,-732 1210,-732 1210,-783.6 1223.97,-843.12 1232.17,-873.63\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1228.86,-874.79 1234.9,-883.49 1235.61,-872.92 1228.86,-874.79\"/>\n</g>\n<!-- fs&#45;&gt;bn -->\n<g id=\"edge101\" class=\"edge\">\n<title>fs&#45;&gt;bn</title>\n<path fill=\"none\" stroke=\"black\" d=\"M750.15,-1211.21C754.88,-1198.73 765.93,-1177.91 775.83,-1162.36\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"778.83,-1164.18 781.47,-1153.92 773.01,-1160.29 778.83,-1164.18\"/>\n</g>\n<!-- fs&#45;&gt;bz -->\n<g id=\"edge100\" class=\"edge\">\n<title>fs&#45;&gt;bz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M743.82,-1211.37C731.39,-1185.89 699.64,-1120.78 682.1,-1084.81\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"685.09,-1082.95 677.56,-1075.5 678.79,-1086.02 685.09,-1082.95\"/>\n</g>\n<!-- hf&#45;&gt;vf -->\n<g id=\"edge102\" class=\"edge\">\n<title>hf&#45;&gt;vf</title>\n<path fill=\"none\" stroke=\"black\" d=\"M512,-716.14C513.94,-688.16 518,-622.89 518,-568 518,-568 518,-568 518,-238 518,-194.27 530.11,-144.49 538.4,-115.53\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"541.78,-116.43 541.25,-105.85 535.07,-114.45 541.78,-116.43\"/>\n</g>\n<!-- vr&#45;&gt;qd -->\n<g id=\"edge104\" class=\"edge\">\n<title>vr&#45;&gt;qd</title>\n<path fill=\"none\" stroke=\"black\" d=\"M318.43,-555.21C320.78,-544.78 324.43,-528.51 327.62,-514.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"331.04,-515.09 329.82,-504.57 324.21,-513.56 331.04,-515.09\"/>\n</g>\n<!-- vr&#45;&gt;cz -->\n<g id=\"edge103\" class=\"edge\">\n<title>vr&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M319.05,-587.14C328.04,-643.51 354.41,-808.83 364.25,-870.47\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"360.8,-871.08 365.83,-880.41 367.71,-869.98 360.8,-871.08\"/>\n</g>\n<!-- rq&#45;&gt;ff -->\n<g id=\"edge106\" class=\"edge\">\n<title>rq&#45;&gt;ff</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1429,-801.21C1429,-791.72 1429,-777.41 1429,-764.25\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1432.5,-764.07 1429,-754.07 1425.5,-764.07 1432.5,-764.07\"/>\n</g>\n<!-- rq&#45;&gt;gp -->\n<g id=\"edge105\" class=\"edge\">\n<title>rq&#45;&gt;gp</title>\n<path fill=\"none\" stroke=\"black\" d=\"M1441.29,-801.18C1467.39,-776.94 1526,-715.23 1526,-650 1526,-650 1526,-650 1526,-402 1526,-349.08 1509.43,-330.93 1468,-298 1419.93,-259.8 1347.69,-246.76 1304.17,-242.31\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1304.3,-238.8 1294.02,-241.37 1303.65,-245.77 1304.3,-238.8\"/>\n</g>\n<!-- sz&#45;&gt;cz -->\n<g id=\"edge107\" class=\"edge\">\n<title>sz&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M317.39,-410.39C274.61,-428.03 164,-481.81 164,-566 164,-650 164,-650 164,-650 164,-696.99 162.54,-711.7 183,-754 193.56,-775.83 235.88,-821.09 255,-836 278.28,-854.15 308.12,-869.18 331.28,-879.39\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"330.19,-882.73 340.76,-883.46 332.96,-876.3 330.19,-882.73\"/>\n</g>\n<!-- sz&#45;&gt;fz -->\n<g id=\"edge108\" class=\"edge\">\n<title>sz&#45;&gt;fz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M341.96,-391.21C350.95,-379.02 365.81,-358.86 377.19,-343.44\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"380.29,-345.12 383.41,-335 374.66,-340.97 380.29,-345.12\"/>\n</g>\n<!-- dn&#45;&gt;cz -->\n<g id=\"edge109\" class=\"edge\">\n<title>dn&#45;&gt;cz</title>\n<path fill=\"none\" stroke=\"black\" d=\"M450.48,-260.96C452.54,-291.82 456,-351.33 456,-402 456,-732 456,-732 456,-732 456,-788.17 414.64,-843.46 388.63,-872.68\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"385.91,-870.47 381.75,-880.21 391.08,-875.19 385.91,-870.47\"/>\n</g>\n<!-- broadcaster -->\n<g id=\"node58\" class=\"node\">\n<title>broadcaster</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"632\" cy=\"-1300\" rx=\"51.19\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"632\" y=\"-1296.3\" font-family=\"Times,serif\" font-size=\"14.00\">broadcaster</text>\n</g>\n<!-- broadcaster&#45;&gt;ps -->\n<g id=\"edge78\" class=\"edge\">\n<title>broadcaster&#45;&gt;ps</title>\n<path fill=\"none\" stroke=\"black\" d=\"M677.71,-1291.47C770.26,-1276.21 977.67,-1242.02 1056.13,-1229.09\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"1057.03,-1232.49 1066.32,-1227.41 1055.89,-1225.58 1057.03,-1232.49\"/>\n</g>\n<!-- broadcaster&#45;&gt;nm -->\n<g id=\"edge77\" class=\"edge\">\n<title>broadcaster&#45;&gt;nm</title>\n<path fill=\"none\" stroke=\"black\" d=\"M587.7,-1290.75C541.73,-1281.69 468.01,-1265.77 406,-1246 397.27,-1243.22 387.95,-1239.65 379.56,-1236.2\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"380.81,-1232.92 370.23,-1232.26 378.08,-1239.37 380.81,-1232.92\"/>\n</g>\n<!-- broadcaster&#45;&gt;sh -->\n<g id=\"edge76\" class=\"edge\">\n<title>broadcaster&#45;&gt;sh</title>\n<path fill=\"none\" stroke=\"black\" d=\"M600.41,-1285.76C566,-1271.34 511.56,-1248.54 479.36,-1235.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"480.31,-1231.65 469.74,-1231.01 477.61,-1238.11 480.31,-1231.65\"/>\n</g>\n<!-- broadcaster&#45;&gt;fs -->\n<g id=\"edge79\" class=\"edge\">\n<title>broadcaster&#45;&gt;fs</title>\n<path fill=\"none\" stroke=\"black\" d=\"M655.68,-1283.82C676.52,-1270.46 706.64,-1251.15 726.98,-1238.12\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"729.03,-1240.96 735.56,-1232.61 725.26,-1235.06 729.03,-1240.96\"/>\n</g>\n</g>\n</svg>\n",
"text/plain": [
"<graphviz.graphs.Digraph at 0x7c481bb7e110>"
]
},
"metadata": {},
"execution_count": 5
}
]
},
{
"cell_type": "markdown",
"source": [
"* Graph made of separate components (independent entry and exit points), ending in $pk, mk, pm, hf$.\n",
"* They all have to receive `high` for $vf$ to send `lo` to $rx$.\n",
"* They can get to looping states of independent lengths.\n",
"* If each component loops state in $a, b, c, d$ iterations, $rx$ will flip in $LCM(a,b,c,d)$\n",
"\n",
"Does this behave like a binary adder? Is loop length function of how many flip flop nodes in the component?\n",
"\n",
"* Each flip flop triggers the following one\n",
"* When the top conditional is triggered, it feeds back to flip flops and resets them\n",
"\n",
"Node | Bits\n",
"-----|------\n",
"$hf$ | 12\n",
"$pk$ | 11\n",
"$mk$ | 12?\n",
"$pm$ | 12\n",
"\n",
"Maybe knowing something more of electric circuits would make this solvable by eyeballing?"
],
"metadata": {
"id": "bFdj5j0MwAy0"
}
},
{
"cell_type": "code",
"source": [
"from math import gcd\n",
"\n",
"def part2(s: str) -> int:\n",
" graph = parse(s)\n",
" state = GraphState()\n",
" watches = ['hf', 'pk', 'mk', 'pm']\n",
" loop_periods = {}\n",
" i = 1\n",
" while True:\n",
" outcome = run_graph(graph, state)\n",
" state = outcome.state\n",
" for p in outcome.pulses:\n",
" if p.source in watches and p.high and p.source not in loop_periods:\n",
" loop_periods[p.source] = i\n",
" if len(loop_periods) == 4:\n",
" break\n",
" i += 1\n",
" return loop_periods\n",
"\n",
"periods = part2(inputstr)\n",
"print(periods)\n",
"lcm = 1\n",
"for i in periods.values():\n",
" lcm = lcm * i // gcd(lcm, i)\n",
"print(lcm)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "7aP5oktf1H6S",
"outputId": "fa5feb54-4a5a-4fe6-caf5-2068e8d0f093"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"{'pm': 3881, 'mk': 3889, 'hf': 4013, 'pk': 4021}\n",
"243548140870057\n"
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment